Division équitable - Fair division

Dans la théorie des jeux , la division équitable est le problème de diviser un ensemble de ressources entre plusieurs personnes qui y ont droit , de telle sorte que chaque personne reçoive sa part qui lui est due. Ce problème se pose dans divers contextes du monde réel, tels que : le partage de l'héritage, les dissolutions de partenariat, les accords de divorce , l' attribution électronique de fréquences , la gestion du trafic aéroportuaire et l'exploitation des satellites d'observation de la Terre . Il s'agit d'un domaine de recherche actif en mathématiques , en économie (en particulier en théorie du choix social ), en résolution de conflits , etc. Le principe central de la division équitable est qu'une telle division doit être effectuée par les joueurs eux-mêmes, peut-être en utilisant un médiateur mais certainement pas un arbitre car seuls les joueurs savent vraiment comment ils apprécient les marchandises.

L' algorithme archétypal de division équitable est diviser et choisir . Cela démontre que deux agents aux goûts différents peuvent partager un gâteau de telle sorte que chacun d'eux pense avoir obtenu le meilleur morceau. La recherche dans la division équitable peut être considérée comme une extension de cette procédure à divers contextes plus complexes.

Il existe de nombreux types différents de problèmes de répartition équitable, selon la nature des biens à répartir, les critères d'équité, la nature des acteurs et leurs préférences, et d'autres critères d'évaluation de la qualité de la répartition.

Des choses qui peuvent être divisées

Formellement, un problème de division équitable est défini par un ensemble (souvent appelé « le gâteau ») et un groupe de joueurs. Une division est une partition de en sous-ensembles disjoints : , un sous-ensemble par joueur. ${\style d'affichage C}$${\style d'affichage n}$${\style d'affichage C}$${\style d'affichage n}$${\displaystyle C=X_{1}\sqcup X_{2}\sqcup \cdots \sqcup X_{n}}$

L'ensemble peut être de différents types : ${\style d'affichage C}$

• ${\style d'affichage C}$peut être un ensemble fini d'éléments indivisibles, par exemple : , de sorte que chaque élément doit être attribué entièrement à une seule personne.${\displaystyle C=\{piano,voiture,appartement\}}$
• ${\style d'affichage C}$peut être un ensemble infini représentant une ressource divisible, par exemple : de l'argent, ou un gâteau. Mathématiquement, une ressource divisible est souvent modélisée comme un sous-ensemble d'un espace réel, par exemple, la section [0,1] peut représenter un gâteau long et étroit, qui doit être découpé en morceaux parallèles. Le disque unité peut représenter une tarte aux pommes.

De plus, l'ensemble à diviser peut être :

• homogène - comme l'argent, où seul le montant compte, ou
• hétérogène - comme un gâteau qui peut avoir différents ingrédients, différents glaçages, etc.

Enfin, il est courant de faire certaines hypothèses quant à savoir si les éléments à diviser sont :

• marchandises - comme une voiture ou un gâteau, ou
• mauvais – comme les tâches ménagères.

Sur la base de ces distinctions, plusieurs types généraux de problèmes de division équitable ont été étudiés :

• Affectation équitable des articles - divisant un ensemble de biens indivisibles et hétérogènes .
• Allocation équitable des ressources - divisant un ensemble de biens divisibles et homogènes . Un cas particulier est la division équitable d'une seule ressource homogène .
• Couper le gâteau équitablement - divisant un bien divisible et hétérogène . Un cas particulier est lorsque le gâteau est un cercle ; alors le problème s'appelle le découpage équitable .
• Division équitable des corvées - diviser un mal divisible et hétérogène.

Les combinaisons et cas particuliers sont également fréquents :

• L'harmonie locative (alias le problème des colocataires) - divisant un ensemble de biens hétérogènes indivisibles (par exemple, des chambres dans un appartement), et simultanément un mal divisible homogène (le loyer de l'appartement).
• Partage équitable des cours d'eau - diviser les eaux coulant dans un fleuve international entre les pays le long de son cours d'eau.
• L'attribution aléatoire équitable - divisant les loteries sur les divisions - est particulièrement courante lors de l'attribution de biens indivisibles.

Définitions de l'équité

La plupart de ce qu'on appelle normalement un partage équitable n'est pas considéré comme tel par la théorie en raison du recours à l' arbitrage . Ce genre de situation arrive assez souvent avec des théories mathématiques nommées d'après des problèmes de la vie réelle. Les décisions du Talmud sur le droit lorsqu'une succession est en faillite reflètent des idées assez complexes sur l'équité, et la plupart des gens les considéreraient comme justes. Cependant ils sont le résultat de débats juridiques par les rabbins plutôt que de divisions selon les évaluations des demandeurs.

Selon la théorie subjective de la valeur , il ne peut y avoir de mesure objective de la valeur de chaque élément. Par conséquent, l' équité objective n'est pas possible, car différentes personnes peuvent attribuer des valeurs différentes à chaque élément. Les expériences empiriques sur la façon dont les gens définissent le concept d'équité conduisent à des résultats peu concluants.

Par conséquent, la plupart des recherches actuelles sur l'équité se concentrent sur les concepts d' équité subjective . Chacune des personnes est supposée avoir une fonction d'utilité personnelle et subjective ou une fonction de valeur , , qui attribue une valeur numérique à chaque sous-ensemble de . Souvent, les fonctions sont supposées être normalisées, de sorte que chaque personne évalue l'ensemble vide à 0 ( pour tout i) et l'ensemble complet d'éléments à 1 ( pour tout i) si les éléments sont souhaitables, et -1 si les éléments sont indésirables. Les exemples sont : ${\style d'affichage n}$${\style d'affichage V_{i}}$${\style d'affichage C}$${\displaystyle V_{i}(\emptyset )=0}$${\style d'affichage V_{i}(C)=1}$

• Si est l'ensemble des éléments indivisibles {piano, voiture, appartement}, alors Alice peut attribuer une valeur de 1/3 à chaque élément, ce qui signifie que chaque élément est important pour elle tout comme n'importe quel autre élément. Bob peut affecter la valeur 1 à l'ensemble {voiture, appartement} et la valeur 0 à tous les autres ensembles sauf X ; cela signifie qu'il ne veut réunir que la voiture et l'appartement ; la voiture seule ou l'appartement seul, ou chacun d'eux avec le piano, ne lui vaut rien.${\style d'affichage C}$
• Si est un gâteau long et étroit (modélisé comme l'intervalle [0,1]), alors, Alice peut attribuer à chaque sous-ensemble une valeur proportionnelle à sa longueur, ce qui signifie qu'elle veut autant de gâteau que possible, quels que soient les glaçages. Bob peut attribuer une valeur uniquement aux sous-ensembles de [0.4, 0.6], par exemple, parce que cette partie du gâteau contient des cerises et Bob ne se soucie que des cerises.${\style d'affichage C}$

Sur la base de ces fonctions de valeur subjectives, il existe un certain nombre de critères largement utilisés pour une répartition équitable. Certains d'entre eux sont en conflit les uns avec les autres, mais ils peuvent souvent être combinés. Les critères décrits ici s'appliquent uniquement lorsque chaque joueur a droit au même montant :

• Une division proportionnelle signifie que chaque personne reçoit au moins sa part due selon sa propre fonction de valeur . Par exemple, si trois personnes se partagent un gâteau, chacune obtient au moins un tiers par sa propre évaluation, c'est-à-dire que chacune des n personnes obtient un sous-ensemble dont elle évalue au moins 1/ n de la valeur totale : ${\style d'affichage C}$
  • ${\style d'affichage V_{i}(X_{i})\geq V_{i}(C)/n}$ pour tout je.
• Une division super-proportionnelle est une division où chaque joueur reçoit strictement plus de 1/ n (une telle division n'existe que si les joueurs ont des évaluations différentes) :
  • ${\style d'affichage V_{i}(X_{i})>V_{i}(C)/n}$pour tout je .
• Une division sans envie garantit que personne ne voudra la part de quelqu'un d'autre plus que la sienne, c'est-à-dire que chaque personne reçoit une part qu'elle valorise au moins autant que toutes les autres parts :
  • ${\style d'affichage V_{i}(X_{i})\geq V_{i}(X_{j})}$ pour tout i et j.
• Une division sans envie de groupe garantit qu'aucun sous-ensemble d'agents n'envie un autre sous-ensemble de la même taille ; c'est beaucoup plus fort que l'absence d'envie.
• Une division équitable signifie que chaque personne ressent exactement le même bonheur, c'est-à-dire que la proportion du gâteau qu'un joueur reçoit selon sa propre évaluation est la même pour chaque joueur. C'est un objectif difficile car les joueurs n'ont pas besoin d'être véridiques si on leur demande leur évaluation :
  • ${\style d'affichage V_{i}(X_{i})=V_{j}(X_{j})}$ pour tout i et j.
• Une division exacte (ou division par consensus) est une division où tous les joueurs s'entendent sur la valeur de chaque action :
  • ${\style d'affichage V_{i}(X_{i})=V_{j}(X_{i})}$ pour tout i et j.

Tous les critères ci-dessus supposent que les participants ont des droits égaux . Si différents participants ont des droits différents (par exemple, dans un partenariat où chaque partenaire a investi un montant différent), alors les critères d'équité doivent être adaptés en conséquence. Voir Découpage proportionnel du gâteau avec différents droits .

Exigences supplémentaires

En plus de l'équité, on souhaite parfois que la division soit Pareto optimale , c'est-à-dire qu'aucune autre attribution ne rendrait quelqu'un mieux loti sans nuire à quelqu'un d'autre. Le terme efficacité vient de l' idée économique du marché efficace . Une division où un joueur obtient tout est optimale selon cette définition, donc à elle seule, cela ne garantit même pas une part équitable. Voir aussi la coupe de gâteau efficace et le prix de l'équité .

Dans le monde réel, les gens ont parfois une idée très précise de la valeur que les autres joueurs accordent aux marchandises et ils peuvent s'en soucier beaucoup. Le cas où ils ont une connaissance complète des évaluations de l'autre peut être modélisé par la théorie des jeux . La connaissance partielle est très difficile à modéliser. Une partie importante du côté pratique de la division équitable est la conception et l'étude de procédures qui fonctionnent bien malgré une connaissance partielle ou de petites erreurs.

Une exigence supplémentaire est que la procédure de répartition équitable soit un mécanisme véridique , c'est-à-dire qu'elle devrait être une stratégie dominante pour les participants de déclarer leurs véritables évaluations. Cette exigence est généralement très difficile à satisfaire en combinaison avec l'équité et l'efficacité de Pareto.

Procédures

Une procédure de répartition équitable répertorie les actions à réaliser par les acteurs en fonction des données visibles et de leurs valorisations. Une procédure valide est celle qui garantit une répartition équitable pour chaque joueur qui agit rationnellement en fonction de son évaluation. Lorsqu'une action dépend de l'évaluation d'un joueur, la procédure décrit la stratégie qu'un joueur rationnel suivra. Un joueur peut agir comme si une pièce avait une valeur différente mais doit être cohérente. Par exemple, si une procédure dit que le premier joueur coupe le gâteau en deux parties égales puis que le deuxième joueur choisit un morceau, alors le premier joueur ne peut pas prétendre que le deuxième joueur en a eu plus.

Ce que font les joueurs, c'est :

• Se mettre d'accord sur leurs critères pour une division équitable
• Sélectionnez une procédure valide et suivez ses règles

On suppose que le but de chaque joueur est de maximiser le montant minimum qu'il pourrait obtenir, ou en d'autres termes, d'atteindre le maximum .

Les procédures peuvent être divisées en procédures discrètes ou continues . Une procédure discrète impliquerait par exemple une seule personne à la fois coupant ou marquant un gâteau. Les procédures continues impliquent des choses comme un joueur déplaçant un couteau et l'autre disant "stop". Un autre type de procédure continue implique qu'une personne attribue une valeur à chaque partie du gâteau.

Pour une liste des procédures de division équitable, voir Category:Fair division protocols .

Rallonges

Récemment, le modèle de répartition équitable a été étendu des agents individuels aux familles (groupes prédéterminés) d'agents. Voir Répartition équitable entre les groupes .

Histoire

Selon Sol Garfunkel , le problème de la coupe du gâteau avait été l'un des problèmes ouverts les plus importants des mathématiques du 20e siècle, lorsque la variante la plus importante du problème a finalement été résolue avec la procédure Brams-Taylor de Steven Brams et Alan Taylor en 1995.

Les origines de Divide and Choose ne sont pas documentées. Les activités connexes de négociation et de troc sont également anciennes. Les négociations impliquant plus de deux personnes sont également assez courantes, la Conférence de Potsdam en est un exemple récent notable.

La théorie de la division équitable ne remonte qu'à la fin de la seconde guerre mondiale. Il a été conçu par un groupe de mathématiciens polonais , Hugo Steinhaus , Bronisław Knaster et Stefan Banach , qui se réunissaient au Scottish Café de Lvov (alors en Pologne). Une division proportionnelle (juste division) pour un nombre quelconque de joueurs appelée "dernier décroissant" a été conçue en 1944. Cela a été attribué à Banach et Knaster par Steinhaus lorsqu'il a rendu le problème public pour la première fois lors d'une réunion de l' Econometric Society à Washington DC le 17 septembre 1947. Lors de cette réunion, il a également proposé le problème de trouver le plus petit nombre de coupes nécessaires pour de telles divisions.

Pour l'histoire de la coupe de gâteau sans envie , voir coupe de gâteau sans envie .

Dans la culture populaire

• Dans l' épisode "One Hour" de la saison 3 de Numb3rs , Charlie parle du problème de la coupe du gâteau appliqué au montant d'argent qu'un kidnappeur exigeait.
• Hugo Steinhaus a décrit un certain nombre de variantes de la division équitable dans son livre Mathematical Snapshots . Dans son livre, il dit qu'une version spéciale à trois personnes de la division équitable a été conçue par G. Krochmainy à Berdechów en 1944 et une autre par Mme L Kott.
• Martin Gardner et Ian Stewart ont tous deux publié des livres avec des sections sur le problème. Martin Gardner a introduit la forme de division de la corvée du problème. Ian Stewart a popularisé le problème de la division équitable avec ses articles dans Scientific American et New Scientist .
• Une bande dessinée Dinosaur Comics est basée sur le problème de la coupe du gâteau.
• Dans le film israélien Sainte Claire , un immigrant russe demande à un professeur de mathématiques israélien, comment un gâteau circulaire peut-il être divisé équitablement entre 7 personnes ? Sa réponse est de faire 3 coupes droites à travers son milieu, faisant 8 pièces égales. Puisqu'il n'y a que 7 personnes, une pièce doit être jetée, dans l'esprit du communisme.

Voir également

• La division de foire en ligne est une variante de la division de foire dans laquelle tous les articles ou agents ne sont pas disponibles au moment de la division.
• Équité (économie)
• Échange international
• Justice (économie)
• Problème de sac à dos
• Liste des problèmes non résolus dans la division équitable
• Nash jeu de négociation
• Théorème de la pizza
• Prix ​​de l'équité
• Malgré (théorie des jeux)
• Division des foires stratégiques
• Tragédie des anticommuns
• Tragédie des biens communs

Les références

Livres de texte

• Jeune, Peyton H. (1995). Équité : en théorie et en pratique . Presse de l'Université de Princeton.
• Brams, Steven J.; Taylor, Alan D. (1996). Division équitable : de la coupe du gâteau au règlement des différends . La presse de l'Universite de Cambridge. ISBN 0-521-55644-9.
• Robertson, Jacques ; Webb, Guillaume (1998). Algorithmes de coupe de gâteau : soyez juste si vous le pouvez . Natick, Massachusetts : AK Peters. ISBN 978-1-56881-076-8. LCCN  97041258 . OL  2730675W .
• Hervé Moulin (2004). Division équitable et bien-être collectif . Cambridge, Massachusetts : MIT Press. ISBN 9780262134231.
• Barbanel, Julius B. ; avec une introduction d'Alan D. Taylor (2005). La géométrie d'une division équitable efficace . Cambridge : Cambridge University Press. doi : 10.1017/CBO9780511546679 . ISBN 0-521-84248-4. MR  2132232 . Un bref résumé est disponible sur : Barbanel, J. (2010). « Une approche géométrique à la division juste ». Le Journal de Mathématiques du Collège . 41 (4) : 268. doi : 10.4169/074683410x510263 .
• Steven J. Brams (2008). Mathématiques et démocratie : concevoir de meilleures procédures de vote et de partage équitable . Princeton, New Jersey : Princeton University Press. ISBN 9780691133218.

Articles de sondage

• Vincent P. Crawford (1987). "juste division," The New Palgrave: A Dictionary of Economics , v. 2, pp. 274-75.
• Hal Varian (1987). « équité », The New Palgrave : A Dictionary of Economics , v. 2, pp. 275-76.
• Bryan Skyrms (1996). L'évolution du contrat social Cambridge University Press. ISBN  978-0-521-55583-8
• Hill, TP (2000). « Dispositifs mathématiques pour obtenir une part équitable ». Scientifique américain . 88 (4) : 325-331. Bibcode : 2000AmSci..88..325H . doi : 10.1511/2000.4.325 .
• Brandt, Félix ; Conitzer, Vincent ; Endriss, Ulle ; Lang, Jérôme; Procaccia, Ariel D. (2016). Manuel de choix social computationnel . La presse de l'Universite de Cambridge. ISBN 9781107060432.( version gratuite en ligne ), chapitres 11-13.
• Fair Division par Christian Klamler - dans Handbook of Group Decision and Negotiation pp 183-202.
• Cake-Cutting: Fair Division of Divisible Goods par Claudia Lindner et Jörg Rothe - in Economics and Computation pp 395–491.
• La division équitable des biens indivisibles par Jérôme Lang et Jörg Rothe - in Economics and Computation pp 493-550.

Liens externes

• Fair Division du Discrete Mathematics Project de l'Université du Colorado à Boulder.
• Division des foires : méthode des marqueurs
• Division équitable : méthode des offres scellées