2025-11-17T18:43:12.758371

Fair and Efficient Allocation of Indivisible Mixed Manna

Barman, HV, Sethia et al.
We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness -- in terms of a relaxation of envy-freeness -- and Pareto efficiency can always be achieved together. Specifically, our fairness guarantees are in terms of envy-freeness up to $k$ reallocations (EFR-$k$): An allocation $A$ of the indivisible items is said to be EFR-$k$ if there exists a subset $R$ of at most $k$ items such that, for each agent $i$, we can reassign items from within $R$ (in $A$) and obtain an allocation, $A^i$, which is envy-free for $i$. We establish that, when allocating mixed manna among $n$ agents with additive valuations, an EFR-$(n-1)$ and Pareto optimal (PO) allocation $A$ always exists. Further, the individual envy-free allocations $A^i$, induced by reassignments, are also PO. In addition, we prove that such fair and efficient allocations are efficiently computable when the number of agents, $n$, is fixed. We also obtain positive results focusing on EFR by itself (and without the PO desideratum). Specifically, we show that an EFR-$(n-1)$ allocation of mixed manna can be computed in polynomial time. In addition, we prove that when all the items are goods, an EFR-${\lfloor n/2 \rfloor}$ allocation exists and can be computed efficiently. Here, the $(n-1)$ bound is tight for chores and $\lfloor n/2 \rfloor$ is tight for goods. Our results advance the understanding of fair and efficient allocation of indivisible mixed manna and rely on a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division. We utilize weighted welfare maximization, with perturbed valuations, to achieve Pareto efficiency, and overall, our techniques are notably different from existing market-based approaches.
academic

Asignación Justa y Eficiente de Maná Mixto Indivisible

Información Básica

  • ID del Artículo: 2507.03946
  • Título: Fair and Efficient Allocation of Indivisible Mixed Manna
  • Autores: Siddharth Barman (Indian Institute of Science), Vishwa Prakash HV (Chennai Mathematical Institute), Aditi Sethia (Indian Institute of Science), Mashbat Suzuki (UNSW Sydney)
  • Clasificación: cs.GT (Ciencia de la Computación - Teoría de Juegos)
  • Fecha de Publicación: 15 de octubre de 2025 (segunda versión del preimpreso arXiv)
  • Enlace del Artículo: https://arxiv.org/abs/2507.03946v2

Resumen

Este artículo estudia el problema de la asignación justa de maná mixto indivisible entre agentes con valoraciones aditivas. El maná mixto se refiere a bienes cuyo valor puede ser positivo, negativo o cero. El artículo establece garantías teóricas de que la equidad (basada en relajaciones de la ausencia de envidia) y la eficiencia de Pareto pueden lograrse simultáneamente. Específicamente, la garantía de equidad se basa en el concepto de "ausencia de envidia con k redistribuciones" (EFR-k): una asignación A es EFR-k si existe un subconjunto R de a lo sumo k bienes tal que para cada agente i, puede obtenerse una asignación A^i sin envidia hacia i mediante la redistribución de bienes en R.

Antecedentes y Motivación de la Investigación

Definición del Problema

La asignación justa es un problema que surge frecuentemente en escenarios reales como división de propiedades, asignación de tareas, disputas fronterizas y distribución de deudas. Cuando los agentes participantes tienen preferencias individuales, la pregunta "¿quién obtiene qué?" posee tanto urgencia práctica como riqueza teórica.

Desafíos de la Investigación

  1. Complejidad del maná mixto: A diferencia de bienes puros o tareas domésticas, en el maná mixto el signo del valor de un bien puede variar según el agente, lo que hace la asignación más compleja.
  2. Equilibrio entre equidad y eficiencia: En el contexto de bienes indivisibles, la ausencia de envidia tradicional no puede garantizarse, requiriendo condiciones de relajación apropiadas.
  3. Limitaciones de métodos existentes:
    • Para la asignación de tareas, incluso para cuatro agentes, la existencia de asignaciones EF1 y óptimas de Pareto permanece sin resolver
    • Para maná mixto, este problema permanece abierto incluso con tres agentes
    • Los métodos basados en mercado existentes no se generalizan directamente cuando las valoraciones son negativas

Motivación de la Investigación

El artículo tiene como objetivo proporcionar garantías teóricas para la asignación justa y eficiente de maná mixto mediante la introducción del concepto EFR-k, y desarrollar algoritmos computacionales efectivos.

Contribuciones Principales

  1. Garantías de existencia teórica: Se demuestra que para la asignación de maná mixto con n agentes con valoraciones aditivas, siempre existe una asignación que es EFR-(n-1) y óptima de Pareto.
  2. Computabilidad algorítmica: Cuando el número de agentes n es fijo, puede computarse una asignación EFR-(n-1) y óptima de Pareto en tiempo polinomial.
  3. Resultados independientes de EFR:
    • La asignación de maná mixto EFR-(n-1) puede computarse en tiempo polinomial
    • Cuando todos los bienes son mercancías, existe asignación EFR-⌊n/2⌋ y puede computarse eficientemente
  4. Resultados de rigidez:
    • Para tareas, la cota (n-1) es rigida
    • Para mercancías, la cota ⌊n/2⌋ es rigida
  5. Innovación técnica: Primera aplicación del teorema de Knaster-Kuratowski-Mazurkiewicz (KKM) en asignación justa discreta.

Explicación Detallada de Métodos

Definición de la Tarea

Entrada:

  • n agentes, denotados como n = {1,...,n}
  • m bienes indivisibles, denotados como m = {1,...,m}
  • Funciones de valoración aditivas {vi}i∈n, donde vi(t) ∈ ℝ representa la valoración del agente i para el bien t

Salida: Asignación A = (A1,...,An), donde Ai ⊆ m es el conjunto de bienes asignados al agente i

Objetivo: Encontrar una asignación que satisfaga simultáneamente EFR-k y optimalidad de Pareto

Conceptos Principales

Definición de EFR-k

Una asignación A es EFR-k si y solo si existe un subconjunto R ⊆ m de tamaño a lo sumo k tal que para cada agente i, puede obtenerse una asignación A^i sin envidia hacia i mediante la redistribución de bienes en R.

Componentes Técnicos Clave

  1. Perturbación de valoraciones: Para obtener condiciones no degeneradas, se añaden perturbaciones aditivas suficientemente pequeñas a las valoraciones dadas:
    v̄i(t) = vi(t) - εi,t

    donde εi,t se extrae uniformemente de (0,ε).
  2. Desplazamiento de pesos: Para cada vector de peso w ∈ Δn-1, se desplaza cada componente por parámetro η > 0:
    SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
  3. Cobertura KKM: Para cada agente i, se define el conjunto
    Ci := {w ∈ Δn-1 : existe asignación Xi ∈ Oη(w) tal que i no tiene envidia bajo Xi}

Marco Algorítmico Principal

Esquema de Prueba del Teorema 3.1

  1. Construcción de valoraciones perturbadas: Asegurar propiedades no degeneradas
  2. Definición de cobertura KKM: Construir familia de conjuntos cerrados {Ci} satisfaciendo condiciones KKM
  3. Aplicación del teorema KKM: Obtener intersección w* ∈ ∩i Ci
  4. Argumento de conteo: Demostrar que el tamaño del conjunto de redistribución R es a lo sumo n-1

Algoritmo 1: Selección de Secuencia Consciente de Conflictos para Mercancías

Para el caso de mercancías puras, se diseña un algoritmo basado en turnos:

  • Fase de resolución de conflictos: Identificar bienes preferidos por múltiples agentes, añadirlos al conjunto de redistribución R
  • Fase de selección: Agentes activos seleccionan el bien más preferido en orden lexicográfico

Puntos de Innovación Técnica

  1. Nueva aplicación del teorema KKM: Primera aplicación del teorema clásico de KKM a problemas de asignación justa discreta, proporcionando una ruta técnica completamente diferente de los métodos basados en mercado existentes.
  2. Técnica de perturbación: Mediante perturbación de valoraciones cuidadosamente diseñada se asegura no degeneración, haciendo que el problema de maximización de bienestar social ponderado tenga buenas propiedades.
  3. Argumento de conteo: Utilizar propiedades acíclicas de grafos bipartitos para demostrar límites del tamaño del conjunto de redistribución.

Configuración Experimental

Marco de Análisis Teórico

Siendo este un artículo teórico, los resultados se verifican principalmente mediante pruebas matemáticas en lugar de experimentos empíricos. El artículo adopta el siguiente marco de análisis:

  1. Pruebas de existencia: Usar el teorema KKM para demostrar la existencia de asignaciones EFR-(n-1) y PO
  2. Análisis de rigidez: Construir contraejemplos para demostrar la rigidez de los límites
  3. Complejidad algorítmica: Analizar la complejidad temporal de los algoritmos

Análisis de Complejidad

  • Número fijo de agentes: Las asignaciones EFR-(n-1) y PO pueden computarse en tiempo m^poly(n)
  • Caso general: Las asignaciones EFR-(n-1) pueden computarse en tiempo polinomial
  • Caso de mercancías: Las asignaciones EFR-⌊n/2⌋ pueden computarse en tiempo polinomial

Resultados Experimentales

Resultados Teóricos Principales

Teorema 3.1 (Resultado Principal de Existencia)

Toda instancia de asignación justa con maná mixto indivisible y valoraciones aditivas admite una asignación que es EFR-(n-1) y óptima de Pareto.

Teorema 4.1 (Resultado de Computabilidad)

Para instancias de asignación de maná mixto con número fijo de agentes, puede computarse una asignación EFR-(n-1) y óptima de Pareto en tiempo polinomial.

Teorema 5.1 (Resultado Independiente de EFR)

Para instancias de asignación justa con maná mixto y valoraciones aditivas, siempre existe una asignación que es tanto EFR-(n-1) como EF1, y puede computarse en tiempo polinomial.

Teorema 5.4 (Límite Mejorado para Mercancías)

Para instancias de asignación justa de mercancías puras, el Algoritmo 1 computa una asignación EFR-⌊n/2⌋ en tiempo polinomial.

Resultados de Rigidez

Teorema 5.2 (Rigidez para Tareas)

Existe una instancia de asignación de tareas que no admite asignación EFR-(n-2), demostrando que el límite (n-1) es rigido.

Teorema 5.5 (Rigidez para Mercancías)

Existe una instancia de asignación de mercancías que no admite asignación EFR-(⌊n/2⌋-1), demostrando que el límite ⌊n/2⌋ es rigido.

Resultados de Complejidad Computacional

Teorema A.1 (Complejidad del Problema de Decisión)

Dado una asignación A y un entero positivo k < n-2, determinar si A es EFR-k es NP-completo.

Trabajo Relacionado

Teoría Clásica de Asignación Justa

  • Caso divisible: Los resultados clásicos de Varian y Weller demuestran que la ausencia de envidia y PO pueden lograrse simultáneamente
  • Bienes indivisibles: La realización simultánea de EF1 y PO tiene teoría madura (maximización del bienestar social de Nash)

Desafíos en Tareas y Maná Mixto

  • Asignación de tareas: Incluso la existencia de EF1+PO para cuatro agentes permanece sin resolver
  • Maná mixto: La existencia de EF1+PO para tres agentes sigue siendo un problema abierto
  • Diferencia metodológica: No existe función análoga al bienestar social de Nash que garantice EF1 para tareas

Conceptos de Relajación Relacionados

  • EF1: Eliminar envidia mediante la remoción de un bien
  • EFX: Eliminar envidia mediante la remoción de un bien arbitrario
  • Asignación fraccionada: Ausencia de envidia con asignación fraccionada de a lo sumo (n-1) bienes

Conclusiones y Discusión

Conclusiones Principales

  1. Avance teórico: Primera provisión de garantías simultáneas de equidad y eficiencia para la configuración general de maná mixto
  2. Innovación técnica: La nueva aplicación del teorema KKM en asignación justa discreta abre nuevas direcciones de investigación
  3. Valor práctico: Los resultados algorítmicos proporcionan base computacional para aplicaciones prácticas

Limitaciones

  1. Límites: El límite EFR-(n-1) es relativamente grande, requiriendo redistribución de aproximadamente 2 bienes por agente en promedio
  2. Suposición de agentes fijos: El algoritmo de tiempo polinomial requiere que el número de agentes sea fijo
  3. Restricción de valoraciones aditivas: Los resultados aplican solo a funciones de valoración aditivas

Direcciones Futuras

  1. Mejora de límites: Buscar conjuntos de redistribución R más pequeños
  2. Extensión de tipos de valoración: Considerar funciones de valoración no aditivas
  3. Aplicaciones prácticas: Aplicar resultados teóricos a escenarios de asignación concretos

Evaluación Profunda

Fortalezas

  1. Contribución teórica significativa: Resuelve el problema fundamental de asignación justa y eficiente de maná mixto
  2. Técnicas novedosas: La aplicación del teorema KKM demuestra profunda perspicacia matemática
  3. Resultados comprehensivos: Incluye existencia y algoritmos, cotas superiores e inferiores
  4. Pruebas rigurosas: Derivaciones matemáticas completas y manejo cuidadoso de detalles técnicos

Insuficiencias

  1. Aplicabilidad práctica limitada: El límite EFR-(n-1) puede ser excesivamente grande en aplicaciones reales
  2. Falta de evaluación empírica: Como artículo teórico, carece de evaluación de desempeño en datos reales
  3. Eficiencia algorítmica: La complejidad m^poly(n) para número fijo de agentes puede ser alta en práctica

Impacto

  1. Impacto académico: Contribución importante a la teoría de asignación justa, se espera sea ampliamente citado
  2. Valor metodológico: La aplicación del teorema KKM puede inspirar investigaciones relacionadas adicionales
  3. Perspectiva práctica: Proporciona base teórica para el diseño de sistemas de asignación reales

Escenarios Aplicables

  1. División de herencias: Escenarios complejos de división con activos y deudas
  2. Asignación de tareas: Distribución de tareas con componentes atractivas e inatractivas
  3. Gestión de recursos: Problemas de asignación de recursos considerando beneficios y costos simultáneamente

Referencias Bibliográficas

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

  • Budish (2011): Introducción del concepto EF1
  • Caragiannis et al. (2019): Relación entre bienestar social de Nash y EF1+PO
  • Aziz et al. (2022): Existencia de EF1 para maná mixto
  • Sandomirskiy & Segal-Halevi (2022): Resultados relacionados con asignación fraccionada

Evaluación General: Este es un artículo teórico de alta calidad que, mediante la introducción del concepto EFR y la aplicación del teorema KKM, proporciona garantías teóricas importantes para la asignación justa y eficiente de maná mixto. Aunque presenta ciertas limitaciones en aplicabilidad práctica, su contribución teórica e innovación técnica lo convierten en un avance importante en el campo de asignación justa.