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

Allocazioni EFX e Orientamenti su Multi-grafi Bipartiti: Un Quadro Completo

Informazioni Fondamentali

  • ID Articolo: 2410.17002
  • Titolo: EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
  • Autori: Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, Nidhi Rathi
  • Classificazione: cs.GT (Teoria dei Giochi), cs.DS (Strutture Dati e Algoritmi)
  • Data di Pubblicazione: Ottobre 2024 (preprint arXiv)
  • Link Articolo: https://arxiv.org/abs/2410.17002

Riassunto

Questo articolo affronta il problema dell'allocazione equa di beni indivisibili secondo funzioni di valutazione rappresentate da multi-grafi. In questo modello, gli agenti corrispondono ai vertici del grafo, i beni corrispondono agli archi, e ogni agente ha valutazione positiva solo per gli archi ad esso incidenti. L'obiettivo è trovare un'allocazione equa che soddisfi la condizione EFX (envy-free up to any item). L'articolo si basa sul lavoro di Christodoulou et al. (2023), che ha provato l'esistenza di allocazioni EFX per funzioni di valutazione monotone su grafi semplici. Questo lavoro estende la ricerca a varie classi di multi-grafi, con i seguenti contributi principali: (1) prova dell'esistenza di allocazioni EFX su multi-grafi bipartiti con valutazioni monotone e su multi-cicli con valutazioni MMS-feasible; (2) fornitura di algoritmi pseudopolinomiali; (3) caratterizzazione completa del problema di orientamento EFX; (4) prova della NP-completezza del problema di decidere l'esistenza di orientamenti EFX.

Contesto di Ricerca e Motivazione

Contesto del Problema

La teoria della divisione equa è un'importante area di ricerca interdisciplinare tra economia, scienze sociali, matematica e informatica, finalizzata a distribuire equamente un insieme di risorse tra più partecipanti. Nel caso di beni indivisibili, l'allocazione classica senza invidia potrebbe non esistere; pertanto, i ricercatori hanno proposto varie versioni rilassate, tra cui EFX è considerato il concetto di equità più vicino all'assenza di invidia nel contesto discreto.

Motivazione della Ricerca

  1. Sfide Teoriche: Per quattro o più agenti, l'esistenza di allocazioni EFX rimane un importante problema aperto
  2. Estensione del Modello: Christodoulou et al. hanno provato l'esistenza di allocazioni EFX su grafi semplici; la domanda naturale è come si comporta il caso dei multi-grafi
  3. Applicazioni Pratiche: Il modello è applicabile in contesti geografici dove gli agenti si interessano solo alle risorse vicine, come corridoi commerciali, gasdotti, ecc.

Limitazioni degli Approcci Esistenti

  • I risultati esistenti sono principalmente limitati a grafi semplici (due agenti condividono al massimo un bene)
  • Manca una ricerca sistematica per il caso dei multi-grafi (due agenti possono condividere più beni)
  • L'esistenza e la complessità computazionale degli orientamenti EFX non sono ancora completamente caratterizzate

Contributi Principali

  1. Teoremi di Esistenza: Prova che le allocazioni EFX esistono sempre su multi-grafi bipartiti con funzioni di valutazione monotone e su multi-cicli con valutazioni MMS-feasible
  2. Progettazione di Algoritmi: Fornisce algoritmi pseudopolinomiali per il calcolo di allocazioni EFX, computabili in tempo polinomiale per funzioni di valutazione riducibili
  3. Caratterizzazione Completa: Fornisce una caratterizzazione completa dell'esistenza di orientamenti EFX su multi-grafi bipartiti basata su due parametri chiave (q e d(G))
  4. Analisi di Complessità: Prova la NP-completezza del problema di decidere l'esistenza di orientamenti EFX, anche per un numero costante di agenti
  5. Risultati di Approssimazione: Per i casi in cui non esistono orientamenti EFX, prova l'esistenza di orientamenti dove almeno ⌈n/2⌉ agenti soddisfano EFX e i rimanenti soddisfano 1/2-EFX

Dettagli dei Metodi

Definizione del Compito

Input:

  • Multi-grafo G = (V,E), dove V = n rappresenta n agenti e E rappresenta m beni
  • Funzioni di valutazione {vi}i∈n, soddisfacenti vi(S) = vi(S ∩ E(i)), dove E(i) è l'insieme degli archi incidenti all'agente i

Output:

  • Allocazione completa X = (X1,...,Xn), soddisfacente la condizione EFX
  • Oppure orientamento EFX (ogni bene allocato a uno dei suoi vertici terminali)

Vincoli:

  • EFX: per qualsiasi agente i,j e bene g ∈ Xj, vale vi(Xi) ≥ vi(Xj \ {g})
  • Tipi di funzioni di valutazione: monotone, riducibili, MMS-feasible, ecc.

Architettura del Modello

Concetti Fondamentali

  1. Configurazioni T-cut: Per agenti adiacenti i ∈ S e j ∈ T, l'agente j divide E(i,j) in due pacchetti C1 e C2, entrambi EFX-feasible per j
  2. Insiemi Disponibili: Definisce Ai,j(X) come l'insieme degli archi disponibili per l'agente i da E(i,j) nell'allocazione corrente X
  3. Insiemi Sicuri: Per un agente invidioso i, definisce Si(X) come il suo insieme sicuro

Proprietà Chiave

L'algoritmo mantiene sei proprietà chiave:

  1. X è un orientamento EFX
  2. I beni in E(i,j) sono allocati secondo la configurazione j-cut
  3. Ogni agente riceve il suo pacchetto preferito disponibile
  4. L'insieme disponibile degli agenti non invidiosi è vuoto
  5. La valutazione degli agenti non invidiosi per gli archi non allocati non supera il pacchetto corrente
  6. Gli invidiatori degli agenti invidiosi si trovano nel loro insieme sicuro

Punti di Innovazione Tecnica

1. Progettazione del Meccanismo di Configurazione

Introduce innovativamente il concetto di configurazione T-cut, combinando le idee del protocollo di scelta di divisione per due persone, fornendo un metodo sistematico per gestire più archi nei multi-grafi.

2. Struttura Algoritmica Multifase

Progetta cinque algoritmi che soddisfano successivamente le sei proprietà chiave:

  • Algoritmo 1: Orientamento greedy soddisfa le proprietà (1)-(3)
  • Algoritmo 2: Gestisce gli agenti non invidiosi soddisfa la proprietà (4)
  • Algoritmo 3: Aumenta la valutazione degli agenti non invidiosi soddisfa la proprietà (5)
  • Algoritmo 4: Costruisce insiemi sicuri soddisfa la proprietà (6)
  • Algoritmo 5: Allocazione finale dei beni rimanenti

3. Utilizzo della Struttura Bipartita

Sfrutta pienamente le caratteristiche strutturali dei grafi bipartiti, in particolare il fatto che i vertici invidiosi possono apparire solo in una partizione, semplificando significativamente l'analisi e la progettazione algoritmica.

Configurazione Sperimentale

Struttura di Analisi Teorica

Questo articolo è principalmente un lavoro teorico, che verifica i risultati attraverso prove matematiche piuttosto che esperimenti. La struttura di analisi include:

  1. Prove di Esistenza: Prove costruttive che mostrano come trovare allocazioni che soddisfano le condizioni
  2. Analisi di Complessità Algoritmica: Analizza la complessità temporale di ogni fase algoritmica
  3. Costruzione di Controesempi: Attraverso istanze specifiche, prova che gli orientamenti EFX non esistono in certi casi

Metriche di Valutazione

  • Conformità EFX: Se tutti gli agenti soddisfano la condizione EFX
  • Complessità Temporale: Tempo di esecuzione dell'algoritmo (polinomiale vs pseudopolinomiale)
  • Rapporto di Approssimazione: Qualità della soluzione approssimata quando non esiste una soluzione esatta

Risultati Sperimentali

Risultati Principali

1. Teoremi di Esistenza

Teorema 4.11: Per multi-grafi bipartiti con valutazioni monotone, le allocazioni EFX esistono sempre e sono computabili in tempo pseudopolinomiale; per valutazioni riducibili sono computabili in tempo polinomiale.

Teorema 5.1: Per multi-cicli con valutazioni MMS-feasible, le allocazioni EFX esistono sempre e sono computabili in tempo pseudopolinomiale.

2. Caratterizzazione Completa degli Orientamenti EFX

Caratterizzazione completa basata sui parametri q (numero massimo di archi tra due agenti qualsiasi) e d(G) (diametro del grafo):

Condizioni dei ParametriEsistenza Orientamento EFX
Aciclico, q=2, d(G)≤4Esiste
Aciclico, q=2, d(G)>4Potrebbe non esistere
Aciclico, q>2, d(G)≤2Esiste
Aciclico, q>2, d(G)>2Potrebbe non esistere
Ciclico, q≥2, d(G)≥2Potrebbe non esistere

3. Risultati di Complessità

Teorema 3.6: Decidere se un multi-grafo bipartito ammette un orientamento EFX è NP-completo, anche per un numero costante di agenti.

4. Risultati di Approssimazione

Teorema 4.12: Per multi-grafi bipartiti con valutazioni additive, esiste sempre un orientamento tale che almeno ⌈n/2⌉ agenti soddisfano EFX e i rimanenti soddisfano 1/2-EFX.

Analisi di Casi

L'articolo illustra il processo di esecuzione dell'algoritmo attraverso più istanze concrete:

  • Le Figure 7-10 mostrano l'esecuzione passo dopo passo dell'algoritmo su specifici multi-grafi bipartiti
  • La costruzione di controesempi (come nelle Figure 1-5) prova la non esistenza di orientamenti EFX in certi casi

Scoperte Teoriche

  1. Ruolo Cruciale della Struttura Bipartita: La struttura bipartita assicura che i vertici invidiosi appaiano solo in una partizione, il che è cruciale per il successo dell'algoritmo
  2. Efficacia del Meccanismo di Configurazione: La configurazione T-cut fornisce un framework unificato per gestire archi multipli
  3. Complessità Parametrizzata: I due parametri q e d(G) caratterizzano completamente l'esistenza di orientamenti EFX

Lavori Correlati

Stato Attuale della Ricerca su EFX

  • Due Agenti: Plaut e Roughgarden hanno provato l'esistenza per valutazioni monotone
  • Tre Agenti: Una serie di lavori ha provato l'esistenza per vari tipi di valutazione
  • Valutazioni Speciali: Esistenza in casi speciali come valutazioni identiche, valutazioni binarie, ecc.

Divisione Equa su Grafi

  • Christodoulou et al. hanno proposto per primi il modello di allocazione EFX su grafi semplici
  • Lavori successivi hanno studiato estensioni come orientamenti EF1, beni misti, ecc.
  • Questo articolo è il primo a studiare sistematicamente il caso dei multi-grafi

Lavori Paralleli

Due lavori indipendenti paralleli hanno anche studiato EFX su multi-grafi:

  • Sgouritsa e Sotiriou (2025): Provano l'esistenza di EFX su multi-grafi bipartiti con valutazioni monotone
  • Bhaskar e Pandit (2024): Studiano EFX su classi specifiche di multi-grafi

Conclusioni e Discussione

Conclusioni Principali

  1. Contributi Teorici: Fornisce per la prima volta una caratterizzazione completa dell'esistenza di allocazioni EFX su multi-grafi bipartiti, estendendo il framework teorico esistente
  2. Contributi Algoritmici: Fornisce algoritmi pseudopolinomiali pratici, raggiungendo tempo polinomiale per specifici tipi di valutazione
  3. Caratterizzazione di Complessità: Analizza completamente la complessità computazionale del problema di orientamento EFX

Limitazioni

  1. Restrizioni sulla Classe di Grafi: I risultati si concentrano principalmente su multi-grafi bipartiti; il caso generale rimane un problema aperto
  2. Restrizioni sulle Funzioni di Valutazione: Sebbene copra vari tipi di valutazione, non raggiunge ancora il caso più generale
  3. Efficienza Algoritmica: Per valutazioni monotone generali, si può raggiungere solo la complessità pseudopolinomiale

Direzioni Future

  1. Multi-grafi Generali: Gli autori congetturano che le allocazioni EFX esistono su qualsiasi multi-grafo, ma la prova richiede ancora nuove tecniche
  2. Ottimizzazione Algoritmica: Ricerca di algoritmi più efficienti, in particolare algoritmi in tempo polinomiale
  3. Benessere Sociale: Studio del compromesso tra allocazioni EFX ed efficienza

Valutazione Approfondita

Punti di Forza

  1. Profondità Teorica: Fornisce prove complete di esistenza e analisi di complessità, con significativi contributi teorici
  2. Innovazione Tecnica: Il meccanismo di configurazione T-cut e il framework algoritmica multifase sono innovativi
  3. Completezza dei Risultati: Fornisce una caratterizzazione parametrizzata completa dell'esistenza di orientamenti EFX
  4. Chiarezza della Scrittura: La struttura dell'articolo è chiara, le prove sono dettagliate e facili da comprendere e verificare

Insufficienze

  1. Mancanza di Verifica Sperimentale: Come lavoro puramente teorico, manca la valutazione delle prestazioni dell'algoritmo su dati reali
  2. Scenari di Applicazione Limitati: Gli scenari di applicazione pratica del modello multi-grafo sono relativamente limitati
  3. Limitazioni Tecniche: L'estensione a multi-grafi generali affronta ancora sfide tecniche

Impatto

  1. Valore Accademico: Fornisce importanti progressi teorici alla teoria della divisione equa, promuovendo lo sviluppo della ricerca su EFX
  2. Contributi Metodologici: Il framework tecnico proposto potrebbe ispirare soluzioni ad altri problemi di divisione equa su grafi
  3. Problemi Aperti: Fornisce un'importante accumulazione tecnica per il problema dell'esistenza di EFX su multi-grafi generali

Scenari di Applicabilità

  1. Ricerca Teorica: Fornisce importanti riferimenti per i ricercatori della teoria della divisione equa
  2. Progettazione di Algoritmi: Il meccanismo di configurazione può essere utilizzato per progettare altri algoritmi di divisione equa
  3. Teoria della Complessità: I risultati di NP-completezza hanno valore per la ricerca sulla complessità computazionale

Bibliografia

L'articolo cita importanti letteratura nel campo della divisione equa, inclusa:

  • Christodoulou et al. 2023: Lavoro pioneristico su allocazioni EFX su grafi semplici
  • Plaut e Roughgarden 2020: Prova dell'esistenza di EFX per due agenti
  • Chaudhury et al. 2020: Importanti progressi nel caso di tre agenti
  • Caragiannis et al. 2016: Prima introduzione del concetto di EFX

Sintesi: Questo è un articolo di alta qualità in informatica teorica che fornisce importanti contributi alla teoria della divisione equa. L'articolo è tecnicamente solido, i risultati sono completi e fornisce profonde intuizioni per comprendere il problema dell'allocazione EFX su multi-grafi, rappresentando un importante progresso in questo campo.