📈 economics

Fair Allocation with Optional Selling

Cet article étudie l'allocation équitable de biens indivis où les agents peuvent choisir de vendre des articles aux prix du marché, adaptant les notions classiques d'équité telles que MMS et EFX à ce cadre hybride et établissant des garanties d'existence ainsi que des bornes d'approximation pour des allocations qui équilibrent la distribution des biens et des recettes.

Auteurs originaux : Uriel Feige, Yotam Gafni

Publié 2026-08-26

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Uriel Feige, Yotam Gafni

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La division équitable est un domaine des mathématiques et de l'économie dédié à la résolution d'un problème aussi vieux que la coopération humaine : comment diviser des ressources pour que chacun ait le sentiment d'avoir reçu une part juste. Pendant des décennies, des chercheurs ont étudié comment diviser des objets qui ne peuvent pas être découpés, comme une maison, une voiture ou une collection de livres rares. Dans ces scénarios, l'objectif est de trouver un arrangement où personne ne ressent d'envie envers ce qu'une autre personne a reçu, ou là où chacun est garanti un niveau minimum de satisfaction basé sur ses propres préférences personnelles. Cependant, ces modèles classiques supposent que les objets en question sont figés dans leur forme actuelle. Ils ignorent une option très courante dans le monde réel : la possibilité de vendre un objet contre de l'argent liquide. Dans un divorce, par exemple, un couple peut décider que vendre la maison familiale et partager l'argent est une meilleure solution que si l'un des deux gardait la maison et l'autre ne recevait rien. Cette simple option de vente change tout le paysage de ce qui est possible, mais elle introduit également de nouvelles complexités que les théories précédentes n'avaient pas abordées.

Uriel Feige et Yotam Gafni, de l'Institut de science Weizmann, sont intervenus pour combler cette lacune en explorant ce qui se passe lorsque les agents peuvent choisir de vendre des biens au prix du marché avant de diviser les articles restants et l'argent qui en résulte. Leurs travaux posent une question fondamentale : si les gens peuvent vendre des objets, cela devient-il plus facile ou plus difficile de garantir un résultat équitable ? Ils ont découvert que si la vente ouvre plus de possibilités, elle rend en réalité plus difficile la garantie de certains types d'équité par rapport au cadre traditionnel où la vente est interdite. Les chercheurs ont développé de nouvelles manières de mesurer l'équité qui tiennent compte à la fois de la valeur des objets que les gens conservent et de l'argent qu'ils reçoivent des ventes. Ils ont prouvé que pour deux personnes, il est toujours possible de trouver une division qui satisfait les normes d'équité les plus strictes, garantissant que personne n'envie le lot d'autrui même après avoir considéré l'option de vente. Cependant, à mesure que le nombre de personnes augmente, les garanties deviennent légèrement plus faibles. Pour trois personnes, ils ont montré qu'il est impossible de garantir que chacun obtienne sa part équitable maximale possible ; dans certains cas, le mieux que l'on puisse espérer est une fraction spécifique de cette part idéale.

Les chercheurs ont également étudié la capacité à approximer ces parts équitables pour des groupes plus larges. Ils ont démontré que pour n'importe quel nombre de personnes, il existe toujours un moyen de diviser les biens et l'argent de sorte que chacun reçoive au moins les deux tiers de sa part minimale garantie. C'est un résultat significatif car il montre que même avec la complexité ajoutée de la vente, un niveau d'équité très élevé est toujours réalisable. De plus, ils ont constaté qu'il est possible de combiner cette équité basée sur la part avec un fort sentiment d'absence d'envie, ce qui signifie que personne ne préférerait échanger l'intégralité de son lot de biens et d'argent avec celui d'une autre personne. Ils y sont parvenus en adaptant un algorithme connu sous le nom de méthode du « Diviseur Solitaire » (Lone Divider), qui implique qu'une personne propose une division et que les autres choisissent leurs parties préférées. Dans le nouveau contexte avec la vente, ils ont dû modifier cette approche avec soin, en veillant à ce que la personne proposant la division soit choisie judicieusement et que les lots soient structurés de manière spécifique pour empêcher que la vente d'articles ne nuise injustement aux participants restants.

L'une des conclusions les plus frappantes de l'article est la différence entre le cadre avec vente et le cadre sans vente. Les auteurs ont construit un exemple spécifique impliquant trois personnes et huit objets où, si la vente était autorisée, il serait impossible de garantir que chacun obtienne plus des onze douzièmes de sa part idéale. Dans le cadre traditionnel où les objets ne peuvent pas être vendus, la limite la plus élevée connue pour ce même scénario est bien supérieure, ce qui signifie que la capacité de vendre crée en fait un écart plus large entre ce qui est théoriquement possible et ce qui peut être garanti en pratique. Ce résultat contre-intuitif suggère que si la vente offre de la flexibilité, elle introduit également un nouveau type de risque où des objets de grande valeur pourraient être vendus à un prix bas, laissant les articles restants insuffisants pour satisfaire les besoins de tous. Les chercheurs ont également exploré un scénario connexe impliquant des tâches, ou des travaux que les gens n'aiment pas, où l'option d'externaliser le travail moyennant des frais joue le même rôle que la vente de biens. Ils ont trouvé des schémas similaires, montrant que la capacité de payer quelqu'un d'autre pour effectuer une tâche rend plus difficile la garantie d'une distribution parfaitement équitable du travail restant.

L'article aborde également l'aspect pratique de ces preuves mathématiques, en demandant si ces allocations équitables peuvent être calculées efficacement par un ordinateur. Les auteurs ont montré que pour le cas spécifique de deux personnes, une division équitable peut être trouvée en un temps raisonnable. Pour des groupes plus larges, ils ont développé des algorithmes qui peuvent s'approcher arbitrairement de la part équitable idéale, ce qui signifie qu'avec suffisamment de puissance de calcul, on peut trouver une solution presque aussi bonne que la meilleure solution théorique. Ils ont également prouvé qu'un type spécifique de garantie d'équité, basé sur une part proportionnelle tronquée, peut être calculé rapidement et combiné avec des conditions d'absence d'envie. Ce travail fournit un cadre robuste pour comprendre comment les marchés et les préférences personnelles interagissent dans les problèmes de division équitable, offrant de nouveaux outils pour des situations allant des règlements de divorce à la division d'actifs hérités. En définissant rigoureusement ce qui est possible lorsque la vente est une option, les chercheurs ont clarifié les limites de l'équité dans un monde où les ressources peuvent être converties en argent, garantissant ainsi que nous sachions exactement sur quelles garanties nous pouvons compter lorsque les enjeux sont élevés.

Résumé Technique : Allocation Équitable avec Vente Optionnelle

Définition du Problème

Cet article traite du problème de l'allocation équitable de biens indivisibles dans un contexte où les agents possèdent des fonctions de valorisation subjectives sur les biens, mais où ces derniers possèdent également des prix de marché exogènes. Contrairement aux modèles traditionnels de division équitable où les biens sont strictement indivisibles, ce cadre introduit une « option extérieure » : les agents peuvent choisir de vendre des biens à leurs prix de marché. Le produit de ces ventes est divisible et possède une valeur additive uniforme pour tous les agents.

Le défi central consiste à concevoir un mécanisme d'allocation qui décide simultanément de :

Quel sous-ensemble de biens doit être vendu.
Comment allouer les biens non vendus restants.
Comment distribuer les produits monétaires issus des ventes.

L'objectif est de satisfaire des notions d'équité qui adaptent les garanties standard basées sur les parts et sur l'absence d'envie à cet environnement hybride. Les auteurs supposent des valorisations additives tant pour les biens que pour l'argent.

Notions d'Équité

Le papier adapte deux catégories de définitions d'équité :

Notions basées sur les parts :
- Part Maximale (MMS - Maximin Share) : Définie comme la valeur maximale qu'un agent peut se garantir en décidant de manière optimale quels biens vendre, puis en partitionnant les biens restants et les produits en $n$ lots, en recevant le moins valuable de ces lots. Contrairement à la MMS standard, l'agent optimise à la fois la décision de vente et la partition.
- Part Proportionnelle Tronquée (TPS - Truncated Proportional Share) : Une extension du concept de TPS des contextes indivisibles, définie comme la plus grande valeur $t$ telle que la somme de $\max\{p(g), \min\{v(g), t\}\}$ sur tous les biens, divisée par $n$ , soit égale à $t$ .
Notions basées sur l'absence d'envie :
- SEF1 et SEFX (Absence d'envie forte/vendable) : Ce sont des adaptations de EF1 et EFX. Une allocation est SEFX si pour tout agent $i$ et tout autre agent $j$ , $i$ n'envie pas le lot de $j$ , même si $j$ vendait l'un de ses biens (et recevait le prix de marché) au lieu de le conserver. Formellement, $\bar{v}_i(A_i) + P_i \ge \bar{v}_i(A_j \setminus \{g\}) + p(g)$ pour chaque bien $g \in A_j$ , où $\bar{v}_i(g) = \max\{v_i(g), p(g)\}$ .

Méthodologie et Algorithmes

Les auteurs emploient une variété de techniques algorithmiques, incluant des variations de paradigmes de « Cut & Choose » (Couper et Choisir), « Bag-Filling » (Remplissage de sac) et « Lone Divider » (Diviseur Isolé), modifiés pour gérer la complexité introduite par la vente optionnelle.

Cut & Give (n=2) : Pour deux agents, les auteurs introduisent un protocole « Cut & Give ». Un agent (le Cutter) propose une partition basée sur sa MMS. Si l'autre agent (le Giver) trouve un lot acceptable, il le prend. Sinon, le Giver modifie la partition en vendant son propre bien et en annulant la vente du Cutter, créant ainsi un nouveau lot qui satisfait à la fois la MMS et la SEFX.
Bag-Filling avec Biens Virtuels (TPS) : Pour atteindre une $n/(2n-1)$ -TPS, l'algorithme utilise une approche de « lame mobile » (moving knife). Les biens ayant des prix de marché élevés sont immédiatement vendus pour satisfaire les exigences de part minimale des agents. Les produits restants sont traités comme des « biens virtuels ». Une procédure de remplissage de sac alloue ensuite les lots jusqu'à ce qu'un agent les valorise au seuil requis.
Partitions Canoniques (Lone Divider pour la MMS) : Pour un $n$ général, les auteurs adaptent la méthode du Lone Divider. Une innovation clé est la construction de « partitions canoniques » proposées par l'agent ayant la MMS la plus élevée. Ces partitions consistent en des « lots purs » (sans argent), des « lots simples » (un bien plus les produits d'au plus un autre bien vendu) et un unique lot de « restes ». Cette structure limite la perte potentielle qu'un agent subit si un lot qu'il a rejeté est alloué à quelqu'un d'autre, en plafonnant spécifiquement la perte causée par les ventes forcées.
Gestion des Articles de Haute Valeur : Les algorithmes incluent des phases préliminaires pour traiter les biens dont la valeur dépasse significativement le seuil de la MMS, soit en les vendant pour satisfaire des agents spécifiques, soit en les allouant directement, garantissant que le problème restant s'insère dans le cadre d'approximation.

Résultats Clés

1. Garanties Combinées de Part et d'Absence d'Envie

Deux Agents (n=2) : Il existe toujours une allocation qui est simultanément MMS et SEFX. C'est un résultat fort, car l'obtention d'une pleine MMS est généralement impossible pour $n \ge 3$ dans les contextes standards, et elle est ici obtenue parallèlement à une notion d'absence d'envie forte.
Agents Généraux (n $\ge$ 2) : Il existe une allocation qui est simultanément $n/(2n-1)$ -TPS et SEFX. Le ratio $n/(2n-1)$ est prouvé comme étant la meilleure approximation possible pour la TPS, même sans l'exigence de SEFX.

2. Bornes d'Approximation MMS

Trois Agents (n=3) : L'article établit un écart quantitatif entre les contextes avec et sans vente. Alors que la pleine MMS est garantie pour $n=3$ avec $m=8$ articles dans le cadre standard des biens indivisibles (où la meilleure borne connue sans vente est de $39/40$ ), dans le cadre de la vente, il existe des instances où aucune allocation ne garantit plus de $11/12$ -MMS.
Agents Généraux (n $\ge$ 4) : Les auteurs fournissent une allocation $2/3$ -MMS. Cela correspond à la meilleure approximation connue pour le cadre indivisible standard (sans le terme additif $O(1/n)$ présent dans certains travaux antérieurs).
Cas Particulier (n=3) : En combinant l'approche générale pour $n$ avec l'algorithme de pleine MMS pour $n=2$ , les auteurs obtiennent une allocation $3/4$ -MMS pour trois agents.

3. Complexité Computationnelle

Calcul de la MMS : Calculer la valeur exacte de la MMS est faiblement NP-difficile pour $n=2$ $n = 2$ et fortement NP-difficile pour un $n$ $n$ général. Cependant, l'article propose :
- Un algorithme en temps pseudo-polynomial pour un $n$ fixé.
- Un Schéma d'Approximation en Temps Polynomial (PTAS) pour calculer les valeurs et les partitions de la MMS.
Calcul de la TPS : La TPS est calculable efficacement en temps polynomial.
Garanties Combinées : Un FPTAS existe pour les allocations qui sont à la fois $n/(2n-1)$ -TPS et $\epsilon$ -SEFX.

4. Extensions

Produits Égaux : L'article analyse un cadre restreint où les produits de vente doivent être distribués équitablement entre tous les agents. Dans ce cas, la garantie d'approximation tombe à $1/n$ -TPS, et la garantie MMS peut être nettement plus faible que dans le cas non restreint.
Corvées avec Sous-traitance (Chores with Outsourcing) : Le modèle est étendu aux corvées (valorisations négatives) où les agents peuvent « sous-traiter » des tâches à un coût de marché. Les résultats reflètent ceux des biens : une approximation de 2-MMS est réalisable, mais l'écart d'approximation est plus large que dans le cadre standard des corvées indivisibles.

Signification et Revendications

L'article prétend fournir un cadre « Le Meilleur des Deux Mondes » pour la division équitable lorsque des options de marché sont disponibles. Ses principales contributions sont :

Identification de l'Écart Théorique : Il démontre que l'introduction d'options de vente, bien qu'élargissant l'ensemble des résultats possibles, peut paradoxalement rendre plus difficile l'approximation de certaines garanties d'équité (spécifiquement la MMS pour $n=3$ ) par rapport au cadre purement indivisible.
Algorithmes Robustes : Il développe des techniques algorithmiques novatrices (partitions canoniques, Lone Divider modifié) qui parviennent à récupérer les meilleurs ratios d'approximation connus pour la MMS en présence de vente, malgré la complexité ajoutée de l'optimisation des décisions de vente.
Équité Unifiée : Il intègre avec succès des garanties de part (MMS/TPS) avec des notions fortes d'absence d'envie (SEFX) dans une seule allocation, montant que des approximations de part de haute qualité n'excluent pas nécessairement une absence d'envie forte dans ce contexte.

Les auteurs soulignent que leurs résultats sont serrés dans plusieurs cas (par exemple, le lien $n/(2n-1)$ pour la TPS) et que les résultats négatifs (l'écart de $11/12$ pour $n=3$ ) sont des limitations prouvables du modèle, et non de simples artefacts des limitations algorithmiques actuelles.