Optimal Subsidy Bounds for Goods and Chores One Dollar Each Suffices

Jul 16, 2026

Upload by Liam

Optimal Subsidy Bounds for Goods and Chores analyzes fair allocation of m indivisible items to n agents with additive utilities, where items can be goods (non-negative utility) for some agents and chores (negative utility) for others. While envy-free allocations may fail for indivisible items, introducing money via a subsidy restores envy-freeness. With per-item utilities bounded by one, a subsidy of at most one dollar per agent guarantees an envy-free allocation, and the bound is tight. The allocation is computable in polynomial time, and the total subsidy needed is at most n−1.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages32

Reading Time1 h 21 min

Introduction

Fairness and envy-freeness with indivisible items

Subsidy model and prior results

Mixed good-and-chores (“mixed manna”) setting

Central question and problem statement

Our Results

Utility bounds and envy-free definition

One-dollar-per-agent subsidy guarantee

Optimal Subsidy Bounds for Goods and Chores: One Dollar Each Suffices Xinhang Lu* Kyushu University Simon Mackenzie† UNSW Sydney Mashbat Suzuki‡ UNSW Sydney arXiv :2607 . 10089v 1 [ cs .GT] 11 Jul 2026 Abstract We study the fair allocation of m indivisible items to n agents with additive utilities. In our setting, each indivisible item may be a good, yielding non-negative utility to some agents, ora chore, yielding negative utility to others. Whilst envy-free allocations may not exist in the indivisible-items setting, envy-freeness can be achieved if some amount of divisible good (i.e., money) is introduced. When each item’s utility or disutility is bounded by one, we show that a subsidy of at most one dollar per agent suffices to guarantee the existence of an envy-free allocation, and that this bound is tight. Moreover, such an allocation can be computed in polynomial time. Since at least one agent need not receive any subsidy, our results imply that a total subsidy of at most n − 1 dollars suffices to ensure envy-freeness. 1 Introduction Dividing scarce resources among multiple parties is ubiquitous, arising in contexts such as divorce settlements and inheritance divisions. A natural objective is to select an allocation that every participant perceives as fair. Among the many fairness notions studied in the literature, the gold standard is arguably envy-freeness, introduced by Foley [1967]: an allocation is envy-free if no agent prefers another agent’s bundle to their own. Our focus is on allocating indivisible items. This includes familiar goods (e.g., houses, artworks, electronics) as well as chores or undesirable tasks (e.g., household chores, shift scheduling) . Withindivisible items, envy-free allocations need not exist; for example, with two agents and a single valuable indivisible good, whichever agent does not receive the good necessarily envies the other. A classical way to circumvent such non-existence is to allow monetary compensation. We follow the standard subsidy model, where an outcome consists of an allocation of the indivisible items together with non-negative payments to agents, and envy-freeness is defined with respect to the sum of an agent’s item-utility and her subsidy. The idea goes back to Maskin [1987] and Svensson [1983], and much early work focuses on assignment-type settings in which each agent receives at most one good [e.g., Alkan et al., 1991; Aragones, 1995; Klijn, 2000],1 with the exception of Meertens et al. [2002], whose model places no restrictions on the number of agents and goods and allows agents to have general preference relations over their allocated bundle of goods and amount of money. * [xinhang.lu@inf.kyushu-u.ac.jp](xinhang.lu@inf.kyushu-u.ac.jp)[ ](xinhang.lu@inf.kyushu-u.ac.jp)†[simon.william.mackenzie@gmail.com](simon.william.mackenzie@gmail.com)[ ](simon.william.mackenzie@gmail.com)‡[mashbat.suzuki@unsw.edu.au](mashbat.suzuki@unsw.edu.au) 1The model of Alkan et al. [1991] allows for undesirable items and negative amounts of money. More recently, Halpern and Shah [2019] initiated the line of research that studies the asymptotic amount of subsidy required to achieve envy-freeness in the setting with n agents, m indivisible goods (with per-item values normalized to [0, 1]), and quasi-linear preferences. In this goods-only setting, Brustle et al. [2020] proved a tight universal bound: one dollar of subsidy per agent always suffices, and this bound is worst-case optimal. Subsidies have also been studied for chores and for fairness notions beyond envy-freeness (e.g., proportionality and maximin share), including tight and small-subsidy guarantees in several settings [Wu and Zhou, 2024; Wu et al., 2023, 2025a,b] . Many real-world allocation problems, however, involve a mix of goods and chores, and the same indivisible item can be desirable to some agents and undesirable to others. For instance, in a shared household, one roommate may enjoy cooking while a

FAQs

Why might envy-free allocations fail when items are indivisible?

With indivisible items, envy-free allocations need not exist because an agent who does not receive a valuable item will necessarily envy the agent who does.

How does the subsidy model restore envy-freeness?

An outcome includes an allocation of items and non-negative payments to agents. Envy-freeness is evaluated using each agent’s item utility plus their subsidy, allowing monetary compensation to offset disagreements.

What subsidy guarantee is proved for goods and chores?

When each item’s (dis)utility is bounded by one (equivalently values in [−1,1]), a subsidy of at most one dollar per agent always suffices to guarantee an envy-free allocation, and the bound is tight.

Jul 16, 2026

Upload by Liam