| paper | Mixed Fair Division: A Survey |
| authors | — |
| venue | AAAI 2024 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.3
Given valuation types \(T\) with rational masses \(\mu\), item kinds \(O\) with rational per-capita supplies \(q\), and rational additive values \(v_t(o)\), output a finite-support distribution \(x\) over integer bundles \(k\) such that type masses and item supplies are respected, every supported type-bundle pair satisfies PROP1 relative to \(P_t = \sum_o q_o v_t(o)\), and \(x\) is Pareto optimal under type-wise couplings of old and new bundles. Determine whether this can be done in time polynomial in \(|T|\), \(|O|\), and the input bit-length.
A high-multiplicity configuration model: \(x_{t,k}\) is the mass of valuation type \(t\) receiving discrete integer bundle \(k\); linear mass and supply constraints enforce feasibility, while the search objective is PROP1 plus population Pareto optimality.
Theorem 3.3's strongly polynomial algorithm for explicitly listed agents and items gives no established polynomial algorithm for the rational bundle-frequency configuration problem with scaled supplies.
fatal: False
The mirror covers Theorem 3.3's PROP1-and-PO allocation result, leaving the survey's other EF1, EFM, MMS, subsidy, cake-protocol, and welfare results untreated.
The strongest honest positive case is a narrow one centred on Theorem 3.3. The survey reports, but does not prove, the result of Aziz, Moulin, and Sandomirskiy (2020):
“For additive utilities, there exists a strongly polynomial-time algorithm that computes a PROP1 and PO allocation.”
I would mirror this theorem, rather than trying to continuize the survey wholesale.
The natural regime is a large-scale allocation service: for example, a city assigning many standardized course seats, benefit slots, and mandatory service duties to households. There are \(N\) agents but only \(\tau\) complete valuation types. A type records the agent’s additive value for every item kind, including whether that item is a good or a chore. Item kinds themselves have repeated copies: if item kind \(o\) has per-capita supply \(q_o\), the finite \(N\)-agent realization has approximately \(Nq_o\) distinct indivisible copies. This is a genuine high-multiplicity regime: the copies remain indivisible for each recipient, but both agents and standardized item copies occur in large numbers.
My lead problem would be HM-PROP1–PO Allocation\(_\infty\).
An instance consists of:
An individual bundle is still discrete, represented by \(k\in\mathbb Z_{\geq0}^m\), where \(k_o\) is the number of copies of item kind \(o\) in the bundle. The decision variable is a bundle-frequency distribution \(x_{t,k}\): the mass of type-\(t\) agents receiving bundle \(k\). It must satisfy
\[ \sum_k x_{t,k}=\mu_t \quad\text{and}\quad \sum_{t,k} k_o x_{t,k}=q_o \]
for every type \(t\) and item kind \(o\). Thus the model does not give a fractional item to an individual; it records the frequencies of discrete bundles across an anonymous population.
The utility of type \(t\) for bundle \(k\) is
\[ u_t(k)=\sum_o k_o v_t(o). \]
The proportional benchmark is
\[ P_t=\sum_o q_o v_t(o), \]
because a finite realization with \(N\) agents has total type-\(t\) resource value \(NP_t\), so its proportional share is \(P_t\).
The output must satisfy PROP1 pointwise on the support of \(x\). For every \(t,k\) with \(x_{t,k}>0\), either \(u_t(k)\geq P_t\), or one can add one available good copy and reach \(P_t\), or one can remove one chore copy from \(k\) and reach \(P_t\). It must also be Pareto optimal in the population sense: there must be no alternative feasible bundle-frequency distribution \(x'\) and type-preserving coupling of old and new bundle assignments such that every positive-mass agent weakly improves and a positive mass strictly improves.
The computational question is simply: output a finite-support rational \(x\) satisfying these conditions, with running time polynomial in the explicitly represented type and item data and the bit-length of \(\mu\) and \(q\).
This is recognisably the same problem as Theorem 3.3. The fairness criterion is unchanged, the resources remain indivisible, and Pareto optimality is still an agent-level condition. Only the population representation changes: named agents are replaced by masses of agents with identical complete valuation types. If all denominators are cleared, \(x\) expands directly to a finite allocation with \(N\mu_t\) agents of type \(t\) and \(Nq_o\) item copies. Conversely, an allocation of that repeated finite instance induces such an \(x\). This gives the desired high-multiplicity dictionary rather than merely an analogy.
I would provisionally expect this problem to be Class A, though the classification is genuinely open. The reason for optimism is that the source theorem is already strongly polynomial, and its inputs have additive valuations. The continuous formulation suggests a configuration or transportation LP: the population repetition is handled by masses, while additive bundle values and item supplies give a finite linear core. The PROP1 condition only refers to local one-item extensions or deletions. A column-generation algorithm would need to produce useful bundle configurations without expanding all repeated agents. This is precisely the sort of high-multiplicity compression the ChoCo programme is designed to investigate.
The main questions are whether a polynomial-size bundle-frequency support always suffices, whether the strongly polynomial guarantee survives rational masses and per-capita supplies, and what rounding loss occurs when \(N\) is not a common denominator. A further question is whether restricting the number of item kinds makes the problem fixed-parameter tractable, or whether the configuration structure introduces continuum-specific hardness.
The weakest point is serious: PROP1 is defined using “one item.” If the paper’s original finite item set is held fixed while the number of agents tends to infinity, one item becomes negligible and the guarantee degenerates. If instead one replaces bundles by fractional item flows, the result is no longer Theorem 3.3’s ex-post indivisible allocation problem. My mirror avoids both failures only by placing the problem in a repeated-supply regime and retaining a distribution over genuinely discrete bundles. That means the compressed object is more complicated than a simple mass vector, and proving polynomial support or polynomial-time construction is not automatic.
So I would not claim that every fair-division result in the survey continuizes. I would claim something narrower: Theorem 3.3 has a credible population mirror in a large market of repeated indivisible goods and chores, and that mirror poses a concrete new high-multiplicity algorithmic problem.
The negative case is weak here, and the reason is that the proponent has chosen the one result that genuinely survives continuization.
The best objection is that their formulation is not merely the high-multiplicity version of Theorem 3.3. If the paper’s \(m\) indivisible items remain fixed while the number of agents grows, each agent’s proportional benchmark tends to zero and PROP1 becomes largely vacuous. To prevent that, the proponent also scales the supply of every item kind with the population. The resulting problem is a new large-market configuration-allocation problem, with distributions over integer bundles, rather than a straightforward continuous version of the theorem.
The source theorem’s strongly polynomial algorithm does not support the claimed optimism either. Its running time is polynomial in explicitly listed agents and items; it gives no reason that the problem remains polynomial when exponentially many identical agents and item copies are encoded by rational masses and per-capita supplies. The bundle-frequency formulation may require solving a genuinely difficult configuration problem, and “continuous” does not automatically produce an LP with manageable pricing.
But these points attack the proponent’s suggested Class-A outcome, not the worth of the mirror. The revised model is still a legitimate population continuization: agents with identical valuation vectors are genuine types, integer bundles remain ex post indivisible, and a rational bundle-frequency solution expands exactly to a finite repeated instance. Pareto optimality also survives aggregation through a type-preserving coupling; it does not require named identities once agents of a type are indistinguishable. Standardized course seats, benefit slots, or recurring duties provide plausible high-multiplicity settings.
Nor can the usual objections do the work. The paper contains named computational results, notably Theorem 3.3. The objective does not fundamentally track individual identities. The continuum does not disappear if item supplies scale per capita. And the presence of cake-cutting or divisible-resource literature is not a collision, since that continuizes resources rather than the agent population.
Thus I cannot honestly defeat this anchor universally. The proponent has identified a credible new high-multiplicity computational problem, even if the claim that the existing strongly polynomial theorem points toward tractability is unjustified. The strongest negative conclusion is that this is a speculative and substantially re-modelled mirror—not that it is worthless.
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.