Pith. sign in

REVIEW 1 major objections 5 minor 24 references

The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective

T0 review · 1 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read Capping every agent at k items degrades optimal social welfare by a worst-case factor that is now known exactly, as a closed-form function of m, n, and k.

desk verdict A nice parametric framing of the price of balancedness, but the proof of the headline utilitarian bound has a gap in Lemma 5 that leaves Theorem 1 unproven as written. read the letter →

arxiv 2501.01660 v1 pith:JVLZEPM7 submitted 2025-01-03 cs.GT

Alexander Lam , Bo Li , Ankang Sun This is my paper · ORCID
classification cs.GT MSC 91B32
keywords fairdivisionindivisiblegoodscardinalityconstraintpriceoffairnessutilitariansocialwelfareegalitarianparametricbounds
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

This paper asks how much social welfare is lost when a fairness rule caps each agent's bundle at k items. It introduces the price of cardinality: the worst-case multiplicative ratio between unconstrained optimal welfare and the best welfare achievable under the caps, for both total utility and the worst-off agent's utility. The central results are exact closed-form formulas: in a single category the utilitarian price is $\frac{1}{2}(1+\sqrt{1+(m-1)/k})$, and the egalitarian price is $\max\{(m-n+1)/k,1\}$. For multiple categories, the paper gives exact or near-exact formulas in terms of each category's item count and cap. If the results are correct, a decision maker can choose k knowing precisely how much worst-case welfare is sacrificed.

What carries the argument

The central object is the price of cardinality, the supremum over instances of OPT(I) divided by the best welfare subject to the caps. For the single-category utilitarian bound, the proof starts from a utilitarian-optimal allocation and partitions agents into those receiving fewer than, exactly, or more than k items. It then runs a greedy procedure that repeatedly moves the least-loss item from an over-full agent to an under-full agent, and reduces the welfare ratio to an expression of the form $(1+\sum_i u_i)/(1+k\sum_i u_i/|A_i^*|)$; a derivative argument plus the arithmetic mean\u2013harmonic mean inequality bounds this by $(1+s)/(1+ks^2/(m-1))$ with $s=-1+\sqrt{1+(m-1)/k}$, which is exactly $\frac{1}{2}(1+\sqrt{1+(m-1)/k})$. The load-bearing ordering claim inside the greedy analysis is Claim 1 in the appendix, which compares per-item losses during the procedure with the lowest-loss sets against a fixed active agent.

What would settle it

For fixed parameters such as $n=2$, $m=5$, $k=2$, search over additive normalized utility profiles and compare the ratio of optimal utilitarian welfare to best cardinal welfare against $\frac{1}{2}(1+\sqrt{1+(m-1)/k})$; a single instance with ratio above that value, or a single violation of the ordering in Claim 1, disproves Theorem 1.

Watch

Extended reading notes

Core claim

With additive, normalized utilities, imposing an at-most-k cap on each agent's bundle changes optimal social welfare by a factor that depends only on m, n, and the cap, not on the fine structure of preferences. In the single-category case the utilitarian price of cardinality is $\frac{1}{2}(1+\sqrt{1+(m-1)/k})$, exactly attained when $m=k(c^2-1)+1$ for some integer $c\ge 2$ and within an additive constant smaller than 1 for every other instance; the egalitarian price is $\max\{(m-n+1)/k,1\}$, attained for all feasible m, n, k. When goods are split into categories, the two-agent utilitarian price is $2/(k_1/m_1+k_2/m_2)$, the general-n utilitarian price is $m_1/k_1$ (tight when all ratios $k_j/m_j$ are equal), and the egalitarian price is $m_1/k_1$ when $n\le \sum_{j=2}^h m_j+1$, otherwise $\max_j (m_j-\max\{n-1-\sum_{t\neq j}m_t,0\})/k_j$. Utilitarian-optimal cardinal allocations meeting these guarantees can be computed in polynomial time by maximum-weight bipartite matching, and egalitarian allocations with the promised welfare follow from letting each agent keep its k most valued items from an egalitarian-optimal allocation.

Load-bearing premise

The whole upper bound rests on Claim 1 in Appendix A.3, which says that during the greedy reassignment the procedure's smallest per-item welfare losses are ordered no worse than the losses from moving a fixed active agent's lowest-value excess items; if that ordering ever fails, the guaranteed welfare of the cardinal allocation is not established.

Editorial extensions

If this is right

  • For a single category, imposing an at-most-k cap loses at most $\frac{1}{2}(1+\sqrt{1+(m-1)/k})$ of the optimal total utility; the bound is attained exactly when $m=k(c^2-1)+1$, and is within an additive 1 for every instance.
  • The egalitarian welfare loss is exactly $\max\{(m-n+1)/k,1\}$, so caps are harmless only when $k\ge m-n+1$; in the balanced case $k=m/n$ the loss can grow linearly with n.
  • For multiple categories, the two-agent utilitarian loss is exactly $2m_1m_2/(m_2k_1+m_1k_2)$, and the general-n loss is $m_1/k_1$, tight when all per-category ratios $k_j/m_j$ coincide.
  • A utilitarian-optimal cardinal allocation achieving the promised welfare exists and is computable in polynomial time via maximum-weight bipartite matching; egalitarian allocations follow by keeping each agent's k most valued items from an egalitarian-optimal allocation.
  • The parametric formulas turn the choice of a fairness cap into an exact tradeoff: a planner can read off the worst-case welfare loss for any k instead of relying on asymptotic estimates.

Reading between the lines

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

  • The single-category utilitarian formula contains no dependence on n beyond the feasibility requirement $n\ge m/k$; a natural testable extension is whether small-n corrections appear when caps are heterogeneous across categories.
  • Inverting the single-category bound gives a design rule the paper leaves implicit: to keep worst-case utilitarian loss at most $\rho$, one needs $k\ge (m-1)/(4\rho(\rho-1))$.
  • The greedy loss-ordering claim resembles exchange arguments used in other constrained-allocation settings; testing it on the paper's suggested dual problem of a minimum-k constraint could show whether the same parametric machinery extends.
  • For general n with many categories, the bound $m_1/k_1$ ignores all but the tightest category; the two-agent formula suggests a sharper bound involving the two smallest ratios, which is exactly the open problem the paper names.
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.

Referee Report

1 major / 5 minor

Summary. The paper introduces the price of cardinality for allocations of indivisible goods, measuring the worst-case multiplicative loss of utilitarian or egalitarian social welfare when each agent is capped at k items (single category) or at k_j items in each of several categories. The authors claim tight or almost-tight parametric bounds: for a single category, 1/2(1+sqrt(1+(m-1)/k)) for utilitarian welfare and max((m-n+1)/k,1) for egalitarian welfare; for multiple categories, 2/(k1/m1+k2/m2) for two agents, m1/k1 for general n under utilitarian welfare, and an exact expression for egalitarian welfare. They also give polynomial-time matching algorithms (Propositions 1 and 2) that construct cardinal allocations meeting the claimed guarantees. The paper is clearly written and the lower-bound constructions are explicit, but the main utilitarian single-category upper bound rests on a proof step in Lemma 5 that appears to be invalid.

Significance. If the results are correct, the paper offers a valuable parametric refinement of the asymptotic price-of-balancedness bound of Bei et al., with closed-form bounds that depend exactly on m and k rather than on asymptotic orders. The egalitarian results (Theorems 2 and 5) appear exact and tight for all feasible parameters, and the polynomial-time algorithms are a useful practical contribution. However, Theorem 1, which is the headline single-category utilitarian result, is not established by the manuscript because the proof of Lemma 5 (Case 1) contains an unsupported equality step. The paper would be significant after that gap is repaired; in its current form, the central claim is only conditional on a missing argument.

major comments (1)
  1. [Lemma 5, Case 1 (Section 3.1)] The displayed chain in Case 1 of Lemma 5 is invalid. Lemma 4 supplies only a lower bound, USW(Ak) >= 1 + sum_{i in S} (k/|A*_i|)(u_i(A*_i) - u_i†(A*_i)). Replacing the denominator USW(Ak) in the first equality by D := 1 + sum_{i in S} (k/|A*_i|)(u_i(A*_i) - u_i†(A*_i)) is therefore not an equality; the correct relation is <=, and the resulting fraction N/USW(Ak) is bounded above by N/D, not equal to it. Moreover, the subsequent equality '= OPT-USW(I')/max_{A in Cκ(I')} USW(A)' is unsupported: the optimal cardinal welfare in I' is at least D (for instance, by giving each i in S its k items with highest u'_i value and assigning g† to an agent in R∪T), so OPT(I')/max(I') <= OPT(I')/D, which is the reverse of the equality needed. Applying Lemma 3 to I' therefore bounds OPT(I')/max(I'), not the larger quantity OPT(I')/D, and the desired upper bound in the case sum_{i in R∪T} u_i(A*) < 1 does not follow. Since this is the only route to the upper bound in that case, Theorem 1 is not established by the manuscript.
minor comments (5)
  1. [Section 3.2, Theorem 2 proof] The notation A* = (A*_1, . . . , A*_k) should be A* = (A*_1, . . . , A*_n); k is the cardinality constraint, not the number of agents.
  2. [Section 3.2, Theorem 2 lower bound] The statement 'max_{A in Cκ(I)} ESW(A) = k/(m-n+1)' should read 'min{k/(m-n+1), 1}' because utilities are normalized to total value 1; when k > m-n+1 the agent can receive all m-n+1 items and obtain utility 1. The construction still yields the claimed lower bound after this correction.
  3. [Section 4.2, Theorem 5 proof] The parenthetical '(this indeed implies j* = 1)' is false; for example, with h=2, m1=10, m2=100, and n=50, one has c1=0 and c2=39, so j* = 2. The subsequent construction is valid for any j*, so the proof is unaffected.
  4. [Section 4.2, Theorem 5 proof] The ratios k_j/|A*_{ij}| are undefined when |A*_{ij}| = 0; they should be interpreted as contributing zero to the sum.
  5. [References and typos] The reference key '[LL W22]' contains a spurious space; it should be '[LLW22]' or similar. In the proof of Lemma 3 in Appendix A.2, 'Observe that for there exists i in S' should be 'Observe that there exists i in S'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper derives its bounds from explicit lower-bound constructions and algebraic upper-bound arguments, with prior work cited only as context.

full rationale

No circular derivation chain was found. The price of cardinality is defined as a worst-case ratio (Definitions 2 and 3) and every bound is obtained either from an explicit instance construction (lower bounds in Lemmas 1 and 2 and in Theorems 2, 3, 4, and 5) or from optimization, AM-HM, and derivative arguments (upper bounds in Lemmas 3 and 5 and in Theorems 2 through 5). The target expressions never appear as hypotheses: Lemma 1 computes the lower-bound ratio from the constructed utilities; Lemma 3 bounds a rational expression in the variables u_i(A*_i) and |A*_i|; Lemma 5 attempts the remaining case by reducing to a modified instance I' and invoking Lemma 3. Self-citations in the Related Work section (e.g., [BLLS24], [SL23], [SL24]) and the reference to [BLMS21] are contextual and motivate the problem; no theorem or bound is imported from those works as a load-bearing premise for the derivation. The manuscript's own admission that Lemma 5 is a 'Partial Proof' and that the multi-category n >= 3 case remains open is a completeness or correctness limitation, not a circularity, because the proof does not presuppose the desired bound. Accordingly, the paper is self-contained against external benchmarks and merits a circularity score of 0.

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

Pure mathematics and TCS paper: no data fitted, no parameters chosen ad hoc. The model assumptions are standard and stated in Section 2. No new entities are postulated. The main burden is the correctness of the proof case analysis, not the axiom load.

assumptions (3)
  • domain assumption Utilities are additive and normalized: u_i(S)=sum_{g in S} u_i({g}), u_i(empty)=0, u_i(M)=1.
    Section 2. Standard in the fair-division price-of-fairness literature; restricts the scope but is not ad hoc.
  • domain assumption Feasibility of cardinality constraints: k_j >= m_j/n for each category j.
    Section 2. Ensures every item can be allocated; the price is undefined or empty otherwise.
  • domain assumption Single-category analysis assumes m > k (else the constraint is vacuous) and egalitarian analysis assumes m >= n (else OPT-ESW=0 and the price is 1 by convention).
    Sections 3 and 3.2, stated as degenerate-case exclusions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective." pith.science (2026). https://pith.science/paper/JVLZEPM7

@misc{pith2026250101660,
  author       = {Pith},
  title        = {Pith review of: The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JVLZEPM7}},
  note         = {Machine review of arXiv:2501.01660}
}
abstract

We adopt a parametric approach to analyze the worst-case degradation in social welfare when the allocation of indivisible goods is constrained to be fair. Specifically, we are concerned with cardinality-constrained allocations, which require that each agent has at most $k$ items in their allocated bundle. We propose the notion of the price of cardinality, which captures the worst-case multiplicative loss of utilitarian or egalitarian social welfare resulting from imposing the cardinality constraint. We then characterize tight or almost-tight bounds on the price of cardinality as exact functions of the instance parameters, demonstrating how the social welfare improves as $k$ is increased. In particular, one of our main results refines and generalizes the existing asymptotic bound on the price of balancedness, as studied by Bei et al. [BLMS21]. We also further extend our analysis to the problem where the items are partitioned into disjoint categories, and each category has its own cardinality constraint. Through a parametric study of the price of cardinality, we provide a framework which aids decision makers in choosing an ideal level of cardinality-based fairness, using their knowledge of the potential loss of utilitarian and egalitarian social welfare.

Figures

Figures reproduced from arXiv: 2501.01660 by the authors.

Figure 1
Figure 1. Plot of the utilitarian price of cardinality in the single-category setting as a function of [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Plot for m = 50 showing the gap between the lower bound as described in the main body and proof of Lemma 2 for any m and k, and the upper bound from Theorem 1. Lemma 2. In the single-category case, if m ̸= k(c 2−1)+1 for all c ∈ N + \{1}, then the utilitarian price of cardinality is at least 1 2  −1 + q 1 + m−1 k  . The missing proofs are deferred to the appendix. We now prove the upper bound of Theorem 1, which h… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

  1. [1]

    Voudouris, and Xiaowei Wu

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos - Ratsikas, Bo Li, Herv \' e Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artif. Intell. , 322:103965, 2023

    work page 2023

  2. [2]

    Fair division under cardinality constraints

    Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In IJCAI , pages 91--97. ijcai.org, 2018

    work page 2018

  3. [3]

    Optimal bounds on the price of fairness for indivisible goods

    Siddharth Barman, Umang Bhaskar, and Nisarg Shah. Optimal bounds on the price of fairness for indivisible goods. In WINE , volume 12495 of Lecture Notes in Computer Science , pages 356--369. Springer, 2020

    work page 2020

  4. [4]

    Fair division of a graph

    Sylvain Bouveret, Katar \' na Cechl \' a rov \' a , Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In IJCAI , pages 135--141. ijcai.org, 2017

    work page 2017

  5. [5]

    Welfare loss in connected resource allocation

    Xiaohui Bei, Alexander Lam, Xinhang Lu, and Warut Suksompong. Welfare loss in connected resource allocation. In IJCAI , pages 2660--2668. ijcai.org, 2024

    work page 2024

  6. [6]

    The price of fairness for indivisible goods

    Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong. The price of fairness for indivisible goods. Theory Comput. Syst. , 65(7):1069--1093, 2021

    work page 2021

  7. [7]

    The efficiency of fair division

    Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou. The efficiency of fair division. Theory Comput. Syst. , 50(4):589--610, 2012

    work page 2012

  8. [8]

    Mind the gap: Cake cutting with separation

    Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. Mind the gap: Cake cutting with separation. Artif. Intell. , 313:103783, 2022

    work page 2022

Show all 24 references
  1. [9]

    Puzzle-Math

    George Gamow and Marvin Stern. Puzzle-Math . Viking press, 1958

    1958

  2. [10]

    Guaranteeing half-maximin shares under cardinality constraints

    Halvard Hummel and Magnus Lie Hetland. Guaranteeing half-maximin shares under cardinality constraints. In AAMAS , pages 1633--1635. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) , 2022

    2022

  3. [11]

    Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations , The IBM Research Symposia Series, pages 85--103. Plenum Press, New York, 1972

    1972

  4. [12]

    H. W. Kuhn. The hungarian method for the assignment problem. Nav. Res. Logist. Q. , 2(1-2):83--97, 1955

    1955

  5. [13]

    A complete landscape for the price of envy-freeness

    Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao, and Yichen Tao. A complete landscape for the price of envy-freeness. In AAMAS , pages 1183--1191. International Foundation for Autonomous Agents and Multiagent Systems / ACM , 2024

    2024

  6. [14]

    Almost (weighted) proportional allocations for indivisible chores

    Bo Li, Yingkai Li, and Xiaowei Wu. Almost (weighted) proportional allocations for indivisible chores. In WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022 , pages 122--131. ACM , 2022

    2022

  7. [15]

    Equitability and welfare maximization for allocating indivisible items

    Ankang Sun, Bo Chen, and Xuan Vinh Doan. Equitability and welfare maximization for allocating indivisible items. Auton. Agents Multi Agent Syst. , 37(1):8, 2023

    2023

  8. [16]

    Fairness criteria for allocating indivisible chores: connections and efficiencies

    Ankang Sun, Bo Chen, and Xuan Vinh Doan. Fairness criteria for allocating indivisible chores: connections and efficiencies. Auton. Agents Multi Agent Syst. , 37(2):39, 2023

    2023

  9. [17]

    Fair and square: Cake-cutting in two dimensions

    Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, and Yonatan Aumann. Fair and square: Cake-cutting in two dimensions. J. Math. Econ. , 70:1--28, 2017

    2017

  10. [18]

    On the price of fairness in the connected discrete cake cutting problem

    Ankang Sun and Bo Li. On the price of fairness in the connected discrete cake cutting problem. In ECAI , volume 372, pages 2242--2249. IOS Press, 2023

    2023

  11. [19]

    Allocating contiguous blocks of indivisible chores fairly: Revisited

    Ankang Sun and Bo Li. Allocating contiguous blocks of indivisible chores fairly: Revisited. In AAMAS , pages 1800--1808. International Foundation for Autonomous Agents and Multiagent Systems / ACM , 2024

    2024

  12. [20]

    The problem of fair division

    Hugo Steinhaus. The problem of fair division. Econometrica , 16:101--104, 1948

    1948

  13. [21]

    Constraints in fair division

    Warut Suksompong. Constraints in fair division. SIGecom Exch. , 19(2):46--61, 2021

    2021

  14. [22]

    Hal R. Varian. Equity, envy and efficiency. J. Econ. Theory , 9:63--91, 1974

    1974

  15. [23]

    Fair division: The computer scientist's perspective

    Toby Walsh. Fair division: The computer scientist's perspective. In IJCAI , pages 4966--4972. ijcai.org, 2020

    2020

  16. [24]

    Budget-feasible maximum nash social welfare is almost envy-free

    Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum nash social welfare is almost envy-free. In IJCAI , pages 465--471. ijcai.org, 2021

    2021

Pith tools

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