de coupe du gâteau juste quand les joueurs se joignent à la fin

Question

La déclaration habituelle du problème de coupe du gâteau de juste suppose que tous les joueurs $ n $ obtiennent leur part à la temps. Cependant, dans de nombreux cas, les joueurs arrivent progressivement. Par exemple, on peut diviser un gâteau de plus de $ n $ joueurs, mais un nouveau joueur arrive et veut une part.

En général, la division équitable du gâteau nécessite beaucoup d'efforts (par exemple, exige que les joueurs de répondre à de nombreuses requêtes), en particulier lorsque le nombre de joueurs est grande.

Est-il possible d'utiliser la répartition actuelle du gâteau plus de $ n joueurs $, afin de créer une nouvelle division du gâteau à n $ + 1 joueurs de $, avec un effort supplémentaire minime (c.-à-beaucoup moins d'effort que re- distribuer le gâteau à partir de zéro)?

Answer 1

Je vais dire à l'avance que je ne peux pas donner une bonne réponse à votre question (je pense que vous pourriez peut-être obtenir un document de recherche sur si vous pouviez), mais je pense que je peux aider en définissant le problème formellement et indiquant où certaines difficultés se trouvent.

Historique . Permettez-moi de dire clairement le modèle de coupe du gâteau. Nous voulons diviser l'intervalle $ [0,1] $ entre $ n $ joueurs. Chaque joueur $ i $ a $ sur des sous-ensembles fonction d'évaluation v_i de $ (S) $ S $ du gâteau. Nous partons du principe que cette fonction est une mesure de probabilité; il est positif ou nul et de l'additif (par disjoint $ A, B \ subseteq [0,1], $ v_i (A \ cup B) = v_i (A) + v_i (B) $) et $ v_i ([0,1] ) = 1 $. Une solution à ce problème est un protocole ou algorithme qui interroge les joueurs et ayants droit des parties de l'intervalle. Notez que les joueurs peuvent faire de fausses déclarations / mensonge pour répondre à des requêtes.

Certains documents seront des restrictions plus précises; par exemple. , les fonctions d'évaluation sont continues, ou linéaire par morceaux, ou constante par morceaux.

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

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

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

Il y a également des propriétés « opérationnelles » que nous pourrions vouloir, comme couper en morceaux, quelques temps polynomial (ou en effet calculabilité / constructibilité du tout - nous ne voulons pas utiliser l'axiome de choix pour sélectionner un sous-ensemble le gâteau!), et ainsi de suite.

---

Des questions spécifiques à poser . Deux notes. Tout d'abord, une réponse à votre question va résoudre le problème général: Commencez par donner tout le gâteau au joueur 1 $, puis laissez les autres joueurs arrivent en ligne et d'appliquer itérativement ce protocole. Donc, nous devrions nous attendre à ce problème plus difficile que le réglage de coupe du gâteau standard qui nous l'appliquons à.

En second lieu, nous pouvons toujours résoudre votre problème en prenant l'ensemble du dos de gâteau de tout le monde et en utilisant un algorithme connu pour le redistribuer à partir de zéro. Donc, la question est juste s'il y a une façon un peu plus élégante de le faire. Je pense qu'une bonne façon de quantifier est « Quand la redistribution nécessitent moins de temps ou moins de coupes que à partir de zéro, et / ou lorsque les joueurs se garder une obtenir partie importante de leur tranche actuelle? »

1. Supposons que nous ayons une allocation sans envie pour $ n $ joueurs. Comment pouvons-nous redistribuons pour produire une allocation sans envie parmi les n $ + 1 joueurs de $?

Je soupçonne que cela est très difficile. La raison en est que la recherche d'une allocation sans envie, efficace est déjà un problème difficile. Pour autant que je sache, les protocoles connus pourraient nécessiter un nombre illimité de coupes dans le gâteau et sont très complexes. (Voir Brams et Taylor, Un protocole Division gâteau sans envie , 1995.) Donc il peut y avoir rien de mieux que de prendre l'ensemble du dos gâteau de tout le monde et de le redistribuer aux n $ + 1 agents $ en utilisant Brams-Taylor.

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

Je pense que cela est encore difficile (bien que plus faisable). Prenons le cas où chaque joueur apprécie le gâteau uniformément et chaque joueur a 1 $ / n $ tranche -sized. Ensuite, quel que soit le nouveau joueur ne nécessitera remaniant entre tous. Voici un autre mauvais cas: joueur 1 $ Suppose a une valeur exactement 1 $ / n $ pour sa tranche, mais les valeurs joueur 2 $ la tranche de '$ à $ (n-1) / n $. joueur $ 2 valeurs Supposons de $ sa propre tranche exactement1 $ / n $, mais le joueur de valeurs 3 $ la tranche de 'la tranche d'au $ (n-1) / n $, et ainsi de suite, avec lecteur $ n $ évaluation sa propre tranche à 1 $ / n $ et le joueur 1 $' à $ (n-1) / n $. Maintenant, le nouveau joueur arrive. Peu importe ce que le nouveau joueur veut, votre protocole finira par avoir à remanier quelque chose de joueur 2 $ au joueur 1 $, de joueur $ 3 $ à joueur $ 2, etc.

---

Une référence pourrait être Walsh, Gâteau en ligne de coupe , dans Algorithmique théorie de la décision 2011 (lien pdf). Mais je pense que le papier suppose que nous savons à l'avance le nombre d'agents qui arrivent, et suppose les joueurs doivent être attribués un morceau précisément quand ils quittent (ce qui est avant la fin du protocole), il est donc vraiment pas applicable à votre problème.

---

Une façon de redistribuer une répartition proportionnelle qui maintient la proportionnalité est la suivante. Que chacun de la présente $ n $ joueurs retranchés son morceau de gâteau alloué en n $ + 1 $ de pièces que lui-même des valeurs également. Joueur $ n + 1 $ choisiront maintenant la meilleure pièce, selon lui, de chacun des $ n réductions de $ joueur. Il est facile de montrer que l'allocation résultante est également proportionnelle.

Answer 2

Supposons que le gâteau / zone est un cercle C $ $ $ avec un rayon r $. Ensuite, nous pouvons créer $ N $ pièces équitables par le découpage du gâteau canonique et donc attribuer à chaque joueur une zone de $ \ frac {\ pi r ^ 2} {n} $. On peut alors attribuer $ (n + 1) $ e un petit cercle autour du centre, et des anneaux de nouveaux joueurs ultérieures autour de celle-là (avaler partie du cercle intérieur), etc. De cette façon, chaque joueur reçoit une pièce / parcelle contiguë qui rétrécit d'une manière monotone pour la première n $ + 1 $, les joueurs de et se déplace vers le centre pour ceux qui se joignent plus tard.

travail sur les chiffres est simple; pour le premier nouveau joueur, résoudre simplement

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

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

$ \ 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 (externe) pour les nouveaux joueurs, et ainsi de suite. Il semble que le joueur $ n + i $ obtient rayon extérieur $ r_i = \ frac {r \ sqrt {i}} {\ sqrt {n + k}} $ après $ k $ joueurs supplémentaires ont rejoint, mais je ne le prouvent.

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

^{[ la source ]}

La même idée fonctionne pour les polygones réguliers avec $ n $ côtés. Si vous assumez un rectangle comme forme de base, vous pouvez faire une chose semblable en attribuant la première $ n $ de taille égale les colonnes et les rangées de joueurs (à partir d'un côté).