OpenAlex ·
EFX Allocations for Three Agents and Seven or Eight Chores
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.10585
- Original
- Read it at the publisher
- Topics
Abstract
We show that every additive chore instance with three agents and seven or eight indivisible chores has an EFX allocation. Costs may be arbitrary nonnegative reals. Together with the theorem of Kobayashi, Mahara, and Sakamoto for at most $2n$ chores, this settles the existence of EFX allocations for three agents and at most eight chores; for four or more agents, He and Tao have shown that EFX allocations of additive chores need not exist. Both proofs are computer-assisted. For seven chores, we normalize each agent's costs and sort the chores, and then express the nonexistence of an EFX allocation as a formula of quantifier-free linear real arithmetic with one clause per allocation; the SMT solvers Z3 and cvc5 show that this formula is unsatisfiable. For eight chores, if two agents share a cheapest chore, we remove that chore, apply the seven-chore result, and put the chore back using an insertion lemma of Kobayashi, Mahara, and Sakamoto. The remaining instances, in which the agents' sets of cheapest chores are pairwise disjoint, are handled by a second formula of the same kind.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
Beyond Aggregate VARs: A Bayesian Benchmark for HANK Models
The Profit Alignment Problem: How Profit Mandates Induce Alignment Failures in LLMs
Measuring DeFi Risk
Price Dislocations, News Citations, and Epistemic Leverage on Polymarket
AI for AI: Optimizing Additional Infrastructure Build-out to Power Artificial Intelligence Data Centers
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.