EFX Allocations on Some Multi-graph Classes
Umang Bhaskar, Yeshwant Pandit · 2024
Read EFX Allocations on Some Multi-graph Classes by Umang Bhaskar, Yeshwant Pandit (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06513.txt.
Introduction
Umang Bhaskar and Yeshwant Pandit study fair division in a setting drawn as a graph, in two thousand twenty-four. People are points on the graph, and goods are the lines joining them. A good has value only for the two people at its ends. The goal is a split that no one envies once any single good is removed.
Earlier work proved such a split exists when each pair of people shares at most one good. The pair extend that result to graphs where pairs can share many goods. They prove the split exists, and can be found fast, for several graph types. These include two-sided graphs, tree-like graphs, and graphs with long shortest cycles.
Catalog record
| CREATOR | Umang Bhaskar, Yeshwant Pandit |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06513
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
EFX Allocations on Some Multi-graph Classes Umang Bhaskar, Yeshwant Pandit Abstract The existence of EFX allocations is one of the most significant open questions in fair division. Recent work by Christodolou, Fiat, Koutsoupias, and Sgouritsa (“Fair allocation in graphs”, EC 2023) establishes the existence of EFX allocations for graphical valuations, when agents are vertices in a graph, items are edges, and each item has zero value for all agents other than those at its end-points. Thus in this setting, each good has non-zero value for at most two agents, and there is at most one good valued by any pair of agents. This marks one of the few cases when an exact and complete EFX allocation is known to exist for arbitrary agents. In this work, we extend these results to multi-graphs, when each pair of vertices can have more than one edge between them. The existence of EFX allocations in multi-graphs is a natural open question given their existence in simple graphs. We show that EFX allocations exist, and can be computed in polynomial time, for agents with cancellable valuations in the following cases: (i) bipartite multi-graphs, (ii) multi-trees with monotone valuations, and (iii) multi-graphs with girth ( 2 t − 1 ) (2t-1) , where t t is the chromatic number of the multi-graph. The existence in multi-cycles follows from (i) and (iii). 1 Introduction We study the existence and computation of allocations that are envy-free up to any item, or EFX, in instances that can be represented as multi-graphs. The question of whether EFX allocations exist in general instances is possibly the most tantalising open question in the fair allocation of resources, and many recent papers have focused on this question, leading to proofs of its existence in ever-larger classes of instances. A fair division instance consists of a set of items that is to be allocated to a set of agents, with each item allocated to an agent. Each agent has a monotone nondecreasing value function over the set of items. Given an allocation, agent i envies agent j if agent i ’s value for its own allocation is less than its value for the set of items allocated to j . An envy-free allocation is one where no agent envies another. Envy-free allocations do not exist in general, and the closest relaxation then studied is envy-freeness upto any good, or EFX. An EFX allocation allows an agent to envy another, but the removal of any item from the envied agent’s allocation should eliminate the envy as well. EFX allocations were first studied by Caragiannis et al. [ CKM+19 ] , who established its relation to other notions of fairness, but left the question of existence open. If all agents have the same valuation function, then an EFX allocation has been shown to exist [ PR20 ] . This can be extended to show the existence for two agents with distinct valuations. This was extended to multiple agents with two distinct additive valuations [ Mah23 ] , then to three agents when at least one has an MMS-feasible valuation [ AAC+23 , CGM24 ] , and recently to multiple agents with three distinct additive valuations [ HGNV24 ] . A number of papers also study partial EFX allocations, when some items may remain unallocated, e.g., [ CKMS21 , BCFF22 ] , as well as approximately EFX allocations [ AFS24 , AMN20 , CCLW19 , PR20 ] . Given the difficulties in establishing the existence of EFX allocations with multiple agents, researchers study special cases of structured valuations. One such class of structured valuations is graphical valuations when the instance can be represented as a graph [ CFKS23 ] . Here the agents correspond to the vertices of the graph, and each item is an edge e=\{u,v\} . The restriction is that each item has nonzero marginal value for only the agents at its end-points, and has zero value for all other agents. Thus if e=\{i,j\} , then for every other agent k and subset S of items, v_{k}(S\cup\{e\})=v_{k}(S) . Further, the graph is simple, and thus there is at most one good valued by every pair of agents. For this case, and agents with monotone valuations over incident edges, Christodolou et al. [ CFKS23 ] show that EFX allocations exist, marking one of the rare cases where EFX allocations are shown to exist with multiple agents. A natural question with graphical valuations is if an EFX orientation exists— an EFX allocation where goods are only allocated to agents at their endpoints. Christodolou et al. show that an EFX orientation may not exist, and it is NP-hard to determine if a given instance has an EFX orientation [ CFKS23 ] . Zeng and Mehta characterize graphs that permit EFX orientations [ ZM24 ] . Given the existence of EFX in simple graphs, a natural question is if these results can be extended to multi-graphs when there are multiple edges between vertices (equivalently, pairs of agents can value multiple goods). Here a 2/3 -approximate EFX was shown to exist [ AFS24 ] , beating the earlier bound of 0.618 for general additive valuations. In independent and concurrent work, Afshinmehr et al. [ ADK+24 ] show that exact EFX allocations exist in bipartite multi-graphs and multi-cycles. They also characterize when EFX orientations exist in bipartite graphs, and show it is NP-hard to decide if a given instance admits an EFX orientation. 1.1 Our contribution We study EFX allocations in multi-graphs, and show that EFX allocations exist in large and important subclasses of multi-graphs. Our results are algorithmic, and for agents with cancellable valuations (defined in the next section), we show an EFX allocation can be obtained in polynomial time. A feature of our algorithms is that they are iterative and fairly simple to state, and are based on the well-known cut-and-choose paradigm. While the algorithms are natural, the analysis is complicated and somewhat subtle. 1. Firstly, we show for bipartite multi-graphs with cancellable valuations, an EFX allocation can be obtained in polynomial time. 2. Secondly, we show that for multi-trees, i.e., when there are no cycles of length three or larger, EFX allocations exist for general monotone valuations. Since multi-trees are also bipartite graphs, for multi-trees with cancellable valuations, a polynomial time algorithm immediately follows. 3. Lastly, we generalize the result for bipartite multi-graphs, and show that for multi-graphs with girth at least (2t-1) , where t is the chromatic number of the graph, EFX allocations can be obtained in polynomial time for agents with cancellable valuations. Our algorithm here is a natural extension of the algorithm for bipartite multi-graphs, though the analysis is more complicated. We note that any multi-cycle is 3-colourable. Hence our last result shows the existence of EFX allocations in multi-cycles of length 5 or greater. A 2-colourable multi-cycle is bipartite, for which existence follows from the first result. The existence in multi-cycles of length 3 is known, and hence our work also shows the existence of EFX allocations for multi-cycles. For the last result, we assume that we are given a t -colouring of the graph. A concrete example of such a graph is the Petersen graph, with chromatic number 3 and girth