betaFeedback

WorksComputer Science

Subquadratic Subsidies for Nonnegative or Nonpositive Valuations

Abstract

We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in [−1,1][-1,1], we prove that a total subsidy of O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}) suffices to achieve envy-freeness among nn agents whenever all agents assign nonnegative values to every bundle or all assign nonpositive values to every bundle. These valuation classes include monotone goods and monotone chores, respectively, but do not require monotonicity. Our result establishes the first subquadratic total-subsidy bound for general monotone valuations that holds for every number of agents.

Introduction

How can we divide indivisible items fairly among agents with different preferences? An allocation is envy-free if every agent values her own bundle at least as much as any other agent’s bundle. Such an allocation need not exist: if two agents both value a single item positively, the agent who does not receive it envies the one who does. Monetary subsidies can compensate for these differences. If agent ii receives bundle AiA_i and subsidy pi≥0p_i \ge0, envy-freeness requires

vi(Ai)+pi≥vi(Aj)+pjfor all agents i,j.v_i(A_i) + p_i \ge v_i(A_j) + p_j \quad\text{for all agents } i,j.

The subsidies are paid by an external source. We seek an allocation and subsidies that satisfy these inequalities at the smallest possible total cost.

Any bound on this cost must fix the scale of the valuations. For additive valuations, the usual assumption is that each item has absolute value at most one. For general valuations, we require that adding or removing a single item changes a bundle’s value by at most one. We also normalize the value of the empty bundle to zero. The central question is then:

How much total subsidy suffices to guarantee envy-freeness in the worst case?

[8] initiated the modern algorithmic study of this question. For additive goods, [3] proved that one unit of subsidy per agent suffices. Subtracting the smallest payment preserves envy-freeness and gives a total of at most n−1n-1. This is tight: with one item valued at one by every agent, each of the n−1n-1 nonrecipients needs at least one unit of subsidy.

[14] extended this guarantee to mixed additive valuations, where an item may be a good for some agents and a chore for others.

For general monotone valuations, the best total-subsidy bounds that apply to every number of agents are substantially larger. [3] proved that a total subsidy of 2(n−1)22(n-1)^2 suffices, and [10] improved this bound to (n2−n−1)/2(n^2-n-1)/2 for n≥3n \ge3. [13] asked whether a subquadratic bound is possible. A partial answer was given by [5], who established a total-subsidy bound of O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}) for arbitrary valuations, but only when the number of agents is a prime power. Thus, obtaining a subquadratic bound for an arbitrary number of agents remained open.

Our contribution

We resolve this question by removing the prime-power restriction: for every number nn of agents, a total subsidy of O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}) suffices. Our result applies whenever all agents assign nonnegative values to every bundle or all assign nonpositive values to every bundle. These two classes include monotone goods and monotone chores, respectively, but neither requires monotonicity.

Theorem 1. Let N=[n]N=[n] be a set of agents and let MM be a finite set of indivisible items. Suppose that each valuation vi:2M→Rv_i:2^M \to\mathbb{R} satisfies vi(∅)=0v_i(\varnothing)=0 and

∣vi(S∪{g})−vi(S)∣≤1∀S⊆M, and ∀g∈M∖S.(1)\lvert v_i(S \cup\{g\}) - v_i(S) \rvert\le1 \qquad\forall S \subseteq M,\ \text{and } \forall g \in M \setminus S. \tag*{(1)}

Assume that either vi(S)≥0v_i(S) \ge0 for every i,Si,S, or vi(S)≤0v_i(S) \le0 for every i,Si,S. Then there exist an allocation A=(A1,…,An)A=(A_1,\ldots,A_n) and nonnegative subsidies (p1,…,pn)(p_1,\ldots,p_n) that are envy-free and satisfy

∑i∈Npi≤52(n−1)3/2log⁡(4n).(2)\sum_{i \in N} p_i \le5\sqrt{2}(n-1)^{3/2}\sqrt{\log(4n)}. \tag*{(2)}

The proof also bounds each agent’s subsidy by 52(n−1)log⁡(4n)5\sqrt{2(n-1)\log(4n)}. The guarantee is existential: the argument identifies a suitable partition through a topological existence theorem, rather than a polynomial-time algorithm.

Proof overview

The proof combines supporting bundle prices, a topological equalization argument, and randomized rounding. The key is to equalize expected prices in a distribution that randomizes only a small number of items.

Bundles, prices, and allocations. Fix an unordered partition B={B1,…,Bn}\mathcal{B}=\{B_1,\ldots,B_n\} of the items, allowing empty bundles. For matching purposes, give each bundle occurrence an arbitrary label j∈[n]j \in[n]. We call the corresponding matching position slot jj; its contents are the bundle BjB_j. These labels specify neither an order on the partition nor its recipients. A maximum-weight perfect matching σ\sigma between agents and slots, with edge weights vi(Bj)v_i(B_j), gives the allocation Ai=Bσ(i)A_i=B_{\sigma(i)}.

We seek bundle prices that support this matching:

vi(Bσ(i))−qσ(i)≥vi(Bk)−qkfor all i,k.v_i(B_{\sigma(i)})-q_{\sigma(i)} \ge v_i(B_k)-q_k \qquad\text{for all } i,k.

At these prices, every agent receives a bundle that maximizes her value minus its price, and all bundles are assigned. We use the coordinatewise least nonnegative supporting price vector, which we call the canonical prices. For fixed slot labels, these prices depend only on the partition, not on the choice of maximum-weight perfect matching, and satisfy min⁡kqk=0\min_k q_k=0.

Give every agent a common allowance qmax⁡=max⁡jqjq_{\max}=\max_j q_j and charge the price of her assigned bundle. Her net subsidy is pi=qmax⁡−qσ(i)≥0p_i=q_{\max}-q_{\sigma(i)} \ge0, and the resulting outcome is envy-free. At least one agent receives zero subsidy, so the total is at most (n−1)qmax⁡(n-1)q_{\max}. It therefore suffices to find a partition with a small spread in its canonical prices.

The prices also have a classical welfare interpretation ([7]). Let WW be the maximum welfare obtainable from the original bundles via maximum weight matching between agents and the bundles. Introduce an additional slot offering a formal copy of BkB_k, and let Wk+W_k^{+} be the maximum welfare when all nn agents are matched to distinct slots, leaving one of the n+1n+1 slots unused. This is an auxiliary matching problem, not a duplication of the actual items. We give a direct proof that the canonical prices satisfy

qk=Wk+−W.q_k = W_k^{+} - W.

This identity controls how prices change when an item moves between bundles: WW changes by at most 22 and Wk+W_k^{+} by at most 33, so each qkq_k changes by at most 55.

Equalizing expected prices. Arrange the items as consecutive unit intervals and cut the resulting interval into nn pieces. A piece is a geometric interval used to specify probabilities. Associate piece kk with slot kk, and assign each whole item independently to a slot with probability equal to the fraction of its interval lying in the corresponding piece. The items assigned to slot kk form its random bundle. Only items cut in their interior have random destinations, so at most n−1n-1 items are randomized. Let QkQ_k be the expected canonical price of the random bundle in slot kk. These functions vary continuously with the cut positions. We use the KKM lemma to choose the cuts so that

Q1=⋯=Qn.Q_1 = \cdots= Q_n.

This is where the sign assumption enters. A zero-length piece produces an empty bundle with probability one. For nonnegative valuations, an empty bundle has price zero, so Qk=0Q_k=0 whenever piece kk has length zero. This is the boundary condition needed for a direct application of KKM. For nonpositive valuations, an empty bundle has maximum price. We therefore apply the same argument to the nonnegative functions max⁡jQj−Qk\max_j Q_j-Q_k, which again vanish when piece kk has length zero.

Rounding. Let μ\mu be the common expected price, that is, μ=Qi\mu=Q_i for each i∈[n]i \in[n]. Since at most n−1n-1 items are randomized and each changes a price by at most 55, McDiarmid’s inequality and a union bound give a partition in which every price lies within O(nlog⁡n)O(\sqrt{n\log n}) of μ\mu. The price spread has the same order. Since the minimum canonical price is zero, the maximum price is also O(nlog⁡n)O(\sqrt{n\log n}), yielding the total-subsidy bound of O(nnlog⁡n)O(n\sqrt{n\log n}).

Subsidies beyond additivity. Linear subsidy bounds are known for several restricted nonadditive classes. For matroid-rank valuations, [6] obtained a total bound of n−1n-1 and studied additional truthfulness and efficacy guarantees. [2] proved the same tight total bound for all dichotomous valuations, whose single-item marginals lie in {0,1}\{0,1\}, without assuming submodularity. [12] established an n−1n-1 bound for general monotone valuations in graphical allocation instances, where each item connects two agents, is valued only by those agents, and must be assigned to one of them. Our result places no such restrictions on the monotone valuations or on which agents may receive an item.

For broader valuation classes, [10] showed how to obtain an envy-free outcome with total subsidy at most n(n−1)/2n(n-1)/2 from an allocation that is envy-free up to one item. Their result yields this quadratic guarantee for doubly monotone valuations, where each item is consistently a good or a chore for each agent. In particular, it covers monotone chores, which are included in our nonpositive setting. The survey of Liu et al. (2024) gives a broader account of fair division with subsidies and explicitly asks for a subquadratic bound for monotone valuations in its Open Question 9.

Discrepancy and rounding. For a prime-power number nn of agents, Dupré la Tour and Fujii (2025) established a total-subsidy bound of O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}) for arbitrary valuations with single-item marginals in [−1,1][-1,1]. Their proof relies on a discrepancy theorem for non-additive set functions, obtained by extending the constrained necklace-splitting argument of Jojić et al. (2021). The prime-power restriction stems from this topological ingredient, leaving open whether a subquadratic subsidy bound holds for every number of agents, even for monotone goods.

The two results are complementary: their subsidy theorem allows arbitrary signs but requires a prime-power number of agents, whereas ours uses a different topological argument to obtain the same asymptotic bound for every number of agents, provided that all agents’ bundle values are nonnegative or all are nonpositive.

Topological fair division. The role of empty bundles has a close parallel in topological fair division. In Su (1999), the assumption that agents either always prefer nonempty pieces (hungry preferences) or never do so (lazy preferences) provides the boundary condition for the Sperner argument establishing an envy-free cake division into connected pieces. Avvakumov and Karasev (2021) show that, without these preference assumptions, existence is still guaranteed when the number of agents is a prime power, but may fail otherwise. In our setting, the sign assumptions play an analogous role, supplying boundary conditions for expected prices rather than for preferences over cake pieces.

Assignment markets. For a fixed partition, the supporting-price problem is closely related to classical assignment markets and multi-item auctions (Shapley and Shubik, 1971; Demange et al., 1986). We use the marginal-welfare characterization of minimum prices (Gul and Stacchetti, 1999) to establish one-item stability, with a self-contained derivation for mandatory assignment and possibly negative bundle values.

Model and preliminaries

Let N=[n]={1,…,n}N=[n]=\{1,\ldots,n\} be the agents and let M={g1,…,gm}M=\{g_1,\ldots,g_m\} be a set of items. Each agent ii has a valuation vi:2M→Rv_i:2^M\to\mathbb{R} with vi(∅)=0v_i(\varnothing)=0. Throughout, we assume the marginal bound

∣vi(S∪{g})−vi(S)∣≤1for all i∈N, S⊆M, g∉S.(3)\left|v_i(S\cup\{g\})-v_i(S)\right|\le1 \qquad\text{for all } i\in N,\ S\subseteq M,\ g\notin S. \tag*{(3)}

We consider two classes of valuations: nonnegative valuations, for which vi(S)≥0v_i(S)\ge0 for all i,Si,S, and nonpositive valuations, for which vi(S)≤0v_i(S)\le0 for all i,Si,S. Each class allows nonmonotone valuations. For example, with two items a,ba,b, the valuation v(∅)=v({a,b})=0v(\varnothing)=v(\{a,b\})=0 and v({a})=v({b})=1v(\{a\})=v(\{b\})=1 is nonnegative and has marginals in [−1,1][-1,1], but is not monotone. Monotone goods satisfy vi(S)≤vi(T)v_i(S)\le v_i(T) whenever S⊆TS\subseteq T and are nonnegative under our normalization. Monotone chores satisfy the reverse inequality and are nonpositive.

Bundles and partitions. A bundle is a subset of MM. A partition into nn bundles is an unordered collection B={B1,…,Bn}\mathcal{B} = \{B_1,\ldots,B_n\} of pairwise disjoint bundles whose union is MM. We allow repeated empty bundles and count each occurrence separately, so the collection has nn members counted with multiplicity. Formally, this is a multiset; throughout, braces denote the unordered collection, including any repeated empty bundles.

Slots and labels. To represent a partition in a matching problem, choose an arbitrary labeling of its nn bundle occurrences by [n][n]. A slot is one of these labeled matching positions: slot jj contains bundle BjB_j. Slots remain distinct even when their bundles are empty. The labels are auxiliary; they impose neither an order on the partition nor an assignment to agents. We keep them fixed when comparing or randomizing partitions. Indexed quantities such as qj(B)q_j(\mathcal{B}) are understood relative to this chosen labeling, which we suppress in the notation.

Matchings and allocations. Given a partition B\mathcal{B} and its slot labels, a bijection σ:N→[n]\sigma:N\to[n] matches agents to slots. It induces the allocation A=(Ai)i∈N\mathcal{A}=(A_i)_{i\in N} defined by

Ai=Bσ(i)for each i∈N.A_i=B_{\sigma(i)} \qquad\text{for each }i\in N.

Thus BjB_j is the bundle occupying slot jj, whereas AiA_i is the bundle received by agent ii. An empty slot contains the empty bundle and can still be assigned to an agent; an unused slot has no agent matched to it. In a perfect matching every slot is used, including the empty ones. For a fixed partition, we use a maximum-weight perfect matching with edge weights vi(Bj)v_i(B_j). The maximum welfare is

W(B):=max⁡σ∈Sn∑i∈Nvi(Bσ(i)).(4)W(\mathcal{B}) := \max_{\sigma\in S_n}\sum_{i\in N}v_i(B_{\sigma(i)}). \tag*{(4)}

where SnS_n is the set of bijections between agents and bundle slots.

Prices and subsidies. Prices are indexed by slots: qj(B)q_j(\mathcal{B}) is the price attached to the bundle BjB_j in slot jj. Subsidies are indexed by agents: pi≥0p_i\ge0 is the payment received by agent ii. An allocation A\mathcal{A} and subsidies pp are envy-free if

vi(Ai)+pi≥vi(Aℓ)+pℓfor every i,ℓ∈N.(5)v_i(A_i)+p_i\ge v_i(A_\ell)+p_\ell\qquad\text{for every }i,\ell\in N. \tag*{(5)}

Given supporting prices and an optimal matching σ\sigma, we will use the allocation Ai=Bσ(i)A_i=B_{\sigma(i)} and payments pi=max⁡jqj(B)−qσ(i)(B)p_i=\max_j q_j(\mathcal{B})-q_{\sigma(i)}(\mathcal{B}).

We use two standard tools. The first is the KKM theorem, which we state on the simplex

Δ={x∈R≥0n:∑kxk=1}.\Delta=\left\{x\in\mathbb{R}_{\ge0}^n:\sum_k x_k=1\right\}.

For nonempty S⊆[n]S\subseteq[n], let ΔS={x∈Δ:xk=0 for k∉S}\Delta_S=\{x\in\Delta:x_k=0\text{ for }k\notin S\} be the face spanned by SS.

Theorem 2 (KKM theorem ([11]).) Let C1,…,CnC_1,\ldots,C_n be closed subsets of Δ\Delta. Suppose that ΔS⊆⋃k∈SCk\Delta_S\subseteq\bigcup_{k\in S}C_k for every nonempty S⊆[n]S\subseteq[n]. Then ⋂k∈[n]Ck≠∅\bigcap_{k\in[n]}C_k\ne\varnothing.

The second tool bounds the deviation of a function of independent random choices when no single choice has much influence.

Lemma 3 (McDiarmid’s inequality ([15]).) Let X1,…,XhX_1,\ldots,X_h be independent random variables, where h≥1h\ge1, and let f=f(X1,…,Xh)f=f(X_1,\ldots,X_h). Suppose that changing one coordinate changes ff by at most L>0L>0. Then, for every t>0t>0,

P[∣f−Ef∣≥t]≤2exp⁡(−2t2hL2).(6)\mathbb{P}\left[|f-\mathbb{E}f|\ge t\right]\le2\exp\left(-\frac{2t^2}{hL^2}\right). \tag*{(6)}

Bundle prices

Fix a partition B={B1,…,Bn}\mathcal{B} = \{B_1,\ldots,B_n\} and choose its slot labels. A price vector π∈Rn\pi\in\mathbb{R}^n supports B\mathcal{B} if there is a matching σ∈Sn\sigma\in S_n such that

vi(Bσ(i))−πσ(i)≥vi(Bk)−πk(i∈N, k∈[n]).(7)v_i(B_{\sigma(i)})-\pi_{\sigma(i)} \ge v_i(B_k)-\pi_k \qquad(i \in N,\ k \in[n]). \tag*{(7)}

At these prices, every agent receives a bundle that maximizes her value minus its price. Since every bundle is assigned, these are market-clearing prices for B\mathcal{B}. Every agent must be matched to one slot and receives its bundle, which may be empty; leaving the market is not an option.

Any supported matching maximizes welfare: summing (7) over agents and comparing with another matching cancels all prices. Moreover, prices supporting one optimal matching support every optimal matching. Each agent weakly prefers her bundle in the supported matching, but the utility differences sum to zero because both matchings have the same welfare and total price. Hence every agent is indifferent between her bundles in the two matchings. Supporting prices are therefore a property of the partition, independent of the optimal matching used to allocate it.

Only price differences matter, since adding the same constant to every coordinate preserves (7). We will use the coordinatewise least nonnegative supporting vector, whose entries are the canonical bundle prices qj(B)q_j(\mathcal{B}). To construct it, fix any maximum-weight matching σ\sigma and write aj=σ−1(j)a_j = \sigma^{-1}(j) for the agent matched to bundle BjB_j.

Define the complete directed weighted envy graph GB,σG_{\mathcal{B},\sigma} on the bundle slots [8], with arc weights

wB,σ(j,k):=vaj(Bk)−vaj(Bj).(8)w_{\mathcal{B},\sigma}(j,k) := v_{a_j}(B_k)-v_{a_j}(B_j). \tag*{(8)}

Indexing vertices by slots is equivalent to indexing them by their assigned agents. A positive arc weight means that the agent assigned to the source envies the destination bundle; we retain zero and negative arc weights as well. Every directed cycle has nonpositive weight, since its weight is exactly the welfare gain from moving each agent on the cycle to the next bundle.

For each slot kk, define

qk(B):=max⁡{wt⁡(P):P is a directed walk in GB,σ ending at k},(9)q_k(\mathcal{B}) := \max\{\operatorname{wt}(P) : P\text{ is a directed walk in }G_{\mathcal{B},\sigma}\text{ ending at }k\}, \tag*{(9)}

where wt⁡(P)\operatorname{wt}(P) is the sum of the arc weights and a walk of length zero has weight zero. The maximum is finite: deleting a repeated-vertex segment removes a nonpositive cycle and cannot decrease the weight. Hence a maximum is attained by a simple path.

Canonical prices and subsidies

The next lemma shows that qq gives the canonical prices and explains how to turn them into subsidies.

Lemma 4. For every partition B\mathcal{B} and every maximum-weight matching σ\sigma:

  1. q(B)q(\mathcal{B}) is the coordinatewise least nonnegative price vector supporting B\mathcal{B}. In particular, qk(B)≥qj(B)+wB,σ(j,k)q_k(\mathcal{B}) \ge q_j(\mathcal{B}) + w_{\mathcal{B},\sigma}(j,k) for all j,k∈[n]j,k \in[n];

  1. min⁡kqk(B)=0\min_k q_k(\mathcal{B}) = 0;

  1. writing qmax⁡(B)=max⁡kqk(B)q_{\max}(\mathcal{B}) = \max_k q_k(\mathcal{B}), the subsidies

pi=qmax⁡(B)−qσ(i)(B)(i∈N)p_i = q_{\max}(\mathcal{B}) - q_{\sigma(i)}(\mathcal{B}) \qquad(i \in N)

make the allocation Ai=Bσ(i)A_i = B_{\sigma(i)} envy-free with total subsidy at most (n−1)qmax⁡(B)(n-1)q_{\max}(\mathcal{B}). Proof. By (7) and matching independence, a vector xx supports B\mathcal{B} if and only if xk≥xj+wB,σ(j,k)x_k \ge x_j + w_{\mathcal{B},\sigma(j,k)} for all j,kj,k. Appending the arc (j,k)(j,k) to a maximum-weight walk ending at jj shows that qq satisfies these inequalities.

To see that qq is the least such vector, let xx be any nonnegative supporting price vector. Summing the inequalities along any walk from jj to kk gives xk≥xj+wt⁡(P)≥wt⁡(P)x_k \ge x_j + \operatorname{wt}(P) \ge\operatorname{wt}(P), so xx dominates qq. This proves the first claim. If min⁡kqk>0\min_k q_k > 0, subtracting this minimum from every coordinate of qq would give a strictly smaller nonnegative supporting vector, a contradiction.

Finally, give each agent a common allowance qmax⁡q_{\max} and charge the price of her assigned bundle. The net payments pi=qmax⁡−qσ(i)p_i = q_{\max} - q_{\sigma(i)} are nonnegative and satisfy

paj−pak=qk−qj≥vaj(Bk)−vaj(Bj).p_{a_j} - p_{a_k} = q_k - q_j \ge v_{a_j}(B_k) - v_{a_j}(B_j).

Rearranging gives the envy-free inequality for agent aja_j comparing her bundle with BkB_k. Every payment is at most qmax⁡q_{\max}, and the agent matched to a slot attaining qmax⁡q_{\max} receives zero payment, so the total is at most (n−1)qmax⁡(n-1)q_{\max}.

Prices as marginal welfare gains

The canonical price of a bundle equals the welfare gain from making an additional copy available. The identity below is the counterpart, for mandatory assignment, of the marginal-welfare characterization of minimum equilibrium prices ([7], Theorem 4). We give a direct proof and then use it to bound price changes.

For k∈[n]k \in[n], introduce an additional slot labeled k′k', offering a formal copy of BkB_k. Every agent ii values the option at k′k' at vi(Bk)v_i(B_k), exactly as at slot kk. Let Wk+(B)W_k^+(\mathcal{B}) be the maximum welfare of a matching that assigns all nn agents to distinct slots in [n]∪{k′}[n] \cup\{k'\}. Exactly one slot is unused. This is an auxiliary matching problem: the original partition is unchanged, and no items are duplicated in the eventual allocation.

Lemma 5 (Duplicate-bundle identity). *For every partition B\mathcal{B} and every k∈[n]k \in[n],

qk(B)=Wk+(B)−W(B).q_k(\mathcal{B}) = W_k^+(\mathcal{B}) - W(\mathcal{B}).
{#eq:10}*

In particular, with the slot labels fixed, the price qk(B)q_k(\mathcal{B}) depends on the partition and the slot kk, but not on the maximum-weight matching used to construct the envy graph.

Proof. Fix a maximum-weight matching σ\sigma, with agent aj=σ−1(j)a_j = \sigma^{-1}(j) assigned to BjB_j. We prove the two inequalities separately.

Let P=(j0,…,jt)P = (j_0,\ldots,j_t) be a simple path ending at jt=kj_t = k. Move agent aka_k to slot k′k', and for each s<ts < t, move agent ajsa_{j_s} to slot js+1j_{s+1}, where she receives Bjs+1B_{j_{s+1}}. Keep every other agent in place. This is a valid matching that leaves slot j0j_0 unused, and its welfare gain is wt⁡(P)\operatorname{wt}(P). The construction also applies when t=0t=0, with gain zero. Taking a maximum-weight path gives

Wk+(B)−W(B)≥qk(B).W_k^+(\mathcal{B}) - W(\mathcal{B}) \ge q_k(\mathcal{B}).

For the reverse inequality, extend the price vector by setting qk′=qkq_{k'} = q_k. Since qq supports σ\sigma and slots kk and k′k' offer identical value and price, each agent’s value minus price in any augmented matching is at most her value minus price under σ\sigma. Consider an optimal augmented matching and let u∈[n]∪{k′}u \in[n] \cup\{k'\} be its unused slot. The prices of its assigned slots sum to ∑j∈[n]qj+qk−qu\sum_{j \in[n]} q_j + q_k - q_u. Since qu≥0q_u \ge0, summing the agents’ utility inequalities gives

Wk+(B)≤W(B)+qk−qu≤W(B)+qk.W_k^+(\mathcal{B}) \le W(\mathcal{B}) + q_k - q_u \le W(\mathcal{B}) + q_k.

which proves the identity.

Empty bundles and one-item changes

We first record the only step in the proof that uses the sign of the valuations.

Lemma 6 (Empty-bundle boundary). Suppose that Bk=∅B_k = \varnothing.

  1. For nonnegative valuations, qk(B)=0q_k(\mathcal{B}) = 0.

  1. For nonpositive valuations, qk(B)=max⁡jqj(B)q_k(\mathcal{B}) = \max_j q_j(\mathcal{B}).

Proof. For nonnegative valuations, every outgoing arc from the empty slot has nonnegative weight:

wB,σ(k,j)=vak(Bj)−vak(∅)=vak(Bj)≥0.w_{\mathcal{B},\sigma}(k,j) = v_{a_k}(B_j) - v_{a_k}(\varnothing) = v_{a_k}(B_j) \ge0.

By Lemma 4, qj≥qk+wB,σ(k,j)≥qkq_j \ge q_k + w_{\mathcal{B},\sigma}(k,j) \ge q_k for every jj. Thus qkq_k is a minimum price and equals zero.

For nonpositive valuations, every incoming arc to the empty slot has nonnegative weight:

wB,σ(j,k)=vaj(∅)−vaj(Bj)=−vaj(Bj)≥0.w_{\mathcal{B},\sigma}(j,k) = v_{a_j}(\varnothing) - v_{a_j}(B_j) = -v_{a_j}(B_j) \ge0.

Hence qk≥qj+wB,σ(j,k)≥qjq_k \ge q_j + w_{\mathcal{B},\sigma}(j,k) \ge q_j for every jj, as required.

Next, we use the matching identity to control how much a price changes when one item moves. This bound holds regardless of the signs of the valuations.

Lemma 7 (One-item stability). If two partitions B\mathcal{B} and B′\mathcal{B}' differ only by moving one item from one bundle to another, with slot labels preserved, then

∣qk(B)−qk(B′)∣≤5for every k∈[n].(10)\lvert q_k(\mathcal{B}) - q_k(\mathcal{B}') \rvert\le5 \qquad\text{for every } k \in[n]. \tag*{(10)}

Proof. Suppose that item gg moves from the bundle in slot rr to the bundle in slot ss. For any fixed matching to the original slots, only the values of the agents assigned to rr and ss change. Each changes by at most one, by (3), so the matching’s welfare changes by at most 2. The same bound holds for the maximum over all matchings: an optimal matching for either partition is a feasible matching for the other. Thus

∣W(B)−W(B′)∣≤2.\lvert W(\mathcal{B}) - W(\mathcal{B}') \rvert\le2.

For a fixed matching to the augmented slots defining Wk+W_k^+, at most three used slots have changed values: slots rr and ss, and slot k′k' if k∈{r,s}k \in\{r,s\}. Each assigned value changes by at most one. Maximizing over these matchings gives

∣Wk+(B)−Wk+(B′)∣≤3.\lvert W_k^+(\mathcal{B}) - W_k^+(\mathcal{B}') \rvert\le3.

The identity in Lemma 5 and the triangle inequality now give ∣qk(B)−qk(B′)∣≤3+2=5\lvert q_k(\mathcal{B}) - q_k(\mathcal{B}') \rvert\le3 + 2 = 5.

Equalizing expected prices

We now construct a distribution over partitions in which all canonical prices have the same expectation and at most n−1n - 1 items have random destinations. Limiting the randomness to these items will make the final bound independent of mm.

Partitions from interval cuts

Arrange the items in an arbitrary order and represent gtg_t by the unit interval It=[t−1,t]I_t=[t-1,t]. A piece is an interval in an auxiliary division of [0,m][0,m], used only to specify assignment probabilities. Divide [0,m][0,m] into nn consecutive pieces, allowing pieces of length zero, and label them from left to right by k∈[n]k\in[n]. Their lengths form the vector

x∈Δm:={x∈R≥0n:∑kxk=m}.x\in\Delta_m:=\left\{x\in\mathbb{R}_{\ge0}^{n}:\sum_k x_k=m\right\}.

Set s0=0s_0=0 and sk=∑ℓ=1kxℓs_k=\sum_{\ell=1}^{k}x_\ell, so piece kk is Jk(x)=[sk−1,sk]J_k(x)=[s_{k-1},s_k]. Note that if xk=0x_k=0 then the length of Jk(x)J_k(x) is zero. Associate piece Jk(x)J_k(x) with slot kk. Assign each whole item gtg_t independently to exactly one slot, choosing slot kk with probability

αt,k(x):=length⁡(It∩Jk(x))=max⁡{0,min⁡{t,sk}−max⁡{t−1,sk−1}}.(11)\alpha_{t,k}(x):=\operatorname{length}(I_t\cap J_k(x))=\max\{0,\min\{t,s_k\}-\max\{t-1,s_{k-1}\}\}. \tag*{(11)}

These probabilities are nonnegative and sum to one for each item. Write

Bk(x):={gt∈M:gt is assigned to slot k},R(x):={B1(x),…,Bn(x)}.B_k(x):=\{g_t\in M:g_t\text{ is assigned to slot }k\},\qquad R(x):=\{B_1(x),\ldots,B_n(x)\}.

Thus Bk(x)B_k(x) is the random bundle corresponding to the geometric piece Jk(x)J_k(x): the piece determines the assignment probabilities, and the bundle contains the whole items assigned to its slot. The partition R(x)R(x) is unordered; its auxiliary slot labels are retained when evaluating indexed prices. Define

Qk(x):=E[qk(R(x))].(12)Q_k(x):=\mathbb{E}\left[q_k(R(x))\right]. \tag*{(12)}

Here Qk(x)Q_k(x) is the expected price of the bundle in slot kk, not a price assigned to the interval Jk(x)J_k(x). We evaluate valuations only on bundles of whole items and prices only on the resulting partitions.

Call an item fractional at xx if it has positive assignment probability to at least two slots. At least one of the cuts s1,…,sn−1s_1,\ldots,s_{n-1} lies strictly inside its unit interval. Each cut is strictly inside at most one item, so there are at most n−1n-1 fractional items. A cut at an integer endpoint does not make an item fractional, and several cuts inside one item still randomize only that item.

Each function QkQ_k is continuous. To see this explicitly, for a map b:[m]→[n]b:[m]\to[n], set Bj(b)={gt:b(t)=j}B_j(b)=\{g_t:b(t)=j\} and B(b)={B1(b),…,Bn(b)}\mathcal{B}(b)=\{B_1(b),\ldots,B_n(b)\}, retaining the labels specified by bb. Independence gives

Qk(x)=∑b:[m]→[n]qk(B(b))∏t=1mαt,b(t)(x).Q_k(x)=\sum_{b:[m]\to[n]}q_k(\mathcal{B}(b))\prod_{t=1}^{m}\alpha_{t,b(t)}(x).

This is a finite sum of products of continuous functions, since every αt,k\alpha_{t,k} is continuous by (11).

If xk=0x_k=0, then Jk(x)J_k(x) has length zero, and αt,k(x)=0\alpha_{t,k}(x)=0 for every item, so the corresponding bundle Bk(x)B_k(x) is empty with probability one. A piece of positive length may also yield an empty bundle after rounding. For nonnegative valuations, Lemma 6 gives qk(R(x))=0q_k(R(x))=0 when xk=0x_k=0, so Qk(x)=0Q_k(x)=0 with probability one. For nonpositive valuations, the same lemma gives qk(R(x))≥qj(R(x))q_k(R(x))\ge q_j(R(x)) on this boundary, for every jj. Taking expectations preserves these inequalities. We therefore have the boundary conditions

xk=0⟹{Qk(x)=0,for nonnegative valuations,Qk(x)=max⁡jQj(x),for nonpositive valuations.(13)x_k=0\quad\Longrightarrow\quad \begin{cases} Q_k(x)=0, & \text{for nonnegative valuations},\\ Q_k(x)=\max_j Q_j(x), & \text{for nonpositive valuations}. \end{cases} \tag*{(13)}

A KKM equalization lemma

The following consequence of KKM turns these boundary conditions into equal expectations.

Lemma 8 (KKM equalization). Let F1,…,Fn:Δm→R≥0F_1,\ldots,F_n:\Delta_m\to\mathbb{R}_{\ge0} be continuous, and suppose that Fk(x)=0F_k(x)=0 whenever xk=0x_k=0. Then there is an x∗∈Δmx^*\in\Delta_m such that

F1(x∗)=⋯=Fn(x∗).F_1(x^*)=\cdots=F_n(x^*).

Proof. If m=0m=0, the domain consists of the zero vector and all functions vanish there. Suppose that m>0m>0. For each kk, define the closed set

Ck={x∈Δm:Fk(x)=max⁡jFj(x)}.C_k=\left\{x\in\Delta_m:F_k(x)=\max_j F_j(x)\right\}.

Consider the face supported on a nonempty set S⊆[n]S\subseteq[n]. On this face, Fk=0F_k=0 for every k∉Sk\notin S. Since all functions are nonnegative, their maximum at each point is attained by some index in SS, even when all functions vanish. Hence the face is covered by ⋃k∈SCk\bigcup_{k\in S}C_k. Rescaling Δm\Delta_m to the unit simplex Δ\Delta and applying the KKM theorem (Theorem 2) yields a point in ⋂k∈[n]Ck\bigcap_{k\in[n]}C_k at which F1=⋯=FnF_1=\cdots=F_n. □

Proposition 9 (Equal expected prices). There is an x∗∈Δmx^*\in\Delta_m such that

Q1(x∗)=⋯=Qn(x∗).Q_1(x^*)=\cdots=Q_n(x^*).

In R(x∗)R(x^*), at most n−1n-1 items have random bundle membership, independently of one another; every other item belongs to a fixed bundle.

Proof. For nonnegative valuations, the functions QkQ_k are nonnegative, continuous, and zero when xk=0x_k=0. Apply Lemma 8 with Fk=QkF_k=Q_k.

For nonpositive valuations, set

Fk(x)=max⁡jQj(x)−Qk(x).F_k(x)=\max_j Q_j(x)-Q_k(x).

These functions are continuous and nonnegative, and (13) gives Fk(x)=0F_k(x)=0 whenever xk=0x_k=0. By Lemma 8, they are all equal at some x∗x^*. At every point, at least one FkF_k equals zero, so their common value at x∗x^* is zero. Therefore all Qk(x∗)Q_k(x^*) are equal.

The statement about random items follows from the interval construction. □

Rounding and subsidies

We now draw an integral partition from the distribution in Proposition 9. Concentration around the common expected price bounds the spread of the realized prices. Their minimum is zero, so the same bound controls the maximum price and hence the subsidies.

Proof of Theorem 1. If n=1n=1, assign every item to the only agent and pay no subsidy. If M=∅M=\varnothing, give every agent the empty bundle and again pay no subsidy. Hence assume that n≥2n\ge2 and m≥1m\ge1.

Choose x∗x^* as in Proposition 9, and write

μ=Q1(x∗)=⋯=Qn(x∗).\mu=Q_1(x^*)=\cdots=Q_n(x^*).

Let HH be the set of fractional items and h=∣H∣≤n−1h=|H|\le n-1. If h=0h=0, the partition is deterministic and all its prices equal μ\mu. By Lemma 4, one price is zero, and hence they all are. A maximum-weight matching then gives an envy-free allocation with zero subsidies. Now suppose that h≥1h \ge1. The price qk(R(x∗))q_k(R(x^*)) is a function of the independent destinations of the hh fractional items. Changing one destination moves one item between bundles, so Lemma 7 bounds the change in this function by 5. McDiarmid’s inequality gives

P[∣qk(R(x∗))−μ∣≥t]≤2exp⁡(−2t225h).(14)\mathbb{P}\left[\left|q_k(R(x^*))-\mu\right|\ge t\right]\le2\exp\left(-\frac{2t^2}{25h}\right). \tag*{(14)}

Set

t=5h2log⁡(4n).t=5\sqrt{\frac{h}{2}\log(4n)}.

For each kk, the probability in (14) is at most 1/(2n)1/(2n). A union bound shows that, with probability at least 1/21/2, all nn prices differ from μ\mu by less than tt. Fix a realized partition B~={B~1,…,B~n}\widetilde{\mathcal{B}}=\{\widetilde{B}_1,\ldots,\widetilde{B}_n\} with this property, where B~k\widetilde{B}_k is the realized bundle in slot kk.

Since the minimum canonical price is zero by Lemma 4, there exists j∈[n]j\in[n] such that qj(B~)=0q_j(\widetilde{\mathcal{B}})=0. Hence, ∣qj(B~)−μ∣=μ≤t\lvert q_j(\widetilde{\mathcal{B}})-\mu\rvert=\mu\le t. As every canonical price is within tt of μ\mu, it follows that

qmax⁡(B~)≤2t=52hlog⁡(4n)≤52(n−1)log⁡(4n).q_{\max}(\widetilde{\mathcal{B}})\le2t=5\sqrt{2h\log(4n)}\le5\sqrt{2(n-1)\log(4n)}.

Finally, choose a maximum-weight matching σ\sigma for B~\widetilde{\mathcal{B}}. Form the allocation Ai=B~σ(i)A_i=\widetilde{B}_{\sigma(i)} and pay agent ii the subsidy pi=qmax⁡(B~)−qσ(i)(B~)p_i=q_{\max}(\widetilde{\mathcal{B}})-q_{\sigma(i)}(\widetilde{\mathcal{B}}). By Lemma 4, the resulting outcome is envy-free, each agent receives at most qmax⁡(B~)q_{\max}(\widetilde{\mathcal{B}}), and

∑i∈Npi≤(n−1)qmax⁡(B~)≤52(n−1)3/2log⁡(4n).\sum_{i\in N}p_i\le(n-1)q_{\max}(\widetilde{\mathcal{B}})\le5\sqrt{2}(n-1)^{3/2}\sqrt{\log(4n)}.

This proves the theorem.

Discussion

We have prioritized a simple, unified analysis over optimizing the constants in the subsidy bound. A more careful accounting in our proof yields a total-subsidy bound of (n−1)(2n+3)log⁡n(n-1)\sqrt{(2n+3)\log n} when valuations are either all nonnegative or all nonpositive. For monotone goods or monotone chores, this bound improves to (n−1)n+52log⁡n(n-1)\sqrt{\frac{n+5}{2}\log n}.

Beyond the sign assumption. The sign assumption enters our proof only through the empty-bundle boundary condition: an empty bundle has minimum canonical price for nonnegative valuations and maximum canonical price for nonpositive valuations. This boundary condition enables the KKM argument to equalize expected prices. All other ingredients—the matching identity, one-item stability, and concentration—apply to arbitrary valuations with bounded single-item marginals. Extending our approach to mixed-sign valuations for every number of agents therefore calls for an alternative way to equalize expected prices.

Closing the gap. The single-good example gives a lower bound of n−1n-1, leaving a gap between this linear lower bound and our upper bound of O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}). In our proof, the factor log⁡n\sqrt{\log n} arises from the union bound over the nn prices. Can a different rounding argument remove this factor? More broadly, does a linear total-subsidy bound hold for general monotone valuations?

Efficient computation. A further question is whether our total-subsidy bound of O(n3/2log⁡n)O(n^{3/2}\sqrt{\log n}) can be achieved by a polynomial-time algorithm. For a fixed partition, the canonical prices can be computed efficiently from the agent–bundle values by solving the matching problems in Lemma 5. The challenge lies in finding a suitable partition. Our KKM argument establishes the existence of an equalizing point x∗x^{*} but does not provide a polynomial-time procedure for finding it. Moreover, direct evaluation of the expected-price functions may require summing over exponentially many rounding outcomes. An efficient implementation of our approach would need to overcome both obstacles.

Acknowledgments. Mashbat Suzuki is supported by the ARC Laureate Project FL200100204 on “Trustworthy AI”.

Declaration of generative AI use. All research results in this paper were obtained by the authors without AI assistance. GPT-5.6 Sol was used solely to refine the exposition, improving the clarity, phrasing, and presentation of the manuscript.

References

  1. [2]Siddharth Barman, Anand Krishna, Yadati Narahari, and Soumyarup Sadhukhan. Achieving envy-freeness with limited subsidies under dichotomous valuations. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, pages 60–66. International Joint Conferences on Artificial Intelligence Organization, 2022. doi: 10.24963/ijcai.2022/9. URL https://www.ijcai.org/proceedings/2022/9.DOI
  2. [3]Johannes Brustle, Jack Dippel, Vishnu V. Narayan, Mashbat Suzuki, and Adrian Vetta. One dollar each eliminates envy. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 23–39. ACM, 2020. doi: 10.1145/3391403.3399447.DOI
  3. [5]Max Dupré la Tour and Kaito Fujii. Discrepancy and fair division for non-additive valuations. arXiv preprint arXiv:2509.16802, 2025. doi: 10.48550/arXiv.2509.16802. URL https://arxiv.org/abs/2509.16802.
  4. [6]Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, and Makoto Yokoo. A fair and truthful mechanism with limited subsidy. Games and Economic Behavior, 144:49–70, 2024. doi: 10.1016/j.geb.2023.12.006.DOI
  5. [7]Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87(1):95–124, 1999. doi: 10.1006/jeth.1999.2531.DOI
  6. [8]Daniel Halpern and Nisarg Shah. Fair division with subsidy. In Algorithmic Game Theory: 12th International Symposium, SAGT 2019, pages 374–389. Springer, 2019. doi: 10.1007/978-3-030-30473-7_25.DOI
  7. [10]Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, and Makoto Yokoo. Towards optimal subsidy bounds for envy-freeable allocations. Proceedings of the AAAI Conference on Artificial Intelligence, 38(9):9824–9831, 2024. doi: 10.1609/aaai.v38i9.28842.
  8. [11]Bronisław Knaster, Kazimierz Kuratowski, and Stefan Mazurkiewicz. Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe. Fundamenta Mathematicae, 14(1):132–137, 1929.
  9. [12]Bo Li, Ankang Sun, Mashbat Suzuki, and Shiji Xing. On the subsidy of envy-free orientations in graphs. arXiv preprint arXiv:2502.13671, 2025. URL https://arxiv.org/abs/2502.13671.
  10. [13]Shengxin Liu, Xinhang Lu, Mashbat Suzuki, and Toby Walsh. Mixed fair division: A survey. Journal of Artificial Intelligence Research, 80:1373–1406, 2024. doi: 10.1613/jair.1.15800. URL https://jair.org/index.php/jair/article/view/15800.DOI
  11. [14]Xinhang Lu, Simon Mackenzie, and Mashbat Suzuki. Optimal subsidy bounds for goods and chores: One dollar each suffices. arXiv preprint arXiv:2607.10089, 2026. URL https://arxiv.org/abs/2607.10089.
  12. [15]Colin McDiarmid. On the method of bounded differences. In Surveys in Combinatorics, 1989, volume 141 of London Mathematical Society Lecture Note Series, pages 148–188. Cambridge University Press, 1989.DOI

Paper details

vlnc:W_qqs7dxhd
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents