Pith. sign in

REVIEW 4 major objections 5 minor 43 references

On the existence of EFX allocations in multigraphs

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Three graph conditions guarantee EFX fair division in multigraphs.

desk verdict New EFX existence results in multigraphs, but the advertised general theorems rest on an incomplete proof roadmap in Section 4. read the letter →

arxiv 2502.09777 v1 pith:PIEQBNTM submitted 2025-02-13 cs.GT cs.AI

Alkmini Sgouritsa , Minas Marios Sotiriou This is my paper · ORCID
classification cs.GTcs.AI MSC 91B32
keywords EFXallocationsfairdivisionmultigraphsenvy-freeuptoanygoodgeneralmonotonevaluationscut-and-chooseprotocolgraphicalindivisiblegoods
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 addresses the main open problem in fair division of indivisible goods: whether envy-free-up-to-any-good (EFX) allocations always exist. In the multigraph model, agents are vertices, goods are edges, and each agent only cares about incident edges. The paper proves three new existence theorems for general monotone valuations: EFX allocations always exist when the multigraph is bipartite, when every agent has at most ceil(n/4)-1 neighbors, or when the shortest cycle without parallel edges has length at least 6. These results extend the known frontier beyond simple graphs and beyond multigraphs with restricted additive valuations. The proof is constructive rather than efficient, relying on a cut-and-choose partitioning of parallel edges and a three-stage allocation procedure.

What carries the argument

The central primitive is the EFX-cut: for the parallel edges between two vertices, one vertex partitions them into two bundles so that, whichever bundle that vertex receives, removing any single good from the other bundle leaves a bundle no better than its own. The paper also uses the 'most valued set of potentially unallocated non-parallel bundles' (denoted UNP), which captures the best bundle an agent could form from unallocated relevant goods together with their own bundle, subject to containing no parallel bundles. These primitives feed a three-stage procedure: build a partial EFX orientation with controlled envy, run an envy-reduction loop that preserves the non-envied status of every already non-envied agent, and finally park every leftover bundle at a non-envied agent that is not an endpoint. In the bounded-neighbor case, the initial allocation comes from a maximum-weight matching in a bipartite graph between agents and their top-two EFX-cut bundles, with Hall's theorem ensuring the matching exists.

What would settle it

A single counterexample would refute the claim: exhibit a bipartite multigraph with general monotone valuations in which every complete allocation has an agent who, after removal of any one good from another agent's bundle, still strictly envies that bundle. Since the paper's construction is explicit, one could also run it on small instances (say up to 6 vertices with up to 3 parallel edges per pair and valuations from a finite set) and check whether the final parking step ever fails to find a non-envied non-endpoint; a failure would identify a false lemma.

Watch

Extended reading notes

Core claim

The paper establishes that, in a multigraph where vertices are agents and edges are indivisible goods, a complete EFX allocation exists under general monotone valuations whenever the multigraph satisfies one of three structural conditions: (a) it is bipartite, (b) every vertex has at most ceil(n/4)-1 neighbors, or (c) every cycle consisting of non-parallel edges has length at least 6. The construction starts with a partial EFX orientation in which no agent prefers an unallocated edge or bundle to their own bundle, then repeatedly reallocates bundles so that any remaining unallocated goods can be given to non-envied agents who are not endpoints of those goods. The graph conditions guarantee that enough such 'parking' agents exist. Multiple parallel edges are handled by partitioning them into bundles via EFX-cuts, rather than treating each edge independently.

Load-bearing premise

The load-bearing premise is that the simplifying reductions are harmless: giving a degree-1 vertex its only incident edge, and adding zero-valued dummy edges so every adjacent pair of vertices has at least two parallel edges, do not change whether an EFX allocation of the original multigraph exists.

Editorial extensions

If this is right

  • Every bipartite multigraph, with any number of parallel edges, admits an EFX allocation under arbitrary monotone valuations.
  • Every multigraph in which each vertex has at most ceil(n/4)-1 neighbors admits an EFX allocation, covering all sufficiently sparse-neighborhood multigraphs regardless of parallel edges.
  • Every multigraph whose non-parallel cycles all have length at least 6 admits an EFX allocation, including all multicycles except those of length 3 and 5.
  • The construction shows that leftover edges need not be assigned to their endpoints; they can be parked at non-envied non-adjacent vertices, which is the key reason the graph restrictions are needed.
  • The bipartite case is settled for both additive and general monotone valuations, and the remaining open gap for general multigraphs is localized to small non-parallel cycles.

Reading between the lines

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

  • The real structural requirement in each proof is that there be enough non-envied vertices to park leftover bundles without creating cycles of envy, so other graph families with similar domination properties may also admit EFX allocations.
  • Because the cycle-length condition is obstructed only by triangles and 5-cycles of non-parallel edges, a natural next target is handling exactly those two cycle lengths, which might lead to EFX for all multigraphs.
  • The cut-and-choose primitive is not known to be polynomial, so these existence results do not by themselves give efficient algorithms; efficient or approximate EFX algorithms on these classes are a natural extension.
  • A testable extension is to run the construction on small random multigraphs with additive valuations to see whether the number of unallocated bundles ever exceeds the available non-envied parking vertices, which would pinpoint where the proof's slack lies.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper studies the existence of envy-free-up-to-any-good (EFX) allocations in multigraphs under general monotone valuations, where agents are vertices, goods are edges, and each agent values only its incident edges. The main theorems (Theorems 1-3) claim that an EFX allocation always exists if the multigraph is bipartite, or if every agent has at most ceil(n/4)-1 neighbors, or if the shortest cycle with non-parallel edges has length at least 6. The proof follows a three-step framework: an initial EFX orientation with structural properties, an envy-reduction algorithm, and a final allocation of unallocated bundles to non-endpoint non-envied vertices. Section 3 presents a complete proof for the special case of at most two parallel edges per pair of vertices, while Section 4, titled 'Many Parallel Edges', is presented as a proof roadmap for the general case.

Significance. If fully established, these results would generalize the simple-graph EFX result of Christodoulou et al. [19] and the restricted-additive multigraph result of Kaviani et al. [29] to general monotone valuations for three classes of multigraphs, and would improve on concurrent work for bipartite multigraphs and for graphs with long non-parallel cycles. The three-step framework is original and the special case of at most two parallel edges (Section 3) is argued carefully, with a sound matching-weight argument in Lemma 3.7 and a coherent final-allocation proof in Lemma 3.12. However, the general-case proofs in Section 4 are incomplete in several load-bearing places, so the theorems as stated for arbitrary parallel multiplicity are not yet fully supported.

major comments (4)
  1. [Section 4.1.2, Lemma 4.9] The proof of Property (1) contains an unsubstantiated assertion: it states that 'if i envies j in XM, then (i,j) ∈ PVCP and j should have received B1_i(j)' without a derivation. For pairs (i,j) not in PVCP, Lemma 4.6 only guarantees that i and j have different most-valued bundles among the 3-partition; it does not rule out the case where j receives i's most-preferred bundle P1 while i receives a strictly lower-valued bundle. Moreover, even if j receives P1, EFX requires vi(Xi) ≥ vi(P1 \ {e}) for every e ∈ P1, and this does not follow from the EFX-cut used in Lemma 4.6, which gives a guarantee between P1 and P2, not between P2 \ {g} and P1. A matching-exchange argument or a counterexample is needed; this gap is load-bearing for Theorem 2 in the general parallel-edge case.
  2. [Section 4.2, Algorithm 8 / Lemma 4.17] The proof relies on Observation 2.1 to assert that the only bundle released is between i and pi(X), but Observation 2.1 is stated and proved for single-edge orientations. The manuscript does not prove that in the bundle setting an envied vertex's bundle cannot be a union of bundles from several neighbors under an EFX orientation, nor does it justify that setting Xpi(X) ← ∅ in line 7 preserves the invariant that every Xi is a union of bundles from Bi. These points are needed for the correctness of Step 2 in all three theorems when extended to bundles.
  3. [Section 4.1.3, Lemma 4.12 / Algorithm 7] The termination proof and the preservation of Properties (1)-(2) after shrinking the sets Baux_i are only sketched. Specifically, the claim that vertex b remains non-envied after Baux_b is updated relies on Observation 4.13, but the proof of that observation only covers the original Baux sets and does not explain why the same reasoning remains valid after the sets are shrunk in lines 12-15. It is also not shown that Property (2) holds with respect to the redefined U Baux_i(X) after the update. These are load-bearing for Theorem 3 in the general case.
  4. [Section 4, general] The paper opens Section 4 with 'We provide a proof roadmap' and defers several arguments from Section 3 to the general case by saying they are 'essentially the same' or 'exactly the same' (e.g., the transition from Claim 3.13 to Claim 4.20, and Step 2's Algorithm 8 relative to Algorithm 4). For a journal publication, the general case must either be proved in full or the theorems should be restricted to the at-most-two-parallel-edges case. As written, Theorems 1-3 for arbitrary parallel multiplicity are not fully established by the provided proofs.
minor comments (5)
  1. [Section 2, 'At least degree 2 in G'] The reductions for degree-1 vertices and for adding dummy zero-value edges are stated as 'w.l.o.g.' but are not formalized. Please add a short argument showing that an EFX allocation in the augmented instance (with degree-1 vertices pre-allocated or dummy edges added) translates back to an EFX allocation in the original multigraph.
  2. [Section 4, Definition 4.7] The sentence 'Note that all edges between two endpoints are partitioned in a single way, i.e., the vertex in side B EFX-cuts' appears to be copied from the bipartite case and is confusing in the general setting, where there is no distinguished side B.
  3. [Section 4.1.2, Lemma 4.6] In the proof, the phrase 'If P2 contains more than one goods' should be 'more than one good', and the argument that vi({g}) ≤ vi(P1) would benefit from an explicit sentence explaining that it follows from the EFX-cut property for i when |P2| > 1.
  4. [Section 4.1.3, Algorithm 7, line 24] The condition 'if Br_ij ∈ Xi ∪ Xj, for some r ∈ {i,j}' is hard to parse; please clarify the index convention and the intended condition.
  5. [References] Reference [29] (Kaviani et al., WINE 2024) is missing page numbers or an article number; please complete the bibliographic details.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorems 1-3 are new existence proofs built on an external two-agent cut-and-choose black box, with the authors' prior graph-EFX paper used only as background and algorithmic template.

full rationale

The paper's central claims (Theorems 1-3) assert EFX existence for three structural classes of multigraphs. The proof is a three-step construction (initial allocation, envy reduction, final allocation) whose lemmas are proved in the paper itself (e.g., Lemmas 3.4, 3.7, 3.9, 3.12 for the at-most-two-parallel-edges case; Lemmas 4.3, 4.6, 4.9, 4.12, 4.17, 4.19 for the general case). The only external, load-bearing ingredient is the two-agent cut-and-choose protocol of Plaut and Roughgarden [33], which is an independent published result and is not defined in terms of the target existence theorems. Hall's theorem is also used independently. The self-citation to Christodoulou et al. [19] (which shares an author with this paper) provides the graph-valuation model and the high-level algorithmic pattern, but the multigraph theorems are not derived by invoking the simple-graph theorem; they are proven through new bundle-partition, matching, and parking arguments. No quantity is fitted to a subset of the data and then renamed as a prediction, and no definition presupposes the existence of the EFX allocation that is being proved. The paper's own admission in Section 4 that it provides 'a proof roadmap' indicates some steps (e.g., the PVCP claim in Lemma 4.9, the 'essentially the same' assertion in Step 2, and the termination/shrinking arguments in Algorithm 7) are sketched rather than fully formalized; however, an incomplete proof is a rigor concern, not a circularity, because the assertions do not reduce the conclusion to its assumptions by construction. Thus the derivation chain is not circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The proof imports the two-agent EFX-cut existence theorem, Hall's theorem, and a few modeling assumptions (minimum degree at least 2, dummy edges). These are all standard or explicitly stated; no free parameters are fitted, and the only invented entity is the technical dummy-edge device.

assumptions (4)
  • standard math Two-agent cut-and-choose: for any two agents with general monotone valuations and any set of goods, there exists a partition into two bundles such that whichever bundle either agent receives, they are EFX-satisfied against the other (Plaut and Roughgarden [33]).
    Invoked throughout Sections 3 and 4 to partition parallel edges into EFX-cut bundles.
  • standard math Hall's theorem guarantees an A-perfect matching in the auxiliary bipartite graph H(G).
    Used in Observation 3.6 and Section 4.1.2 to ensure a matching where every vertex receives one bundle.
  • domain assumption W.l.o.g. the multigraph has minimum degree at least 2, because degree-0 and degree-1 vertices can be pre-allocated without breaking EFX.
    Stated in Section 2; used to ensure every vertex has at least two candidate edges for the cut-and-choose and matching constructions.
  • ad hoc to paper Zero-value dummy edges can be added between adjacent vertices that share only one edge, without changing the EFX question.
    Introduced in Section 3 to ensure every adjacent pair has two parallel edges so the cut-and-choose partition is well-defined; the dummy edge has value 0 for both endpoints.
invented entities (1)
  • Dummy zero-value edge
    purpose: Ensures every pair of adjacent vertices has at least two parallel edges, making the cut-and-choose partition well-defined in Section 3.
    This is a technical proof device, not a physical postulate. It has zero value for both endpoints, so it does not affect any agent's preferences; the paper states its addition as w.l.o.g. without giving an explicit EFX-preserving translation back to the original instance.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the existence of EFX allocations in multigraphs." pith.science (2026). https://pith.science/paper/PIEQBNTM

@misc{pith2026250209777,
  author       = {Pith},
  title        = {Pith review of: On the existence of EFX allocations in multigraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PIEQBNTM}},
  note         = {Machine review of arXiv:2502.09777}
}
abstract

We study the problem of "fairly" dividing indivisible goods to several agents that have valuation set functions over the sets of goods. As fair we consider the allocations that are envy-free up to any good (EFX), i.e., no agent envies any proper subset of the goods given to any other agent. The existence or not of EFX allocations is a major open problem in Fair Division, and there are only positive results for special cases. [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] introduced a restriction on the agents' valuations according to a graph structure: the vertices correspond to agents and the edges to goods, and each vertex/agent has zero marginal value (or in other words, they are indifferent) for the edges/goods that are not adjacent to them. The existence of EFX allocations has been shown for simple graphs with general monotone valuations [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023], and for multigraphs for restricted additive valuations [Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei 2024]. In this work, we push the state-of-the-art further, and show that the EFX allocations always exists in multigraphs and general monotone valuations if any of the following three conditions hold: either (a) the multigraph is bipartite, or (b) each agent has at most $\lceil \frac{n}{4} \rceil -1$ neighbors, where $n$ is the total number of agents, or (c) the shortest cycle with non-parallel edges has length at least 6.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 23 canonical work pages

  1. [19]

    Fair allocation in graphs

    George Christodoulou, Amos Fiat, Elias Koutsoupias, and Alkmini Sgouritsa. Fair allocation in graphs. In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, pages 473–488. ACM, 2023. doi:10.1145/3580507.3597764. URL https...

    work page arXiv 2023

  2. [29]

    Almost envy-free allocation of indivisible goods: A tale of two valuations

    Alireza Kaviani, Masoud Seddighin, and AmirMohammad Shahrezaei. Almost envy-free allocation of indivisible goods: A tale of two valuations. In Web and Internet Economics - 20th International Conference, WINE 2024, Edinburgh, United Kingdom, December 2-5

    work page 2024

  3. [1]

    Efx allocations and orientations on bipartite multi-graphs: A complete picture, 2024

    Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi. Efx allocations and orientations on bipartite multi-graphs: A complete picture, 2024. URL https://arxiv.org/abs/2410.17002

    arXiv 2024

  4. [3]

    Multiple birds with one stone: Beat- ing 1/2 for EFX and GMMS via envy cycle elimination

    Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beat- ing 1/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci. , 841:94–109, 2020. doi:10.1016/J.TCS.2020.07.006. URL https://doi.org/10.1016/j.tcs.2020.07.006

    doi:10.1016/j.tcs.2020.07.006 2020

  5. [4]

    V oudouris

    Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. V oudouris. Maximum nash welfare and other stories about EFX. Theor. Comput. Sci. , 863:69–85, 2021. doi:10.1016/J.TCS.2021.02.020. URL https://doi.org/10.1016/j.tcs.2021.02.020

    doi:10.1016/j.tcs.2021.02.020 2021

  6. [5]

    V oudouris, and Xiaowei Wu

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. V oudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions.Artif. Intell., 322:103965, 2023. doi:10.1016/J.ARTINT.2023.103965. URL https://doi.org/10.1016/j.artint.2023. 103965

    work page arXiv 2023

  7. [6]

    Pushing the frontier on approximate efx allocations

    Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pushing the frontier on approximate efx allocations. In Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, United States of America, July 8 - 11, 2024, 2024

    work page 2024

  8. [7]

    A discrete and bounded envy-free cake cutting protocol for four agents

    Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for four agents. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. ACM, 2016. doi:10.1145/2897518.2897522. URL https://doi.org/10.1145/2897518.2897522

    work page arXiv 2016

Show all 43 references
  1. [8]

    Fair and truthful mechanisms for dichotomous valuations

    Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair and truthful mechanisms for dichotomous valuations. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innova- tive Applications of Artificial Intelligence, IAAI 2021, The Eleventh...

    2021 doi

  2. [9]

    Fixed-point cycles and approxi- mate EFX allocations

    Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. Fixed-point cycles and approxi- mate EFX allocations. In Stefan Szeider, Robert Ganian, and Alexandra Silva, editors, 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, Augus...

    2022 doi

  3. [10]

    Almost full EFX exists for four agents

    Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full EFX exists for four agents. In Thirty- Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Appli- cations of Artificial Intelligence, IAAI 2022, The Twelveth Sympo...

    2022 doi

  4. [11]

    Efx allocations on some multi-graph classes, 2024

    Umang Bhaskar and Yeshwant Pandit. Efx allocations on some multi-graph classes, 2024. URL https: //arxiv.org/abs/2412.06513

    2024 arXiv

  5. [12]

    The combinatorial assignment problem: approximate competitive equilibrium from equal incomes

    Eric Budish. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. In Moshe Dror and Greys Sosic, editors, Proceedings of the Behavioral and Quantitative Game Theory - Conference on Future Directions, BQGT ’10, Newport Beach, California,...

    2010

  6. [13]

    The multi-unit assignment problem: Theory and evidence from course allocation at harvard

    Eric Budish and Estelle Cantillon. The multi-unit assignment problem: Theory and evidence from course allocation at harvard. American Economic Review, 102, 01 2010. doi:10.1257/aer.102.5.2237

    2010 doi

  7. [14]

    Envy-freeness up to any item with high nash welfare: The virtue of donating items

    Ioannis Caragiannis, Nick Gravin, and Xin Huang. Envy-freeness up to any item with high nash welfare: The virtue of donating items. In Anna R. Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Ph...

    2019

  8. [15]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Trans. Economics and Comput., 7(3):12:1–12:32, 2019. doi:10.1145/3355902. URL https://doi.org/10.1145/3355902

    2019 doi

  9. [16]

    Improving EFX guarantees through rainbow cycle number

    Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra. Improving EFX guarantees through rainbow cycle number. In Péter Biró, Shuchi Chawla, and Federico Echenique, editors, EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hun...

    2021

  10. [17]

    A little charity guarantees almost envy-freeness

    Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness. SIAM J. Comput. , 50(4):1336–1358, 2021. doi:10.1137/20M1359134. URL https: //doi.org/10.1137/20M1359134

    2021 doi

  11. [18]

    EFX exists for three agents

    Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents. J. ACM, 71(1):4:1–4:27,

  12. [20]

    On the pursuit of efx for chores: Non-existence and approximations

    Vasilis Christoforidis and Christodoulos Santorinaios. On the pursuit of efx for chores: Non-existence and approximations. In Kate Larson, editor, Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, pages 2713–2721. Internationa...

    2024 doi

  13. [21]

    Ef1 and efx orientations, 2024

    Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, and Viktoriia Korchemna. Ef1 and efx orientations, 2024. URL https://arxiv.org/abs/2409.13616

    2024 arXiv

  14. [22]

    Resource allocation and the public sector

    Duncan Karl Foley. Resource allocation and the public sector. Yale University, 1966

    1966

  15. [23]

    Gamow and M

    G. Gamow and M. Stern. Puzzle-math. Viking Press, 1958. ISBN 9780670583355. URL https://books. google.gr/books?id=_vdytgAACAAJ

    1958

  16. [24]

    Goldberg, Kasper Høgh, and Alexandros Hollender

    Paul W. Goldberg, Kasper Høgh, and Alexandros Hollender. The frontier of intractability for EFX with two agents. In Argyrios Deligkas and Aris Filos-Ratsikas, editors, Algorithmic Game Theory - 16th International Symposium, SAGT 2023, Egham, UK, September 4-7, 2023, Proceeding...

    2023 doi

  17. [25]

    P. Hall. On representatives of subsets. Journal of the London Mathematical Society , s1-10(1):26–30, 1935. doi:https://doi.org/10.1112/jlms/s1-10.37.26. URL https://londmathsoc.onlinelibrary.wiley.com/ doi/abs/10.1112/jlms/s1-10.37.26

    1935 doi

  18. [26]

    Fair and efficient allocations under lexicographic preferences

    Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Fair and efficient allocations under lexicographic preferences. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI ...

    2021 doi

  19. [27]

    Efx orientations of multigraphs, 2024

    Kevin Hsu. Efx orientations of multigraphs, 2024. URL https://arxiv.org/abs/2410.12039

    2024

  20. [28]

    Rainbow cycle number and EFX allocations: (almost) closing the gap

    Shayan Chashm Jahan, Masoud Seddighin, Seyed Mohammad Seyed Javadi, and Mohammad Sharifi. Rainbow cycle number and EFX allocations: (almost) closing the gap. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th Au...

    2023

  21. [30]

    Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

    Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Jack S. Breese, Joan Feigenbaum, and Margo I. Seltzer, editors, Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, US...

    2004

  22. [31]

    Extension of additive valuations to general valuations on the existence of EFX.Math

    Ryoga Mahara. Extension of additive valuations to general valuations on the existence of EFX.Math. Oper. Res., 49 (2):1263–1277, 2024. doi:10.1287/MOOR.2022.0044. URL https://doi.org/10.1287/moor.2022.0044. 25

    2024

  23. [32]

    Improved EFX approximation guarantees under ordinal- based assumptions

    Evangelos Markakis and Christodoulos Santorinaios. Improved EFX approximation guarantees under ordinal- based assumptions. In Noa Agmon, Bo An, Alessandro Ricci, and William Yeoh, editors, Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Sys...

    2023

  24. [33]

    Almost envy-freeness with general valuations

    Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. SIAM J. Discret. Math., 34 (2):1039–1068, 2020. doi:10.1137/19M124397X. URL https://doi.org/10.1137/19M124397X

    2020 doi

  25. [34]

    Procaccia

    Ariel D. Procaccia. An answer to fair division’s most enigmatic question: technical perspective. Commun. ACM, 63(4):118, 2020. doi:10.1145/3382131. URL https://doi.org/10.1145/3382131

    2020 doi

  26. [35]

    Steihaus

    H. Steihaus. The problem of fair division. Econometrica, 16:101–104, 1948

    1948

  27. [36]

    Stromquist

    Walter R. Stromquist. How to cut a cake fairly. American Mathematical Monthly, 87:640–644, 1980. URL https://doi.org/10.1080/00029890.1980.11995109

    1980

  28. [37]

    Equity, envy, and efficiency

    Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory , 9(1):63–91, 1974. ISSN 0022-0531. doi:https://doi.org/10.1016/0022-0531(74)90075-1. URL https://www.sciencedirect.com/ science/article/pii/0022053174900751

    1974

  29. [38]

    Dividing a cake fairly

    D.R Woodall. Dividing a cake fairly. Journal of Mathematical Analysis and Applications, 78(1):233–247, 1980. ISSN 0022-247X. doi:https://doi.org/10.1016/0022-247X(80)90225-5. URL https://www.sciencedirect. com/science/article/pii/0022247X80902255

    1980

  30. [39]

    On the structure of envy-free orientations on graphs

    Jinghan A Zeng and Ruta Mehta. On the structure of envy-free orientations on graphs. CoRR, abs/2404.13527,

    arXiv

  31. [40]

    A complete landscape of efx allocations on graphs: Goods, chores and mixed manna

    Yu Zhou, Tianze Wei, Minming Li, and Bo Li. A complete landscape of efx allocations on graphs: Goods, chores and mixed manna. In Kate Larson, editor, Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24, pages 3049–3056, Jeju, Kor...

    2024 doi

  32. [43]

    URLhttps://doi.org/10.48550/arXiv.2404.13527

    doi:10.48550/ARXIV .2404.13527. URLhttps://doi.org/10.48550/arXiv.2404.13527

    doi arXiv

  33. [2004]

    URL https://doi.org/10.1145/988772.988792

    doi:10.1145/988772.988792. URL https://doi.org/10.1145/988772.988792

  34. [2024]

    URL https://doi.org/10.1145/3616009

    doi:10.1145/3616009. URL https://doi.org/10.1145/3616009

    doi

  35. [2580]

    doi:10.24963/IJCAI.2023/286

    ijcai.org, 2023. doi:10.24963/IJCAI.2023/286. URL https://doi.org/10.24963/ijcai.2023/286

    2023 doi

Pith tools

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