Pith. sign in

REVIEW 2 major objections 6 minor 2 cited by

Almost and Approximate EFX for Few Types of Agents

T0 review · 2 major / 6 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read For instances with at most four types of additive valuations, a complete 2/3-EFX allocation always exists for any number of agents, and with k types a (1−ε)-EFX allocation can leave only about √(k/ε) goods in charity.

desk verdict The charity bound and the corrections to Amanatidis et al. are solid, but the four-type 2/3-EFX theorem has a genuine proof gap in Case 3.2 that the current argument does not fill. read the letter →

arxiv 2508.15380 v1 pith:ZYQH5FEP submitted 2025-08-21 cs.GT cs.DS

Vishwa Prakash HV , Ruta Mehta , Prajakta Nimbhorkar This is my paper · ORCID
classification cs.GTcs.DS MSC 91B3268W25
keywords fairdivisionindivisiblegoodsEFX2/3-EFXadditivevaluationsfewtypesofagentswithcharityrainbowcyclenumber
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

The paper proves that envy-freeness up to any good, the standard fairness guarantee for indivisible goods, can be approximated in settings with few distinct preference types. Its main result is that for any number of agents whose additive valuations fall into at most four groups, a complete allocation exists in which every agent is $\frac{2}{3}$-EFX: each agent prefers her own bundle to any other agent's bundle with its single best item removed, up to a $\frac{2}{3}$ factor. This extends the previously known three-type guarantee to four types. A second result shows that with $k$ types, a $(1-\varepsilon)$-EFX allocation can leave only about $\sqrt{k/\varepsilon}$ goods unallocated, replacing the previous charity bound's dependence on the number of agents $n$ by the number of types $k$. These are practical settings because demographic grouping, public housing categories, and similar applications naturally produce few preference types.

What carries the argument

The object carrying the argument is the 3PA+-TYPES algorithm: the property-preserving partial-allocation algorithm of [5] modified by Steps 9.1–9.4, which add a Pseudo-Cycle-Resolution subroutine. The subroutine shifts bundles along an envy path that passes through leading agents only, and then reorders bundles within each group to preserve the ordering invariant; this is what lets the algorithm allocate the contested critical goods when a single source exists. Around this sits the standard machinery of leading agents, the ordering invariant, reduced and enhanced envy graphs, and the critical-good completion lemma of [19], plus, for the charity result, the rainbow cycle number of [9].

What would settle it

Construct a four-type instance that reaches Case 3.2 of the proof—one source, at least two agents in the source's group, and three critical goods—where $|X_{d2}|=1$ and $(d_1,d_2)$ is an edge of the enhanced envy graph, while the stated inequality $v_d((X_{d1} \cup C) \setminus g_1) < \frac{2}{3} v_d(X_{d2})$ holds; then run Algorithm 4 and check whether any agent in groups A, B, or C fails to be $\frac{2}{3}$-EFX toward $d_2$. A single such instance, or an exhaustive search of small four-type instances finding no complete $\frac{2}{3}$-EFX allocation, would refute the theorem.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is Theorem 3: every additive-valuation instance with at most four valuation types admits a complete $\frac{2}{3}$-EFX allocation, no matter how many agents there are. The proof extends the 3PA+ algorithm of [5] with extra steps (9.1–9.4) that handle the single-source, three-critical-goods configuration, using a 'pseudo-cycle' swap among leading agents of the four groups to redistribute bundles without breaking the $\frac{2}{3}$-EFX property. Theorem 4 then gives a $(1-\varepsilon)$-EFX allocation with $\tilde{O}(\sqrt{k/\varepsilon})$ charity for $k$ types, by building a rainbow-cycle-free 'champion graph' on leading agents and invoking the $O(d \log d)$ bound on the rainbow cycle number. Along the way the

Load-bearing premise

The four-types theorem rests on the claim that in the single-source, three-critical-goods case, the valuation inequalities in the proof force the algorithm's Step 9.2 condition to hold; that implication is asserted but not established.

Editorial extensions

If this is right

  • Complete 2/3-EFX is now guaranteed for any number of agents with at most four distinct additive valuations, not just three.
  • For k valuation types, one can compute a (1−ε)-EFX allocation that leaves out O~(√(k/ε)) goods, with the charity bound independent of the total number of agents.
  • The corrected analysis of the 3PA+ algorithm—termination via a product potential and the use of the enhanced envy graph in path resolution—restores the previously claimed seven-agent 2/3-EFX guarantee.
  • The non-degeneracy assumption is harmless for α-EFX, so the existence results apply to degenerate instances as well.

Reading between the lines

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

  • If the gap in Theorem 3's Case 3.2 can be closed by a stronger argument, the pseudo-cycle technique could extend to more than four types; the paper's own bottleneck note about critical goods suggests the current construction is near its limit.
  • The charity bound's dependence on k rather than n implies that for large populations with few preference types, the number of unallocated goods stays manageable—exactly the regime in which the result has practical force.
  • A natural test is to implement the 3PA+-TYPES algorithm and search random four-type instances for violations of the Step 9.2 implication, which would turn the suspected proof gap into a concrete counterexample if it exists.
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

2 major / 6 minor

Summary. The paper studies approximate envy-freeness up to any good (α-EFX) for indivisible-goods allocation with additive valuations, focusing on instances with few valuation types. The first contribution is Theorem 3, which claims that for any number of agents with at most four distinct additive valuations, Algorithm 4 (FewTypesAllocate) computes a complete 2/3-EFX allocation. The algorithm modifies the 3PA+ algorithm of Amanatidis et al. with new steps 9.1–9.4 and a Pseudo-Cycle-Resolution subroutine; termination is argued via a configuration-repetition argument. The second contribution is Theorem 4, which claims that for any number of agents with at most k distinct valuations there is a (1−ε)-EFX allocation with charity size O~(√(k/ε)), by adapting the rainbow-cycle-number framework of Chaudhury et al. to a graph on leading agents. The paper also reports and corrects an error in the termination proof of the Envy-Cycle-Elimination subroutine in [5], giving a counterexample and a potential-function proof.

Significance. If both main theorems are correct, the paper makes a significant advance. Theorem 3 would give the first complete 2/3-EFX guarantee for an unrestricted number of agents under a type restriction weaker than the known three-type exact-EFX result. Theorem 4 would improve the charity bound from O~(√(n/ε)) to O~(√(k/ε)) when the number of valuation types is small, which is a natural and useful parameter. The paper also contains a concrete, checkable correction to a published proof: the counterexample in Appendix C genuinely shows that the earlier edge-count argument for termination of cycle resolution on the enhanced envy graph is invalid, and the proposed potential function appears to repair it. These are real strengths. However, the proof of Theorem 3 has a load-bearing gap in Case 3.2: the argument that Step 9.2 does not fail is a non sequitur, and the subsequent EFX verification for leading agents toward d2 depends on that unsupported conclusion. The theorem may still be true, but the written proof is incomplete.

major comments (2)
  1. [§4, proof of Theorem 3, Case 3.2 (p.16)] The sentence 'Hence Step 9.2 does not fail' is a non sequitur. In the subcase |X_d2|=1 and (d1,d2)∈G_e(X), Step 9.2's condition is false by definition, so Steps 9.3 and 9.4 are never evaluated; their 'failure' cannot be used to infer anything about the final allocation. The attempted contradiction derives v_d((X_d1∪C)\ {g1}) ≤ (2/3)v_d(X_d2)+(2/3)v_d(X_d2), but Step 3 only bounds pairs of pool goods; X_d1 is not in the pool, so v_d(X_d1) is not controlled by that step. Even if the inequality held, it concerns d2's valuation of a large bundle and does not contradict (d1,d2)∈G_e(X), which asserts v_d(X_d1) < (2/3)v_d(X_d2). Since the claim that leading agents in A∪B∪C are 2/3-EFX toward d2 rests entirely on the failure of Steps 9.3 and 9.4, this subcase is not proven. The theorem may be true, but the written argument does not cover the case where Step 9.2 fails.
  2. [§5.1, proof of Theorem 4] The proof asserts without proof that for every source s and every unallocated good g_i there is a leading agent a that is a heavy-champion of X_s∪{g_i}. This existence is what guarantees that every vertex of the t-partite graph has an incoming edge from every other part, and it is therefore load-bearing for the rainbow-cycle argument. The manuscript neither proves this nor cites a specific lemma from [9] that establishes it. It should also explicitly justify that a heavy-champion among non-leading agents can be replaced by the leading agent of the same type (this follows from Proposition 1 but is not stated), and correct the citation to 'Part 2 of Proposition 2' for the fact that a champion finds the relevant good valuable. The gap is likely repairable using standard arguments from [9], but as written the proof is incomplete.
minor comments (6)
  1. [Abstract / §1] 'due to HV et al.' is informal; use a proper author name or reference number.
  2. [Algorithm 2, Step 9.2] The notation '(d1,d2) /∈ G_e(X)' is ambiguous; use a clear '∉' symbol and state explicitly that the step executes when the edge is absent.
  3. [Procedure 3 and Figure 1] The subroutine is named Pseudo-Cycle-Resolution, but Figure 1 and surrounding text call it Pseudo-Path-Resolution. Please unify the terminology.
  4. [Algorithm 4, line 14] Typo: 'least valued good om C' should be 'least valued good in C'.
  5. [§5, Proposition 2 proof] The phrase 'assuming 2ε≤1/2' should read 'assuming ε≤1/2'.
  6. [Theorem 3 proof, Case 2] The citation 'from Lemma 4' for the fact that |X_d1|=2 appears to be a citation error; the relevant statement is Lemma 2 (or its analogue for 3PA+-TYPES).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proofs are self-contained uses of standard lemmas; the only self-citation (Proposition 1 from [16]) is an elementary ordering-invariant fact, and the flagged Case 3.2 concern is a proof-gap/correctness issue, not a circular reduction.

full rationale

The paper is a non-empirical existence/algorithmic proof. Its main derivation chain is: modify the 3PA+ algorithm of [5] with Steps 9.1-9.4; prove Lemma 4 that these steps preserve Properties 1 and 2; prove Theorem 3 by case analysis on the number of critical goods and sources; and prove Theorem 4 by adapting the rainbow-cycle-number machinery of [9,1] to the leading agents of k groups. I find no step where a claimed output is equivalent by construction to an input, and no fitted parameter is renamed as a prediction. Proposition 1 is cited from the authors' prior work [16], and the authors do overlap with that reference. However, Proposition 1 is an elementary consequence of the ordering invariant: within each group, the leading agent has the minimum-valued bundle, so every source is a leading agent and any bundle envied by a non-leading agent is also envied by the leading agent. It is parameter-free, its assumptions do not include the target 2/3-EFX result, and it is independently verifiable; therefore it is real evidence and does not raise the circularity score. The reader-flagged inference in Case 3.2 of Theorem 3, 'Hence Step 9.2 does not fail,' is at worst a condensed or potentially flawed argument about the existing case assumption that d2 is not 2/3-EFX towards X_d1∪C. It is not a circular reduction: the failure of Step 9.2 is not defined to be the desired conclusion, and the proof does not presuppose the theorem. Even if that inference were invalid, a proof gap is a correctness question, not a circularity question. Theorem 4 similarly imports the rainbow-cycle-number upper bound R(d)=O(d log d) and the heavy-champion observations as external lemmas from [1,9]; it only changes the construction to use leading agents, so the bound is not assumed in the conclusion. No other definitional, fitting, or self-citation circularity appears. Hence the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper's contributions are conditional on several lemmas from prior work; none are machine-checked, but they are standard in the fair division literature. No free parameters are fitted to data, and no new entities are postulated.

assumptions (5)
  • domain assumption Non-degeneracy assumption can be assumed w.l.o.g. for alpha-EFX
    Invoked in Section 2.1 and Appendix A.1; standard in the literature, but it is an assumption on the input instances.
  • domain assumption Properties 1-4 of the 3PA+ algorithm are preserved by steps 1-9 of the original algorithm
    The paper relies on the correctness of [5]'s algorithm, with corrections to two proofs provided in Appendix C.
  • domain assumption Lemma 1 from [19] on completing partial EFX allocations
    Used to complete the partial allocation in Theorem 3.
  • domain assumption Rainbow cycle number bound R(d) = O(d log d) from [1]
    Used in Theorem 4 to bound charity.
  • domain assumption Proposition 1 from [16] (properties of k-type instances)
    Used throughout; proved in prior work by partly overlapping authors.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Almost and Approximate EFX for Few Types of Agents." pith.science (2026). https://pith.science/paper/ZYQH5FEP

@misc{pith2026250815380,
  author       = {Pith},
  title        = {Pith review of: Almost and Approximate EFX for Few Types of Agents},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZYQH5FEP}},
  note         = {Machine review of arXiv:2508.15380}
}
abstract

We study the problem of fair allocation of a set of indivisible goods among $n$ agents with $k$ distinct additive valuations, with the goal of achieving approximate envy-freeness up to any good ($\alpha-\mathrm{EFX}$). It is known that EFX allocations exist for $n$ agents when there are at most three distinct valuations due to HV et al. Furthermore, Amanatidis et al. showed that a $\frac{2}{3}-\mathrm{EFX}$ allocation is guaranteed to exist when number of agents is at most seven. In this paper, we show that a $\frac{2}{3}-\mathrm{EFX}$ allocation exists for any number of agents when there are at most four distinct valuations. Secondly, we consider a relaxation called $\mathrm{EFX}$ with charity, where some goods remain unallocated such that no agent envies the set of unallocated goods. Akrami et al. showed that for $n$ agents and any $\varepsilon \in \left(0, \frac{1}{2}\right]$, there exists a $(1-\varepsilon)-\mathrm{EFX}$ allocation with at most $\tilde{\mathcal{O}}((n/\varepsilon)^{\frac{1}{2}})$ goods to charity. In this paper, we show that a $(1-\varepsilon)-\mathrm{EFX}$ allocation with a $\tilde{\mathcal{O}}(k/\varepsilon)^{\frac{1}{2}}$ charity exists for any number of agents when there are at most $k$ distinct valuations.

Figures

Figures reproduced from arXiv: 2508.15380 by the authors.

Figure 1
Figure 1. Illustration of the Pseudo-Cycle-Resolution procedure. The path 𝜋 = (𝑑1, 𝑐1, 𝑏1, 𝑎1). Agent 𝑎1 prefers one good 𝑔 from 𝑋𝑑𝑗 and one good 𝑔 ′ from the pool over her own bundle 𝑋𝑎1 . The Pseudo-Path-Resolution procedure reallocates as follows: 𝑋𝑐1 is assigned to 𝑑𝑗 , 𝑋𝑏1 to 𝑐1, 𝑋𝑎1 to 𝑏1, and {𝑔, 𝑔′} to 𝑎1. The bundles are then reordered within each group to maintain the ordering invariant. In the additional steps, whe… view at source ↗
Figure 2
Figure 2. Enhanced Envy Graphs before and after resolving the cycle (𝑠, 𝑖1, 𝑖2, 𝑖3, 𝑠). 26 [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗
Figure 3
Figure 3. The path from 𝑠 to 𝑖 does not exist in the reduced envy graph 𝐺r. Therefore, the Path Resolution* in Step 8.5 must be invoked with the enhanced envy graph 𝐺e. This correction is made in Algorithm 1. 28 [PITH_FULL_IMAGE:figures/full_fig_p028_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Linear Bound on the Rainbow Cycle Number and Approximate EFX

    cs.GT 2026-07 accept novelty 7.5 of 10

    R(d)<e d, so every additive fair-division instance has a partial (1−ε)-EFX allocation with O(√(n/ε)) unallocated goods, found by a randomized poly-time algorithm.

  2. A Simple Polynomial-Time EFX Repair for Cancelable Valuations

    cs.GT 2026-08 conditional novelty 6.0 of 10

    A deterministic tie-breaking rule in the Plaut-Roughgarden repair procedure yields at most m transfers for monotone cancelable valuations, giving polynomial-time EFX repair.

Reference graph

Works this paper leans on

29 extracted references · 19 canonical work pages · cited by 2 Pith papers

  1. [5]

    Pushing the Frontier on Approximate EFX Allocations

    Georgios Amanatidis, Aris Filos-Ratsikas, and Alkmini Sgouritsa. Pushing the Frontier on Approximate EFX Allocations. InProceedings of the 25th ACM Conference on Economics and Computation, pages 1268–1286, New Haven CT USA, July 2024. ACM. ISBN 979-8-4007-0704-

    work page 2024

  2. [9]

    doi: 10.1145/3670865.3673582

    work page arXiv

  3. [1]

    EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number.Operations Research, 73(2):738–751, March 2025

    Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta. EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number.Operations Research, 73(2):738–751, March 2025. ISSN 0030-364X, 1526-5463. doi: 10.1287/opre.2023.0433

    work page arXiv 2025

  4. [2]

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

    Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoretical Computer Science, 841:94–109, November 2020. ISSN 03043975. doi: 10.1016/j.tcs.2020.07.006

    doi:10.1016/j.tcs.2020.07.006 2020

  5. [3]

    Maximum nash welfare and other stories about efx

    Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A Voudouris. Maximum nash welfare and other stories about efx. Theoretical Computer Science, 863:69–85, 2021

    work page 2021

  6. [4]

    Fair division of indivisible goods: Recent progress and open questions.Artificial Intelligence, 322:103965, 2023

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions.Artificial Intelligence, 322:103965, 2023

    work page 2023

  7. [6]

    Fixed-Point Cycles and Approximate EFX Allocations

    Benjamin Aram Berendsohn, Simona Boyadzhiyska, and László Kozma. Fixed-Point Cycles and Approximate EFX Allocations. LIPIcs, Volume 241, MFCS 2022, 241:17:1–17:13, 2022. ISSN 1868-8969. doi: 10.4230/LIPICS.MFCS.2022.17

    doi:10.4230/lipics.mfcs.2022.17 2022

  8. [7]

    Almost Full EFX Exists for Four Agents

    Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost Full EFX Exists for Four Agents. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5):4826–4833, June

    work page

Show all 29 references
  1. [8]

    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 Transactions on Economics and Computation, 7(3):1–32, August 2019. ISSN 2167-8375, 2167-8383. doi: 10.1145/3355902

    2019 doi

  2. [10]

    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 Journal on Computing, 50(4):1336–1358, January 2021. ISSN 0097-5397, 1095-7111. doi: 10.1137/20M1359134

    2021 doi

  3. [11]

    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. InProceedings of the 22nd ACM Conference on Economics and Computation, pages 310–311, Budapest Hungary, July 2021. ACM. ISBN 978-1-4503-85...

    2021

  4. [12]

    Duncan K. Foley. Resource allocation and the public sector.Yale Economic Essays, 7(1):45–98, 1967. 20

    1967

  5. [13]

    EFX Exists for Three Agents

    Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX Exists for Three Agents. Journal of the ACM, 71(1):1–27, February 2024. ISSN 0004-5411, 1557-735X. doi: 10.1145/ 3616009

    2024

  6. [14]

    (Almost Full) EFX for Three (and More) Types of Agents.Proceedings of the AAAI Conference on Artificial Intelligence, 39(13):13889–13896, April 2025

    Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar, and Nithin Varma. (Almost Full) EFX for Three (and More) Types of Agents.Proceedings of the AAAI Conference on Artificial Intelligence, 39(13):13889–13896, April 2025. ISSN 2374-3468, 2159-5399. doi: 10.1609/aaai. v39i13.33519

    2025 doi

  7. [15]

    Computing fair and efficient allocations with few utility values

    Jugal Garg and Aniket Murhekar. Computing fair and efficient allocations with few utility values. Theoretical Computer Science, 962:113932, 2023

    2023

  8. [16]

    EFX Exists for Three Types of Agents, November 2024

    Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, and Nithin Varma. EFX Exists for Three Types of Agents, November 2024

    2024

  9. [17]

    Fair allocation of a multiset of indivisible items

    Pranay Gorantla, Kunal Marwaha, and Santhoshini Velusamy. Fair allocation of a multiset of indivisible items. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 304–331. 2023. doi: 10.1137/1.9781611977554.ch13

    2023 doi

  10. [18]

    Extension of Additive Valuations to General Valuations on the Existence of EFX

    Ryoga Mahara. Extension of Additive Valuations to General Valuations on the Existence of EFX. Mathematics of Operations Research, 49(2):1263–1277, May 2024. ISSN 0364-765X, 1526-5471. doi: 10.1287/moor.2022.0044

    2024

  11. [19]

    R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125–131, New York NY USA, May 2004. ACM. ISBN 978-1-58113-771-2. doi: 10.1145/988772. 988792

    2004 doi

  12. [20]

    Almost Envy-Freeness with General Valuations.SIAM Journal on Discrete Mathematics, 34(2):1039–1068, January 2020

    Benjamin Plaut and Tim Roughgarden. Almost Envy-Freeness with General Valuations.SIAM Journal on Discrete Mathematics, 34(2):1039–1068, January 2020. ISSN 0895-4801, 1095-7146. doi: 10.1137/19M124397X

    2020 doi

  13. [21]

    Improved EFX approximation guarantees under ordinal-based assumptions

    Evangelos Markakis and Christodoulos Santorinaios. Improved EFX approximation guarantees under ordinal-based assumptions. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, Aamas ’23, pages 591–599, Richland, SC, 2023. Internationa...

    2023

  14. [23]

    Equity, envy, and efficiency.Journal of Economic Theory, 9(1):63–91, September

    Hal R Varian. Equity, envy, and efficiency.Journal of Economic Theory, 9(1):63–91, September

  15. [25]

    |𝑋𝑠| = 2;|𝑋𝑖1| =|𝑋𝑖3| = 1;|𝑋𝑖2| = 2;∀ℓ∈ [5],|𝑋𝑘ℓ| = 2;∀ℓ∈ [4],|𝑋𝑗ℓ| = 1

  16. [26]

    Furthermore, 𝑣𝑠(𝑋𝑖1) > 3 2 𝑣𝑠(𝑋𝑠), 𝑣𝑖1(𝑋𝑖2) > 3 2 𝑣𝑖1(𝑋𝑖1) and 𝑣𝑖2(𝑋𝑖3) > 3 2 𝑣𝑖2(𝑋𝑖2)

    The only envy edges in𝐺(𝑋) are (𝑠, 𝑖1), (𝑖1, 𝑖2), and(𝑖2, 𝑖3). Furthermore, 𝑣𝑠(𝑋𝑖1) > 3 2 𝑣𝑠(𝑋𝑠), 𝑣𝑖1(𝑋𝑖2) > 3 2 𝑣𝑖1(𝑋𝑖1) and 𝑣𝑖2(𝑋𝑖3) > 3 2 𝑣𝑖2(𝑋𝑖2). Therefore, all the three envy edges in𝐺(𝑋) also appear in the reduced envy graph𝐺r(𝑋) and also the enhanced envy graph𝐺e(𝑋). 24

  17. [27]

    Therefore, (𝑖3, 𝑠) is a red edge in the enhanced envy graph𝐺e(𝑋)

    𝑣𝑖3(𝑋𝑠) > 2 3 𝑣𝑖3(𝑋𝑖3). Therefore, (𝑖3, 𝑠) is a red edge in the enhanced envy graph𝐺e(𝑋)

  18. [28]

    ∀ℓ∈ [5], 𝑣𝑖3(𝑋𝑖3) = 𝑣𝑖3(𝑋𝑘ℓ)

  19. [29]

    However,(𝑗ℓ, 𝑖2) is not a red edge in𝐺e(𝑋) as 𝑖2 is not a source vertex

    ∀ℓ∈ [4], 𝑣𝑗ℓ(𝑋𝑖2) > 2 3 𝑣𝑗ℓ(𝑋𝑗ℓ). However,(𝑗ℓ, 𝑖2) is not a red edge in𝐺e(𝑋) as 𝑖2 is not a source vertex. The enhanced envy graph𝐺e(𝑋) is shown in Figure 2a. It has three envy edges and one red edge. Obtain allocation 𝑋′ by applying theCycle Resolution subroutine on the alloc...

  20. [1974]

    doi: 10.1016/0022-0531(74)90075-1

    ISSN 00220531. doi: 10.1016/0022-0531(74)90075-1. 21 Appendix A Missing Proofs from Preliminaries A.1 The Non-Degeneracy Assumption In [11], it is shown that ifEFX exists for all non-degenerate instances (Definition 3) with𝑛 agents, then it exists for all instances of𝑛 agents....

    doi

  21. [2022]

    doi: 10.1609/aaai.v36i5.20410

    ISSN 2374-3468, 2159-5399. doi: 10.1609/aaai.v36i5.20410

    doi

Pith tools

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