Coupe du gâteau juste quand les joueurs se joignent tard

L'énoncé habituel du problème de la coupe du gâteau suppose que tous les joueurs obtiennent leur part en même temps. Cependant, dans de nombreux cas, les joueurs arrivent progressivement. Par exemple, nous pouvons diviser un gâteau sur joueurs, mais un nouveau joueur arrive et veut une part.$n$$n$

Habituellement, la division du gâteau équitable nécessite beaucoup d'efforts (par exemple, oblige les joueurs à répondre à de nombreuses requêtes), surtout lorsque le nombre de joueurs est important.

Est-il possible d'utiliser la division existante du gâteau sur joueurs, afin de créer une nouvelle division du gâteau à joueurs, avec un effort supplémentaire minimal (c'est-à-dire beaucoup moins d'efforts que de redistribuer le gâteau à partir de zéro)?n + $n$$n+1$

Je dirai d'emblée que je ne peux pas fournir une bonne réponse à votre question (je pense que vous pourriez peut-être en tirer un document de recherche si vous le pouviez), mais je pense que je peux vous aider en définissant le problème de manière formelle et en indiquant où certains des difficultés résident.

Contexte . Permettez-moi d'indiquer clairement le modèle de découpe de gâteaux. Nous souhaitons diviser l'intervalle entre joueurs. Chaque joueur a une fonction de valorisation sur les sous-ensembles du gâteau. Nous supposerons que cette fonction est une mesure de probabilité; il est non négatif et additif (pour disjoint , ) et . Une solution à ce problème est un protocole ou un algorithme qui interroge les joueurs et attribue des parties de l'intervalle. Notez que les joueurs peuvent déformer / mentir en répondant aux requêtes.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$

Certains papiers auront des restrictions plus spécifiques; par exemple , les fonctions de valorisation sont continues, linéaires par morceaux ou constantes par morceaux.

Que les pièces attribuées aux joueurs soient . Nous voulons souvent les propriétés suivantes d'un protocole:$\{S_1,\dots,S_n\}$

• proportionnalité : Chaque joueur a une stratégie qui garantit qu'il reçoit une valeur d'au moins . (Du point de vue de , il obtient de la valeur totale du gâteau.)$i$$(1/n)v_i([0,1])$$i$$1/n$
• l'envie-libre : chaque joueur a une stratégie qui garantit que pour chaque autre joueur . (Chaque joueur préfère sa propre pièce à la pièce de tout autre joueur.)$v_i(S_i) \geq v_i(S_j)$$j$

Notez que l'absence d'envie implique la proportionnalité.

Il existe également des propriétés "opérationnelles" que nous pourrions souhaiter, telles que la découpe en quelques morceaux, le temps d'exécution polynomial (ou bien la calculabilité / constructibilité du tout - nous ne voulons pas utiliser l'Axiom of Choice pour sélectionner un sous-ensemble du gâteau! ), etc.

Questions spécifiques à poser . Deux notes. Tout d'abord, toute réponse à votre question résoudra le problème général: commencez par donner tout le gâteau au joueur , puis laissez les autres joueurs arriver en ligne et appliquez ce protocole de manière itérative. Nous devons donc nous attendre à ce que ce problème soit plus difficile que le paramètre de découpe de gâteau standard auquel nous l'appliquons.$1$

Deuxièmement, nous pouvons toujours résoudre votre problème en reprenant le gâteau entier à tout le monde et en utilisant un algorithme connu pour le redistribuer à partir de zéro. La question est donc de savoir s'il existe une manière un peu plus élégante de procéder. Je pense qu'un bon moyen de quantifier cela est "quand la redistribution nécessite-t-elle moins de temps ou moins de coupes que de recommencer à zéro; et / ou quand les joueurs peuvent-ils conserver une partie importante de leur tranche actuelle?"

1. Supposons que nous ayons une allocation sans envie pour joueurs. Comment redistribuer pour produire une allocation sans envie entre les joueurs?$n$$n+1$

Je soupçonne que c'est très difficile. La raison en est que trouver une allocation efficace et sans envie est déjà un problème difficile. Pour autant que je sache, les protocoles connus pourraient nécessiter un nombre illimité de coupes et sont très complexes. (Voir Brams et Taylor, An Envy-Free Cake Division Protocol , 1995.) Il n'y a donc rien de mieux que de reprendre tout le gâteau à tout le monde et de le redistribuer aux agents aide de Brams-Taylor.$n+1$

1. Supposons que nous ayons une allocation proportionnelle pour ; comment redistribuer pour obtenir une allocation proportionnelle pour ?$n$$n+1$

Je pense que c'est toujours difficile (bien que plus faisable). Considérez le cas où chaque joueur apprécie le gâteau uniformément et chaque joueur a une tranche de . Ensuite, quoi que fasse le nouveau joueur, il faudra un remaniement entre tous. Voici un autre mauvais cas: supposons que le joueur ait une évaluation d'exactement pour sa tranche, mais évalue la tranche du joueur à . Supposons que le joueur évalue sa propre tranche à exactement , mais évalue la tranche du joueur à , et ainsi de suite, le joueur évaluant sa propre tranche à et la tranche du joueur à$1/n$$1$$1/n$$2$$(n-1)/n$$2$$1/n$$3$$(n-1)/n$$n$$1/n$$1$$(n-1)/n$ . Maintenant, le nouveau joueur arrive. Peu importe ce que le nouveau joueur veut, votre protocole finira par devoir remanier quelque chose du joueur au joueur , du joueur au joueur , etc.$2$$1$$3$$2$

Une référence pourrait être Walsh, Online Cake Cutting , dans Algorithmic Decision Theory 2011 (lien pdf). Mais je pense que le papier suppose que nous savons à l'avance le nombre d'agents arrivant, et suppose que les joueurs doivent se voir attribuer un morceau précisément lorsqu'ils partent (ce qui est avant la fin du protocole), donc ce n'est vraiment pas celui qui s'applique à votre problème.

Une façon de redistribuer une allocation proportionnelle qui maintient la proportionnalité est la suivante. Laissez chacun des joueurs actuels couper son morceau de gâteau alloué en morceaux qu'il apprécie lui-même également. Le joueur choisira désormais la meilleure pièce, selon lui, parmi chacune des coupes du joueur . Il est facile de montrer que l'allocation qui en résulte est également proportionnelle.$n$$n+1$$n+1$$n$

Supposons que le gâteau / la zone est un cercle de rayon . Ensuite, nous pouvons créer pièces justes par la coupe canonique du gâteau et ainsi affecter à chaque joueur une zone de . Nous pouvons ensuite attribuer au ème un petit cercle autour du centre, et les nouveaux joueurs suivants sonnent autour de celui-ci (avalant une partie du cercle intérieur), et ainsi de suite. De cette façon, chaque joueur obtient une pièce / intrigue contiguë qui rétrécit de manière monotone pour les premiers joueurs, et se déplace vers le centre pour ceux qui rejoindront plus tard.$C$$r$$n$$\frac{\pi r^2}{n}$$(n+1)$$n+1$

L'élaboration des chiffres est simple; pour le premier nouveau joueur, résolvez simplement

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

pour obtenir le rayon de son intrigue. Pour la seconde, résolvez

$\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}$

pour obtenir des rayons (externes) pour les deux nouveaux joueurs, etc. Il semble que le joueur le rayon extérieur après que joueurs supplémentaires se soient joints, mais je n'ai pas prouvé cela.r i = r $n + i$$r_i = \frac{r\sqrt{i}}{\sqrt{n+k}}$$k$

Voici ce que vous obtenez pour et :k = 0 , 1 , 2 , $n=6$$k=0,1,2,3$

^{[ source ]}

La même idée fonctionne pour les polygones réguliers avec côtés. Si vous supposez un rectangle comme forme de base, vous pouvez faire la même chose en affectant les premières colonnes de taille égale et les rangées de joueurs suivantes (en commençant d'un côté).$n$$n$