Approximately EFX and PO Allocations for Bivalued Chores

Shengwei Zhou; Xiaowei Wu; Zehan Lin

REVIEW 2 major objections 4 minor 31 references

Approximately EFX and PO Allocations for Bivalued Chores

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper gives polynomial-time algorithms that turn a payment-envy-free equilibrium for bi-valued chores into a (2-1/k)-EFX and Pareto-optimal allocation, and into an exact EFX and Pareto-optimal allocation when k=2.

desk verdict The (2-1/k)-EFX+PO result for {1,k} chores is likely correct and is a real improvement; the EFX+PO result for {1,2} chores rests on a false invariant about unraised agents and is unsupported as written. read the letter →

arxiv 2501.04550 v1 pith:TG47RC2M submitted 2025-01-08 cs.GT

Zehan Lin , Xiaowei Wu , Shengwei Zhou This is my paper · ORCID

classification cs.GT MSC 91B3268W25

keywords fairdivisionchoresEFXParetooptimalitybi-valuedvaluationsmarketequilibriumpaymentenvy-freenessapproximationalgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that bi-valued chores—where every item costs each agent either 1 or k—admit allocations that are both fair and efficient, and that such allocations can be computed quickly. Its first result is a polynomial-time algorithm that returns a (2-1/k)-approximate EFX allocation that is also Pareto optimal, improving the previous 3-EFX guarantee. Its second result says that when k=2, a related algorithm returns an exact EFX allocation that is also Pareto optimal. If correct, the k=2 case adds a broad family to the small set of chore instances known to admit EFX and PO allocations simultaneously.

What carries the argument

The engine is the pEF1 {1,k}-payment equilibrium, an integral allocation with item payments in {1,k} where each agent receives only items minimizing her cost-per-payment ratio and every payment-envy can be removed by deleting one item from the envier's bundle. The algorithm's load-bearing lemma shows that if an agent is not (2-1/k)-EFX toward another, then the envying agent holds a unique high-payment item, the envied agent's entire bundle lies in the envying agent's minimum pain-per-buck set, and the swap—giving the high-payment item to the envied agent and taking that agent's bundle—is feasible for both sides. Because payments never change, maintaining the equilibrium is exactly maintaining Pareto optimality. The k=2 refinement partitions agents into earning classes z, z+1, and z+2 and restricts swaps to unraised agents, making exact EFX reachable.

What would settle it

Take any {1,2}-instance, run the preliminary equilibrium construction exactly as written, and record each unraised agent's bundle after every round; if any unraised agent ever loses an item, then the proof of Lemma 4.9 collapses, and running the final reallocation on that instance would show whether the claimed EFX-and-PO output still appears or the algorithm fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that a payment-envy-free equilibrium (pEF1) for bi-valued chores—an allocation where each agent receives only items minimizing her cost-to-payment ratio, payments are 1 or k, and every payment-envy can be removed by deleting one item from the envier's bundle—can be reshaped by item swaps that preserve the equilibrium into an allocation that is (2-1/k)-EFX and Pareto optimal. The algorithm never changes item payments; every item moved is a minimum pain-per-buck item for its new owner, so the allocation remains a market equilibrium throughout, and Pareto optimality follows from the First Welfare Theorem. For k=2, the finer structure of the starting equilibrium, with agent earnings confined to z, z+1, and z+2, supports an exact EFX and PO result.

Load-bearing premise

For the k=2 theorem, the load-bearing premise is that during the preliminary equilibrium construction an unraised agent only gains items and never gives one away; the construction as written updates an unraised agent's bundle as X_i + e1 - e2, so the proof does not currently establish that premise.

Editorial extensions

If this is right

For every {1,k}-instance, a (2-1/k)-EFX and PO allocation now has a polynomial-time construction, improving the previous 3-EFX-and-PO guarantee.
For {1,2}-instances, EFX and PO allocations exist for every number of agents and items, adding a broad family to the short list of chore cases with exact EFX plus Pareto optimality.
Because every transfer is minimum-pain-per-buck feasible and payments are static, the returned allocation is a market equilibrium and hence Pareto optimal; the entire difficulty is concentrated in the fairness loop.
The k=2 algorithm terminates in O(n) reallocation rounds after the pEF1 equilibrium is built, so the total running time stays polynomial.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the unraised-agent invariant can be restored or replaced, the k=2 claim might survive with a different potential or a modified update; a direct counterexample search on small {1,2}-instances would tell whether the construction as written actually allows an unraised agent to lose items in an execution that reaches a non-EFX output.
The same 'round an integral pEF1 equilibrium instead of a fractional one' idea is likely to transfer to chores with three or more fixed cost levels; the known failure of EFX plus PO for unrestricted ternary instances marks the boundary where the method must stop.
The earning-class argument for k=2 suggests a testable extension to weighted chores with bounded payment spread: if earnings fall in a bounded interval around some z, a similar classification might yield exact EFX for other small values of k.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: Section 3 is genuinely good; Section 4 is not established. The (2-1/k)-EFX + PO guarantee for {1,k} chores improves Garg et al.'s 3-EFX and appears to hold. The proof via a pEF1 integral equilibrium and a swap between high- and low-payment agents is clean, and the invariants in 3.8–3.10 are checked carefully. I read the termination argument and it is fine. This is a solid new result.

The problem is the EFX+PO for {1,2} chores. Theorem 4.13 depends on Lemma 4.9, which asserts that if i is not EFX towards j then j is unraised. The proof invokes 'only raised agents give out items' to get that i has never lost an item. But Algorithm 2 line 18 updates X_i <- X_i + e1 - e2 with i in U: an unraised agent gives out e2 and receives e1. So the claimed invariant is false. The subsequent case analysis in Lemma 4.9 assumes the losing/gaining history of i is one-sided, which is exactly what line 18 breaks. Without j in U, Algorithm 3's reallocation to j may not give j an MPB item, and the equilibrium property—and hence PO—is no longer guaranteed. The gap is load-bearing, not cosmetic.

I want to stress what this is not. It is not a counterexample or a claim that the theorem is false; the theorem may well be true, and a repaired invariant or a different argument for j in U could save it. The first half of the paper is unaffected and stands on its own.

So my recommendation: this should go to peer review, not a desk reject. A serious referee will want the authors to fix Lemma 4.9 or replace it. If the fix is straightforward, the paper becomes a strong contribution. If not, the second theorem is part of the paper and the rejection is justified for the preprint as written. I would bring it to reading group to discuss the reallocation technique, but I would not cite the second theorem until it is proven.

Referee Report

2 major / 4 minor

Summary. The paper studies fair and efficient allocations of indivisible chores with bivalued costs ({1,k}). The authors first design an algorithm that, starting from a pEF1 integral equilibrium, performs MPB-feasible item swaps to compute a (2-1/k)-EFX and PO allocation in polynomial time, improving the prior 3-EFX guarantee. They then claim that for k=2, the same framework yields exact EFX and PO allocations in polynomial time. The first result is supported by a detailed invariant-based proof; the second result, presented in Section 4, relies on a Lemma 4.9 whose proof contains a false assertion about the behavior of unraised agents in the equilibrium algorithm.

Significance. If the (2-1/k)-EFX guarantee is correct, it is a noteworthy improvement over the state-of-the-art 3-EFX result for bivalued chores, and the technique of avoiding fractional rounding in favor of integral equilibrium reallocations is likely to be useful. The claimed EFX+PO result for {1,2}-instances would be a significant existence and computation result, as exact EFX+PO allocations for chores are known only for very restricted cases. However, the proof gap in Lemma 4.9 currently leaves the second theorem unsupported. The paper also provides a self-contained proof of the First Welfare Theorem in this context and makes appropriate references to prior equilibrium constructions.

major comments (2)

[§4.1.2, Algorithm 2; §4.2, Lemma 4.9] The proof of the fourth bullet of Lemma 4.9 rests on the assertion that 'only raised agents give out items' during Algorithm 2. This invariant is false as written: Algorithm 2 line 18 updates X_i ← X_i + e1 − e2 with i ∈ U, so an unraised agent can give away an item. Consequently, the dichotomy in the proof—that i has either never received any item or has received some items—omits the possibility that an unraised agent has both received and lost items. The subsequent earning-history argument that establishes t_j < t_i depends on this dichotomy and does not go through. Without the conclusion j ∈ U, Algorithm 3 cannot rely on Lemma 4.7 to guarantee that the high-payment item e_i lies in MPB_j, so the equilibrium property (and hence Pareto optimality) may be lost; the termination proof of Theorem 4.13 also uses j ∈ U. This is a load-bearing gap for Theorem 4.13.
[§4.2, Lemma 4.12 and Theorem 4.13] The proof of Lemma 4.12 asserts that 'by Lemma 4.7 and 4.9, the new item received by an agent must be an MPB item.' Since Lemma 4.9's proof is incomplete (as explained above), the claim that both reallocated items are MPB-feasible is not established. In particular, the case in Algorithm 3 line 7 where no low-payment item exists in X_j relies on j ∈ U to ensure e_i ∈ MPB_j via Lemma 4.7; without this, the pEF1 equilibrium invariant in Invariant 4.8 may fail, and the PO guarantee of the output allocation is unsupported. Thus the correctness of Algorithm 3 is not proven as written.

minor comments (4)

[Abstract and Introduction] The text contains several spacing artifacts (e.g., 'th e', 'it em', 'a llocation') that should be cleaned up in the final version.
[§4.2] The notation N_t is used for the earning groups {N_z, N_{z+1}, N_{z+2}}, which collides with the notation N_r for the agent groups in Algorithm 2 (Section 4.1.1). Consider using different symbols to avoid confusion.
[§3.3, Lemma 3.12] In part (1) of the proof, the inequality p(X_i^{t+1}) − 1 ≤ 2·p(X_j^t) − 1 is justified by citing that the allocation is pEF1 for agent i, but the specific bound p(X_i^t ∩ L) ≤ p(X_j^t) follows from Lemma 3.4. Please cite Lemma 3.4 explicitly.
[§4.2, Lemma 4.9] The notation in the earning-history argument, such as p^{t_i}(X^{t_i}_{l_{t_i}}), is introduced implicitly; please define it or use the established notation from Lemma 4.6 for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the EFX and EFX+PO theorems are derived by new reallocation arguments from a prior pEF1 equilibrium theorem whose assumptions do not include the target.

full rationale

I walked Theorem 3.14 and Theorem 4.13 through their proofs. The only imported heavy machinery is the pEF1 (payment-envy-free-up-to-one-item) equilibrium of [21,30], used as the starting allocation. The paper does not fit parameters to the fairness notion it claims; the (2-1/k)-EFX and EFX bounds come from explicit payment/envy inequalities (Lemmas 3.5, 3.11-3.12, 4.9-4.12) and the reallocations in Algorithms 1 and 3 maintain MPB-feasibility, so Pareto optimality follows from the standard First Welfare Theorem rather than being assumed. The self-citations to [30] are load-bearing for the structure of the starting equilibrium, but the cited theorem is a distinct, parameter-free statement (EF1+PO for bivalued chores) whose assumptions do not contain EFX or the approximation ratio, so under the stated criteria it counts as independent support. The reader-identified defect in Lemma 4.9 (the claim that only raised agents give out items, while Algorithm 2 line 18 updates X_i <- X_i + e1 - e2 for i in U) is a potential correctness gap in the proof of Theorem 4.13, not a circularity: it does not make the theorem equivalent to its input. No definitional, fitted-input, or uniqueness-imported circularity is present.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central argument rests on the definition of {1,k} instances, on the black-box pEF1 equilibrium of [21,30], and on the First Welfare Theorem. No free parameters are fitted and no new entities are invented. The fragile input is the unproven invariant in Lemma 4.9 that unraised agents never give out items, which contradicts Algorithm 2 line 18.

assumptions (3)

domain assumption Cost functions are additive and each item costs either 1 or k to every agent.
This is the bi-valued chores model; the theorems are explicitly restricted to it, so all results inherit this restriction.
domain assumption A pEF1 {1,k}-payment equilibrium exists and can be computed in polynomial time, with the structural properties of Lemma 4.5, including unraised agents having alpha_i=1 and raised agents having alpha_i=1/k.
Taken as a black box from [21,30]. Lemma 4.9 additionally assumes unraised agents never lose items during this construction, a property not proved in the cited work and contradicted by Algorithm 2 line 18.
standard math Every market equilibrium allocation is Pareto optimal, per the First Welfare Theorem.
The paper gives its own proof in Lemma 2.6; it converts the maintained equilibrium into the PO guarantee.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Approximately EFX and PO Allocations for Bivalued Chores." pith.science (2026). https://pith.science/paper/TG47RC2M

@misc{pith2026250104550,
  author       = {Pith},
  title        = {Pith review of: Approximately EFX and PO Allocations for Bivalued Chores},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TG47RC2M}},
  note         = {Machine review of arXiv:2501.04550}
}

abstract

We consider the computation for allocations of indivisible chores that are approximately EFX and Pareto optimal (PO). Recently, Garg et al. (2024) show the existence of $3$-EFX and PO allocations for bi-valued instances, where the cost of an item to an agent is either $1$ or $k$ (where $k > 1$) by rounding the (fractional) earning restricted equilibrium. In this work, we improve the approximation ratio to $(2-1/k)$, while preserving the Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores, introduced by Garg et al. (AAAI 2022) and Wu et al. (EC 2023), and reallocates items until approximate EFX is achieved. We further improve our result for the case when $k=2$ and devise an algorithm that computes EFX and PO allocations.

Figures

Figures reproduced from arXiv: 2501.04550 by the authors.

**Figure 1.** The illustration of Example 3.7. (a) The earning status of agents at the beginning of round t. (b) The earning status of agents after the swap operation. 3.3 Invariants and Analysis of Algorithm Note that we can use Xt+1 , N t+1 H , N t+1 L to denote the allocation, the set of agents with and without high payment items at the end of round t, respectively. Before analyzing the algorithm, we first 7 [PITH_FULL_IMAGE:… view at source ↗

**Figure 2.** The illustration of Example 4.10. (a) In this instance, z = 4, with Nz = {1}, Nz+1 = {2, 3, 4} and Nz+2 = {5, 6}. (b) The earning status of agents after reallocation, where p(X1) = p(X5) = 5, i.e., both of them joins Nz+1 after the reallocation. 1 2 3 4 5 6 0 4 6 p(e5) = 2 Agents Earning (a) 1 2 3 4 5 6 0 4 6 Agents Earning (b) [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

**Figure 3.** The illustration of Example 4.11. (a) The earning status of agents before reallocation. (b) The earning status of agents after reallocation, where agent 1 receives only high payment items. Given all lemmas and invariants, we can now prove the main result of this section. Theorem 4.13. For any {1, 2}-instances with n agents and m indivisible chores, EFX and PO allocations exist and can be computed in polynomial time… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 28 canonical work pages

[1]

Afshinmehr, M

M. Afshinmehr, M. Ansaripour, A. Danaei, and K. Mehlhorn. Appr oximate EFX and exact tefx allocations for indivisible chores: Improved algorithms. CoRR, abs/2410.18655, 2024

arXiv 2024
[2]

Akrami, N

H. Akrami, N. Alon, B. R. Chaudhury, J. Garg, K. Mehlhorn, and R . Mehta. EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle numb er. In EC, page 61. ACM, 2023

work page 2023
[3]

Amanatidis, H

G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Mou lin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open que stions. Artif. Intell. , 322:103965, 2023

work page 2023
[4]

Amanatidis, G

G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris. Maximum nash welfare and other stories about EFX. Theor. Comput. Sci. , 863:69–85, 2021

work page 2021
[5]

Amanatidis, A

G. Amanatidis, A. Filos-Ratsikas, and A. Sgouritsa. Pushing the f rontier on approximate EFX allocations. In EC, pages 1268–1286. ACM, 2024

work page 2024
[6]

Amanatidis, E

G. Amanatidis, E. Markakis, and A. Ntokos. Multiple birds with one s tone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci. , 841:94–109, 2020

work page 2020
[7]

H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh. Fair allocation o f indivisible goods and chores. Auton. Agents Multi Agent Syst. , 36(1):3, 2022

work page 2022
[8]

H. Aziz, B. Li, H. Moulin, and X. Wu. Algorithmic fair allocation of indivis ible items: a survey and new questions. SIGecom Exch., 20(1):24–40, 2022

work page 2022

Show all 31 references

[9]

H. Aziz, B. Li, H. Moulin, X. Wu, and X. Zhu. Almost proportional allo cations of indivisible chores: Computation, approximation and eﬃciency. Artif. Intell. , 331:104118, 2024

2024
[10]

H. Aziz, J. Lindsay, A. Ritossa, and M. Suzuki. Fair allocation of t wo types of chores. In AAMAS, pages 143–151. ACM, 2023

2023
[11]

Berger, A

B. Berger, A. Cohen, M. Feldman, and A. Fiat. Almost full EFX ex ists for four agents. In AAAI, pages 4826–4833. AAAI Press, 2022

2022
[12]

Bhaskar, A

U. Bhaskar, A. R. Sricharan, and R. Vaish. On approximate env y-freeness for indivisible chores and mixed resources. In APPROX-RANDOM, volume 207 of LIPIcs, pages 1:1–1:23. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2021

2021
[13]

Caragiannis, D

I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Sha h, and J. Wang. The unreasonable fairness of maximum nash welfare. ACM Trans. Economics and Comput. , 7(3):12:1–12:32, 2019

2019
[14]

H. Chan, J. Chen, B. Li, and X. Wu. Maximin-aware allocations of in divisible goods. In IJCAI, pages 137–143. ijcai.org, 2019. 15

2019
[15]

B. R. Chaudhury, J. Garg, and K. Mehlhorn. EFX exists for thr ee agents. J. ACM, 71(1):4:1–4:27, 2024

2024
[16]

B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa. A little charity guarantees almost envy-freeness. SIAM J. Comput. , 50(4):1336–1358, 2021

2021
[17]

Christoforidis and C

V. Christoforidis and C. Santorinaios. On the pursuit of EFX for chores: Non-existence and approximations. In IJCAI, pages 2713–2721. ijcai.org, 2024

2024
[18]

Ebadian, D

S. Ebadian, D. Peters, and N. Shah. How to fairly allocate easy a nd diﬃcult chores. In AA- MAS, pages 372–380. International Foundation for Autonomous Age nts and Multiagent Systems (IF AAMAS), 2022

2022
[19]

Gafni, X

Y. Gafni, X. Huang, R. Lavi, and I. Talgam-Cohen. Uniﬁed fair allo cation of goods and chores via copies. ACM Transactions on Economics and Computation , 11(3-4):1–27, 2023

2023
[20]

Garg and A

J. Garg and A. Murhekar. Computing fair and eﬃcient allocations with few utility values. Theor. Comput. Sci. , 962:113932, 2023

2023
[21]

J. Garg, A. Murhekar, and J. Qin. Fair and eﬃcient allocations of chores under bivalued prefer- ences. In AAAI, pages 5043–5050. AAAI Press, 2022

2022
[22]

J. Garg, A. Murhekar, and J. Qin. New algorithms for the fair an d eﬃcient allocation of indivisible chores. In IJCAI, pages 2710–2718. ijcai.org, 2023

2023
[23]

J. Garg, A. Murhekar, and J. Qin. Constant-factor EFX exist s for chores. arXiv preprint arXiv:2407.03318, 2024

2024 arXiv
[24]

Kobayashi, R

Y. Kobayashi, R. Mahara, and S. Sakamoto. EFX allocations for indivisible chores: Matching- based approach. In SAGT, volume 14238 of Lecture Notes in Computer Science , pages 257–270. Springer, 2023

2023
[25]

R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approxim ately fair allocations of indi- visible goods. In EC, pages 125–131. ACM, 2004

2004
[26]

R. Mahara. Existence of EFX for two additive valuations. Discret. Appl. Math. , 340:115–122, 2023

2023
[27]

Mas-Colell, M

A. Mas-Colell, M. D. Whinston, J. R. Green, et al. Microeconomic theory, volume 1. Oxford university press New York, 1995

1995
[28]

Plaut and T

B. Plaut and T. Roughgarden. Almost envy-freeness with gene ral valuations. SIAM J. Discret. Math., 34(2):1039–1068, 2020

2020
[29]

B. Tao, X. Wu, Z. Yu, and S. Zhou. On the existence of EFX (and pareto-optimal) allocations for binary chores. CoRR, abs/2308.12177, 2023

2023 arXiv
[30]

X. Wu, C. Zhang, and S. Zhou. Weighted EF1 allocations for indivis ible chores. In EC, page
[31]

Zhou and X

S. Zhou and X. Wu. Approximately EFX allocations for indivisible cho res. Artif. Intell. , 326:104037, 2024. 16

2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Afshinmehr, M

M. Afshinmehr, M. Ansaripour, A. Danaei, and K. Mehlhorn. Appr oximate EFX and exact tefx allocations for indivisible chores: Improved algorithms. CoRR, abs/2410.18655, 2024

arXiv 2024

[2] [2]

Akrami, N

H. Akrami, N. Alon, B. R. Chaudhury, J. Garg, K. Mehlhorn, and R . Mehta. EFX: A simpler approach and an (almost) optimal guarantee via rainbow cycle numb er. In EC, page 61. ACM, 2023

work page 2023

[3] [3]

Amanatidis, H

G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Mou lin, A. A. Voudouris, and X. Wu. Fair division of indivisible goods: Recent progress and open que stions. Artif. Intell. , 322:103965, 2023

work page 2023

[4] [4]

Amanatidis, G

G. Amanatidis, G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris. Maximum nash welfare and other stories about EFX. Theor. Comput. Sci. , 863:69–85, 2021

work page 2021

[5] [5]

Amanatidis, A

G. Amanatidis, A. Filos-Ratsikas, and A. Sgouritsa. Pushing the f rontier on approximate EFX allocations. In EC, pages 1268–1286. ACM, 2024

work page 2024

[6] [6]

Amanatidis, E

G. Amanatidis, E. Markakis, and A. Ntokos. Multiple birds with one s tone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci. , 841:94–109, 2020

work page 2020

[7] [7]

H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh. Fair allocation o f indivisible goods and chores. Auton. Agents Multi Agent Syst. , 36(1):3, 2022

work page 2022

[8] [8]

H. Aziz, B. Li, H. Moulin, and X. Wu. Algorithmic fair allocation of indivis ible items: a survey and new questions. SIGecom Exch., 20(1):24–40, 2022

work page 2022