OpenAlex ·

EFX Allocations for Three Agents and Seven or Eight Chores

Xinkai Zhang

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2609.10585
Original
Read it at the publisher
Topics
Artificial IntelligenceComputational ComplexityEconometricsGeneral Economics

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.

Already a reader? Sign in

All new papers in Artificial Intelligence

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.

Papers belong to their authors and publishers; every page here links to the original. All research topics