| paper | Fair Division with Market Values |
| authors | Siddharth Barman, Soroush Ebadian, Mohamad Latifian, Nisarg Shah |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 1
statement extracted from the paper’s text layer
Given rational masses \(\mu\) over complete additive subjective valuation types on finitely many recurring good classes \(G\), a common additive market valuation \(v\), and per-capita copy supplies \(b_g\), find a finite-support distribution \(\lambda_{t,B}\) over integral bundles \(B\) satisfying type-mass and supply constraints, such that every occupied source-target pair satisfies subjective EF1 and market SD-EF1.
Market-SD-EF1 / Subjective-EF1 Allocation\(\infty\) with typed agents, per-capita repeated indivisible goods, bundle-frequency variables \(\lambda_{t,B}\), and a feasibility objective.
The mirror requires a repeated-goods, per-capita supply model absent from the paper, and the paper's polynomial algorithm in agents and goods gives no polynomial algorithm in the compressed type-and-mass representation.
fatal: False
The mirror covers Corollary 1's subjective-EF1 and market-SD-EF1 allocation result, with a narrower common-ranking special case; it leaves the impossibility, PO, MMS, EFX, monotone-valuation, and cake-cutting results aside.
I think this paper does admit a credible continuous mirror, with Theorem 3 as the strongest anchor. The right mirror is a high-multiplicity population model, not the cake-cutting section: cake cutting continuizes the goods, whereas ChoCo continuizes the agents.
Take a large compensation or allocation programme serving millions of households, where households fall into a small number of complete valuation types. A type records the entire additive subjective valuation vector over standardized indivisible goods. The market valuation is a common additive valuation over those goods. For example, there may be \(N\) households, only \(\tau=20\)–\(100\) valuation types, and \(K\) standardized indivisible lots per household. The \(N\mu_t\) households of type \(t\) are exact clones for the purposes of the allocation problem. This is a plausible high-multiplicity regime: the households may be different people, but the legal or administrative programme treats them through a finite menu of complete valuation profiles.
Formally, let \(G\) be a finite set of good classes, let \(\mu_t\in\mathbb Q_{\ge 0}\) be the mass of type \(t\), and let \(b_g\) be the number of copies of good class \(g\) per unit population. Assume \(\sum_t\mu_t=1\) and \(K=\sum_g b_g\) is the number of goods per agent. A bundle is an integral vector \(B\in\mathbb Z_{\ge0}^{G}\) with \(\sum_g B_g=K\).
The allocation variable is not a fractional bundle. It is a bundle-frequency distribution
\[
\lambda_{t,B}\ge 0,
\]
where \(\lambda_{t,B}\) is the mass of type-\(t\) agents receiving the whole indivisible bundle \(B\). It must satisfy
\[
\sum_B\lambda_{t,B}=\mu_t
\quad\text{and}\quad
\sum_{t,B}\lambda_{t,B}B_g=b_g
\]
for every type \(t\) and good class \(g\). The objective is feasibility: output any such allocation satisfying the relevant fairness guarantee.
Fairness must be imposed support-wise, not on average utilities. If \(\lambda_{t,B}>0\) and \(\lambda_{s,B'}>0\), then the type-\(t\) agent receiving \(B\) must compare fairly with the type-\(s\) agent receiving \(B'\), exactly as two named agents would in the paper. For SD-EF1, this means that for some good \(g\in B'\), \(B\) SD-dominates \(B'\setminus\{g\}\) under \(u_t\); for market SD-EF1, the analogous condition uses the common market valuation \(v\). Thus the continuum aggregates clone identities but does not replace integral bundles by fractional goods.
This has an exact rational-clone dictionary. Given rational \(\mu\), \(b\), and \(\lambda\), clear denominators and create \(N\) agents, \(N\mu_t\) agents of type \(t\), and \(Nb_g\) indivisible copies of each good class. Each mass \(\lambda_{t,B}\) becomes a group of \(N\lambda_{t,B}\) cloned agents receiving \(B\). Conversely, any finite allocation that is symmetric within types and good classes compresses to such a \(\lambda\). The continuous problem is therefore a compact high-multiplicity encoding, not an appeal to fractional allocation.
My lead anchor is Theorem 3, proved in this paper:
“When the subjective utilities of the agents induce the same ranking over the goods, an allocation that is SD-EF1 w.r.t. the subjective utilities and the market valuation always exists, and can be computed in polynomial time.”
The corresponding problem is Common-Ranking SD-EF1\(_\infty\). Its input is the rational type distribution \(\mu\), per-capita good supply \(b\), additive utilities \(u_t\), and common additive market valuation \(v\), with all subjective types inducing the same ranking over goods. Its output is a finite rational-support \(\lambda\) satisfying the supply equations and support-wise SD-EF1 under both the subjective utilities and \(v\).
I would expect this mirror to be Class A. Once all subjective types share a ranking, the cardinal values largely disappear from SD-EF1; what matters is the interaction between the common subjective order, the market order, and the integral bundle structure. The natural compressed formulation is a weighted rank-layer allocation or bipartite matching/edge-colouring problem. Type masses can then be attached to the resulting bundle patterns. The finite theorem already identifies the relevant structural simplification; the new question is whether its construction can be represented in time polynomial in \(\tau\), the number of good classes, the per-capita supply, and the encoding length, without expanding \(N\).
This is recognisably the authors’ problem. It retains their two valuation profiles, indivisible goods, SD-EF1 semantics, and constructive objective. The only substantive extension is replacing a long list of clone agents by their type masses. It also creates useful follow-up questions: whether ties in the market ranking admit the same compact construction; whether support size can be bounded polynomially; how rounding behaves when \(\mu\) is approximated; and whether the common-ranking restriction can be relaxed while preserving a compact algorithm.
A second worthwhile anchor is Corollary 1, also proved in this paper, although its algorithmic engine is the cited Biswas–Barman (2018) cardinality-constraints algorithm:
“An allocation that is EF1 w.r.t. the subjective utilities and SD-EF1 w.r.t. the market valuation always exists, and can be computed in polynomial time.”
Its mirror is Market-SD-EF1 / Subjective-EF1 Allocation\(_\infty\). The input is the same typed population and per-capita indivisible-goods supply, but the subjective types may have arbitrary additive rankings. The output is a bundle-frequency distribution \(\lambda\) such that every occupied type/bundle pair satisfies ordinary EF1 under the first type’s subjective valuation, while every pair satisfies SD-EF1 under the common market valuation.
This mirror is perhaps more important than the first because the type distribution genuinely matters: two agents with different subjective valuations can receive different bundle patterns, even though the market-side constraint is common. I would currently classify the unrestricted compressed version as a plausible Class C boundary. The finite corollary is polynomial in the explicitly listed number of agents and goods, but that does not imply polynomiality in \(\tau\), the number of good classes, and \(\log N\). The market-side SD-EF1 condition gives structured rank constraints, but subjective EF1 introduces a potentially large family of bundle comparisons. A compact algorithm would need a configuration or pricing theorem; alternatively, the bundle-support problem might itself encode continuum-specific hardness. Either outcome would be valuable.
The paper’s other results need not be stretched into this case. The cake section is continuity of the outcome space, not of the population. Theorem 8 could support a broader variant with monotone subadditive valuation types, but its value-query and bundle-support issues make it a weaker anchor for the present purpose. Existing work by Biswas and Barman is supporting prior art, not a novelty collision: it shows that the cardinality-constrained allocation machinery already exists. Likewise, prior high-multiplicity allocation work would strengthen the case that this regime is meaningful.
The weakest point is that the paper proves polynomial algorithms in \(n\) and \(m\), not in a compressed type-and-mass representation. The rational-clone dictionary establishes fidelity, but not efficient continuization. In the lead theorem, the common-ranking structure gives a credible route to Class A. For Corollary 1, the compressed support and separation problem remains genuinely open. That concession does not undermine the mirror itself: the paper supplies an unusually clean source problem whose finite semantics survive exactly, while the new computational question is precisely whether fairness under market values remains tractable after the population is represented by types rather than named agents.
The strongest objection is that the proposed “rational-clone dictionary” does not preserve the paper’s instance regime. With the paper’s original finite goods set \(M\), replicating agents while holding goods fixed leaves only \(O(|M|)\) agents with nonempty bundles. In the limit, almost all population mass receives the empty bundle, while the interesting recipients are zero-mass exceptions. EF1 and SD-EF1 then become a property of a vanishing finite set, not of a continuous society.
The proposed repair—scaling the goods with the population—changes the model. It introduces \(N b_g\) recurring copies of each good class. To keep finitely many complete valuation types, one must additionally assume that copies have a repeated, parametrically described valuation structure. The paper does not make that assumption. If copies retain arbitrary item-specific utilities, a “type” is a vector whose dimension grows with \(N\), so there is no fixed finite type space. Thus the claimed dictionary is exact only for a new repeated-goods allocation model, not for the paper’s fair division problem in general.
This defeats the proposed Theorem 3 mirror especially cleanly. Under its premise, all subjective utilities induce the same ranking. SD-EF1 depends only on that ranking, not on cardinal utility values; the paper’s Lemma 1 explicitly says that any utility profile consistent with the ranking gives the same guarantee. Consequently, all the proposed subjective types are indistinguishable for the actual predicate, and the variables \(\lambda_{t,B}\) can be aggregated to \(\lambda_B\). The population distribution \(\mu\) does no work. A version with different rankings is no longer Theorem 3; a version with different cardinal values remains equivalent to one type. The result therefore supplies no genuinely population-sensitive continuous question.
Corollary 1 is a stronger anchor because subjective EF1 does depend on heterogeneous types. But the proponent’s support-wise configuration formulation exposes its real status: it is a new high-multiplicity fair-division problem, not a direct continuization of the corollary. The paper’s polynomial algorithm is polynomial in the explicitly listed agents and goods. Nothing in it gives a polynomial algorithm in the number of valuation types, the number of repeated good classes, and \(\log N\). The market-side block partition itself depends on \(N\), and preserving indivisibility requires retaining a distribution over integral bundles, potentially an exponential configuration space. The rational expansion proves semantic fidelity of a proposed repeated-goods model; it does not establish a compact computational formulation.
That is a serious modelling-distance objection, but it is not a decisive objection to the research question. A repeated course-allocation, housing-lot, or benefits programme with finitely many household valuation types is plausible, and the \(\lambda\)-formulation can preserve individual integral bundles and exact EF1 comparisons. Existing cardinality-constrained fair-division work is supporting evidence, not a collision. A configuration/separation theorem for this compressed problem could be a worthwhile ChoCo result.
So the negative case successfully disposes of Theorem 3 as a meaningful population anchor and shows that the proponent overstates the directness of both mirrors. It does not honestly defeat the strengthened Corollary 1 formulation. The universal claim that no worthwhile continuous mirror exists is therefore too strong: the remaining mirror is best classified as a new, author-recognizable high-multiplicity configuration-allocation programme rather than rejected outright.
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.