Corte utilitarista de bolo - Utilitarian cake-cutting

O corte de bolo utilitário (também chamado de corte de bolo máximo ) é uma regra para dividir um recurso heterogêneo, como um bolo ou uma propriedade de terra, entre vários parceiros com diferentes funções de utilidade cardinais , de modo que a soma das utilidades dos parceiros é o maior possível. É um caso especial da regra da escolha social utilitária . Cortar bolo utilitarista muitas vezes não é "justo"; portanto, o utilitarismo está frequentemente em conflito com o corte justo do bolo .

Exemplo

Considere um bolo com duas partes: chocolate e baunilha, e dois parceiros: Alice e George, com as seguintes avaliações:

Parceiro	Chocolate	Baunilha
Alice	9	1
George	6	4

A regra utilitária dá cada parte ao parceiro com a maior utilidade. Nesse caso, a regra utilitária dá o chocolate inteiro para Alice e o Vanilla inteiro para George. O maxsum é 13.

A divisão utilitária não é justa: não é proporcional, pois George recebe menos da metade do valor total do bolo, e não é isenta de inveja, pois George inveja Alice.

Notação

O bolo é chamado . É geralmente assumido como sendo um segmento unidimensional finito, um polígono bidimensional ou um subconjunto finito do plano euclidiano multidimensional . ${\ displaystyle C}$ ${\ displaystyle \ mathbb {R} ^ {d}}$

Existem parceiros. Cada parceiro tem uma função de valor pessoal que mapeia subconjuntos de ("peças") para números. ${\ displaystyle n}$ ${\ displaystyle i}$ ${\ displaystyle V_ {i}}$ ${\ displaystyle C}$

${\ displaystyle C}$ tem que ser dividido para separar as peças, uma peça por parceiro. A peça alocada ao parceiro é chamada , e . ${\ displaystyle n}$ ${\ displaystyle i}$ ${\ displaystyle X_ {i}}$ ${\ displaystyle C = X_ {1} \ sqcup ... \ sqcup X_ {n}}$

Uma divisão é chamada utilitarista ou utilitarista-maximal ou maxsum se maximizar a seguinte expressão: ${\ displaystyle X}$

{\ displaystyle \ sum _ {i = 1} ^ {n} {V_ {i} (X_ {i})}}

O conceito é geralmente generalizado atribuindo-se um peso diferente a cada parceiro. Uma divisão é chamada de ponderada-utilitarista-máxima (WUM) se ela maximiza a seguinte expressão: ${\ displaystyle X}$

{\ displaystyle \ sum _ {i = 1} ^ {n} {\ frac {V_ {i} (X_ {i})} {w_ {i}}}}

onde são fornecidas constantes positivas. ${\ displaystyle w_ {i}}$

Eficiência de Maxsum e Pareto

Cada divisão WUM com pesos positivos é obviamente Pareto-eficiente . Isso ocorre porque, se uma divisão Pareto-domina uma divisão , então a soma de utilidades ponderada em é estritamente maior do que em , portanto, não pode ser uma divisão WUM. ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X}$ ${\ displaystyle X}$

O que é mais surpreendente é que cada divisão Pareto-eficiente é WUM para alguma seleção de pesos.

Caracterização da regra utilitária

Christopher P. Chambers sugere uma caracterização da regra WUM. A caracterização é baseada nas seguintes propriedades de uma regra de divisão R :

Eficiência de Pareto (PE) : a regra R retorna apenas divisões que são eficientes de Pareto.
Independência divisão (DI) : sempre que um bolo é repartido para várias sub-endurece e cada bolo é dividido de acordo com a regra R , o resultado é o mesmo que se o bolo original foram divididas conforme a R .
Independência de terra inviável (IIL) : sempre que um sub-bolo é dividido de acordo com R , o resultado não depende das utilidades dos parceiros nos outros sub-bolos.
Tratamento positivo de iguais (PTE) : sempre que todos os parceiros têm a mesma função de utilidade, R recomenda pelo menos uma divisão que dê uma utilidade positiva a cada parceiro.
Invariância de escala (SI) : sempre que as funções de utilidade dos parceiros são multiplicadas por constantes (uma constante possivelmente diferente para cada parceiro), as recomendações dadas por R não mudam.
Continuidade (CO) : para um pedaço de bolo fixo, o conjunto de perfis de utilidade que mapeiam para uma alocação específica é um conjunto fechado sob convergência pontual .

O seguinte é comprovado para parceiros que atribuem utilidade positiva a cada pedaço de bolo com tamanho positivo:

Se R é PE DI e IIL, então existe uma sequência de pesos tal que todas as divisões recomendadas por R são WUM com esses pesos (sabe-se que toda divisão PE é WUM com alguns pesos; a notícia é que todas as divisões recomendadas por R são WUM com os mesmos pesos. Isso decorre da propriedade DI). ${\ displaystyle w_ {1}, \ dots, w_ {n}}$
Se R for PE DI IIL e PTE, então todas as divisões recomendadas por R são utilitaristas-máximas (em outras palavras, todas as divisões devem ser WUM e todos os agentes devem ter pesos iguais. Isso decorre da propriedade PTE).
Se R for PE DI IIL e SI, então R é uma regra ditatorial - dá o bolo inteiro para um único parceiro.
Se R for PE DI IIL e CO, então existe uma sequência de pesos tal que R é uma regra WUM com esses pesos (ou seja, R recomenda todas e apenas as divisões WUM com esses pesos). ${\ displaystyle w_ {1}, \ dots, w_ {n}}$

Encontrando divisões utilitárias

Peças desconectadas

Quando as funções de valor são aditivas, as divisões maxsum sempre existem. Intuitivamente, podemos dar cada fração do bolo ao parceiro que mais a valoriza, como no exemplo acima . Da mesma forma, as divisões WUM podem ser encontradas dando cada fração do bolo ao parceiro para quem a proporção é maior. ${\ displaystyle V_ {i} / w_ {i}}$

Este processo é fácil de realizar quando o bolo é homogêneo por partes , ou seja, o bolo pode ser dividido em um número finito de pedaços de forma que a densidade de valor de cada pedaço seja constante para todos os parceiros.

Quando o bolo não é homogêneo por partes, o algoritmo acima não funciona, pois há um número infinito de "pedaços" diferentes a serem considerados.

As divisões Maxsum ainda existem. Este é um corolário do teorema de compactação de Dubins-Spanier e também pode ser provado usando o conjunto Radon-Nikodym .

No entanto, nenhum algoritmo finito pode encontrar uma divisão maxsum. Prova : um algoritmo finito possui dados de valor apenas sobre um número finito de peças. Ou seja, existe apenas um número finito de subconjuntos do bolo, para os quais o algoritmo conhece as avaliações dos parceiros. Suponha que o algoritmo tenha parado após ter dados de valor sobre subconjuntos. Agora, pode ser que todos os parceiros respondam a todas as perguntas como se tivessem a mesma medida de valor. Nesse caso, o maior valor utilitário possível que o algoritmo pode atingir é 1. No entanto, é possível que no fundo de uma das peças haja um subconjunto que dois parceiros valorizam de forma diferente. Nesse caso, existe uma divisão superproporcional , na qual cada parceiro recebe um valor maior que , então a soma das utilidades é estritamente maior que 1. Logo, a divisão retornada pelo algoritmo finito não é maxsum. ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle 1 / n}$

Peças conectadas

Quando o bolo é unidimensional e os pedaços devem ser conectados, o simples algoritmo de atribuir cada pedaço ao agente que mais o valoriza não funciona mais, mesmo quando os pedaços são constantes por partes. Nesse caso, o problema de encontrar uma divisão UM é NP-difícil e, além disso, nenhum FPTAS é possível a menos que P = NP.

Existe um algoritmo de aproximação de 8 fatores e um algoritmo tratável de parâmetro fixo que é exponencial no número de jogadores.

Para cada conjunto de pesos positivos, uma divisão WUM existe e pode ser encontrada de maneira semelhante.

Maxsum e justiça

Uma divisão maxsum nem sempre é justa; veja o exemplo acima . Da mesma forma, uma divisão justa nem sempre é maxsum.

Uma abordagem para esse conflito é limitar o "preço da justiça" - calcular os limites superior e inferior da quantidade de redução na soma das utilidades, que é necessária para a justiça. Para obter mais detalhes, consulte o preço de justiça .

Outra abordagem para combinar eficiência e justiça é encontrar, entre todas as divisões de feiras possíveis, uma divisão de feiras com a maior soma de utilidades:

Encontrar alocações utilitárias justas

Os seguintes algoritmos podem ser usados para encontrar um corte de bolo sem inveja com soma de utilidades máxima, para um bolo que é um intervalo unidimensional, quando cada pessoa pode receber pedaços desconectados e as funções de valor são aditivas:

Para parceiros com avaliações constantes por partes : divida o bolo em m regiões totalmente constantes. Resolva um programa linear com variáveis nm : cada par (agente, região) tem uma variável que determina a fração da região dada ao agente. Para cada região, há uma restrição dizendo que a soma de todas as frações dessa região é 1; para cada par (agente, agente), há uma restrição dizendo que o primeiro agente não inveja o segundo. Observe que a alocação produzida por este procedimento pode ser altamente fracionada. ${\ displaystyle n}$
Para parceiros com lineares por partes avaliações: para cada ponto no bolo, calcular a razão entre os utilitários: . Dê ao parceiro 1 os pontos com e ao parceiro 2 os pontos com , onde é um limite calculado para que a divisão seja livre de inveja. Em geral, não pode ser calculado porque pode ser irracional, mas na prática, quando as avaliações são lineares por partes, podem ser aproximadas por um algoritmo de aproximação de "busca irracional". Para qualquer , o algoritmo encontra uma alocação que é -EF (o valor de cada agente é pelo menos o valor de cada outro agente menos ) e atinge uma soma que é pelo menos a soma máxima de uma alocação de EF. Seu tempo de execução é polinomial na entrada e em . ${\ displaystyle 2}$ ${\ displaystyle r = u_ {1} / u_ {2}}$ ${\ displaystyle r \ geq r ^ {*}}$ ${\ displaystyle r <r ^ {*}}$ ${\ displaystyle r ^ {*}}$ ${\ displaystyle r ^ {*}}$ ${\ displaystyle r ^ {*}}$ ${\ displaystyle \ epsilon> 0}$ ${\ displaystyle \ epsilon}$ ${\ displaystyle \ epsilon}$ ${\ displaystyle \ log (1 / \ epsilon)}$
Para parceiros com avaliações gerais: aproximação aditiva à inveja e eficiência, com base no algoritmo de avaliações constantes por partes. ${\ displaystyle n}$

Propriedades de alocações de feiras utilitárias

Brams, Feldman, Lai, Morgenstern e Procaccia estudam as divisões do bolo sem inveja (EF) e equitativas (EQ), e as relacionam com o máximo e a otimização de Pareto (PO). Conforme explicado acima, as alocações maxsum são sempre PO. No entanto, quando maxsum é restringido pela justiça, isso não é necessariamente verdade. Eles provam o seguinte:

Quando há dois agentes, as alocações maxsum-EF, maximum-EQ e maximum-EF-EQ são sempre PO.
Quando há três ou mais agentes com avaliações uniformes por partes , as alocações maxsum-EF são sempre PO (uma vez que EF é equivalente à proporcionalidade , que é preservada nas melhorias de Pareto). No entanto, pode não haver alocações maxsum-EQ e maxsum-EQ-EF que são PO.
Quando há três ou mais agentes com avaliações constantes por partes , pode até mesmo não haver alocações EF maxsum que sejam PO. Por exemplo, considere um bolo com três regiões e três agentes com valores: Alice : 51/101, 50/101, 0 Bob : 50/101, 51/101, 0 Carl : 51/111, 10/111, 50/111 A regra maxsum dá a região i ao agente i, mas não é EF, pois Carl inveja Alice. Usando um programa linear, é possível encontrar a alocação única maxsum-EF e mostrar que ela deve compartilhar a região 1 e a região 2 entre Alice e Bob. No entanto, essa alocação não pode ser PO, pois Alice e Bob poderiam ganhar trocando suas ações nessas regiões.
Quando todos os agentes têm avaliações lineares por partes , a soma da utilidade de uma alocação EF-maxsum é pelo menos tão grande quanto uma alocação EQ-maxsum. Este resultado se estende a avaliações gerais até uma aproximação aditiva (ou seja, alocações -EF têm uma soma de utilidade de pelo menos alocações EQ menos ). ${\ displaystyle \ epsilon}$ ${\ displaystyle \ epsilon}$

Propriedades de monotonicidade do corte utilitário de bolos

Quando os pedaços podem ser desconectado , a regra absoluta-utilitária (maximizar a soma de utilidades não normalizados) é recurso-monótona e população monótona . A regra utilitária relativa (maximizar a soma das utilidades normalizadas) é monotônica para a população, mas não monotônica para os recursos.

Isso não é mais válido quando as peças são conectadas.

Veja também

Corte eficiente de bolo
Corte de bolo justo
Teorema de Weller
Divisão sem inveja eficiente de Pareto
Alocação de classificação máxima
Votação utilitarista - o princípio utilitarista em um contexto diferente.

Languages

In other projects