CS Paper Radar

A Polynomial Time Characterization For Strongly EFX Orientable Graphs

Jinghan A Zeng

cs.GT ·submitted 2026-09-29 01:52 UTC · v2

Abstract

Discrete fair division is the problem of dividing a discrete set of goods among agents in a fair manner. In this setting, one of the most sought-after notions of fairness is envy-freeness up to any good (EFX). In 2023, Christodoulou, Fiat, Koutsoupias, and Sgouritsa introduced the idea of a graphical valuation, where the fair division problem is represented by a simple graph where vertices are the agents and the edges are the goods, and each vertex only values incident edges. They showed that an EFX allocation always exists, while determining the existence of an EFX orientation is NP-hard. They posed a open question of determining which graphs always admit an EFX orientation regardless of valuation. These graphs, called strongly EFX orientable graphs, were first studied by Zeng and Mehta in 2025, who demonstrated that all such graphs have chromatic number at most 3, and bipartite graphs always admit an EFX orientation regardless of valuation. In this manuscript, we finish resolving this question by giving a polynomial time characterization of strongly EFX orientable graphs. In particular, we show that a connected graph $G$ is strongly EFX orientable if and only if either of the following is true: (1) $G$ is bipartite, or (2) the block decomposition of $G$ contains exactly one nonbipartite block $B$, and there exists a vertex $v \in B$ such that the degree of $v$ within $B$ is 2 and $G-v$ is bipartite. This proof was discovered by AI, with human intervention to break the problem into the appropriate subproblems.

Comment
16 pages, 9 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Settling PROPm and PROPavg in Graphical Resource Allocation

cs.GT ·2026-10-07 ·Bo Li, Ankang Sun, Ruijie Wang
publishedtheory similarity 0.74
Abstract · Full version of a paper to appear in WINE 2026. V2 includes an extended related work section

We study proportional fairness in graphical resource allocation, where agents are vertices, indivisible items are edges, and each item must be allocated to one of its two endpoints. It has been proved that PROP1 orientations always exist and PROPx orientations may not, but it has remained open whether the intermediate relaxations PROPm and PROPavg (both can be satisfied without graphical constraints) can always be satisfied. In this paper, we resolve this gap. We prove that PROPm orientations always exist for goods on multigraphs and can be computed efficiently. The guarantee extends to chores and a mixture of goods and chores. In sharp contrast, we show that PROPavg orientations need not exist, even for simple graphs with binary valuations, and that deciding their existence is NP-complete. We further quantify the efficiency loss of PROPm: for goods, the price of PROPm is exactly $2$, which is one of the few settings where a constant bound on the price of fairness can be obtained. We complement these results with hardness results for welfare optimization under PROPm and for the existence of orientations that are simultaneously PROPm and Pareto optimal.

0.25

Fair Division of Graphs: Beyond Traceability

cs.GT cs.DMmath.CO ·2026-08-30 ·Nicolas Bousquet, Frank Connor, Agnès Totschnig, Sébastien Zeitoun
similarity 0.72
Abstract

In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally alters the problem, making it significantly more challenging than its classical counterpart. We focus on the fairness notion of $\mathrm{EF1}_{\mathrm{outer}}$, where envy can be eliminated by removing at most one vertex whose deletion does not disconnect the bundle -- a critical constraint for applications such as land division and network allocation. Our first result extends prior work by establishing the existence of $\mathrm{EF1}_{\mathrm{outer}}$ allocations for an infinite family of non-traceable graphs (that is, graphs that do not admit a Hamiltonian path), answering a central open question and generalizing Bilò et al.'s result for traceable graphs. We then make progress on a conjecture concerning the $\mathrm{EF1}_{\mathrm{outer}}$ spectrum of trees due to Chen and Zwicker. Finally, we complement our structural results with algorithmic insights, showing that deciding the existence of an $\mathrm{EF1}_{\mathrm{outer}}$ allocation is NP-complete even for binary additive valuations, thereby resolving an open complexity question. Taken together, our results deepen the connection between graph theory and fair division, and offer new tools for studying fairness in structured resource environments.

0.06

Reconfiguration in Fair Division Revisited

cs.GT cs.DM ·2026-09-14 ·Fabian Frank, Warut Suksompong
theory similarity 0.68
Abstract

We revisit reconfiguration in the fair allocation of indivisible goods, where the goal is to transform one fair allocation into another through a sequence of exchanges while preserving fairness at every step. Our focus is on the hierarchy of envy-freeness up to $k$ goods (EF$k$). We show that for any fixed $k$, two EF1 allocations with the same size vector need not admit a reconfiguration path whose intermediate allocations satisfy EF$k$. This impossibility persists even when the two allocations arise from standard EF1 approaches: the envy cycle elimination algorithm or the maximum Nash welfare solution. In contrast, we prove that allocations with the same size vector produced by recursively balanced picking sequences, including round-robin, are always connected via a path that maintains EF2. We also show that deciding whether an EF1 reconfiguration path exists is NP-hard for any fixed number of agents. Furthermore, we complement these exchange-based results by studying a more permissive model that also allows transfers, establishing additional connectivity guarantees.

0.11

Simultaneous Envy and Equitability Guarantees

cs.GT cs.AIecon.TH ·2026-08-26 ·Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang
similarity 0.68
Abstract · 43 pages

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. For normalized binary goods, we give a polynomial-time algorithm for computing an EF1+EQ1 allocation with at most seven agents, but also construct a normalized instance with a larger number of agents for which no such allocation exists. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante and ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

0.23

Rival-Injective Allocations: Support-List Structure and Maximum-Anchor EFX$_0$ Certificates

cs.GT ·2026-08-31 ·Junshuo Wang
hot direction similarity 0.67
Abstract · 18 pages, no figures. Includes a statement on human direction, AI contributions, verification, and author responsibility

We study complete allocations under nonnegative additive valuations through the positive supports of goods, focusing on the all-good form of envy-freeness up to any good (EFX$_0$). We define rival-injective (RI) endpoint ownership: every good with nonempty positive support is assigned to an agent who values it positively, and every ordered observer--owner pair is used by at most one good. RI ownership is exactly proper list coloring of the graph joining goods whose positive supports overlap in at least two agents. For pair-supported goods with arbitrary exceptional goods, fixing the exceptional owners yields a necessary-and-sufficient pair-capacity criterion and an exact finite-domain owner constraint satisfaction problem (CSP). Every RI allocation in which each agent's own bundle is worth at least her maximum-valued singleton is all-good EFX$_0$. A specified injective choice of maximum-singleton anchors, together with residual support-list degeneracy, constructs such an allocation by reverse greedy coloring in $O(nm^2)$ time. We give two explicit witness families: a nonempty relatively open, 22-dimensional cone on a fixed $4\times10$ support face, and a family for every $n\ge4$ with two universal-support goods and $m=(n-1)(n-2)+2$ goods. Both fail unanchored list degeneracy and are not implied by the explicit pure-multigraph or published high-girth/controlled-multiplicity hypotheses compared here. We also study recognition of the maximum-anchor certificate class, leaving its general complexity unresolved. The exact list-coloring and pair-capacity results concern RI ownership, not general EFX$_0$ existence; unrestricted four-agent, ten-good all-good EFX$_0$ remains unresolved.

0.27

Balanced Fair Division and Generalized Kneser Graphs

cs.GT ·2026-11-03 ·Sharareh Alipour, Amir Jafari
theory similarity 0.67
Abstract

We study indivisible goods allocated to two prescribed nonempty groups whose members have arbitrary monotone valuations. We guarantee balanced envy-freeness up to one good (EF1) for at most five agents and up to two goods (EF2) for at most nine, for any number of goods. Bundle sizes differ by at most one. The EF1 threshold is sharp: every split of six agents can fail. EF2 improves the previous five-agent guarantee. Via the connection of Kyropoulou, Suksompong, and Voudouris, these guarantees follow from chromatic bounds for $\mathrm{KG}(2n,n,r)$, whose vertices are $n$-subsets of a $2n$-set, adjacent when their intersection has size less than $r$. We prove its chromatic number is six for $r=2$, $n\ge2$, resolving Jafari and Alipour's conjecture, and at least ten for $r=3$, $n\ge4$, improving the previous lower bound of six; the known upper bound is fourteen. We show that the standard box-complex $\mathbb{Z}_2$-index bound yields exactly five and nine for $n\ge3$ and $n\ge5$, respectively. To exceed these bounds, we exploit restrictions on maps induced by colorings: a proper five- or nine-coloring must induce a nonzero homology map, yet local constraints force all generators, supported on pentagon or rook configurations, to map to zero. The ten-color proof compares integral and fractional common centers using a sharp rounding theorem for five subset constraints. A linear-time retraction from the full allocation graph onto balanced layers adds cardinality balance to known nonlinear discrepancy guarantees. For each fixed removal allowance in the guaranteed-existence range, finding a balanced fair allocation or an explicit monotonicity violation from valuation circuits is polynomial-time equivalent to finding a monochromatic edge in a circuit-specified coloring of the corresponding graph. The reverse reduction produces normalized monotone binary valuations using ordinary circuits.

0.10

Balanced Fair Division for Three Agents under General Valuations and Laminar Constraints

cs.GT ·2026-08-10 ·Max Dupré la Tour
theory similarity 0.67
Abstract

We study fair allocations of indivisible items under general set valuations. We prove that every instance with three agents and arbitrary real-valued valuations admits a balanced allocation that is envy-free up to one good and one chore (EF$1^c_g$). This directly implies balanced EF$1$ when each valuation is either monotone nondecreasing or monotone nonincreasing. We also show that balanced EF$1$ cannot be guaranteed without monotonicity: there exists an instance with three agents, nine items, and identical nonmonotone valuations that admits no balanced EF$1$ allocation. We then consider a common laminar matroid constraint. Whenever a complete feasible allocation exists, we prove that there is a complete feasible allocation that is balanced and envy-free up to two goods and two chores (EF$2^c_g$) for arbitrary valuations. The allocation can additionally be chosen so that the numbers of items from every laminar set assigned to the three agents differ by at most two. Most proofs in this paper were obtained using GPT-5.6. We subsequently verified the proofs for correctness and refined their exposition and arguments, also with the aid of GPT-5.6.

0.04

To EFX OR to MMS, That is the Question

cs.GT ·2026-08-11 ·Hadi Hosseini, Payas Khurana, Shraddha Pathak, Rohit Vaish
theory similarity 0.67
Abstract

We study the agent-wise disjunction of two central fairness notions for indivisible items, where every agent must be either envy-free up to any item (EFX) or maximin-share (MMS) satisfied. One might expect that having a flexible fairness requirement for individual agents will restore existence, especially because the existence of EFX itself resisted resolution for nearly a decade. Surprisingly, it does not. We construct counterexamples with three agents and eight submodular goods, and with three agents and seven submodular chores, significantly strengthening recent EFX impossibility results. On the positive side, we prove existence for additive mixed items with at most three valuation types when one type is a singleton. Additionally, we obtain polynomial-time approximation schemes for additive goods-only and chores-only instances. We also identify a clean separation between the disjunction and its constituents: For additive chores with two valuation types, EFX and MMS are both known to fail, whereas an EFX $\vee$ MMS allocation always exists. Finally, we show that identical additive valuations even admit the conjunction EFX $\wedge$ MMS for mixed items. Overall, our results show that allowing flexibility in choosing agent-specific fairness certificates expands the frontier of fair solutions while also uncovering surprising impossibilities.

0.32