WorksComputer Science
Computing EF1 Allocations with Few Value Queries
Abstract
We give a deterministic polynomial-time algorithm that allocates indivisible goods among agents with nonnegative additive valuations using value queries and guarantees envy-freeness up to one good (EF1). Concurrent work of Lin, Liu, Tao, and Zhou achieves comparison queries, attaining the optimal dependence on for fixed . 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 agents and goods, envy-cycle elimination admits an implementation in polynomial time using 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 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 value queries suffice for two or three agents with additive valuations. These results motivate studying the dependence on 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 agents with nonnegative additive valuations over goods, finds a complete EF1 allocation using value queries. It runs in time polynomial in in the exact real-arithmetic model.
For fixed , the query bound is . 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 comparison-query algorithm for additive goods and chores. A comparison query asks an agent which of two bundles she weakly prefers. Their dependence on is better than ours and is tight for fixed , matching the known lower bound for deterministic algorithms [7]. Their bound also yields value queries by simulating each comparison with two value queries. Thus our contribution is not a sharper dependence on .
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 time. Our algorithm runs in time polynomial in both and in the exact real-arithmetic model.
Proof overview
Sparse fractional consensus. The algorithm maintains a small set of goods, called the core, to be allocated individually. In each round, we divide the remaining goods into bundles, temporarily allowing goods to be split between bundles. We require every agent to value each bundle at exactly . Such a division is called a fractional consensus allocation. We compute a sparse allocation of this kind, in which at most 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 shared equally among all bundles. Linear dependencies among the blocks’ value vectors let us adjust their shares while preserving consensus until at most 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 stages. This adaptation of consensus-splitting methods [1, 4] uses value queries per round.
Setting aside fractional goods. Let contain the goods assigned entirely to bundle , and let contain the fractional goods. Then partition , with . Removing the fractional goods gives the key inequality
We query each agent’s value for every base and every individual good in . The values of the core goods in are already known.

Figure 1. One round of the algorithm.
Certifying the completed bundles. Starting from the bases, we insert the goods of 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 be the value to agent of the core after deleting its most valuable goods, or all its goods if . If envies an unchanged bundle, summing the base bounds (1) and the last-insertion inequalities shows that some satisfies . We add such a good to and charge the addition to .
Bounding the number of rounds. Every additions charged to an agent at least double her trimmed core value . A short initialization ensures , where . If agent is charged an addition, she envies a bundle contained in , so and hence . Since later additions all come from , this value can grow by at most a factor of . Thus each agent receiving a charge can undergo only such doublings and can be charged only additions. Every unsuccessful round adds one good and charges it to one of the agents. There are therefore at most 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 bound for three monotone agents and an 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 agents, indexed by , and a set of goods. Each agent has a nonnegative additive valuation :
where . A bundle is a subset of .
A partial allocation consists of pairwise disjoint bundles, where agent receives , and is complete if their union is .
A fractional allocation allows each good to be split among the bundles, with each bundle receiving a share of the good. Formally, a fractional allocation of assigns shares with for every . Writing for the th fractional bundle, we extend the valuations to fractional bundles linearly:
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 bundles equally. Thus every bundle is worth exactly one nth of the total value to each agent:
Giving each bundle a share of every good always yields consensus.
Fairness
Given a partial allocation , agent envies if . A bundle is unenvied if no agent envies it. An allocation is envy-free up to one good (EF1) if, for every with , some satisfies .
If , allocating all goods to the single agent is EF1. If , allocating at most one good to each agent is EF1. These cases require no queries, so we assume and .
Query model
A value query specifies an agent and a bundle and returns exactly. We count oracle calls across all agents. Running time is measured in the exact real-arithmetic model: each operation , , , 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 has one vertex for each agent and an edge whenever envies . Starting from a partial allocation, the envy-cycle elimination algorithm of Lipton et al. [6] repeats the following steps until all goods are allocated.
Eliminate envy cycles. If the envy graph contains a directed cycle , simultaneously give each agent the bundle of , with indices taken modulo . Update the envy graph and repeat until it is acyclic.
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 cycle exchanges.
Proof. Without insertions, the contents of the bundles remain fixed. For each agent , define the rank of a bundle as the number of bundles she values strictly less. Each rank lies between and , so the sum of the agents’ ranks for their own bundles lies between and . 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 , every bundle that received a new good satisfies
where is the last good inserted into . If every nonempty unchanged bundle is unenvied, the completed allocation is EF1.
Proof. Since is the last good inserted into , the bundle’s contents just before this insertion were . At that time, the bundle was unenvied, so every agent valued her own bundle at least as much as . 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 whose singleton values are known for every agent. Each round constructs a sparse consensus allocation of , 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 . 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 , value queries suffice to find a consensus allocation of with at most strictly fractional goods.
Proof. The claim is immediate if , so assume is nonempty. All choices in the construction follow fixed deterministic rules.
Working with blocks. Throughout the construction, we represent by a partition of into blocks. All goods in a block have identical shares, and denotes the common value of for . The contribution of to is therefore . Knowing the block values 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 for every agent, use the single block , and set . This is a consensus allocation with one strictly fractional block. We will maintain consensus and keep at most 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.
Split the blocks. Divide each nonsingleton strictly fractional block into two parts whose cardinalities differ by at most one. Query both and for every agent. Give both children their parent’s shares: . No good’s share changes, so consensus is preserved. Keep singleton blocks as they are.
Adjust the shares. Keeping integral blocks fixed, change the shares of the strictly fractional blocks until at most 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 strictly fractional blocks. In each such block , choose two positive shares and introduce one signed transfer amount between them: add to one share and subtract it from the other. Thus each good’s shares still sum to one. The change in is a linear function of the transfer amounts, with coefficients given by the known block values. Requiring this change to be zero for every and every gives homogeneous linear equations in variables. Since , 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 .
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 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 blocks remain strictly fractional. No value queries are needed for these computations.
Termination and query count. After refinement stages, every strictly fractional block has at most goods. Indeed, every nonsingleton such block is halved in each stage, and integral blocks are never split again. Hence after at most stages, the remaining strictly fractional blocks are singletons. The adjustment step leaves at most of them, giving the required bound on strictly fractional goods.
Each stage starts with at most strictly fractional blocks and uses queries for each block that is split. Including the initial queries, the total number of value queries is at most
Constructing the bases
Fix a core and write . Apply Lemma 3.1 to obtain a consensus allocation of . For each , the base
contains the goods assigned entirely to bundle . Let be the set of strictly fractional goods in . Then partition , with .
We query every agent’s value for every base and every good in . There are bases and at most goods in , so this uses value queries.
The consensus equality gives
Removing the nonnegative contribution of the fractional goods yields
This key inequality will let us prove progress after a failed completion test by identifying a sufficiently valuable good in to add to the core.
Completing the allocation
Starting from the bases constructed in § 3.2, complete by inserting using envy-cycle elimination, and let 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
This deletes the core goods most valuable to , or all core goods if . The deletion accounts for the at most last inserted goods in the completion bounds. We use 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, is EF1. If agent envies an unchanged bundle, some satisfies .
Proof. The first claim follows from Lemma 2.2. For the second, the envied unchanged bundle satisfies (2), so . Let be the set of last inserted goods of the bundles that received a new good. These goods are distinct and lie in . Since at least one bundle is unchanged, .
An unchanged bundle has value at most by (2). For a bundle that received a new good, let be its last inserted good. Additivity and Lemma 2.2 give
Thus every final bundle satisfies
The inequality is strict for , since . Summing over the bundles yields . Since and partition , subtracting gives . As and , additivity lets us write this as
Cancelling gives . Moreover, , so is an allowed deletion set in the definition of . Hence
Thus is nonempty and contains fewer than goods, one of which is worth more than .
Bounding the number of rounds
We charge each added good to the agent whose envy triggered its addition. Lemma 3.2 guarantees for the charged agent . We will show that every 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 fraction of the remaining value for every agent.
Lemma 3.3 (Initial core). Using value queries, one can select a core of at most goods such that, for ,
Proof. For agent and a nonempty set , 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 steps we obtain a good with
The search uses queries.
Process the agents in order, selecting fresh goods for each, or all remaining goods if fewer are available. Each search starts from all goods not yet selected. This uses queries. If is empty, (4) follows from nonnegativity. Otherwise all selections were made. Every good selected for is worth at least , since its search started from a set containing with at most goods. At least one of these goods survives every deletion of goods.
Lemma 3.4 (Growth). Let satisfy (4) and let . Starting from , only add goods outside the current core. Suppose each added good is charged to an agent and satisfies
where is the core before the addition. Then every agent with is charged fewer than additions.
Proof. Adding goods cannot decrease : after any deletion of at most goods, the surviving old core is worth at least its previous trimmed value.
Consider additions charged to , starting from a core . Each new good is worth at least . Deleting at most goods leaves at least of these new goods, worth at least in total. The surviving part of is also worth at least . Thus each group of additions at least doubles . Intervening additions charged to other agents cannot decrease it.
In any later core, delete the same set of goods that attains . All newly added goods lie in , so
where the second inequality uses (4). If , the seed inequality also gives . There cannot be doublings, since their combined factor is greater than . This proves the bound.
Proof of the main theorem
Algorithm 1. Construct by Lemma 3.3, learn every core good’s value to every agent, and set . Repeat the following round:
Apply Lemma 3.1 to , obtaining a sparse consensus allocation .
Form the bases and the set , and query every agent’s value for every base and every good in , as in § 3.2.
Complete by inserting using envy-cycle elimination.
If no nonempty unchanged bundle is envied, return the allocation. Otherwise choose an agent who envies one and a good maximizing . Add to and charge the addition to .
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 and some goods of , all with known values. Thus completion, the final envy test, and the choice of a maximum in require no queries. Every good added to the core already has known singleton values.
In a failed round, the selected agent envies an unchanged bundle contained in , so . Lemma 3.2 ensures that contains a good worth more than to . The selected maximum meets this bound, so the required addition is always possible. Lemma 3.4 bounds the additions by per agent, hence the number of rounds by . At termination, Lemma 3.2 certifies EF1.
Constructing the sparse consensus allocation uses queries per round, and querying the bases and the goods in uses more. Thus each round uses queries. Initialization and learning the initial core’s singleton values use queries. The total is
It remains to bound the running time. At each refinement stage, the fractional blocks have positive shares in total. Each transfer step makes a positive share zero and never makes a zero share positive. Thus steps suffice per stage. Each step uses Gaussian elimination on a system with 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 . Constructing the envy graph and finding a cycle or an unenvied bundle take polynomial time. The algorithm has rounds and core goods, at most refinement stages per round, and at most 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 . This proves the claimed running time in .
Discussion
The concurrent work of Lin et al. [5] achieves the optimal logarithmic dependence on for EF1. It remains interesting to combine this dependence with a running-time bound polynomial in both and , 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]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]Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011.
- [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]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]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]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]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]Hal R. Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63–91, 1974.