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

Asignaciones EFX y Orientaciones en Multigrafos Bipartitos: Una Imagen Completa

Información Básica

  • ID del Artículo: 2410.17002
  • Título: EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
  • Autores: Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, Nidhi Rathi
  • Clasificación: cs.GT (Teoría de Juegos), cs.DS (Estructuras de Datos y Algoritmos)
  • Fecha de Publicación: Octubre de 2024 (preimpresión arXiv)
  • Enlace del Artículo: https://arxiv.org/abs/2410.17002

Resumen

Este artículo estudia el problema de la asignación justa de bienes indivisibles bajo funciones de valoración representadas por multigrafos. En este modelo, los agentes corresponden a vértices del grafo, los bienes corresponden a aristas, y cada agente solo tiene valoración positiva para las aristas incidentes. El objetivo es encontrar una asignación justa que satisfaga la condición EFX (envy-free up to any item). El artículo se basa en el trabajo de Christodoulou et al. (2023), quienes probaron la existencia de asignaciones EFX para funciones de valoración monótonas en grafos simples. Este trabajo extiende la investigación a varias categorías de multigrafos, con contribuciones principales que incluyen: (1) prueba de existencia de asignaciones EFX para valoraciones monótonas en multigrafos bipartitos y valoraciones MMS-feasible en ciclos múltiples; (2) provisión de algoritmos de tiempo pseudopolinomial correspondientes; (3) caracterización completa del problema de orientación EFX; (4) prueba de completitud NP para determinar la existencia de orientaciones EFX.

Antecedentes y Motivación de la Investigación

Contexto del Problema

La teoría de división justa es una importante dirección de investigación en la intersección de economía, ciencias sociales, matemáticas e informática, con el objetivo de distribuir equitativamente un conjunto de recursos entre múltiples participantes. En el caso de bienes indivisibles, la asignación clásica sin envidia puede no existir; por lo tanto, los investigadores han propuesto varias versiones relajadas, siendo EFX considerada como el concepto de equidad más cercano a la ausencia de envidia en configuraciones discretas.

Motivación de la Investigación

  1. Desafíos Teóricos: Para cuatro o más agentes, la existencia de asignaciones EFX sigue siendo un importante problema abierto
  2. Extensión del Modelo: Christodoulou et al. probaron la existencia de asignaciones EFX en grafos simples; la pregunta natural es cómo se comporta en multigrafos
  3. Aplicaciones Prácticas: El modelo es aplicable en contextos geográficos donde los agentes solo se preocupan por recursos cercanos, como corredores comerciales, gasoductos, etc.

Limitaciones de Métodos Existentes

  • Los resultados existentes se limitan principalmente a grafos simples (dos agentes cualesquiera comparten como máximo un bien)
  • Falta investigación sistemática para multigrafos (donde dos agentes pueden compartir múltiples bienes)
  • La existencia y complejidad computacional de orientaciones EFX aún no han sido completamente caracterizadas

Contribuciones Principales

  1. Teoremas de Existencia: Se prueba que las asignaciones EFX siempre existen para valoraciones monótonas en multigrafos bipartitos y para valoraciones MMS-feasible en ciclos múltiples
  2. Diseño de Algoritmos: Se proporcionan algoritmos de tiempo pseudopolinomial para calcular asignaciones EFX; para funciones de valoración reducibles, se puede calcular en tiempo polinomial
  3. Caracterización Completa: Se proporciona una caracterización completa de la existencia de orientaciones EFX en multigrafos bipartitos basada en dos parámetros clave (q y d(G))
  4. Análisis de Complejidad: Se prueba la completitud NP del problema de determinar la existencia de orientaciones EFX, incluso para un número constante de agentes
  5. Resultados de Aproximación: Para casos donde no existen orientaciones EFX, se prueba la existencia de orientaciones donde al menos ⌈n/2⌉ agentes satisfacen EFX y los agentes restantes satisfacen 1/2-EFX

Explicación Detallada de Métodos

Definición de la Tarea

Entrada:

  • Multigrafo G = (V,E), donde V = n representa n agentes y E representa m bienes
  • Funciones de valoración {vi}i∈n, satisfaciendo vi(S) = vi(S ∩ E(i)), donde E(i) es el conjunto de aristas incidentes del agente i

Salida:

  • Asignación completa X = (X1,...,Xn), satisfaciendo la condición EFX
  • U orientación EFX (cada bien se asigna a uno de sus vértices extremos)

Restricciones:

  • EFX: Para cualesquiera agentes i,j y bien g ∈ Xj, se tiene vi(Xi) ≥ vi(Xj \ {g})
  • Tipos de funciones de valoración: monótonas, reducibles, MMS-feasible, etc.

Arquitectura del Modelo

Conceptos Principales

  1. Configuración T-cut: Para agentes adyacentes i ∈ S y j ∈ T, el agente j particiona E(i,j) en dos paquetes C1 y C2, donde ambos son EFX-feasible para j
  2. Conjunto Disponible: Se define Ai,j(X) como el conjunto de aristas disponibles para el agente i desde E(i,j) bajo la asignación actual X
  3. Conjunto Seguro: Para un agente envidiado i, se define Si(X) como su conjunto seguro

Propiedades Clave

El algoritmo mantiene seis propiedades clave:

  1. X es una orientación EFX
  2. Los bienes en E(i,j) se asignan según la configuración j-cut
  3. Cada agente recibe su paquete disponible preferido
  4. El conjunto disponible de agentes no envidiados está vacío
  5. La valoración de agentes no envidiados para aristas incidentes no asignadas no excede su paquete actual
  6. Los envidiadores de agentes envidiados están en su conjunto seguro

Puntos de Innovación Técnica

1. Diseño del Mecanismo de Configuración

Se introduce innovadoramente el concepto de configuración T-cut, combinando ideas del protocolo de división de dos personas, proporcionando un método sistemático para manejar múltiples aristas en multigrafos.

2. Marco de Algoritmo por Fases

Se diseña un algoritmo de cinco fases que satisface sucesivamente las seis propiedades clave:

  • Algoritmo 1: Orientación codiciosa satisfaciendo propiedades (1)-(3)
  • Algoritmo 2: Procesamiento de agentes no envidiados satisfaciendo propiedad (4)
  • Algoritmo 3: Aumento de valoración de agentes no envidiados satisfaciendo propiedad (5)
  • Algoritmo 4: Construcción de conjunto seguro satisfaciendo propiedad (6)
  • Algoritmo 5: Asignación final de bienes restantes

3. Utilización de Estructura de Grafo Bipartito

Se aprovecha completamente la estructura característica de grafos bipartitos, particularmente que vértices envidiados solo pueden aparecer en una partición, simplificando significativamente el análisis y diseño de algoritmos.

Configuración Experimental

Marco de Análisis Teórico

Este trabajo es principalmente teórico, verificando resultados mediante pruebas matemáticas en lugar de experimentación. El marco de análisis incluye:

  1. Pruebas de Existencia: Pruebas constructivas que demuestran cómo encontrar asignaciones que satisfacen las condiciones
  2. Análisis de Complejidad de Algoritmos: Análisis de la complejidad temporal de cada paso del algoritmo
  3. Construcción de Contraejemplos: Mediante instancias concretas se prueba que en ciertos casos las orientaciones EFX no existen

Métricas de Evaluación

  • Satisfacción de EFX: Si todos los agentes satisfacen la condición EFX
  • Complejidad Temporal: Tiempo de ejecución del algoritmo (polinomial vs. pseudopolinomial)
  • Razón de Aproximación: Para casos donde no existen soluciones exactas, la calidad de la solución aproximada

Resultados Experimentales

Resultados Principales

1. Teoremas de Existencia

Teorema 4.11: Para valoraciones monótonas en multigrafos bipartitos, las asignaciones EFX siempre existen y pueden calcularse en tiempo pseudopolinomial; para valoraciones reducibles pueden calcularse en tiempo polinomial.

Teorema 5.1: Para valoraciones MMS-feasible en ciclos múltiples, las asignaciones EFX siempre existen y pueden calcularse en tiempo pseudopolinomial.

2. Caracterización Completa de Orientaciones EFX

Caracterización completa basada en parámetros q (número máximo de aristas entre dos agentes cualesquiera) y d(G) (diámetro del grafo):

Condiciones de ParámetrosExistencia de Orientación EFX
Sin ciclos, q=2, d(G)≤4Existe
Sin ciclos, q=2, d(G)>4Posiblemente no existe
Sin ciclos, q>2, d(G)≤2Existe
Sin ciclos, q>2, d(G)>2Posiblemente no existe
Con ciclos, q≥2, d(G)≥2Posiblemente no existe

3. Resultados de Complejidad

Teorema 3.6: Determinar si existe una orientación EFX en un multigrafo bipartito es NP-completo, incluso para un número constante de agentes.

4. Resultados de Aproximación

Teorema 4.12: Para valoraciones aditivas en multigrafos bipartitos, siempre existe una orientación tal que al menos ⌈n/2⌉ agentes satisfacen EFX y los agentes restantes satisfacen 1/2-EFX.

Análisis de Casos

El artículo demuestra el proceso de ejecución del algoritmo mediante múltiples instancias concretas:

  • Las figuras 7-10 muestran la ejecución paso a paso del algoritmo en multigrafos bipartitos específicos
  • Las construcciones de contraejemplos (como figuras 1-5) prueban la no existencia de orientaciones EFX en ciertos casos

Hallazgos Teóricos

  1. Papel Crítico de la Estructura Bipartita: La estructura de grafo bipartito asegura que vértices envidiados solo aparezcan en una partición, siendo esto clave para el éxito del algoritmo
  2. Efectividad del Mecanismo de Configuración: La configuración T-cut proporciona un marco unificado para manejar múltiples aristas
  3. Complejidad Parametrizada: Los dos parámetros q y d(G) caracterizan completamente la existencia de orientaciones EFX

Trabajo Relacionado

Estado Actual de la Investigación EFX

  • Dos Agentes: Plaut y Roughgarden probaron la existencia para valoraciones monótonas
  • Tres Agentes: Una serie de trabajos probaron la existencia para varios tipos de valoración
  • Valoraciones Especiales: Existencia en casos especiales como valoraciones idénticas, valoraciones binarias, etc.

División Justa en Grafos

  • Christodoulou et al. propusieron por primera vez el modelo de asignación EFX en grafos simples
  • Trabajos posteriores investigaron orientaciones EF1, bienes mixtos y otras extensiones
  • Este trabajo es el primero en estudiar sistemáticamente el caso de multigrafos

Trabajos Paralelos

Dos trabajos independientes y paralelos también investigaron EFX en multigrafos:

  • Sgouritsa y Sotiriou (2025): Probaron la existencia de EFX para valoraciones monótonas en multigrafos bipartitos
  • Bhaskar y Pandit (2024): Investigaron la existencia de EFX en categorías específicas de multigrafos

Conclusiones y Discusión

Conclusiones Principales

  1. Contribución Teórica: Primera caracterización completa de la existencia de asignaciones EFX en multigrafos bipartitos, extendiendo el marco teórico existente
  2. Contribución Algorítmica: Provisión de algoritmos de tiempo pseudopolinomial prácticos, alcanzando tiempo polinomial para tipos específicos de valoración
  3. Caracterización de Complejidad: Análisis completo de la complejidad computacional del problema de orientación EFX

Limitaciones

  1. Restricción de Clases de Grafos: Los resultados se concentran principalmente en multigrafos bipartitos; el caso de multigrafos generales sigue siendo un problema abierto
  2. Restricción de Funciones de Valoración: Aunque cubre múltiples tipos de valoración, aún no alcanza el caso más general
  3. Eficiencia del Algoritmo: Para valoraciones monótonas generales solo se puede alcanzar complejidad de tiempo pseudopolinomial

Direcciones Futuras

  1. Multigrafos Generales: Los autores conjeturan que las asignaciones EFX existen en cualquier multigrafo, pero la prueba requiere nuevas técnicas
  2. Optimización de Algoritmos: Búsqueda de algoritmos más eficientes, particularmente algoritmos de tiempo polinomial
  3. Bienestar Social: Investigación de la relación de compensación entre asignaciones EFX y eficiencia

Evaluación Profunda

Fortalezas

  1. Profundidad Teórica: Proporciona pruebas de existencia completas y análisis de complejidad; la contribución teórica es significativa
  2. Innovación Técnica: El mecanismo de configuración T-cut y el marco de algoritmo por fases poseen innovación
  3. Completitud de Resultados: Proporciona caracterización parametrizada completa de la existencia de orientaciones EFX
  4. Claridad de Escritura: La estructura del artículo es clara, las pruebas son detalladas y fáciles de entender y verificar

Deficiencias

  1. Falta de Verificación Experimental: Como trabajo puramente teórico, carece de evaluación del desempeño del algoritmo en datos reales
  2. Escenarios de Aplicación Limitados: El modelo de multigrafo tiene escenarios de aplicación práctica relativamente limitados
  3. Limitaciones Técnicas: La extensión a multigrafos generales aún enfrenta desafíos técnicos

Impacto

  1. Valor Académico: Proporciona progreso teórico importante para la teoría de división justa, impulsando el desarrollo de la investigación EFX
  2. Contribución Metodológica: El marco técnico propuesto puede inspirar soluciones para otros problemas de división justa en grafos
  3. Problemas Abiertos: Proporciona acumulación técnica importante para el problema de existencia de EFX en multigrafos generales

Escenarios Aplicables

  1. Investigación Teórica: Proporciona referencia importante para investigadores en teoría de división justa
  2. Diseño de Algoritmos: El mecanismo de configuración puede utilizarse para diseñar otros algoritmos de división justa
  3. Teoría de Complejidad: Los resultados de completitud NP tienen valor para la investigación en complejidad computacional

Referencias

El artículo cita literatura importante en el campo de división justa, incluyendo:

  • Christodoulou et al. 2023: Trabajo pionero sobre asignaciones EFX en grafos simples
  • Plaut y Roughgarden 2020: Prueba de existencia de EFX para dos agentes
  • Chaudhury et al. 2020: Progreso importante en el caso de tres agentes
  • Caragiannis et al. 2016: Primera introducción del concepto EFX

Resumen: Este es un artículo de alta calidad en informática teórica que realiza contribuciones importantes en la teoría de división justa. El artículo es técnicamente sólido, los resultados son completos, proporciona perspectivas profundas para entender el problema de asignaciones EFX en multigrafos, y representa un progreso importante en este campo.