Pith. sign in

REVIEW 6 cited by

EFX Exists for Three Types of Agents

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2410.13580 v3 pith:7BREELHC submitted 2024-10-17 cs.GT cs.DScs.MA

Vishwa Prakash HV , Pratik Ghosal , Prajakta Nimbhorkar , Nithin Varma This is my paper · ORCID
classification cs.GTcs.DScs.MA
keywords agentsnumberopenthreevaluationsadditiveallocationscase
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

We study the problem of finding an envy-free allocation of indivisible goods among agents with additive valuations. We focus on the fairness notion of envy-freeness up to any good (EFX). A central open question in fair division is whether EFX allocations always exist for any number of agents. While EFX has been established for three agents [CGM24] and for any number of agents with at most two distinct valuations [Mah23], its existence in more general settings remains open. In this paper, we make significant progress by proving that EFX allocations exist for any number of agents when there are at most three distinct additive valuations. This result simultaneously generalizes both the three-agent case and the two-type case, settling an open question in the field (see [Mah23]).

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 6 Pith papers

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

  1. Existence of 2-EFX Allocations of Chores

    cs.GT 2025-07 conditional novelty 8.0 of 10

    For any additive disutility chore division instance, a 2-EFX allocation always exists, improving the prior best-known 4-EFX guarantee.

  2. On the existence of EFX allocations for goods

    econ.TH 2025-07 conditional novelty 8.0 of 10

    EFX allocations always exist for any number of agents when two agents have arbitrary set monotonic valuations and all others have size monotonic valuations.

  3. Simultaneously Satisfying MXS and EFL

    cs.GT 2024-11 conditional novelty 7.0 of 10

    For monotone restricted MMS-feasible valuations, an allocation that is simultaneously MXS and EFL always exists, and the paper gives a constructive algorithm for it.

  4. EF2X Exists For Four Agents

    cs.GT 2024-11 conditional novelty 7.0 of 10

    EF2X allocations are guaranteed to exist for any four-agent fair division instance with cancelable valuations, and can be computed in pseudopolynomial time.

  5. Improved Approximate EFX Guarantees for Multigraphs

    cs.GT 2025-06 conditional novelty 5.0 of 10

    For additive valuations over goods relevant to at most two agents, the paper proves existence of a 1/√2-approximate EFX allocation, improving the prior 2/3 bound.

  6. EFX Allocations on Some Multi-graph Classes

    cs.GT 2024-12 conditional novelty 5.0 of 10

    Exact EFX allocations exist for bipartite multi-graphs and high-girth t-chromatic multi-graphs with cancellable valuations via polynomial-time algorithms, and for multi-trees with monotone valuations.

Pith tools