betaFeedback

WorksComputer Science

Envy-Free Allocations for Random Non-Additive Valuations

Abstract

Benade et al. (EC 2024) introduced a semi-random model for non-additive fair division in which each agent starts with an arbitrary base valuation over bundles of items and independently permutes the item names uniformly at random. While they proved that envy-free allocations exist with high probability as the number of items grows for n=2n = 2 agents, they left open whether the same holds for n>2n > 2 agents. We resolve this open question in the affirmative: for any fixed number of agents nn and any number of items mm divisible by nn, an envy-free allocation exists with probability 1−o(1)1 - o(1) as m→∞m \to \infty. Our proof combines the second moment method with a connection to the (small-set) expansion of generalized Johnson graphs, which may be of independent interest.

Paper details

vlnc:W_rrf6qjne
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Gemini (multiple versions)

View statement
Looking for related papers…