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

Allocazione Equa ed Efficiente di Manna Mista Indivisibile

Informazioni Fondamentali

  • ID Articolo: 2507.03946
  • Titolo: Fair and Efficient Allocation of Indivisible Mixed Manna
  • Autori: Siddharth Barman (Indian Institute of Science), Vishwa Prakash HV (Chennai Mathematical Institute), Aditi Sethia (Indian Institute of Science), Mashbat Suzuki (UNSW Sydney)
  • Classificazione: cs.GT (Informatica - Teoria dei Giochi)
  • Data di Pubblicazione: 15 ottobre 2025 (Preprint arXiv versione 2)
  • Link Articolo: https://arxiv.org/abs/2507.03946v2

Riassunto

Questo articolo affronta il problema dell'allocazione equa di manna mista indivisibile tra agenti con valutazioni additive. La manna mista si riferisce a beni il cui valore può essere positivo, negativo o nullo. L'articolo stabilisce garanzie teoriche secondo cui l'equità (basata su rilassamenti dell'assenza di invidia) e l'efficienza paretiana possono essere simultaneamente realizzate. Nello specifico, la garanzia di equità si basa sul concetto di "assenza di invidia con k riallocazioni" (EFR-k): un'allocazione A è EFR-k se esiste un sottoinsieme R di al massimo k beni tale che per ogni agente i, è possibile ottenere un'allocazione A^i priva di invidia verso i attraverso la riallocazione dei beni in R.

Contesto di Ricerca e Motivazione

Definizione del Problema

L'allocazione equa è un problema che ricorre frequentemente in scenari reali come la divisione di proprietà, l'assegnazione di compiti, le controversie di confine e la distribuzione dei debiti. Quando gli agenti partecipanti hanno preferenze individuali, la questione "chi ottiene cosa" presenta sia urgenza pratica che ricchezza teorica.

Sfide di Ricerca

  1. Complessità della Manna Mista: A differenza di beni puri o faccende domestiche, il segno del valore dei beni nella manna mista può variare tra gli agenti, rendendo l'allocazione più complessa.
  2. Compromesso tra Equità ed Efficienza: Nel contesto di beni indivisibili, l'assenza di invidia tradizionale non può essere garantita, rendendo necessario cercare condizioni di rilassamento appropriate.
  3. Limitazioni degli Approcci Esistenti:
    • Per l'allocazione di faccende, l'esistenza di allocazioni EF1 e pareto-ottimali rimane irrisolta anche nel caso di quattro agenti
    • Per la manna mista, questo problema rimane aperto anche nel caso di tre agenti
    • Gli approcci basati su mercato non si generalizzano direttamente quando le valutazioni sono negative

Motivazione della Ricerca

L'articolo mira a fornire garanzie teoriche per l'allocazione equa ed efficiente di manna mista introducendo il concetto di EFR-k e sviluppando algoritmi computazionali efficaci.

Contributi Principali

  1. Garanzie di Esistenza Teorica: Dimostra che per l'allocazione di manna mista tra n agenti con valutazioni additive, esiste sempre un'allocazione EFR-(n-1) e pareto-ottimale.
  2. Computabilità Algoritmica: Quando il numero di agenti n è fisso, è possibile calcolare un'allocazione EFR-(n-1) e pareto-ottimale in tempo polinomiale.
  3. Risultati EFR Indipendenti:
    • L'allocazione di manna mista EFR-(n-1) può essere calcolata in tempo polinomiale
    • Quando tutti i beni sono merci, esiste un'allocazione EFR-⌊n/2⌋ e può essere calcolata efficientemente
  4. Risultati di Stretta Limitazione:
    • Per le faccende, il limite (n-1) è stretto
    • Per le merci, il limite ⌊n/2⌋ è stretto
  5. Innovazione Tecnica: Prima applicazione del teorema di Knaster-Kuratowski-Mazurkiewicz (KKM) nell'allocazione equa discreta.

Spiegazione Dettagliata dei Metodi

Definizione del Compito

Input:

  • n agenti, denotati come n = {1,...,n}
  • m beni indivisibili, denotati come m = {1,...,m}
  • Funzioni di valutazione additive {vi}i∈n, dove vi(t) ∈ ℝ rappresenta la valutazione dell'agente i per il bene t

Output: Allocazione A = (A1,...,An), dove Ai ⊆ m è l'insieme di beni allocati all'agente i

Obiettivo: Trovare un'allocazione che soddisfi simultaneamente EFR-k e pareto-ottimalità

Concetti Fondamentali

Definizione di EFR-k

Un'allocazione A è EFR-k se e solo se esiste un sottoinsieme R ⊆ m di dimensione al massimo k tale che per ogni agente i, è possibile ottenere un'allocazione A^i priva di invidia verso i attraverso la riallocazione dei beni in R.

Componenti Tecniche Chiave

  1. Perturbazione di Valutazione: Per ottenere condizioni non degeneri, si aggiunge una perturbazione additiva sufficientemente piccola alle valutazioni date:
    v̄i(t) = vi(t) - εi,t

    dove εi,t è estratto uniformemente da (0,ε).
  2. Spostamento di Peso: Per ogni vettore di peso w ∈ Δn-1, si sposta ogni componente di un parametro η > 0:
    SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
  3. Copertura KKM: Per ogni agente i, si definisce l'insieme
    Ci := {w ∈ Δn-1 : esiste un'allocazione Xi ∈ Oη(w) tale che i è privo di invidia sotto Xi}

Quadro Algoritmico Principale

Strategia di Prova del Teorema 3.1

  1. Costruzione di Valutazioni Perturbate: Assicura proprietà di non degenerazione
  2. Definizione di Copertura KKM: Costruisce una famiglia di insiemi chiusi {Ci} che soddisfa le condizioni KKM
  3. Applicazione del Teorema KKM: Ottiene l'intersezione w* ∈ ∩i Ci
  4. Argomento di Conteggio: Dimostra che la dimensione dell'insieme di riallocazione R è al massimo n-1

Algoritmo 1: Sequenza di Selezione Consapevole dei Conflitti per Merci

Per il caso di pure merci, è stato progettato un algoritmo basato su turnazione:

  • Fase di Risoluzione dei Conflitti: Identifica i beni più preferiti dagli stessi agenti multipli e li aggiunge all'insieme di riallocazione R
  • Fase di Selezione: Gli agenti attivi selezionano il bene più preferito in ordine lessicografico

Punti di Innovazione Tecnica

  1. Nuova Applicazione del Teorema KKM: Prima applicazione del classico teorema KKM ai problemi di allocazione equa discreta, fornendo un percorso tecnico completamente diverso dai metodi basati su mercato esistenti.
  2. Tecnica di Perturbazione: Attraverso una perturbazione di valutazione accuratamente progettata, assicura la non degenerazione, rendendo il problema di massimizzazione del benessere sociale ponderato ben comportato.
  3. Argomento di Conteggio: Utilizza l'aciclicità di grafi bipartiti per provare i limiti sulla dimensione dell'insieme di riallocazione.

Configurazione Sperimentale

Quadro di Analisi Teorica

Poiché si tratta di un articolo teorico, i risultati vengono verificati principalmente attraverso prove matematiche piuttosto che esperimenti empirici. L'articolo adotta il seguente quadro di analisi:

  1. Prova di Esistenza: Utilizza il teorema KKM per provare l'esistenza di allocazioni EFR-(n-1) e PO
  2. Analisi di Stretta Limitazione: Costruisce controesempi per provare la stretta limitazione dei limiti
  3. Complessità Algoritmica: Analizza la complessità temporale degli algoritmi

Analisi di Complessità

  • Numero Fisso di Agenti: L'allocazione EFR-(n-1) e PO può essere calcolata in tempo m^poly(n)
  • Caso Generale: L'allocazione EFR-(n-1) può essere calcolata in tempo polinomiale
  • Caso di Merci: L'allocazione EFR-⌊n/2⌋ può essere calcolata in tempo polinomiale

Risultati Sperimentali

Risultati Teorici Principali

Teorema 3.1 (Risultato di Esistenza Principale)

Ogni istanza di allocazione equa di manna mista indivisibile con valutazioni additive ammette un'allocazione EFR-(n-1) e pareto-ottimale.

Teorema 4.1 (Risultato di Computabilità)

Per istanze di allocazione di manna mista con un numero fisso di agenti, è possibile calcolare un'allocazione EFR-(n-1) e pareto-ottimale in tempo polinomiale.

Teorema 5.1 (Risultato EFR Indipendente)

Per ogni istanza di allocazione equa di manna mista con valutazioni additive, esiste sempre un'allocazione che è sia EFR-(n-1) che EF1, e può essere calcolata in tempo polinomiale.

Teorema 5.4 (Limite Migliorato per Merci)

Per istanze di allocazione equa di pure merci, l'Algoritmo 1 calcola un'allocazione EFR-⌊n/2⌋ in tempo polinomiale.

Risultati di Stretta Limitazione

Teorema 5.2 (Stretta Limitazione per Faccende)

Esiste un'istanza di allocazione di faccende che non ammette un'allocazione EFR-(n-2), provando che il limite (n-1) è stretto.

Teorema 5.5 (Stretta Limitazione per Merci)

Esiste un'istanza di allocazione di merci che non ammette un'allocazione EFR-(⌊n/2⌋-1), provando che il limite ⌊n/2⌋ è stretto.

Risultati di Complessità Computazionale

Teorema A.1 (Complessità del Problema di Decisione)

Dato un'allocazione A e un intero positivo k < n-2, determinare se A è EFR-k è NP-completo.

Lavori Correlati

Teoria Classica dell'Allocazione Equa

  • Caso Divisibile: I risultati classici di Varian e Weller mostrano che l'assenza di invidia e PO possono essere simultaneamente realizzate
  • Beni Indivisibili: L'implementazione simultanea di EF1 e PO ha una teoria consolidata (massimizzazione del benessere sociale di Nash)

Sfide nelle Faccende e nella Manna Mista

  • Allocazione di Faccende: L'esistenza di EF1+PO rimane irrisolta anche per quattro agenti
  • Manna Mista: L'esistenza di EF1+PO per tre agenti rimane un problema aperto
  • Differenza Metodologica: Non esiste una funzione analoga al benessere sociale di Nash che garantisca EF1 per le faccende

Concetti di Rilassamento Correlati

  • EF1: Eliminazione dell'invidia attraverso la rimozione di un bene
  • EFX: Eliminazione dell'invidia attraverso la rimozione di un bene arbitrario
  • Allocazione Frazionaria: Assenza di invidia con allocazione frazionaria di al massimo (n-1) beni

Conclusioni e Discussione

Conclusioni Principali

  1. Scoperta Teorica: Prima fornitura di garanzie simultanee di equità ed efficienza per il contesto generale di manna mista
  2. Innovazione Tecnica: La nuova applicazione del teorema KKM nell'allocazione equa discreta apre nuove direzioni di ricerca
  3. Valore Pratico: I risultati algoritmici forniscono una base computazionale per applicazioni pratiche

Limitazioni

  1. Limiti: Il limite EFR-(n-1) è relativamente grande, richiedendo in media circa 2 beni per agente da riallocare
  2. Assunzione di Agenti Fissi: L'algoritmo in tempo polinomiale richiede che il numero di agenti sia fisso
  3. Restrizione di Valutazione Additiva: I risultati si applicano solo a funzioni di valutazione additive

Direzioni Future

  1. Miglioramento dei Limiti: Ricerca di insiemi di riallocazione R più piccoli
  2. Estensione dei Tipi di Valutazione: Considerazione di funzioni di valutazione non additive
  3. Applicazioni Pratiche: Applicazione dei risultati teorici a scenari di allocazione concreti

Valutazione Approfondita

Punti di Forza

  1. Contributo Teorico Significativo: Risolve il problema fondamentale dell'allocazione equa ed efficiente di manna mista
  2. Tecniche Innovative: L'applicazione del teorema KKM dimostra intuizioni matematiche profonde
  3. Risultati Completi: Presenta sia risultati di esistenza che algoritmici, sia limiti superiori che inferiori
  4. Prove Rigorose: Le derivazioni matematiche sono complete e i dettagli tecnici sono gestiti adeguatamente

Carenze

  1. Praticità Limitata: Il limite EFR-(n-1) potrebbe essere eccessivamente grande per applicazioni pratiche
  2. Mancanza di Valutazione Empirica: Come articolo teorico, manca la valutazione delle prestazioni su dati reali
  3. Efficienza Algoritmica: La complessità m^poly(n) con numero fisso di agenti potrebbe essere elevata in pratica

Impatto

  1. Impatto Accademico: Fornisce un contributo importante alla teoria dell'allocazione equa, con previsione di ampia citazione
  2. Valore Metodologico: L'applicazione del teorema KKM potrebbe ispirare ulteriori ricerche correlate
  3. Prospettive Pratiche: Fornisce fondamenti teorici per la progettazione di sistemi di allocazione reali

Scenari Applicabili

  1. Divisione di Eredità: Scenari complessi di divisione che includono beni e debiti
  2. Assegnazione di Compiti: Allocazione di compiti che includono sia attività attraenti che non attraenti
  3. Gestione delle Risorse: Problemi di allocazione di risorse che richiedono la considerazione simultanea di ricavi e costi

Bibliografia

L'articolo cita importanti letterature nel campo dell'allocazione equa, incluse:

  • Budish (2011): Introduzione del concetto di EF1
  • Caragiannis et al. (2019): Relazione tra benessere sociale di Nash e EF1+PO
  • Aziz et al. (2022): Esistenza di EF1 per manna mista
  • Sandomirskiy & Segal-Halevi (2022): Risultati correlati su allocazione frazionaria

Valutazione Complessiva: Questo è un articolo teorico di alta qualità che, attraverso l'introduzione del concetto di EFR e l'applicazione del teorema KKM, fornisce importanti garanzie teoriche per l'allocazione equa ed efficiente di manna mista. Sebbene presenti alcune limitazioni in termini di praticità, il suo contributo teorico e l'innovazione tecnica lo rendono un importante progresso nel campo dell'allocazione equa.