2025-11-12T03:19:33.205062

EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture

Afshinmehr, Danaei, Kazemi et al.
We consider the fundamental problem of fairly allocating a set of indivisible items among agents having valuations that are represented by a multi-graph -- here, agents appear as vertices and items as edges between them and each vertex (agent) only values the set of its incident edges (items). The goal is to find a fair, i.e., envy-free up to any item (EFX) allocation. This model has recently been introduced by Christodoulou et al. (EC-23) where they show that EFX allocations always exist on simple graphs for monotone valuations, i.e., where any two agents can share at most one edge (item). A natural question arises as to what happens when we go beyond simple graphs and study various classes of multi-graphs? We answer the above question affirmatively for the valuation class of bipartite multi-graphs and multi-cycles. The main contribution of this work is to establish the existence of EFX allocations on bipartite multi-graphs for monotone valuations and on multi-cycles for MMS-feasible valuations. We also present pseudo-polynomial time algorithms to compute EFX allocations for the above settings. Furthermore, we show that for bipartite multi-graphs with cancelable valuations, EFX allocations can be computed in polynomial time. We thus widen the spectrum where EFX allocations are guaranteed to exist. Next, we study EFX orientations (allocations where every item is assigned to one of its two endpoint agents) and provide a complete characterization of their existence on bipartite multi-graphs in terms of two key parameters: (i) the number of edges shared between any two agents and (ii) the diameter of the graph. Finally, we prove that it is NP-complete to determine whether a given fair division instance on a bipartite multi-graph admits an EFX orientation, even with a constant number of agents.
academic

Allocations EFX et Orientations sur Multi-graphes Bipartis : Une Image Complète

Informations Fondamentales

  • ID de l'article: 2410.17002
  • Titre: EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
  • Auteurs: Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, Nidhi Rathi
  • Classification: cs.GT (Théorie des jeux), cs.DS (Structures de données et algorithmes)
  • Date de publication: Octobre 2024 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2410.17002

Résumé

Cet article étudie le problème de l'allocation équitable d'objets indivisibles sous des fonctions d'évaluation représentées par des multi-graphes. Dans ce modèle, les agents correspondent aux sommets du graphe, les objets aux arêtes, et chaque agent n'a une évaluation positive que pour les arêtes qui lui sont adjacentes. L'objectif est de trouver une allocation équitable, c'est-à-dire satisfaisant la condition EFX (envy-free up to any item). L'article s'appuie sur les travaux de Christodoulou et al. (2023), qui ont prouvé l'existence d'allocations EFX pour les fonctions d'évaluation monotones sur les graphes simples. Cet article étend la recherche à diverses catégories de multi-graphes, avec les contributions principales suivantes : (1) preuve de l'existence d'allocations EFX pour les évaluations monotones sur les multi-graphes bipartis et les évaluations MMS-feasible sur les multi-cycles ; (2) fourniture d'algorithmes en temps pseudo-polynomial correspondants ; (3) caractérisation complète du problème d'orientation EFX ; (4) preuve de la NP-complétude du jugement de l'existence d'orientations EFX.

Contexte et Motivation de la Recherche

Contexte du Problème

La théorie du partage équitable est un important domaine de recherche à l'intersection de l'économie, des sciences sociales, des mathématiques et de l'informatique, visant à distribuer équitablement un ensemble de ressources entre plusieurs participants. Dans le cas d'objets indivisibles, l'allocation sans envie classique peut ne pas exister ; les chercheurs ont donc proposé diverses versions relaxées, dont EFX est considérée comme le concept d'équité le plus proche de l'absence d'envie dans le cadre discret.

Motivation de la Recherche

  1. Défis théoriques: Pour quatre agents ou plus, l'existence d'allocations EFX reste un problème ouvert majeur
  2. Extension du modèle: Christodoulou et al. ont prouvé l'existence d'allocations EFX sur les graphes simples ; la question naturelle est celle des multi-graphes
  3. Applications pratiques: Ce modèle s'applique aux contextes géographiques où les agents ne s'intéressent qu'aux ressources à proximité, comme les corridors commerciaux, les gazoducs, etc.

Limitations des Approches Existantes

  • Les résultats existants se limitent principalement aux graphes simples (deux agents quelconques partagent au maximum un objet)
  • Manque d'étude systématique des multi-graphes (deux agents peuvent partager plusieurs objets)
  • L'existence et la complexité computationnelle des orientations EFX n'ont pas été complètement caractérisées

Contributions Principales

  1. Théorèmes d'existence: Preuve que les allocations EFX existent toujours pour les fonctions d'évaluation monotones sur les multi-graphes bipartis, et pour les évaluations MMS-feasible sur les multi-cycles
  2. Conception d'algorithmes: Fourniture d'algorithmes en temps pseudo-polynomial pour calculer les allocations EFX, calculables en temps polynomial pour les fonctions d'évaluation réductibles
  3. Caractérisation complète: Caractérisation complète de l'existence d'orientations EFX sur les multi-graphes bipartis basée sur deux paramètres clés (q et d(G))
  4. Analyse de complexité: Preuve de la NP-complétude du problème de jugement de l'existence d'orientations EFX, même pour un nombre constant d'agents
  5. Résultats d'approximation: Preuve de l'existence d'orientations où au moins ⌈n/2⌉ agents satisfont EFX et les autres satisfont 1/2-EFX pour les cas où l'orientation EFX n'existe pas

Détails Méthodologiques

Définition de la Tâche

Entrée:

  • Multi-graphe G = (V,E), où V = n représente n agents et E représente m objets
  • Fonctions d'évaluation {vi}i∈n, satisfaisant vi(S) = vi(S ∩ E(i)), où E(i) est l'ensemble des arêtes adjacentes à l'agent i

Sortie:

  • Allocation complète X = (X1,...,Xn), satisfaisant la condition EFX
  • Ou orientation EFX (chaque objet alloué à l'un de ses agents extrémités)

Contraintes:

  • EFX: Pour tous agents i,j et objet g ∈ Xj, vi(Xi) ≥ vi(Xj \ {g})
  • Types de fonctions d'évaluation: monotone, réductible, MMS-feasible, etc.

Architecture du Modèle

Concepts Fondamentaux

  1. Configuration T-cut: Pour les agents adjacents i ∈ S et j ∈ T, l'agent j divise E(i,j) en deux ensembles C1 et C2, tous deux EFX-feasible pour j
  2. Ensemble disponible: Définition de Ai,j(X) comme l'ensemble des arêtes disponibles pour l'agent i de E(i,j) sous l'allocation courante X
  3. Ensemble sûr: Pour l'agent envieux i, définition de Si(X) comme son ensemble sûr

Propriétés Clés

L'algorithme maintient six propriétés clés :

  1. X est une orientation EFX
  2. Les objets dans E(i,j) sont alloués selon la configuration j-cut
  3. Chaque agent reçoit son ensemble préféré disponible
  4. L'ensemble disponible des agents non envieux est vide
  5. L'évaluation des agents non envieux pour les arêtes adjacentes non allouées ne dépasse pas le paquet courant
  6. Les envieux de l'agent envieux se trouvent dans son ensemble sûr

Points d'Innovation Technique

1. Conception du Mécanisme de Configuration

Introduction innovante du concept de configuration T-cut, combinant les idées du protocole de sélection de partition pour deux personnes, fournissant une approche systématique pour traiter plusieurs arêtes dans les multi-graphes.

2. Cadre d'Algorithme par Étapes

Conception de cinq algorithmes satisfaisant successivement les six propriétés clés :

  • Algorithme 1: Orientation gourmande satisfaisant les propriétés (1)-(3)
  • Algorithme 2: Traitement des agents non envieux satisfaisant la propriété (4)
  • Algorithme 3: Augmentation de l'évaluation des agents non envieux satisfaisant la propriété (5)
  • Algorithme 4: Construction de l'ensemble sûr satisfaisant la propriété (6)
  • Algorithme 5: Allocation finale des objets restants

3. Exploitation de la Structure Bipartie

Exploitation complète des caractéristiques structurelles des graphes bipartis, en particulier le fait que les sommets envieux ne peuvent apparaître que dans une partition, simplifiant considérablement l'analyse et la conception d'algorithmes.

Configuration Expérimentale

Cadre d'Analyse Théorique

Cet article est principalement un travail théorique, vérifiant les résultats par des preuves mathématiques plutôt que par des expériences. Le cadre d'analyse comprend :

  1. Preuve d'existence: Preuve constructive montrant comment trouver une allocation satisfaisant les conditions
  2. Analyse de complexité d'algorithme: Analyse de la complexité temporelle de chaque étape d'algorithme
  3. Construction de contre-exemples: Preuve par des instances concrètes que les orientations EFX n'existent pas dans certains cas

Métriques d'Évaluation

  • Satisfaction EFX: Si tous les agents satisfont la condition EFX
  • Complexité temporelle: Temps d'exécution de l'algorithme (polynomial vs pseudo-polynomial)
  • Ratio d'approximation: Qualité de la solution approximée pour les cas où la solution exacte n'existe pas

Résultats Expérimentaux

Résultats Principaux

1. Théorèmes d'Existence

Théorème 4.11: Pour les évaluations monotones sur les multi-graphes bipartis, les allocations EFX existent toujours et peuvent être calculées en temps pseudo-polynomial ; pour les évaluations réductibles, elles peuvent être calculées en temps polynomial.

Théorème 5.1: Pour les évaluations MMS-feasible sur les multi-cycles, les allocations EFX existent toujours et peuvent être calculées en temps pseudo-polynomial.

2. Caractérisation Complète des Orientations EFX

Caractérisation complète basée sur les paramètres q (nombre maximal d'arêtes entre deux agents quelconques) et d(G) (diamètre du graphe) :

Conditions de ParamètresExistence d'Orientation EFX
Acyclique, q=2, d(G)≤4Existe
Acyclique, q=2, d(G)>4Peut ne pas exister
Acyclique, q>2, d(G)≤2Existe
Acyclique, q>2, d(G)>2Peut ne pas exister
Cyclique, q≥2, d(G)≥2Peut ne pas exister

3. Résultats de Complexité

Théorème 3.6: Le jugement de l'existence d'orientations EFX sur les multi-graphes bipartis est NP-complet, même pour un nombre constant d'agents.

4. Résultats d'Approximation

Théorème 4.12: Pour les évaluations additives sur les multi-graphes bipartis, il existe toujours une orientation telle qu'au moins ⌈n/2⌉ agents satisfont EFX et les autres satisfont 1/2-EFX.

Analyses de Cas

L'article démontre le processus d'exécution de l'algorithme par plusieurs instances concrètes :

  • Les figures 7-10 montrent l'exécution étape par étape de l'algorithme sur des multi-graphes bipartis spécifiques
  • La construction de contre-exemples (comme les figures 1-5) prouve la non-existence des orientations EFX dans certains cas

Découvertes Théoriques

  1. Rôle clé de la structure bipartie: La structure bipartie garantit que les sommets envieux n'apparaissent que dans une partition, ce qui est clé pour le succès de l'algorithme
  2. Efficacité du mécanisme de configuration: La configuration T-cut fournit un cadre unifié pour traiter les multi-arêtes
  3. Complexité paramétrée: Les deux paramètres q et d(G) caractérisent complètement l'existence d'orientations EFX

Travaux Connexes

État Actuel de la Recherche EFX

  • Deux agents: Plaut et Roughgarden ont prouvé l'existence pour les évaluations monotones
  • Trois agents: Une série de travaux a prouvé l'existence pour diverses types d'évaluations
  • Évaluations spéciales: Existence dans les cas spéciaux comme les évaluations identiques, les évaluations binaires, etc.

Partage Équitable sur Graphes

  • Christodoulou et al. ont proposé le premier modèle d'allocation EFX sur graphes simples
  • Les travaux ultérieurs ont étudié les extensions comme les orientations EF1, les objets mixtes, etc.
  • Cet article est le premier à étudier systématiquement les multi-graphes

Travaux Parallèles

Deux travaux parallèles indépendants ont également étudié EFX sur les multi-graphes :

  • Sgouritsa et Sotiriou (2025): Preuve de l'existence EFX pour les évaluations monotones sur les multi-graphes bipartis
  • Bhaskar et Pandit (2024): Étude de l'existence EFX sur des catégories spécifiques de multi-graphes

Conclusions et Discussion

Conclusions Principales

  1. Contribution théorique: Première caractérisation complète de l'existence d'allocations EFX sur les multi-graphes bipartis, étendant le cadre théorique existant
  2. Contribution algorithmique: Fourniture d'algorithmes pratiques en temps pseudo-polynomial, atteignant le temps polynomial pour certains types d'évaluations
  3. Caractérisation de complexité: Analyse complète de la complexité computationnelle du problème d'orientation EFX

Limitations

  1. Restriction sur les classes de graphes: Les résultats se concentrent principalement sur les multi-graphes bipartis ; les multi-graphes généraux restent un problème ouvert
  2. Restriction sur les fonctions d'évaluation: Bien que couvrant plusieurs types d'évaluations, le cas le plus général n'a pas été atteint
  3. Efficacité algorithmique: Pour les évaluations monotones générales, seule la complexité pseudo-polynomiale peut être atteinte

Directions Futures

  1. Multi-graphes généraux: Les auteurs conjecturent que les allocations EFX existent sur tout multi-graphe, mais la preuve nécessite de nouvelles techniques
  2. Optimisation algorithmique: Recherche d'algorithmes plus efficaces, en particulier d'algorithmes en temps polynomial
  3. Bien-être social: Étude du compromis entre les allocations EFX et l'efficacité

Évaluation Approfondie

Avantages

  1. Profondeur théorique: Fourniture de preuves d'existence complètes et d'analyses de complexité, avec des contributions théoriques significatives
  2. Innovation technique: Le mécanisme de configuration T-cut et le cadre d'algorithme par étapes sont innovants
  3. Complétude des résultats: Caractérisation complète et paramétrée de l'existence d'orientations EFX
  4. Clarté de la rédaction: Structure claire de l'article, preuves détaillées, faciles à comprendre et à vérifier

Insuffisances

  1. Absence de vérification expérimentale: En tant que travail purement théorique, manque d'évaluation de la performance algorithmique sur des données réelles
  2. Scénarios d'application limités: Les scénarios d'application pratique du modèle de multi-graphes sont relativement limités
  3. Limitations techniques: L'extension aux multi-graphes généraux fait face à des défis techniques

Impact

  1. Valeur académique: Progrès théorique important pour la théorie du partage équitable, promouvant le développement de la recherche EFX
  2. Contribution méthodologique: Le cadre technique proposé peut inspirer d'autres problèmes de partage équitable sur graphes
  3. Problèmes ouverts: Accumulation technique importante pour le problème d'existence EFX sur les multi-graphes généraux

Scénarios Applicables

  1. Recherche théorique: Référence importante pour les chercheurs en théorie du partage équitable
  2. Conception d'algorithmes: Le mécanisme de configuration peut être utilisé pour concevoir d'autres algorithmes de partage équitable
  3. Théorie de la complexité: Les résultats de NP-complétude ont une valeur pour la recherche en complexité computationnelle

Références

L'article cite les littératures importantes du domaine du partage équitable, notamment :

  • Christodoulou et al. 2023: Travail fondateur sur les allocations EFX sur graphes simples
  • Plaut et Roughgarden 2020: Preuve d'existence EFX pour deux agents
  • Chaudhury et al. 2020: Progrès importants pour le cas de trois agents
  • Caragiannis et al. 2016: Première introduction du concept EFX

Résumé: Cet article est un travail de haute qualité en informatique théorique, apportant des contributions importantes à la théorie du partage équitable. L'article est techniquement solide, les résultats sont complets, fournissant des perspectives profondes pour comprendre le problème des allocations EFX sur les multi-graphes, constituant un progrès important dans ce domaine.