Overview
This research investigates fair allocations of indivisible goods among agents possessing heterogeneous monotone valuations, specifically focusing on envy-free-up-to-any-good (EFX) allocations. The study operates within a (multi)hypergraph setting, where agents are represented by vertices and goods by edges. In this model, only the endpoints of an edge can have a non-zero marginal value for that edge.
Research Context
The determination of whether EFX allocations consistently exist, even for agents with additive valuations, constitutes a significant unresolved challenge within the field of Fair Division. Christodoulou et al. (2023) introduced the (multi-hyper)graph framework as a specific context for studying such allocation problems.
Approach
The research approaches the EFX allocation problem by analyzing hypergraphs and multi-hypergraphs. For hypergraphs, the approach focuses on structures with a girth of at least 4 and agents with general monotone valuations. The methodology then generalizes to multi-hypergraphs, under the condition that the simple hypergraph derived from the multi-hypergraph also has a girth of at least 4. An additional condition for multi-hypergraphs requires the existence of at least one vertex where incident edges have a multiplicity at most two less than the size of that edge.
Findings
- For hypergraphs characterized by a girth of at least 4 and agents endowed with general monotone valuations, an EFX allocation invariably exists.
- These EFX allocations for hypergraphs with girth at least 4 can be constructed in polynomial time.
- The approach generalizes to multi-hypergraphs: if the underlying simple hypergraph has a girth of at least 4 and there is at least one vertex whose incident edges exhibit a multiplicity at most the size of that edge minus 2, then an EFX allocation is guaranteed to exist.
- The construction of EFX allocations for these specified multi-hypergraphs requires pseudo-polynomial time.