Nuovi Risultati sulle Allocazioni EFX Approssimate per Beni Indivisibili
Un nuovo articolo su arXiv (2406.12413) presenta garanzie di esistenza migliorate per allocazioni approssimativamente prive di invidia di beni indivisibili. Gli autori dimostrano che allocazioni 2/3-EFX esistono quando ci sono al massimo sette agenti, quando le valutazioni degli agenti assumono al massimo tre valori, o quando le valutazioni sono rappresentate da un multigrafo. Questo estende lavori precedenti che stabilivano EFX esatto per un massimo di tre agenti e 0.618-EFX per qualsiasi numero di agenti. I risultati rilassano la nozione di EFX per ottenere una maggiore esistenza.
Fatti principali
- Articolo arXiv:2406.12413
- Studia l'allocazione di beni indivisibili ad agenti con valutazioni additive
- Obiettivo è l'assenza di invidia approssimata fino a qualsiasi bene (α-EFX)
- EFX esatto noto per ≤3 agenti, valutazioni a due valori o valutazioni rappresentabili tramite grafi
- 0.618-EFX noto per qualsiasi numero di agenti
- Nuovo risultato: 2/3-EFX esiste per ≤7 agenti
- Nuovo risultato: 2/3-EFX esiste per valutazioni a tre valori
- Nuovo risultato: 2/3-EFX esiste per valutazioni rappresentabili tramite multigrafo
Entità
Istituzioni
- arXiv