Pith. sign in

REVIEW 3 major objections 5 minor 48 references

Tractable Graph Structures in EFX Orientation

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read EFX-orientation on graphs is linear-time solvable one edge from bipartite, NP-complete two edges away, with P5 paths as the core obstruction.

desk verdict A genuinely useful complexity map for EFX orientation with one real gap: the Theorem 4 2-SAT reduction drops internal 0-edges and is incomplete as written, but the min-uncut dichotomy and parameterized work are solid and deserve a serious referee. read the letter →

arxiv 2506.15379 v1 pith:3JYK7IPR submitted 2025-06-18 cs.GT cs.DS

Václav Blažej , Sushmita Gupta , M.S. Ramanujan , Peter Strulo This is my paper · ORCID
classification cs.GTcs.DS MSC 91B3268Q2568R10
keywords EFX-orientationfairdivisiongraphorientationbinaryadditivevaluationsmin-uncutnumberP5-freegraphstreewidthparameterizedcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper pins down the computational boundary of EFX-orientation, the fair-division problem where agents are vertices, items are edges, and each item must go to one of its endpoints so that no agent strongly envies another. With symmetric, additive, and mostly binary valuations, it shows that bipartite graphs are not the only easy case: every instance one edge-removal away from bipartite is solvable in linear time, but two edge-removals make the problem NP-complete, and a single non-binary value already brings NP-hardness at distance one. The same boundary reappears inside the graph: the obstruction is an induced path on five vertices in the subgraph of value-1 edges, and excluding that path restores linear-time solvability. These results give a nearly complete map of which graph structures make fair allocations easy or hard to compute, plus linear-time algorithms on constant-treewidth graphs.

What carries the argument

The load-bearing machinery is the rooting characterization: after preprocessing, $G_1$ is a forest of trees, and an EFX-orientation exists exactly when each tree can be rooted so that the union of the roots' 1-neighborhoods is an independent set in $G_0$ (Proposition 8). All algorithms and reductions work on this root-placement problem. To tame it, the paper introduces the core of a tree, a maximal subtree in which no vertex is adjacent to two leaves, and a leaf-merging lemma showing that only non-dominated rootings matter and that each small core has at most two genuinely distinct states. The $P_5$-free case reduces to 2-SAT, the treewidth case is expressed in MSO and solved by Courcelle's theorem, and the hardness reductions encode constraints on roots directly as 0-edges between root-neighborhoods. The min-uncut-1 algorithm instead uses a partition of the vertices into parts whose induced structure guarantees a valid orientation.

What would settle it

Compute, for all preprocessed graphs up to ten vertices whose value-1 subgraph is a $P_5$-free forest, both the existence of an EFX-orientation by brute force over all orientations and the paper's root/independent-set condition; any mismatch, or any min-uncut-1 binary instance with no EFX-orientation, would refute the central claims.

Watch

Extended reading notes

Core claim

The central claim is a sharp pair of dichotomies. For binary symmetric additive valuations, the min-uncut number, the minimum number of edges whose deletion makes the graph bipartite, is decisive: Theorem 1 gives a linear-time algorithm for every instance with min-uncut number 1, while Theorem 2 proves NP-hardness for min-uncut number 2 and hardness for min-uncut number 1 when one edge has a non-binary value. The paper also identifies the combinatorial reason behind this boundary: induced paths on five vertices, $P_5$, in the subgraph $G_1$ of value-1 edges are the essential obstruction. Theorem 3 shows NP-completeness persists even when every component of $G_1$ is a $P_2$, $P_3$, or $P_5$, $G_0$ has maximum degree 1, and $G$ is planar; Theorem 4 shows linear-time solvability whenever every component of $G_1$ is $P_5$-free or contains a cycle. The paper further proves that constant-treewidth graphs are solvable in linear time via MSO logic, and it calibrates the parameterized complexity: with a tree-core notion, instances with few small cores and few big cores are solvable in $\tau^k n^{O(b)}$ time, while the number of big cores is $W[1]$-hard, so a $f(k)n^{O(1)}$ algorithm is unlikely under standard assumptions.

Load-bearing premise

Everything rests on a previously proved equivalence: a preprocessed graph has a fair orientation exactly when its trees of value-1 edges can each be given a root so that no two root-neighbors are joined by a value-0 edge; if that equivalence is not exact, the algorithms and reductions built on it collapse.

Editorial extensions

If this is right

  • Every EFX-orientation instance with binary symmetric additive valuations and min-uncut number 1 has a solution, and that solution can be found in linear time, so bipartite graphs are not the only easy case.
  • At min-uncut number 2 the same valuation class becomes NP-complete, placing the easy-hard boundary exactly at the second deleted edge; allowing even one non-binary edge moves hardness to min-uncut number 1.
  • If every component of $G_1$ is $P_5$-free, the instance is linear-time solvable; the planar hardness instances with $G_1$ components $P_2$, $P_3$, or $P_5$ show that induced five-vertex paths are the essential obstruction.
  • On graphs of constant treewidth the problem is linear-time solvable, and because known results make it NP-hard on constant-vertex-cover graphs once valuations are not binary, the binary assumption in this result is necessary.
  • Parameterized by the number of large cores in $G_1$, the problem is $W[1]$-hard, so the $\tau^k n^{O(b)}$ running time of the core-based algorithm is essentially the best one can expect under standard parameterized-complexity assumptions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the $P_5$ dichotomy suggests a broader pattern: for binary symmetric additive EFX-orientation, tractability of a hereditary class of $G_1$ may be governed by whether the class contains $P_5$; testing other small forbidden induced trees would directly probe this pattern.
  • Beyond the paper, the sharp min-uncut threshold of 2 suggests that the right parameter for further algorithms is the pair (distance to bipartite, number of non-binary edges), since Theorem 2 shows either parameter alone is insufficient.
  • Beyond the paper, the core and split-orientation machinery is defined entirely inside $G_1$, with 0-edges used only to forbid root pairs, so the same structural analysis could transfer to EF1-orientations or to chores with costs if analogous root/independent-set characterizations hold there.
  • Beyond the paper, the planar NP-hardness at constant degree means geometric restrictions alone will not restore tractability, so bounded-treewidth or bounded-core-count algorithms are the natural route for practical instances, and an implementation of the 2-SAT reduction on $P_5$-free inputs would be a useful benchmark.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the EFX-orientation problem for graphical fair division with symmetric additive valuations, building on the characterization of Zeng and Mehta. The main claims are: (1) binary instances whose graph has min-uncut number 1 are always solvable in linear time (Theorem 1); (2) the problem is NP-hard for binary instances with min-uncut number 2 and for instances with min-uncut number 1 when one edge is allowed to be non-binary (Theorem 2); (3) NP-completeness persists when every connected component of G1 is a P2, P3, or P5, G0 has maximum degree 1, and G is planar (Theorem 3); (4) the problem is linear-time solvable when every component of G1 is P5-free or cyclic (Theorem 4); (5) the problem is linear-time solvable on graphs of constant treewidth via an MSO formulation (Theorem 5); and (6) the number of large "cores" in G1 yields W[1]-hardness (Theorem 32). The proofs use Proposition 8 of Zeng and Mehta as the external characterization, standard algorithmic tools (2-SAT, Courcelle's theorem, min-uncut), and an internal decomposition into cores and split orientations.

Significance. If the results are correct, they substantially clarify the tractability frontier of EFX orientations: they show that min-uncut number 1 is tractable, min-uncut 2 is hard, and that induced P5s in the 1-edge graph are the essential obstruction for the binary case. The proposed core-based structural decomposition and the split-orientation gadgets are interesting and novel, and the use of Courcelle's theorem in this domain is a reasonable contribution. The paper is also careful to state its dependence on the external Zeng--Mehta characterization and on standard complexity results. However, the current version contains a serious gap in the proof of Theorem 4 that affects a central tractability claim, an incomplete proof step in Theorem 12 that affects Theorem 1, and unverified min-uncut counts in the gadgets of Theorem 2. Because these issues are load-bearing for the main claims, the manuscript requires substantive revision before it can be accepted.

major comments (3)
  1. [Section 5.3 and Appendix, 'Missing details of the proof of Theorem 4'] The 2-SAT reduction is not sound as written because it discards 0-edges that have both endpoints inside a single root-state neighborhood. In the reduction, for a state u, all G0-edges with an endpoint in N1(u) are reconnected to the opposite new vertex v; an edge with both endpoints in N1(u) therefore becomes a loop. Since G0 is a simple graph and the text does not state that such loops are kept as unit clauses, the most straightforward reading is that they are omitted. This can turn infeasible root states into feasible ones. Concretely, take two P3 components with centers a,d and leaves b,c and e,f, and add the 0-edges bc, ad, ae, bd, cd. By Proposition 8 no rooting works: the four root-pair types are blocked respectively by ad, ae, bd/cd, and bc. In the reduced 2-SAT instance, the clauses for ad, ae, bd, and cd forbid three of the four pairs, but the loop obtained from bc is dropped, so the center/center pair is unconstrained and the 2-SAT instance is satisfiable. The appendix's claim that 'the neighborhoods of the new states are the same' fails for such internal 0-edges. The proof must explicitly encode these loops as unit clauses (or otherwise preserve the infeasibility of states whose neighborhood is not independent), and the correctness argument must account for them. This is a load-bearing error in the proof of Theorem 4.
  2. [Section 4.1, Theorem 12, Step 2] Step 2 as written is ambiguous about how many value-1 edges a root receives from B. The text says: 'For each vertex u selected as a root in the previous step, check if there is a vertex v in B such that w(uv)=1 and if so, orient the edge uv towards u.' If u has several 1-edges to B, the instruction to 'orient the edge uv towards u' is naturally read as orienting all of them towards u. Then a root u receives multiple 1-items, and a B-vertex that ends up with no 1-item can strongly envy u (conditions (1)--(3) of Observation 6 are all satisfied when u has another item besides the shared edge). The proof rules out strong envy from A to B and from B to B, but it does not rule out strong envy from B to A. The construction should orient at most one incident 1-edge towards each root from Step 1, and orient all other 1-edges between A and B towards their B endpoints; then every vertex in A has exactly one 1-item, so condition (3) of Observation 6 fails for any envier in B. The statement may be true, but the proof as written does not establish an EFX orientation. This gap affects Theorem 1, which relies directly on Theorem 12.
  3. [Section 4.2, Theorem 2] The min-uncut number of the three gadgets is asserted but not proved. The text states that the first gadget 'will have min-uncut number two', that the second 'again ... will have min-uncut number two', and that in the third gadget the single m-valued edge is 'the only edge contributing to the min-uncut number'. Since the hardness claims explicitly require min-uncut number exactly 2 in the binary cases and min-uncut number exactly 1 in the almost-binary case, these assertions are load-bearing. The authors should provide the explicit bipartition of the base construction (including a1,a2,b1,b2 and the auxiliary trees) and prove that deleting fewer than the claimed number of edges cannot make the graph bipartite. Without this verification, the hardness results for exactly these min-uncut values are not established.
minor comments (5)
  1. [Abstract / Introduction] The name 'Christadolou' in the abstract is a typo; it should be 'Christodoulou'.
  2. [Definition 20] 'ACore of a tree' should be 'A core of a tree', and the sentence following the definition should end with a period.
  3. [Appendix, Proof of Lemma 25] The sentence 'We root Tat an arbitrarily chosen non-leaf' is missing a period and a definite article. The dynamic programming table D is defined with modes 'no, bot, top' but the recurrence uses both j and q for children; please make the indexing consistent.
  4. [Appendix, Proof of Theorem 3] The planarity of the final graph after applying Lemma 17 is argued in a single sentence ('embed T such that its leaves are ordered according to P'). Since the theorem asserts planarity as a key restriction, please provide a short formal argument or a figure showing that the replacement preserves the planar embedding.
  5. [Section 6.3.1] The definition of split orientation is clear, but the phrase 'no two arcs in M can share their heads or tails' is followed by a footnote defining head and tail that is not referenced in the main text at that point; consider moving the definition into the main text or adding a forward reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivations rest on an external characterization and standard algorithmic results, not on self-referential fits.

full rationale

I traced the load-bearing chain. The central reduction to tree-rooting (Proposition 8) is quoted from Zeng and Mehta 2024, Lemma 3.1, an externally published characterization of EFX-orientations; the paper does not redefine success in terms of its own output. Theorem 1 combines this characterization with Theorem 12 (a constructive orientation argument) and Lemma 13 (min-uncut 1 yields the required A/B partition), plus a cited linear-time algorithm for min-uncut 1/edge-odd-cycle-transversal from Iwata et al. and Ramanujan and Saurabh 2017. Although one current author is a coauthor of the latter, the cited algorithm is an independent, parameter-free subroutine for a different problem (returning an edge whose deletion makes the graph bipartite), so it does not smuggle in the EFX conclusion. Theorems 2 and 3 are hardness reductions from independent NP-hard problems (multicolored independent set and planar monotone 3-SAT) and are verified through the external characterization, not through assumptions equivalent to the target. Theorem 4's linear-time algorithm reduces each P5-free tree to two root states and encodes the independent-set condition of Proposition 8 as a 2-CNF formula; the appendix gives the equivalence argument. Theorem 5 expresses the same external condition in MSO and invokes Courcelle's theorem for constant treewidth. I found no equation that defines a prediction in terms of a fitted parameter, no load-bearing premise justified only by self-citation, and no uniqueness claim imported from the authors' own prior work. The only self-citation is the black-box min-uncut subroutine, which is independent support and therefore does not raise the circularity score.

Assumptions & free parameters 1 free parameters · 6 assumptions · 2 invented entities

The central claims rest on external characterizations and standard complexity tools. No data-fitting parameters are used; the only hand-chosen value is the non-binary edge weight m in a hardness gadget, which works for any 0<m<1.

free parameters (1)
  • m = any value in (0,1)
    In Theorem 2's third gadget, a single edge b1b2 is assigned value m with 0<m<1 to prove NP-hardness with min-uncut 1 and one non-binary edge; the construction works for any such m, it is not estimated from data.
assumptions (6)
  • domain assumption Proposition 8 (Zeng and Mehta 2024, Lemma 3.1): EFX-orientation on preprocessed instances is equivalent to rootability with independent root-neighborhoods in G0.
    Used in Sections 4-6 to justify the rooting framework for algorithms and hardness; not proved in this paper.
  • domain assumption Proposition 14 (Iwata et al. 2016; Ramanujan and Saurabh 2017): linear-time algorithm that finds an edge e with G-e bipartite or certifies min-uncut > 1.
    Used in Theorem 1 to turn min-uncut 1 into the partition required by Theorem 12.
  • standard math Courcelle's theorem: MSO-definable properties are decidable in linear time on constant-treewidth graphs.
    Used in Theorem 5; standard model-checking result.
  • standard math 2-SAT is decidable in linear time (Aspvall et al. 1979).
    Used in Theorem 4's reduction.
  • standard math Planar Monotone 3-SAT is NP-complete (de Berg and Khosravi 2012).
    Base problem for Theorem 3 reduction.
  • standard math Multicolored Independent Set is W[1]-hard parameterized by number of colors (Cygan et al. 2015).
    Base problem for Theorems 2 and 32.
invented entities (2)
  • Core of a tree (Definition 20)
    purpose: A maximal subtree with no vertex adjacent to two leaves; after leaf-merging (Lemma 21) each G1 tree has a core, bounding the number of distinct root states to at most two for P5-free trees.
    Pure graph-theoretic definition introduced as an algorithmic device; no empirical claim, so external falsification does not apply.
  • Split orientation and leafed split orientation (Section 6.3.1)
    purpose: Represents sets of mutually compatible root choices in a tree core via arcs; used to build hardness gadgets in Theorem 32.
    Combinatorial definitions introduced for the parameterized hardness proof; no empirical claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tractable Graph Structures in EFX Orientation." pith.science (2026). https://pith.science/paper/3JYK7IPR

@misc{pith2026250615379,
  author       = {Pith},
  title        = {Pith review of: Tractable Graph Structures in EFX Orientation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3JYK7IPR}},
  note         = {Machine review of arXiv:2506.15379}
}
read the original abstract

Since its introduction, envy-freeness up to any good (EFX) has become a fundamental solution concept in fair division of indivisible goods. Its existence remains elusive -- even for four agents with additive utility functions, it is unknown whether an EFX allocation always exists. Unsurprisingly, restricted settings to delineate tractable and intractable cases have been explored. Christadolou, Fiat et al.[EC'23] introduced the notion of EFX-orientation, where the agents form the vertices of a graph and the items correspond to edges, and an agent values only the items that are incident to it. The goal is to allocate items to one of the adjacent agents while satisfying the EFX condition. Building on the work of Zeng and Mehta'24, which established a sharp complexity threshold based on the structure of the underlying graph -- polynomial-time solvability for bipartite graphs and NP-hardness for graphs with chromatic number at least three -- we further explore the algorithmic landscape of EFX-orientation using parameterized graph algorithms. Specifically, we show that bipartiteness is a surprisingly stringent condition for tractability: EFX orientation is NP-complete even when the valuations are symmetric, binary and the graph is at most two edge-removals away from being bipartite. Moreover, introducing a single non-binary value makes the problem NP-hard even when the graph is only one edge removal away from being bipartite. We further perform a parameterized analysis to examine structures of the underlying graph that enable tractability. In particular, we show that the problem is solvable in linear time on graphs whose treewidth is bounded by a constant and that the complexity of an instance is closely tied to the sizes of acyclic connected components on its one-valued edges.

Figures

Figures reproduced from arXiv: 2506.15379 by the authors.

Figure 1
Figure 1. EFX-orientations where (a) is not nice and (b) is nice. Thick blue are 1-items, thin red are 0-items. 0-items [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. EFX-orientation created during the proof of Theorem 12. Initial graph with two parts 𝐴 and 𝐵, and result after application of Step 1, 2, and 3; the edges that were oriented by the previous step are in color. Observation 6 (1), no vertex in 𝐵 can strongly envy another vertex in 𝐵 since all edges between these vertices are 0-valued. It remains to show that vertices in 𝐴 do not strongly envy vertices in 𝐵. Suppose for … view at source ↗
Figure 3
Figure 3. An illustration of the part of our construction representing the edge [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: (a) The first gadget to ensure min-uncut number 2 in our construction. Note that both of the uncut edges [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Reduction that replaces high 0-degree vertex with an equivalent binary tree. Recall that the thick blue [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: Reduction example for a 3-CNF formula 𝜙 = (𝑥 ∨𝑦 ∨ ¬𝑧) ∧ (𝑧 ∨ ¬𝑟 ∨ 𝑧) ∧ (¬𝑦 ∨ ¬𝑧 ∨ 𝑟). Note that the first clause gadget cannot be rooted in 𝑡1 nor 𝑡2 due to its 0-edges. Rooting the first clause gadget in 𝑥 forbids rooting the variable gadget in ¬𝑥. Due to Proposition …
Figure 7
Figure 7. Figure 7: A figure depicting the reduction from Planar Monotone 3-SAT to planar 0/1 EFX-orientation. The reduced instance is created essentially by a 1-to-1 mapping from the given instance of Planar Monotone 3-SAT so that planarity is maintained. 𝑁1 (𝑢) ⊂ 𝑁1 (𝑣) then if there is…
Figure 8
Figure 8. Figure 8: A graph where its maximal leafed split orientation is smaller than its maximum split orientation. Split [PITH_FULL_IMAGE:figures/full_fig_p017_8.png]
Figure 9
Figure 9. Figure 9: Example graphs that attain extremes with respect to their maximum induced matchings of size [PITH_FULL_IMAGE:figures/full_fig_p027_9.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 23 canonical work pages

  1. [3]

    EFX Allocations: Simplifications and Improvements

    EFX Allocations: Simplifications and Improvements. arXiv:2205.07638 [cs.GT] https://arxiv.org/abs/2205.07638 Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta

    work page Pith review arXiv

  2. [6]

    InProceedings of the 25th ACM Conference on Economics and Computation(New Haven, CT, USA)(EC ’24)

    Pushing the Frontier on Approximate EFX Allocations. InProceedings of the 25th ACM Conference on Economics and Computation(New Haven, CT, USA)(EC ’24). Association for Computing Machinery, New York, NY, USA, 1268–1286. https://doi.org/10.1145/3670865.3673582 Stefan Arnborg, Jens Lagergren, and Detlef Seese

    arXiv

  3. [8]

    Note that this reduction takes linear time and as 2-SAT has a linear-time algorithm, see e.g. [Aspvall et al., 1979], so we can solve theEFX-orientation instance in linear time.□ Proof of Lemma 11 Each tree in𝐺1 has fewer edges equal to the number of vertices minus one so we know that in any orientation at least one agent gets no 1-item. There could be mu...

    work page 1979

  4. [11]

    (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 241). 17:1–17:13. https://doi.org/10.4230/LIPIcs.MFCS.2022.17 Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat

    doi:10.4230/lipics.mfcs.2022.17 2022

  5. [13]

    arXiv:2412.06513 [cs.GT] https://arxiv.org/abs/2412.06513 Eric Budish

    EFX Allocations on Some Multi-graph Classes. arXiv:2412.06513 [cs.GT] https://arxiv.org/abs/2412.06513 Eric Budish

    arXiv

  6. [15]

    Fair Division in a Variable Setting

    Fair Division in a Variable Setting. arXiv:2410.14421 [cs.GT] https://arxiv.org/abs/2410.14421 Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn

    work page Pith review arXiv

  7. [16]

    ACM71, 1, Article 4 (Feb

    EFX Exists for Three Agents.J. ACM71, 1, Article 4 (Feb. 2024), 27 pages. https://doi.org/10.1145/3616009 Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. 2021a. Improving EFX Guarantees through Rainbow Cycle Number. InProceedings of the 22nd ACM Conference on Economics and Computation(Budapest, Hungary)(EC ’21). Associa...

    doi:10.1145/3616009 2021

  8. [18]

    George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa

    Fair Allocation of Indivisible Items with Conflict Graphs.Algorithmica(2022), 1–31. George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. 2023a. Fair allocation in graphs. InProceedings of the 24th ACM Conference on Economics and Computation(London, United Kingdom)(EC ’23). Association for Computing Machinery, New York, NY, USA, 473–4...

    arXiv 2022

Show all 48 references
  1. [19]

    In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)

    On the Nisan-Ronen conjecture. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 839–850. https://doi.org/10.1109/FOCS52979.2021.00086 Vasilis Christoforidis and Christodoulos Santorinaios

    2021

  2. [20]

    InProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence(Jeju, Korea)(IJCAI ’24)

    On the pursuit of EFX for chores: non-existence and approximations. InProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence(Jeju, Korea)(IJCAI ’24). Article 300, 9 pages. https://doi.org/10.24963/ijcai.2024/300 Bruno Courcelle

    doi

  3. [22]

    Comput.39, 1 (2009), 195–259

    The Complexity of Computing a Nash Equilibrium.SIAM J. Comput.39, 1 (2009), 195–259. https://doi.org/10.1137/070699652 Mark de Berg and Amirali Khosravi

    2009 doi

  4. [24]

    arXiv:2409.13616 [cs.GT] https://arxiv.org/abs/2409.13616 Jack Dippel, Max Dupré la Tour, April Niu, Sanjukta Roy, and Adrian Vetta

    EF1 and EFX Orientations. arXiv:2409.13616 [cs.GT] https://arxiv.org/abs/2409.13616 Jack Dippel, Max Dupré la Tour, April Niu, Sanjukta Roy, and Adrian Vetta

    arXiv

  5. [25]

    Jugal Garg, Aniket Murhekar, and John Qin

    Computing fair and efficient allocations with few utility values.Theoretical Computer Science962 (2023), 113932. Jugal Garg, Aniket Murhekar, and John Qin

    2023

  6. [26]

    Proceedings of the AAAI Conference on Artificial Intelligence36, 5 (Jun

    Fair and Efficient Allocations of Chores under Bivalued Preferences. Proceedings of the AAAI Conference on Artificial Intelligence36, 5 (Jun. 2022), 5043–5050. Paul W. Goldberg, Kasper Høgh, and Alexandros Hollender

    2022

  7. [27]

    In Algorithmic Game Theory: 16th International Symposium, SAGT Proceedings

    The Frontier of Intractability for EFX with Two Agents. In Algorithmic Game Theory: 16th International Symposium, SAGT Proceedings. 290–307. https://doi.org/10.1007/978-3-031- 43254-5_17 Jiong Guo, Falk Hüffner, and Rolf Niedermeier

    doi

  8. [31]

    arXiv:2501.13481 [cs.GT] https://arxiv.org/abs/2501.13481 Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida

    A Polynomial-Time Algorithm for EFX Orientations of Chores. arXiv:2501.13481 [cs.GT] https://arxiv.org/abs/2501.13481 Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida

  9. [33]

    InProceedings of the 5th ACM Conference on Electronic Commerce(New York, NY, USA)(EC ’04)

    On approximately fair allocations of indivisible goods. InProceedings of the 5th ACM Conference on Electronic Commerce(New York, NY, USA)(EC ’04). Association for Computing Machinery, New York, NY, USA, 125–131. https://doi.org/10.1145/988772.988792 Jayakrishnan Madathil

  10. [34]

    InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence(Macao, P.R.China)(IJCAI ’23)

    Fair division of a graph into compact bundles. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence(Macao, P.R.China)(IJCAI ’23). Article 316, 9 pages. https://doi.org/10.24963/ijcai. 2023/316 Ryoga Mahara

    doi

  11. [35]

    Extension of Additive Valuations to General Valuations on the Existence of EFX.Math. Oper. Res.49, 2 (May 2024), 1263–1277. https://doi.org/10.1287/moor.2022.0044 Shaily Mishra, Manisha Padala, and Sujit Gujar

    2024

  12. [36]

    https://doi.org/10.1609/aaai.v36i5.20410 Umang Bhaskar and Yeshwant Pandit

    4826–4833. https://doi.org/10.1609/aaai.v36i5.20410 Umang Bhaskar and Yeshwant Pandit

    doi

  13. [37]

    Neeldhara Misra and Aditi Sethia

    Fair Allocation of goods and chores–Tutorial and Survey of Recent Results.arXiv preprint arXiv:2307.10985(2023). Neeldhara Misra and Aditi Sethia

    2023 arXiv

  14. [38]

    InProceedings of Algorithmic Decision Theory - 8th International Conference, ADT (Lecture Notes in Computer Science, Vol

    Envy-Free and Efficient Allocations for Graphical Valuations. InProceedings of Algorithmic Decision Theory - 8th International Conference, ADT (Lecture Notes in Computer Science, Vol. 15248). Springer, 258–272. https://doi.org/10.1007/978-3-031-73903-3_17 Noam Nisan and Amir Ronen

    doi

  15. [39]

    InProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

    Relaxations of Envy-Freeness Over Graphs. InProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS). ACM, 2652–2654. https: //doi.org/10.5555/3545946.3599032 Benjamin Plaut and Tim Roughgarden

    2023

  16. [40]

    https://doi.org/10.1137/19M124397X Ariel D

    Almost Envy-Freeness with General Valuations.SIAM Journal on Discrete Mathematics34, 2 (2020), 1039–1068. https://doi.org/10.1137/19M124397X Ariel D. Procaccia

    2020 doi

  17. [41]

    ACM63, 4 (March 2020),

    Technical perspective: An answer to fair division’s most enigmatic question.Commun. ACM63, 4 (March 2020),

    2020

  18. [44]

    arXiv:2404.13527 [cs.GT] https: //arxiv.org/abs/2404.13527 Yu Zhou, Tianze Wei, Minming Li, and Bo Li

    On the structure of EFX orientations on graphs. arXiv:2404.13527 [cs.GT] https: //arxiv.org/abs/2404.13527 Yu Zhou, Tianze Wei, Minming Li, and Bo Li

    arXiv

  19. [45]

    InProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence(Jeju, Korea)(IJCAI ’24)

    A complete landscape of EFX allocations on graphs: goods, chores and mixed manna. InProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence(Jeju, Korea)(IJCAI ’24). Article 338, 8 pages. https://doi.org/10.24963/ijcai.2024/338 Václav Blažej, S...

    doi

  20. [46]

    Moreover, they initiate work on graphical EFX onchores, also studied by [Hsu and King, 2025]; andmixed manna, which is a generalization of both

    show thatEFX+ orientation always exists and can be found in polynomial-time, drawing a contrast withEFXorientation which may not always exist, [Christodoulou et al ., 2023a]. Moreover, they initiate work on graphical EFX onchores, also studied by [Hsu and King, 2025]; andmixed...

    2025

  21. [47]

    Charity.Caragiannis et al

    also study EF1 allocation in the multi-graph setting in relation to problem of EF1 restoration. Charity.Caragiannis et al. [2019a] initiated the research of finding desirable EFX allocations that satisfy certain properties, such as maximizing the Nash social welfare, where som...

    2022

  22. [48]

    Chores.Work on EFX allocation for chores has caught steam

    showing that for four agents, giving at most one good to charity is enough. Chores.Work on EFX allocation for chores has caught steam. Recently, [Christoforidis and Santori- naios, 2024] showed that an EFX allocation for chores need not exist under general cost functions. They...

    2024

  23. [118]

    https://doi.org/10.1145/3382131 M. S. Ramanujan and Saket Saurabh

    doi

  24. [1979]

    A linear-time algorithm for testing the truth of certain quantified boolean formulas.Inform. Process. Lett.8, 3 (1979), 121–123. https://doi.org/10.1016/0020-0190(79)90002-4 Haris Aziz, Péter Biró, Jérôme Lang, Julien Lesca, and Jérôme Monnot

    1979 doi

  25. [1990]

    The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs.Inf. Comput.85, 1 (1990), 12–75. https://doi.org/10.1016/0890-5401(90)90043-H Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Sa...

    1990 doi

  26. [1991]

    Bengt Aspvall, Michael F

    Easy problems for tree-decomposable graphs.Journal of Algorithms 12 (1991), 308–340. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan

    1991

  27. [2001]

    https://doi.org/10.1006/game.1999.0790 Václav Blažej, Sushmita Gupta, M.S

    Algorithmic Mechanism Design.Games and Economic Behavior35, 1 (2001), 166–196. https://doi.org/10.1006/game.1999.0790 Václav Blažej, Sushmita Gupta, M.S. Ramanujan, and Peter Strulo20 Justin Payan, Rik Sengupta, and Vignesh Viswanathan

    2001

  28. [2004]

    InParameterized and Exact Computation, First International Workshop, IWPEC 2004, Proceedings (Lecture Notes in Computer Science, Vol

    A Structural View on Parameterizing Problems: Distance from Triviality. InParameterized and Exact Computation, First International Workshop, IWPEC 2004, Proceedings (Lecture Notes in Computer Science, Vol. 3162), Rodney G. Downey, Michael R. Fellows, and Frank K. H. A. Dehne (...

    2004 doi

  29. [2009]

    ACM 56, 3, Article 14 (May 2009), 57 pages

    Settling the complexity of computing two-player Nash equilibria.J. ACM 56, 3, Article 14 (May 2009), 57 pages. https://doi.org/10.1145/1516512.1516516 Nina Chiarelli, Matjaž Krnc, Martin Milanič, Ulrich Pferschy, Nevena Pivač, and Joachim Schauer

    2009

  30. [2011]

    Journal of Political Economy119, 6 (2011), 1061–1103

    The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy119, 6 (2011), 1061–1103. https://EconPapers.repec.org/RePEc:ucp:jpolec:doi:10.1086/664613 Ioannis Caragiannis, Nick Gravin, and Xin Huang. 2019a. Envy-Fre...

    2011

  31. [2012]

    https://doi.org/10.1142/S0218195912500045 Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak

    Optimal Binary Space Partitions for Segments in the Plane.International Journal of Computational Geometry & Applications22, 03 (2012), 187–205. https://doi.org/10.1142/S0218195912500045 Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak

    2012 doi

  32. [2015]

    Intell.227 (2015), 71–92

    Fair assignment of indivisible objects under ordinal preferences.Artif. Intell.227 (2015), 71–92. https://doi.org/10.1016/J.ARTINT.2015.06.002 Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma

    2015 doi

  33. [2016]

    Comput.45, 4 (2016), 1377–1411

    Half-integrality, LP-branching, and FPT Algorithms.SIAM J. Comput.45, 4 (2016), 1377–1411. https://doi.org/10.1137/140962838 R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi

    2016 doi

  34. [2017]

    Algorithms13, 4 (2017), 46:1–46:25

    Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts.ACM Trans. Algorithms13, 4 (2017), 46:1–46:25. https://doi.org/10.1145/3128600 Jinghan A Zeng and Ruta Mehta

    2017 doi

  35. [2019]

    Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh

    Efficient reallocation under additive and responsive preferences.Theoretical Computer Science790 (2019), 1–15. Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh

    2019

  36. [2020]

    Proceedings of the AAAI Conference on Artificial Intelligence34 (04 2020), 2014–2021

    Fair Division Through Information Withholding. Proceedings of the AAAI Conference on Artificial Intelligence34 (04 2020), 2014–2021. https://doi.org/10.1609/aaai.v34i02.5573 Kevin Hsu and Valerie King

    2020 doi

  37. [2022]

    InCombinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings (Lecture Notes in Computer Science, Vol

    Distance from Triviality 2.0: Hybrid Parameterizations. InCombinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings (Lecture Notes in Computer Science, Vol. 13270), Cristina Bazgan and Henning Fernau (Eds.). Springer, 3–20....

    2022 doi

  38. [2023]

    Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa

    Fair division of indivisible goods: Recent progress and open questions.Artificial Intelligence322 (2023), 103965. Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa

    2023

  39. [2024]

    arXiv:2410.17002 [cs.GT] https://arxiv.org/abs/2410.17002 Akanksha Agrawal and M

    EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture. arXiv:2410.17002 [cs.GT] https://arxiv.org/abs/2410.17002 Akanksha Agrawal and M. S. Ramanujan

  40. [2025]

    2025), 29 pages

    Budget-feasible egalitarian allocation of conflicting jobs.Autonomous Agents and Multi-Agent Systems39, 1 (Jan. 2025), 29 pages. https://doi.org/10.1007/s10458-024-09686-1 Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, Hejun Wang, and Lirong Xia

    2025 doi

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.