betaFeedback

WorksComputer Science

Computing EF1 Allocations with Few Value Queries

Abstract

We give a deterministic polynomial-time algorithm that allocates mm indivisible goods among nn agents with nonnegative additive valuations using O(n5log⁡2m)O(n^5\log^2 m) value queries and guarantees envy-freeness up to one good (EF1). Concurrent work of Lin, Liu, Tao, and Zhou achieves O(n8log⁡m)O(n^8\log m) comparison queries, attaining the optimal O(log⁡m)O(\log m) dependence on mm for fixed nn. Each comparison query can be simulated using two value queries, so their bound also holds for value queries. Our contributions are a much simpler algorithm and proofs, and polynomial-time computation.

Introduction

We study how to allocate indivisible goods fairly among agents with different preferences. A central fairness requirement is envy-freeness (EF) [8], under which no agent prefers another agent’s bundle to her own. However, an envy-free allocation need not exist: if two agents must divide a single good that both value positively, whoever receives it is envied by the other agent.

A standard relaxation is envy-freeness up to one good (EF1) [2]: for every pair of agents, removing at most one good from the second agent’s bundle must eliminate the first agent’s envy toward that bundle. For monotone valuations, the classical envy-cycle elimination algorithm of Lipton et al. [6] guarantees an EF1 allocation.

Finding a fair allocation requires information about the agents’ preferences. In the value-query model, an algorithm asks an agent for the exact numerical value of a specified bundle. The query complexity counts these requests, separately from the computation performed by the algorithm. With nn agents and mm goods, envy-cycle elimination admits an implementation in polynomial time using O(mn)O(mn) value queries [7]. This bound applies to arbitrary monotone valuations.

We focus on the regime in which the number of agents is small while the number of goods is large. Asking each agent to report a value for every good can be time-consuming. This concern persists even for nonnegative additive valuations, where a bundle’s value is the sum of its goods’ values and the entire instance can be specified by mnmn numbers. Value queries permit the algorithm to evaluate large bundles directly, raising the possibility of computing an EF1 allocation without learning all singleton values.

Oh, Procaccia, and Suksompong [7] established that O(log⁡m)O(\log m) value queries suffice for two or three agents with additive valuations. These results motivate studying the dependence on mm for an arbitrary fixed number of agents. In this paper, we develop a simple polynomial-time algorithm for additive valuations based on the envy-cycle elimination algorithm.

Our results

Theorem 1.1 (Value queries). There is a deterministic algorithm that, for n≥2n \ge2 agents with nonnegative additive valuations over m>nm > n goods, finds a complete EF1 allocation using O(n5log⁡2m)O(n^5 \log^2 m) value queries. It runs in time polynomial in n,mn,m in the exact real-arithmetic model.

For fixed nn, the query bound is O(log⁡2m)O(\log^2 m). Our running-time bound uses unit-cost exact arithmetic and comparisons. It excludes oracle evaluation time.

Concurrent work

In concurrent work, Lin, Liu, Tao, and Zhou [5] give an O(n8log⁡m)O(n^8 \log m) comparison-query algorithm for additive goods and chores. A comparison query asks an agent which of two bundles she weakly prefers. Their dependence on mm is better than ours and is tight for fixed nn, matching the known Ω(log⁡m)\Omega(\log m) lower bound for deterministic algorithms [7]. Their bound also yields O(n8log⁡m)O(n^8 \log m) value queries by simulating each comparison with two value queries. Thus our contribution is not a sharper dependence on mm.

Our contributions are a simpler proof and polynomial running time. Their paper does not state an explicit total running-time bound, but a straightforward implementation takes mO(n)m^{O(n)} time. Our algorithm runs in time polynomial in both nn and mm in the exact real-arithmetic model.

Proof overview

Sparse fractional consensus. The algorithm maintains a small set HH of goods, called the core, to be allocated individually. In each round, we divide the remaining goods R=M∖HR = M \setminus H into nn bundles, temporarily allowing goods to be split between bundles. We require every agent ii to value each bundle at exactly vi(R)/nv_i(R)/n. Such a division is called a fractional consensus allocation. We compute a sparse allocation of this kind, in which at most n(n−1)n(n-1) goods are split between bundles [4].

Refining blocks with few queries. To compute this allocation with few value queries, we group goods into blocks, starting with the single block RR shared equally among all nn bundles. Linear dependencies among the blocks’ value vectors let us adjust their shares while preserving consensus until at most n(n−1)n(n-1) blocks remain fractional. We fix the blocks assigned entirely to one bundle and split each remaining nonsingleton block into two parts of nearly equal cardinality. Only the new blocks require value queries. Repeating this procedure leaves only singleton fractional blocks after O(log⁡m)O(\log m) stages. This adaptation of consensus-splitting methods [1, 4] uses O(n3log⁡m)O(n^3 \log m) value queries per round.

Setting aside fractional goods. Let BjB_j contain the goods assigned entirely to bundle jj, and let FF contain the fractional goods. Then B1,…,Bn,FB_1,\ldots,B_n,F partition RR, with ∣F∣≤n(n−1)|F| \le n(n-1). Removing the fractional goods gives the key inequality

vi(Bj)≤vi(R)/n(i,j∈[n]).(1)v_i(B_j) \le v_i(R)/n \qquad(i,j \in[n]). \tag*{(1)}

We query each agent’s value for every base and every individual good in FF. The values of the core goods in HH are already known.

One round of the algorithm

Figure 1. One round of the algorithm.

Certifying the completed bundles. Starting from the bases, we insert the goods of H∪FH \cup F by envy-cycle elimination. Each insertion goes to an unenvied bundle, while every agent’s own value never decreases. Consequently, bundles receiving new goods satisfy the EF1 inequalities after deleting their last inserted good. Only bundles receiving no new good need a final test. If all such bundles are unenvied, the allocation is EF1.

A failed test grows the core. Let Ti(H)T_i(H) be the value to agent ii of the core after deleting its nn most valuable goods, or all its goods if ∣H∣<n|H| < n. If ii envies an unchanged bundle, summing the base bounds (1) and the last-insertion inequalities shows that some g∈Fg \in F satisfies vi(g)>Ti(H)/nv_i(g) > T_i(H)/n. We add such a good to HH and charge the addition to ii.

Bounding the number of rounds. Every 2n2n additions charged to an agent at least double her trimmed core value Ti(H)T_i(H). A short initialization ensures Ti(H0)≥vi(R0)/(2m)T_i(H_0) \ge v_i(R_0)/(2m), where R0=M∖H0R_0 = M \setminus H_0. If agent ii is charged an addition, she envies a bundle contained in R0R_0, so vi(R0)>0v_i(R_0) > 0 and hence Ti(H0)>0T_i(H_0) > 0. Since later additions all come from R0R_0, this value can grow by at most a factor of 2m+12m + 1. Thus each agent receiving a charge can undergo only O(log⁡m)O(\log m) such doublings and can be charged only O(nlog⁡m)O(n \log m) additions. Every unsuccessful round adds one good and charges it to one of the nn agents. There are therefore at most O(n2log⁡m)O(n^2 \log m) unsuccessful rounds.

Related work

Oh, Procaccia, and Suksompong [7] study the value-query complexity of fair allocation. In addition to their logarithmic bounds for up to three additive agents, they give an O(log⁡2m)O(\log^2 m) bound for three monotone agents and an O(nm)O(nm) implementation of envy-cycle elimination for arbitrary monotone valuations.

Our fractional construction draws on consensus splitting. Goldberg et al. [4] use linear dependencies among value vectors to leave few fractional goods, and Alon and Graur [1] refine fractional pieces in necklace splitting. We adapt these ideas to aggregate queries and combine them with envy-cycle completion. Feige [3] studies communication and description complexity for fair allocation, which measure different resources from the value queries considered here.

Preliminaries

Allocation

There are nn agents, indexed by [n]={1,…,n}[n] = \{1,\ldots,n\}, and a set MM of mm goods. Each agent ii has a nonnegative additive valuation vi:2M→R≥0v_i: 2^M \to\mathbb{R}_{\ge0}:

vi(S)=∑g∈Svi(g)(S⊆M),v_i(S) = \sum_{g \in S} v_i(g) \qquad(S \subseteq M),

where vi(g)=vi({g})v_i(g) = v_i(\{g\}). A bundle is a subset of MM.

A partial allocation A=(A1,…,An)A = (A_1,\ldots,A_n) consists of pairwise disjoint bundles, where agent ii receives AiA_i, and is complete if their union is MM.

A fractional allocation allows each good to be split among the nn bundles, with each bundle receiving a share of the good. Formally, a fractional allocation of S⊆MS \subseteq M assigns shares xjg≥0x_{jg} \ge0 with ∑j=1nxjg=1\sum_{j=1}^{n} x_{jg} = 1 for every g∈Sg \in S. Writing xj=(xjg)g∈Sx_j = (x_{jg})_{g \in S} for the jjth fractional bundle, we extend the valuations to fractional bundles linearly:

vi(xj)=∑g∈Sxjgvi(g).v_i(x_j) = \sum_{g \in S} x_{jg}v_i(g).

A good is integral if it belongs entirely to one bundle, that is, one share is 1. It is strictly fractional if it is split between at least two bundles.

A consensus allocation is a fractional allocation in which every agent values all nn bundles equally. Thus every bundle is worth exactly one nth of the total value to each agent:

vi(xj)=vi(S)/n(i,j∈[n]).v_i(x_j) = v_i(S)/n \qquad(i,j \in[n]).

Giving each bundle a 1/n1/n share of every good always yields consensus.

Fairness

Given a partial allocation (A1,…,An)(A_1,\ldots,A_n), agent ii envies AjA_j if vi(Ai)<vi(Aj)v_i(A_i) < v_i(A_j). A bundle is unenvied if no agent envies it. An allocation is envy-free up to one good (EF1) if, for every i,ji,j with Aj≠∅A_j \ne\varnothing, some g∈Ajg \in A_j satisfies vi(Ai)≥vi(Aj∖{g})v_i(A_i) \ge v_i(A_j \setminus\{g\}).

If n=1n = 1, allocating all goods to the single agent is EF1. If m≤nm \le n, allocating at most one good to each agent is EF1. These cases require no queries, so we assume n≥2n \ge2 and m>nm > n.

Query model

A value query specifies an agent ii and a bundle SS and returns vi(S)v_i(S) exactly. We count oracle calls across all agents. Running time is measured in the exact real-arithmetic model: each operation ++, −-, ×\times, ÷\div and each comparison of real numbers costs one step. Bundles are represented explicitly. We include query preparation and output, but exclude the oracle’s own evaluation time. All logarithms are base two.

Envy Cycle

The envy graph of a partial allocation AA has one vertex for each agent and an edge i→ji \to j whenever ii envies AjA_j. Starting from a partial allocation, the envy-cycle elimination algorithm of Lipton et al. [6] repeats the following steps until all goods are allocated.

  1. Eliminate envy cycles. If the envy graph contains a directed cycle i1→i2→⋯→ik→i1i_1 \to i_2 \to\cdots\to i_k \to i_1, simultaneously give each agent iti_t the bundle of it+1i_{t+1}, with indices taken modulo kk. Update the envy graph and repeat until it is acyclic.

  1. Insert a good. Choose an agent with no incoming edge in the resulting graph and add any unallocated good to her bundle. Such an agent exists because the graph is acyclic, and her bundle is unenvied before the insertion. Update the envy graph.

Each cycle exchange strictly increases the value of every participant’s own bundle and leaves all other agents’ bundles unchanged. An insertion cannot decrease the recipient’s value, since valuations are nonnegative. Thus every agent’s value for her own bundle is nondecreasing throughout the algorithm.

To track insertions when bundles change owners, give each initial bundle a distinct fixed label. A label follows its bundle through cycle exchanges and is retained when a good is added. Call a bundle unchanged if it receives no new good during completion, even if it changes owners.

Lemma 2.1 (Number of cycle exchanges). Between consecutive insertions, and before the first insertion, envy-cycle elimination performs at most n(n−1)/2n(n-1)/2 cycle exchanges.

Proof. Without insertions, the contents of the nn bundles remain fixed. For each agent ii, define the rank of a bundle as the number of bundles she values strictly less. Each rank lies between 00 and n−1n-1, so the sum of the agents’ ranks for their own bundles lies between 00 and n(n−1)n(n-1). A cycle exchange gives each participant a strictly more valuable bundle, increasing her rank by at least one. Every cycle has at least two participants, so each exchange increases the rank sum by at least two. The claimed bound follows.

Lemma 2.2 (Last-insertion property). Suppose a partial allocation is completed by inserting goods into unenvied bundles and exchanging bundles, without decreasing any agent’s value for her own bundle. In the final allocation AA, every bundle PP that received a new good satisfies

vi(Ai)≥vi(P∖{g})(i∈[n]),v_i(A_i) \ge v_i(P \setminus\{g\}) \qquad(i \in[n]),

where gg is the last good inserted into PP. If every nonempty unchanged bundle is unenvied, the completed allocation is EF1.

Proof. Since gg is the last good inserted into PP, the bundle’s contents just before this insertion were P∖{g}P \setminus\{g\}. At that time, the bundle was unenvied, so every agent valued her own bundle at least as much as P∖{g}P \setminus\{g\}. Agents’ own values never decrease, which proves the inequality at completion. If a nonempty unchanged bundle is unenvied at completion, removing any one of its goods also gives the EF1 inequalities by nonnegativity.

Thus, when completing an arbitrary partial allocation, the only possible obstruction to EF1 is an unchanged bundle: some agent may still envy it after the removal of any one of its goods. Every bundle that receives a new good satisfies EF1 by the last-insertion property, regardless of who owns it at completion. In particular, starting from empty bundles gives a complete EF1 allocation, since every nonempty final bundle has received a good.

Algorithm and analysis

The algorithm maintains a core H⊆MH \subseteq M whose singleton values are known for every agent. Each round constructs a sparse consensus allocation of R=M∖HR = M \setminus H, sets aside its strictly fractional goods, and uses the remaining bundles as bases. We complete these bases by inserting the goods set aside together with the core goods. A failed completion test identifies a good to add to HH. We describe these steps in order, then choose the initial core and bound the number of rounds.

Constructing a sparse consensus allocation

Equal shares give a consensus allocation, but make every good strictly fractional. We reduce the number of such goods by treating groups of goods together. Whenever a group is assigned entirely to one bundle, its allocation is fixed. Only groups that remain strictly fractional are divided into smaller groups.

Lemma 3.1 (Sparse consensus allocation). For any S⊆MS \subseteq M, O(n3log⁡m)O(n^3 \log m) value queries suffice to find a consensus allocation x=(x1,…,xn)x = (x_1,\ldots,x_n) of SS with at most n(n−1)n(n-1) strictly fractional goods.

Proof. The claim is immediate if S=∅S = \varnothing, so assume SS is nonempty. All choices in the construction follow fixed deterministic rules.

Working with blocks. Throughout the construction, we represent xx by a partition of SS into blocks. All goods in a block CC have identical shares, and xjCx_{jC} denotes the common value of xjgx_{jg} for g∈Cg \in C. The contribution of CC to vi(xj)v_i(x_j) is therefore xjCvi(C)x_{jC}v_i(C). Knowing the block values vi(C)v_i(C) lets us compute how changing these shares affects every agent’s value for every bundle. We call a block integral or strictly fractional according to its goods. Once a block becomes integral, we keep its assignment fixed and never split it again.

Initially, query vi(S)v_i(S) for every agent, use the single block SS, and set xjg=1/nx_{jg} = 1/n. This is a consensus allocation with one strictly fractional block. We will maintain consensus and keep at most n(n−1)n(n-1) blocks strictly fractional at the end of each stage.

One refinement stage. As long as some strictly fractional block contains at least two goods, perform the following two steps.

  1. Split the blocks. Divide each nonsingleton strictly fractional block CC into two parts C1,C2C_1,C_2 whose cardinalities differ by at most one. Query both vi(C1)v_i(C_1) and vi(C2)v_i(C_2) for every agent. Give both children their parent’s shares: xjC1=xjC2=xjCx_{jC_1}=x_{jC_2}=x_{jC}. No good’s share changes, so consensus is preserved. Keep singleton blocks as they are.

  1. Adjust the shares. Keeping integral blocks fixed, change the shares of the strictly fractional blocks until at most n(n−1)n(n-1) of them remain. The argument below shows how to do this while preserving consensus, using only the block values already known.

Splitting makes the blocks smaller but can double their number. Adjusting the shares restores the bound on their number. We stop after the adjustment step once every strictly fractional block is a singleton.

Why the shares can be adjusted. Suppose there are r>n(n−1)r > n(n-1) strictly fractional blocks. In each such block CC, choose two positive shares and introduce one signed transfer amount zCz_C between them: add zCz_C to one share and subtract it from the other. Thus each good’s shares still sum to one. The change in vi(xj)v_i(x_j) is a linear function of the rr transfer amounts, with coefficients given by the known block values. Requiring this change to be zero for every i∈[n]i \in[n] and every j<nj < n gives n(n−1)n(n-1) homogeneous linear equations in rr variables. Since r>n(n−1)r > n(n-1), there is a nonzero solution. The value of the last bundle is also preserved for every agent, because the sum of her values for all bundles remains vi(S)v_i(S).

Scale all transfers in this solution by the same positive factor, increasing it until a decreasing share first reaches zero. Such a factor exists: all selected shares are initially positive, and every nonzero transfer decreases one of them. This step preserves consensus and nonnegativity, eliminates at least one positive share, and never makes a zero share positive. While more than n(n−1)n(n-1) blocks remain strictly fractional, repeat this operation, choosing two positive shares anew in each such block. Each step reduces the total number of positive shares, so after finitely many steps at most n(n−1)n(n-1) blocks remain strictly fractional. No value queries are needed for these computations.

Termination and query count. After kk refinement stages, every strictly fractional block has at most ⌈∣S∣/2k⌉\lceil|S|/2^k\rceil goods. Indeed, every nonsingleton such block is halved in each stage, and integral blocks are never split again. Hence after at most ⌈log⁡∣S∣⌉\lceil\log|S|\rceil stages, the remaining strictly fractional blocks are singletons. The adjustment step leaves at most n(n−1)n(n-1) of them, giving the required bound on strictly fractional goods.

Each stage starts with at most n(n−1)n(n-1) strictly fractional blocks and uses 2n2n queries for each block that is split. Including the initial nn queries, the total number of value queries is at most

n+2n⋅n(n−1)⌈log⁡∣S∣⌉=O(n3log⁡m).n+2n\cdot n(n-1)\lceil\log|S|\rceil=O(n^3\log m).

Constructing the bases

Fix a core HH and write R=M∖HR=M\setminus H. Apply Lemma 3.1 to obtain a consensus allocation xx of RR. For each j∈[n]j\in[n], the base

Bj={g∈R:xjg=1}B_j=\{g\in R:x_{jg}=1\}

contains the goods assigned entirely to bundle jj. Let FF be the set of strictly fractional goods in xx. Then B1,…,Bn,FB_1,\ldots,B_n,F partition RR, with ∣F∣≤n(n−1)|F|\le n(n-1).

We query every agent’s value for every base BjB_j and every good in FF. There are nn bases and at most n(n−1)n(n-1) goods in FF, so this uses O(n3)O(n^3) value queries.

The consensus equality gives

vi(Bj)+∑g∈Fxjgvi(g)=vi(R)/n(i,j∈[n]).v_i(B_j)+\sum_{g\in F}x_{jg}v_i(g)=v_i(R)/n \qquad(i,j\in[n]).

Removing the nonnegative contribution of the fractional goods yields

vi(Bj)≤vi(R)/n(i,j∈[n]).(2)v_i(B_j)\le v_i(R)/n \qquad(i,j\in[n]). \tag*{(2)}

This key inequality will let us prove progress after a failed completion test by identifying a sufficiently valuable good in FF to add to the core.

Completing the allocation

Starting from the bases constructed in § 3.2, complete (B1,…,Bn)(B_1,\ldots,B_n) by inserting H∪FH\cup F using envy-cycle elimination, and let AA be the resulting allocation. We use the sufficient condition from Lemma 2.2 to certify EF1: check whether every nonempty unchanged bundle is unenvied. If this test fails, we use the resulting envy to identify a good to add to the core.

To measure progress when this test fails, define the trimmed core value

Ti(H)=min⁡D⊆H∣D∣≤nvi(H∖D).(3)T_i(H)=\min_{\substack{D\subseteq H\\ |D|\le n}} v_i(H\setminus D). \tag*{(3)}

This deletes the nn core goods most valuable to ii, or all core goods if ∣H∣≤n|H|\le n. The deletion accounts for the at most nn last inserted goods in the completion bounds. We use TiT_i only in the analysis; the algorithm does not compute it.

Lemma 3.2 (Completion). For the completion described above, if all nonempty unchanged bundles are unenvied, AA is EF1. If agent ii envies an unchanged bundle, some g∈Fg\in F satisfies vi(g)>Ti(H)/nv_i(g)>T_i(H)/n.

Proof. The first claim follows from Lemma 2.2. For the second, the envied unchanged bundle satisfies (2), so vi(Ai)<vi(R)/nv_i(A_i)<v_i(R)/n. Let UU be the set of last inserted goods of the bundles that received a new good. These goods are distinct and lie in H∪FH\cup F. Since at least one bundle is unchanged, ∣U∣<n|U|<n.

An unchanged bundle has value at most vi(R)/nv_i(R)/n by (2). For a bundle PP that received a new good, let gg be its last inserted good. Additivity and Lemma 2.2 give

vi(P)=vi(P∖{g})+vi(g)≤vi(Ai)+vi(g)≤vi(R)/n+vi(g).v_i(P)=v_i(P\setminus\{g\})+v_i(g) \le v_i(A_i)+v_i(g)\le v_i(R)/n+v_i(g).

Thus every final bundle PP satisfies

vi(P)≤vi(R)/n+vi(P∩U).v_i(P)\le v_i(R)/n+v_i(P\cap U).

The inequality is strict for P=AiP=A_i, since vi(Ai)<vi(R)/nv_i(A_i)<v_i(R)/n. Summing over the bundles yields vi(M)<vi(R)+vi(U)v_i(M)<v_i(R)+v_i(U). Since HH and RR partition MM, subtracting vi(R)v_i(R) gives vi(H)<vi(U)v_i(H)<v_i(U). As U⊆H∪FU\subseteq H\cup F and H∩F=∅H\cap F=\varnothing, additivity lets us write this as

vi(H∖U)+vi(U∩H)<vi(U∩H)+vi(U∩F).v_i(H\setminus U)+v_i(U\cap H)<v_i(U\cap H)+v_i(U\cap F).

Cancelling vi(U∩H)v_i(U\cap H) gives vi(H∖U)<vi(U∩F)v_i(H\setminus U)<v_i(U\cap F). Moreover, ∣U∩H∣<n|U\cap H|<n, so U∩HU\cap H is an allowed deletion set in the definition of Ti(H)T_i(H). Hence

Ti(H)≤vi(H∖U)<vi(U∩F).T_i(H)\le v_i(H\setminus U)<v_i(U\cap F).

Thus U∩FU\cap F is nonempty and contains fewer than nn goods, one of which is worth more than Ti(H)/nT_i(H)/n.

Bounding the number of rounds

We charge each added good to the agent whose envy triggered its addition. Lemma 3.2 guarantees vi(g)>Ti(H)/nv_i(g)>T_i(H)/n for the charged agent ii. We will show that every 2n2n additions charged to an agent at least double her trimmed core value. To bound the number of such doublings, we first choose an initial core whose trimmed value is at least a 1/(2m)1/(2m) fraction of the remaining value for every agent.

Lemma 3.3 (Initial core). Using O(n2log⁡m)O(n^2\log m) value queries, one can select a core H0H_0 of at most n(n+1)n(n+1) goods such that, for R0=M∖H0R_0=M\setminus H_0,

Ti(H0)≥vi(R0)/(2m)(i∈[n]).(4)T_i(H_0)\ge v_i(R_0)/(2m)\qquad(i\in[n]). \tag*{(4)}

Proof. For agent ii and a nonempty set SS, repeatedly split the current set into two parts of nearly equal cardinality, query their values, and retain a part of maximum value. Each step keeps at least half the value. Within ⌈log⁡∣S∣⌉\lceil\log|S| \rceil steps we obtain a good gg with

vi(g)≥vi(S)2⌈log⁡∣S∣⌉≥vi(S)2∣S∣.v_i(g) \ge\frac{v_i(S)}{2^{\lceil\log|S| \rceil}} \ge\frac{v_i(S)}{2|S|}.

The search uses O(log⁡m)O(\log m) queries.

Process the agents in order, selecting n+1n+1 fresh goods for each, or all remaining goods if fewer are available. Each search starts from all goods not yet selected. This uses O(n2log⁡m)O(n^2 \log m) queries. If R0R_0 is empty, (4) follows from nonnegativity. Otherwise all selections were made. Every good selected for ii is worth at least vi(R0)/(2m)v_i(R_0)/(2m), since its search started from a set containing R0R_0 with at most mm goods. At least one of these n+1n+1 goods survives every deletion of nn goods.

Lemma 3.4 (Growth). Let H0H_0 satisfy (4) and let R0=M∖H0R_0 = M \setminus H_0. Starting from H0H_0, only add goods outside the current core. Suppose each added good gg is charged to an agent ii and satisfies

vi(g)≥Ti(H)n,v_i(g) \ge\frac{T_i(H)}{n},

where HH is the core before the addition. Then every agent ii with vi(R0)>0v_i(R_0)>0 is charged fewer than 2n(1+⌈log⁡(2m+1)⌉)2n(1+\lceil\log(2m+1)\rceil) additions.

Proof. Adding goods cannot decrease TiT_i: after any deletion of at most nn goods, the surviving old core is worth at least its previous trimmed value.

Consider 2n2n additions charged to ii, starting from a core CC. Each new good is worth at least Ti(C)/nT_i(C)/n. Deleting at most nn goods leaves at least nn of these new goods, worth at least Ti(C)T_i(C) in total. The surviving part of CC is also worth at least Ti(C)T_i(C). Thus each group of 2n2n additions at least doubles TiT_i. Intervening additions charged to other agents cannot decrease it.

In any later core, delete the same set of goods that attains Ti(H0)T_i(H_0). All newly added goods lie in R0R_0, so

Ti(H)≤Ti(H0)+vi(R0)≤(2m+1)Ti(H0),T_i(H) \le T_i(H_0) + v_i(R_0) \le(2m+1)T_i(H_0),

where the second inequality uses (4). If vi(R0)>0v_i(R_0)>0, the seed inequality also gives Ti(H0)>0T_i(H_0)>0. There cannot be 1+⌈log⁡(2m+1)⌉1+\lceil\log(2m+1)\rceil doublings, since their combined factor is greater than 2m+12m+1. This proves the bound.

Proof of the main theorem

Algorithm 1. Construct H0H_0 by Lemma 3.3, learn every core good’s value to every agent, and set H=H0H=H_0. Repeat the following round:

  1. Apply Lemma 3.1 to R=M∖HR=M\setminus H, obtaining a sparse consensus allocation xx.

  1. Form the bases B1,…,BnB_1,\ldots,B_n and the set FF, and query every agent’s value for every base and every good in FF, as in § 3.2.

  1. Complete (B1,…,Bn)(B_1,\ldots,B_n) by inserting H∪FH\cup F using envy-cycle elimination.

  1. If no nonempty unchanged bundle is envied, return the allocation. Otherwise choose an agent ii who envies one and a good g∈Fg\in F maximizing vi(g)v_i(g). Add gg to HH and charge the addition to ii.

After a failed round, retain the enlarged core and its singleton values and recompute the partial allocation of the remainder.

Proof of Theorem 1.1. In Algorithm 1, every bundle during completion consists of one BjB_j and some goods of H∪FH \cup F, all with known values. Thus completion, the final envy test, and the choice of a maximum in FF require no queries. Every good added to the core already has known singleton values.

In a failed round, the selected agent ii envies an unchanged bundle contained in R0R_0, so vi(R0)>0v_i(R_0) > 0. Lemma 3.2 ensures that FF contains a good worth more than Ti(H)/nT_i(H)/n to ii. The selected maximum meets this bound, so the required addition is always possible. Lemma 3.4 bounds the additions by O(nlog⁡m)O(n \log m) per agent, hence the number of rounds by O(n2log⁡m)O(n^2 \log m). At termination, Lemma 3.2 certifies EF1.

Constructing the sparse consensus allocation uses O(n3log⁡m)O(n^3 \log m) queries per round, and querying the bases and the goods in FF uses O(n3)O(n^3) more. Thus each round uses O(n3log⁡m)O(n^3 \log m) queries. Initialization and learning the initial core’s singleton values use O(n2log⁡m+n3)O(n^2 \log m + n^3) queries. The total is

O(n5log⁡2m).O(n^5 \log^2 m).

It remains to bound the running time. At each refinement stage, the O(n2)O(n^2) fractional blocks have O(n3)O(n^3) positive shares in total. Each transfer step makes a positive share zero and never makes a zero share positive. Thus O(n3)O(n^3) steps suffice per stage. Each step uses Gaussian elimination on a system with O(n2)O(n^2) rows and columns, then computes the largest transfer scale that keeps all shares nonnegative. These computations take polynomially many arithmetic operations.

Lemma 2.1 bounds the number of cycle exchanges between singleton insertions by O(n2)O(n^2). Constructing the envy graph and finding a cycle or an unenvied bundle take polynomial time. The algorithm has O(n2log⁡m)O(n^2 \log m) rounds and core goods, at most ⌈log⁡m⌉\lceil\log m \rceil refinement stages per round, and at most ∣H∣+n(n−1)|H| + n(n - 1) insertions per completion. Thus it performs polynomially many arithmetic and graph operations. With bundles represented explicitly, all set operations, query preparation, and output also take polynomial time in mm. This proves the claimed running time in n,mn, m.

Discussion

The concurrent work of Lin et al. [5] achieves the optimal logarithmic dependence on mm for EF1. It remains interesting to combine this dependence with a running-time bound polynomial in both nn and mm, or with the simple completion argument developed here. Finally, additivity is used both to express fractional bundle values in terms of block values and to sum the completion inequalities. Extending these arguments to broader valuations would require new ideas.

Declaration of AI use

The proofs in this paper were found with the assistance of ChatGPT Astra. The authors subsequently simplified the initial argument and improved the exposition. Large language models were also used to assist with writing and editing the manuscript. The authors take full responsibility for the content of the paper.

References

  1. [1]Noga Alon and Andrei Graur. Efficient splitting of necklaces. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics, pages 14:1–14:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021.
  2. [2]Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011.
  3. [3]Uriel Feige. Low communication protocols for fair allocation of indivisible goods. In Proceedings of the 26th ACM Conference on Economics and Computation, pages 358–382. ACM, 2025.arxiv.org/abs/2407.07641
  4. [4]Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, and Warut Suksompong. Consensus halving for sets of items. Mathematics of Operations Research, 47(4):3357–3379, 2022.
  5. [5]Zehan Lin, Shengxin Liu, Baoshuai Tao, and Shengwei Zhou. Logarithmic comparison-query complexity for EF1 allocations, 2026. Version 1, November 3, 2026. https://arxiv.org/abs/2611.04753v1.
  6. [6]Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125–131. ACM, 2004.DOI
  7. [7]Hoon Oh, Ariel D. Procaccia, and Warut Suksompong. Fairly allocating many goods with few queries. SIAM Journal on Discrete Mathematics, 35(2):788–813, 2021.DOI
  8. [8]Hal R. Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63–91, 1974.

Paper details

vlnc:W_6ju6zn74
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

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