| paper | The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective |
| authors | Alexander Lam, Bo Li, Ankang Sun |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 3.7
statement extracted from the paper’s text layer
Given rational masses over finitely many additive valuation types, rational per-capita supplies of finitely many good kinds, and a cardinality cap k, compute a mass allocation of each type to integral bundles of size at most k, meeting all supplies and maximizing total utilitarian welfare.
A high-multiplicity configuration or transportation LP: type masses are capacities, good-kind supplies are aggregate resource constraints, decision variables assign type mass to integral bundles, and the objective is additive utilitarian welfare.
Scaling supplies and identifying repeated goods changes the finite named-good instance into a type-to-resource market, so the mirror does not preserve every finite-instance phenomenon or the exact price formula.
fatal: False
The mirror covers the single-category and multi-category utilitarian cardinal-allocation algorithms in Propositions 3.7 and 4.4; it leaves the exact finite price theorems and egalitarian results unresolved.
The strongest positive case is a high-multiplicity allocation market in which many agents share complete additive-valuation types, while the goods are repeated indivisible items. My lead anchor is Proposition 3.7, proved in this paper.
Take a finite set of good kinds \(G\), partitioned into categories \(C_1,\ldots,C_h\). There are \(q_g\) copies of good kind \(g\) per unit population; in a finite lift with \(N\) agents, this means \(Nq_g\) individually indivisible copies. Let \(T\) be a finite set of agent types. Type \(t\) has mass \(\mu_t\) and additive value \(v_t(g)\) for each good kind. The type includes the entire valuation vector and every other parameter relevant to allocation. In the intended regime, \(N\gg |T|\), and every active type has a substantial mass, say \(\mu_t\ge\rho>0\).
A continuum allocation is a measure \(x_{t,a}\), where \(a\in\mathbb Z_{\ge0}^{G}\) is an integer bundle and \(x_{t,a}\) is the mass of type-\(t\) agents receiving that bundle. For cardinality vector \(\kappa\),
\[ \sum_a x_{t,a}=\mu_t,\qquad \sum_{t,a}a_gx_{t,a}=q_g, \]
and only bundles satisfying
\[ \sum_{g\in C_j}a_g\le k_j \]
may receive positive mass. The utilitarian objective is
\[ U(x)=\sum_{t,a}x_{t,a}\sum_g a_gv_t(g). \]
This is not divisible-goods allocation. Every bundle \(a\) is integral; \(x\) records the proportions of agents receiving different integral bundles. If \(\mu\), \(q\), and \(x\) are rational, multiplying by a common denominator gives an exact finite allocation with indivisible goods. Thus this is a genuine high-multiplicity mirror.
The lead problem is HM-Cardinal Utilitarian Allocation:
Given \((T,\mu,G,q,v,\kappa)\), find a feasible continuum allocation maximizing \(U(x)\), and return the allocation as either bundle masses \(x\) or an equivalent incidence certificate.
For one category, this collapses to the transportation LP
\[ \max \sum_{t,g}v_t(g)y_{t,g} \]
subject to
\[ \sum_g y_{t,g}\le k\mu_t,\qquad \sum_t y_{t,g}=q_g,\qquad y_{t,g}\ge0. \]
The variable \(y_{t,g}\) is the mass of type-\(t\) agents receiving copies of \(g\). It is precisely the continuous analogue of the \(k\)-copies-per-agent bipartite matching used in Proposition 3.7. The proposition states, and proves here, that the finite cardinal allocation is computable in polynomial time; the continuous problem is even more naturally a flow problem. I would expect Class A: polynomial-time solvability in \(|T|+|G|\) and the encoding length of the rational data.
The multi-category version is a second, closely related anchor: Proposition 4.4, also proved here. Its continuous problem is the same allocation problem with separate capacity constraints
\[ \sum_{g\in C_j}y_{t,g}\le k_j\mu_t \]
for every type and category. Each category gives an independent transportation problem, and the resulting category-wise allocations can be coupled across the same type mass. This is a very plausible Class A mirror of the paper’s separate-matching algorithm. It covers the paper’s practically important extension in which different kinds of resources have different per-agent limits.
The natural high-multiplicity scenario is a large university or grant system. There may be hundreds of thousands of professors, laboratories, or departments, but only a few dozen supervisory or preference profiles. The goods are a large cohort of individually distinct but standardized students, projects, grant packages, or equipment units. A cardinality cap models workload or fairness: each professor may supervise at most \(k_j\) students from category \(j\). This is not an artificial story invented to make the LP easy; it is close to the paper’s own PhD-supervision motivation, with the repeated-cohort assumption making high multiplicity explicit.
A third possible anchor is Theorem 3.1, proved here, which gives the exact finite utilitarian price
\[ \frac12\left(1+\sqrt{1+\frac{m-1}{k}}\right). \]
Its continuous counterpart should be called Continuum Utilitarian Price of Cardinality. For fixed good supply densities \(q\), cap \(k\), type bound \(\tau\), and minimum active mass \(\rho\), ask for
\[ P_\infty^U(q,k,\tau,\rho) = \sup \frac{U^0(\mu,q,v)} {U^k(\mu,q,v)}, \]
where the supremum ranges over finite type systems with at most \(\tau\) active types, \(\mu_t\ge\rho\), and normalized additive valuations. Here
\[ U^0(\mu,q,v) = \sum_g q_g\max_{t:\mu_t>0}v_t(g) \]
is the unconstrained welfare, while \(U^k\) is the optimum of the cardinal transportation problem above. A solution consists of the exact worst-case value together with an extremal type distribution and valuation profile, or a proof that the supremum is approached but not attained.
I would expect this to be Class A for a fixed good catalogue and bounded type support. Theorem 3.1’s proof already shows that the worst case has strong structure, reducing arbitrary valuation profiles to a small extremal pattern. The continuous question is new—the displayed formula should not be copied unchanged, because \(m\) is a total item count whereas \(q\) is an item density—but it is unmistakably the same question about the welfare loss caused by cardinality. Natural follow-ups are whether the price depends only on total supply and \(k\), whether it admits an FPT algorithm in \(\tau\), and how precisely finite-\(N\) allocations converge to the continuum value.
This mirror covers the paper’s single- and multi-category utilitarian allocation results and its price-of-cardinality question. I would not use the paper’s egalitarian discussion as a primary anchor: the relevant continuous objective would be an essential infimum over the support of \(x\), and its exact computational status is a separate, more delicate question. Also, the paper has no numbered hardness theorem of its own; the NP-hardness of egalitarian optimization is mentioned as a cited fact from Karp (1972).
The weakest point is that goods must scale in a meaningful way with the population, or at least come in repeated standardized cohorts. If one holds a fixed finite set of goods while sending the population to a continuum, almost all mass receives nothing and per-capita welfare becomes degenerate. Conversely, if every agent has an idiosyncratic valuation, the number of types grows with the population and the high-multiplicity gain disappears. That is a real limitation. But it is a limitation of the regime, not of the mirror: large repeated cohorts of agents and indivisible resource copies are a sensible high-multiplicity instance class, and within that class the paper’s cardinal-allocation problem becomes a precise continuous computational object.
The strongest case against is that the paper’s results are driven by indivisible *goods*, not by population multiplicity. If the goods remain a fixed finite set while the number of agents tends to infinity, only finitely many agents receive anything; the cardinality constraint becomes nonbinding, and per-capita welfare collapses. There is then no nondegenerate continuous population problem.
The proposed rescue scales the goods as well: \(Nq_g\) copies of each good kind for \(N\) agents. That is a plausible model, but it is no longer merely the paper’s population continuization. It replaces named goods by interchangeable cohorts and turns the problem into a type-to-resource transportation market.
This undercuts Proposition 3.7 as a faithful mirror. With repeated goods, the matching construction becomes the standard transportation LP on type capacities \(k\mu_t\). It is mathematically valid, but it has discarded the finite-good structure that made the original allocation problem an allocation of a particular set of indivisible objects. The same objection applies more strongly to Proposition 4.4: because utilities and constraints are separable by category, the proposed continuum problem is just a product of independent transportation problems. It is a sensible new market model, but its connection to the paper is motivational rather than genuinely continuizing the paper’s allocation instance.
Theorem 3.1 is the best target. Its extremal construction relies on \(s=\Theta(\sqrt{m/k})\) individually distinguished agents, each with a disjoint block of valued goods, together with one exceptional good. Under a genuine finite-type continuum, those exceptional agents either have zero mass—in which case their welfare contribution disappears—or become positive-mass types. In the latter case their capacity and valued good blocks must both scale with \(N\), eliminating the finite construction’s \(\sqrt m\) mechanism. Preserving it requires the number of types to grow with the population or the type masses to vanish, which gives up the high-multiplicity regime.
A repaired quantity such as the proponent’s \(P_\infty^U(q,k,\tau,\rho)\) can certainly be studied, but it is a new supply-density extremal problem, not a canonical continuous version of the paper’s price theorem. The paper’s parameter \(m\) has no unique continuum counterpart: fixed supply causes degeneration, while per-capita supply changes the welfare-loss phenomenon itself.
That is the strongest negative case. It is not airtight, because the repeated-cohort university scenario is genuinely plausible, and Propositions 3.7 and 4.4 do yield legitimate Class-A high-multiplicity flow problems. So the honest conclusion is that the negative case defeats the price-of-cardinality mirror as a faithful continuation, but cannot convincingly establish that no worthwhile continuous mirror exists at all.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.