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

11

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.nnn

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 + 1nn+1

Erel Segal-Halevi
la source
2
Les premiers joueurs ont-ils commencé à manger? Est-il juste de donner à un joueur plusieurs pièces, ou est-ce que tout le monde doit obtenir exactement une pièce? n
Raphael
@Raphael, je suis spécifiquement intéressé par une répartition équitable des terres, donc les joueurs ne peuvent pas littéralement commencer à manger leur part (ils peuvent construire sur leur part, mais ignorons ce problème pour le moment). Il est préférable de donner à chaque joueur exactement une pièce, cependant, cela n'est apparemment pas possible de le faire équitablement au cas où une seule nouvelle personne arriverait. Je devrais probablement demander ce qui se passe si nouveaux joueurs arrivent. Dans ce cas, il est possible (au moins en théorie) de diviser chaque part des premiers joueurs en 2 nouvelles parts. Dans tous les cas, toute référence est la bienvenue. nnn
Erel Segal-Halevi
En cas de terrain inutilisé, pourquoi ne pas tout redistribuer?
Raphael
2
Je pense que vous devez clarifier votre objectif. Minimiser le nombre de coupes de mise à jour? Minimisez la longueur totale des nouvelles coupes? Pouvons-nous réaffecter des pièces à d'anciens joueurs, ou pouvons-nous seulement perdre?
Raphael
Ah, maintenant je vois ce que vous voulez dire: vous voulez dire que certains joueurs ont commencé à manger leur part, et maintenant de nouveaux joueurs arrivent, et nous voulons diviser les rappels équitablement, en tenant compte de ce que chaque joueur a déjà mangé. Bien que ce soit un problème intéressant en soi, mon intention était différente - j'espère que mon récent montage clarifie cela.
Erel Segal-Halevi

Réponses:

6

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 ] ) = 1[0,1]nivi(S)SA,B[0,1]vi(AB)=vi(A)+vi(B)vi([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:{S1,,Sn}

  • 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)vi([0,1])i1/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.)vi(Si)vi(Sj)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?nn+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 ?nn+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/n11/n2(n1)/n21/n3(n1)/nn1/n1(n1)/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.2132


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.nn+1n+1n

usul
la source
Je ne sais pas comment le problème général (avec une préférence non uniforme) est utile ici; whoops ? Résoudre le problème des joueurs immuables (et des formes raisonnables) est facile. Je suppose que nous devrons déterminer ce que "efficace" ou "bon" signifie par rapport aux coupures / allocations et aux changements de celles-ci.
Raphael
1
@Raphael - pour autant que je sache, la question porte sur la résolution du problème général. (Je suis d'accord que nous devrions utiliser une structure supplémentaire si elle est spécifiée.)
usul
Merci, votre définition a précisément saisi mon intention. Et la référence sur la découpe de gâteaux en ligne est intéressante et pertinente.
Erel Segal-Halevi
6

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.Crnπr2n(n+1)n+1

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

πr12=πr2n+1

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

πr12=πr2n+2πr22πr12=πr2n+2

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 kri=rin+kk

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

exemple [ 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é).nnn

Raphael
la source
1
Il serait intéressant de comparer la zone qui est réaffectée par cette méthode à la zone qui est réaffectée en insérant un nouveau morceau (c'est-à-dire un secteur) de gâteau et en déplaçant (et rétrécissant) toutes les pièces existantes dans le sens des aiguilles d'une montre. Le nombre de parties affectées par un mouvement (pas seulement une perte) ne diffère que par une constante. Notez également que les anneaux ne sont pas plus efficaces que les secteurs, mais le passage d'une méthode à l'autre permet de ne pas déplacer la zone affectée par la première méthode.
frafl
@frafl Je suis d'accord. Pouvez-vous présenter les autres variantes dans une réponse? (Vous avez raison: il ne semble pas y avoir de bonne raison de mélanger les méthodes. Pour moi c'était motivé par le problème du gâteau: supposons que le gâteau soit déjà coupé, que faire?)
Raphaël
@frafl Notez qu'un avantage du schéma que j'utilise peut être que les pièces des premiers joueurs ne rétrécissent que mais ne bougent pas. En d'autres termes, ce schéma rend moins de coupes (complètement) obsolètes que l'insertion de nouveaux secteurs de gâteau. n+1
Raphael
1
C'est une belle solution gemoetrical, mais elle n'est pertinente que pour des gâteaux uniformes et des prérérences uniformes. Je me suis référé au problème général de découpe de gâteau: en.wikipedia.org/wiki/Fair_division qui suppose que le gâteau peut être non uniforme, et différents joueurs peuvent avoir des évaluations différentes pour différentes parties du gâteau.
Erel Segal-Halevi