(Almost Full) EFX for Three (and More) Types of Agents

Pratik Ghosal, Vishwa Prakash HV, Prajakta Nimbhorkar, Nithin Varma
1/25/2023
cs.GTcs.MA

No confident code implementation found for this paper. 3 possible matches can be shown below.

Abstract

We study the problem of determining an envy-free allocation of indivisible goods among multiple agents with additive valuations. EFX, which stands for envy-freeness up to any good, is a well-studied relaxation of the envy-free allocation problem and has been shown to exist for specific scenarios. EFX is known to exist for three agents, and for any number of agents when there are only two types of valuations. EFX allocations are also known to exist for four agents with at most one good unallocated. In this paper, we show that EFX exists with at most k-2 goods unallocated for any number of agents having k distinct valuations. Additionally, we show that complete EFX allocations exist when all but two agents have identical valuations.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 3 weaker matches are hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

EFX Exists for Three Types of Agents

95% match2024

On the existence of EFX allocations in multigraphs

87% match2025

PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations

87% match2026

Temporal Fair Division of Indivisible Items

86% match2024

Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division

86% match2025

Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

85% match2025

Cite this paper

@article{ghosal2023almost,
  title  = {(Almost Full) EFX for Three (and More) Types of Agents},
  author = {Pratik Ghosal and Vishwa Prakash HV and Prajakta Nimbhorkar and Nithin Varma},
  year   = {2023},
  eprint = {2301.10632},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2301.10632v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2301.10632.svg)](https://codeofpaper.com/paper/2301.10632)

Discussion