Fair allocation in graphs
We study <i>envy freeness up to any good (EFX)</i> in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex m...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for Computing Machinery
2023
|
| Subjects: |
| _version_ | 1826311003912011776 |
|---|---|
| author | Christodoulou, G Fiat, A Koutsoupias, E Sgouritsa, A |
| author_facet | Christodoulou, G Fiat, A Koutsoupias, E Sgouritsa, A |
| author_sort | Christodoulou, G |
| collection | OXFORD |
| description | We study <i>envy freeness up to any good (EFX)</i> in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore that it is NP-complete to decide whether an EFX orientation exists. Our main result is that (EFX) allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than 3 agents. |
| first_indexed | 2024-03-07T08:02:01Z |
| format | Conference item |
| id | oxford-uuid:5c39ce84-f0a8-4209-bdfa-f17a6c4f9cc7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:02:01Z |
| publishDate | 2023 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:5c39ce84-f0a8-4209-bdfa-f17a6c4f9cc72023-10-05T14:02:51ZFair allocation in graphsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:5c39ce84-f0a8-4209-bdfa-f17a6c4f9cc7Algorithmic game theoryTheory of computationEnglishSymplectic ElementsAssociation for Computing Machinery2023Christodoulou, GFiat, AKoutsoupias, ESgouritsa, AWe study <i>envy freeness up to any good (EFX)</i> in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore that it is NP-complete to decide whether an EFX orientation exists. Our main result is that (EFX) allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than 3 agents. |
| spellingShingle | Algorithmic game theory Theory of computation Christodoulou, G Fiat, A Koutsoupias, E Sgouritsa, A Fair allocation in graphs |
| title | Fair allocation in graphs |
| title_full | Fair allocation in graphs |
| title_fullStr | Fair allocation in graphs |
| title_full_unstemmed | Fair allocation in graphs |
| title_short | Fair allocation in graphs |
| title_sort | fair allocation in graphs |
| topic | Algorithmic game theory Theory of computation |
| work_keys_str_mv | AT christodouloug fairallocationingraphs AT fiata fairallocationingraphs AT koutsoupiase fairallocationingraphs AT sgouritsaa fairallocationingraphs |