Corte justo quando jogadores se atrasam

A afirmação usual do problema justo de cortar bolos supõe que todos os jogadores tenham sua participação ao mesmo tempo. No entanto, em muitos casos, os jogadores chegam de forma incremental. Por exemplo, podemos dividir um bolo por jogadores, mas um novo jogador chega e quer compartilhar.$n$$n$

Geralmente, a divisão justa do bolo exige muito esforço (por exemplo, exige que os jogadores respondam a muitas perguntas), especialmente quando o número de jogadores é grande.

É possível usar a divisão existente do bolo sobre jogadores, a fim de criar uma nova divisão do bolo para jogadores, com um esforço adicional mínimo (isto é, substancialmente menos esforço do que redistribuir o bolo do zero)?n + $n$$n+1$

Eu direi de antemão que não posso fornecer uma boa resposta para sua pergunta (acho que talvez você possa obter um trabalho de pesquisa, se puder), mas acho que posso ajudar definindo o problema formalmente e indicando onde alguns das dificuldades estão.

Background . Deixe-me indicar claramente o modelo de corte de bolo. Desejamos dividir o intervalo entre jogadores. Cada jogador tem uma função de avaliação sobre os subconjuntos do bolo. Assumiremos que essa função é uma medida de probabilidade; é não-negativo e aditivo (para disjuntos , ) e . Uma solução para esse problema é um protocolo ou algoritmo que consulta os players e atribui partes do intervalo. Observe que os jogadores podem falsificar / mentir ao responder a perguntas.n i v i ( S ) S A , B ⊆ [ 0 , 1 ] v i ( A ∪ B ) = v i ( A ) + v i ( B ) v i ( [ 0 , 1 ] ) = $[0,1]$$n$$i$$v_i(S)$$S$$A,B \subseteq [0,1]$$v_i(A \cup B) = v_i(A) + v_i(B)$$v_i([0,1]) = 1$

Alguns trabalhos terão restrições mais específicas; por exemplo , funções de avaliação são contínuas, lineares por partes ou constantes por partes.

Deixe as peças atribuídas aos jogadores serem . Muitas vezes queremos as seguintes propriedades de um protocolo:$\{S_1,\dots,S_n\}$

• proporcionalidade : Todo jogador possui uma estratégia que garante que recebe um valor de pelo menos . (Da perspectiva de , ele recebe do valor total do bolo.)$i$$(1/n)v_i([0,1])$$i$$1/n$
• inveja-liberdade : Todo jogador tem uma estratégia que garante que para todos os outros jogadores . (Cada jogador prefere sua própria peça à peça de qualquer outro jogador.)$v_i(S_i) \geq v_i(S_j)$$j$

Observe que inveja implica proporcionalidade.

Também existem propriedades "operacionais" que podemos desejar, como cortar em pedaços, tempo de execução polinomial (ou mesmo capacidade de computação / construtibilidade - não queremos usar o Axiom of Choice para selecionar um subconjunto do bolo! ), e assim por diante.

Perguntas específicas a serem feitas . Duas notas. Primeiro, qualquer resposta à sua pergunta resolverá o problema geral: comece dando o bolo inteiro ao jogador , depois deixe os outros jogadores chegarem online e aplique este protocolo de forma iterativa. Portanto, devemos esperar que esse problema seja mais difícil do que a configuração padrão de corte de bolo à qual o aplicamos.$1$

Segundo, sempre podemos resolver seu problema retirando todo o bolo de todos e usando um algoritmo conhecido para redistribuí-lo do zero. Portanto, a questão é apenas se existe uma maneira um pouco mais elegante de fazer isso. Eu acho que uma boa maneira de quantificar isso é "quando a redistribuição exige menos tempo ou menos cortes do que começar do zero; e / ou quando os jogadores conseguem manter uma parte significativa de sua fatia atual?"

1. Suponha que tenhamos uma alocação livre de inveja para jogadores. Como redistribuímos para produzir uma alocação livre de inveja entre os jogadores ?$n$$n+1$

Eu suspeito que isso é muito difícil. O motivo é que encontrar uma alocação eficiente e sem inveja já é um problema difícil. Tanto quanto eu sei, protocolos conhecidos podem exigir um número ilimitado de cortes no bolo e são muito complexos. (Veja Brams e Taylor, um protocolo da divisão de bolos sem inveja , 1995.) Portanto, pode não haver nada melhor do que retirar todo o bolo de todos e redistribuí-lo aos agentes que usam Brams-Taylor.$n+1$

1. Suponha que tenhamos uma alocação proporcional para ; como redistribuímos para obter uma alocação proporcional para ?$n$$n+1$

Eu acho que isso ainda é difícil (embora mais factível). Considere o caso em que cada jogador valoriza o bolo de maneira uniforme e cada jogador tem uma fatia de . Então, o que quer que o novo jogador faça exigirá reorganização entre todos. Aqui está outro caso ruim: suponha que o jogador tenha uma avaliação de exatamente para sua fatia, mas valorize a fatia do jogador em . Suponha que o jogador valorize sua própria fatia em exatamente , mas valorize a fatia do jogador em e assim por diante, com o jogador avaliando sua própria fatia em e a fatia do jogador às$1/n$$1$$1/n$$2$$(n-1)/n$$2$$1/n$$3$$(n-1)/n$$n$$1/n$$1$$(n-1)/n$ . Agora o novo jogador chega. Não importa o que o novo jogador deseje, seu protocolo terá que reorganizar algo do jogador para o jogador , do jogador para o jogador , etc.$2$$1$$3$$2$

Uma referência pode ser Walsh, Online Cake Cutting , na Algorithmic Decision Theory 2011 (link em pdf). Mas acho que o jornal pressupõe que sabemos com antecedência o número de agentes que chegam e assume que os jogadores devem receber uma peça exatamente quando eles saírem (o que é antes do final do protocolo), portanto, isso não é realmente aplicável ao seu problema.

Uma maneira de redistribuir uma alocação proporcional que mantém a proporcionalidade é a seguinte. Que cada um dos jogadores atuais corte seu pedaço de bolo alocado em pedaços que ele mesmo valoriza. O jogador agora escolherá a melhor peça, de acordo com ele, de cada um dos cortes do jogador. É fácil mostrar que a alocação resultante também é proporcional.$n$$n+1$$n+1$$n$

Suponha que o bolo / área seja um círculo com raio . Então, podemos criar peças justas pelo corte canônico do bolo e assim atribuir a cada jogador uma área de . Podemos então atribuir ao um pequeno círculo ao redor do centro, e os novos jogadores subsequentes tocam em torno dele (engolir parte do círculo interno), e assim por diante. Dessa forma, todo jogador recebe uma peça / parcela contígua que diminui de maneira monótona para os primeiros jogadores e se move em direção ao centro para os que se juntarem mais tarde.$C$$r$$n$$\frac{\pi r^2}{n}$$(n+1)$$n+1$

Determinar os números é simples; para o primeiro novo jogador, basta resolver

$\qquad \pi r_1^2 = \frac{\pi r^2}{n+1}$

para obter o raio de sua trama. Para o segundo, resolva

$\qquad\begin{align} \pi r_1^2 &= \frac{\pi r^2}{n+2} \\ \pi r_2^2 - \pi r_1^2 &= \frac{\pi r^2}{n+2} \end{align}$

para obter raios (externos) para os dois novos jogadores e assim por diante. Parece que o jogador recebe o raio externo depois que jogadores adicionais se juntaram, mas eu não provei isso.r i = r $n + i$$r_i = \frac{r\sqrt{i}}{\sqrt{n+k}}$$k$

Isto é o que você começa para e :k = 0 , 1 , 2 , $n=6$$k=0,1,2,3$

^{[ fonte ]}

A mesma idéia funciona para polígonos regulares com lados. Se você assumir um retângulo como forma básica, poderá fazer uma coisa semelhante atribuindo as primeiras colunas de tamanho igual e as seguintes linhas de jogadores (começando de um lado).$n$$n$