| paper | d4-conf-sagt-2021-0027 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\); a qualifying assignment always exists. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5.4
Given rational type masses \(\mu_t\), additive values \(v_t(g)\), per-capita supplies \(q_g\) for finitely many item categories \(g\), and a target \(\alpha\in(0,1]\), can one compute in time polynomial in the number of categories, support size \(\tau\), and input bit length a finite-support assignment of masses \(x_{t,b,p}\) to integral bundles \(b\in\mathbb{Z}_{\ge 0}^{G}\) and transfers \(p\)? Require each type’s assigned mass to equal \(\mu_t\), each category’s per-capita supply to equal \(q_g\), transfers to balance, and every positive-mass class to be envy-free toward every other positive-mass class. The assignment must have utilitarian welfare at least \(\alpha W^*\) and per-capita total transfer at most \(\alpha M^*+2\), where \(W^*\) is optimal per-capita welfare and \(M^*\) is the largest bundle value in a designated welfare-optimal assignment.
A continuum of agents with finitely many complete additive valuation types and rational masses; each agent receives an integral bundle from recurring indivisible item categories, while mass can be divided among bundle-and-transfer classes. Per-capita supplies and balanced per-capita transfers preserve the paper’s allocation, envy, and welfare structure.
Theorem 5.4 does not establish an algorithm polynomial in the number of types and input bit length, and scaling supplies with population turns its total-transfer guarantee into a per-capita bound rather than the paper’s original negligible-total-transfer guarantee.
fatal: False
The mirror covers the additive utilitarian trade-off in Theorem 5.4; it leaves the paper’s Nash welfare results, general-valuation results, and lower bounds unaddressed.
The strongest honest case is one lead mirror of Theorem 5.4. This is a positive case about an algorithmic result, not a claim that continuization removes a hardness barrier: the paper gives no numbered hardness result for me to anchor on.
Consider a large institution distributing repeated copies of a fixed set of indivisible goods to a population with a small number of recurring preference profiles—for example, role cohorts in a large workforce. A type \(t\) is the complete additive value vector \(v_t(g)\) over good categories \(g\). The society has rational type masses \(\mu_t\), with \(\sum_t\mu_t=1\), and \(\tau\ll n\). Each category has a rational per-capita supply \(q_g\), so a finite market with \(n\) agents has \(nq_g\) copies. This supply scaling is part of the mirror. Goods remain indivisible for each person; only the mass of people assigned to each bundle is fractional.
Here is the continuous problem I would hand to a prover. An instance consists of the type masses, additive values, per-capita supplies, and a target \(\alpha\in(0,1]\), all rational. A bundle \(b\in\mathbb Z_{\ge 0}^{G}\) gives each individual an integral number of copies of each category, with value \(v_t(b)=\sum_g v_t(g)b_g\). The solution is a finite-support assignment of masses \(x_{t,b,p}\ge 0\) to type, bundle, and transfer classes. It must assign all type mass, use each category’s supply exactly, and balance payments:
\[
\sum_{b,p}x_{t,b,p}=\mu_t,\qquad
\sum_{t,b,p}x_{t,b,p}b_g=q_g,\qquad
\sum_{t,b,p}x_{t,b,p}p=0.
\]
It must also be envy-free at the individual level: for every two positive-mass classes \((t,b,p)\) and \((t',b',p')\), \(v_t(b)+p\ge v_t(b')+p'\). Let \(x^\star\) be a welfare-maximizing feasible assignment before imposing envy-freeness, and let \(M^\star\) be the largest bundle value in that designated benchmark. The question is to find an envy-free assignment with utilitarian welfare at least \(\alpha W^\star\) and per-capita total transfer \(\sum_{t,b,p}x_{t,b,p}|p|\le \alpha M^\star+2\). Since transfers balance, utilitarian welfare here equals the value of the allocated goods.
The anchor is Theorem 5.4, proved in this paper. It says that for additive valuations and any \(\alpha\in(0,1]\), a polynomial-time algorithm computes an envy-free allocation with transfers whose utilitarian welfare is at least \(\alpha\) times optimal and whose total absolute transfer is at most \(n(\alpha\max_i v_i(A_i^*)+2)\). The continuous question preserves that whole trade-off; dividing the finite-market transfer bound by \(n\) gives the per-capita bound above. This is the paper’s direct three-way objective—envy-freeness, high welfare, and bounded transfers—with integral bundles still going to each individual. It is my strongest anchor.
I expect this mirror to be Class A, though that is a research conjecture, not a consequence of Theorem 5.4. The mass variables make type-level allocation fractional while retaining integral bundles, suggesting configuration-LP and pricing methods. The questions are whether the stated guarantee holds for every rational mass instance, whether a finite-support solution can be found in time polynomial in the number of categories, \(\tau\), and input bit length, and how such solutions relate to large finite markets. Stronger transfer bounds and extensions to general valuations or Nash welfare are further questions.
The scope is limited to the additive utilitarian result in Theorem 5.4; I would not use the paper’s unnumbered NP-completeness remark about envy-free allocation without transfers as an anchor for this problem.
My weakest point is that Theorem 5.4 is already a positive algorithmic result, so this mirror does not test whether discrete hardness dissolves. Also, per-capita inventories of repeated goods move from one-off objects to a recurring-supply setting. The case rests on that being a plausible high-multiplicity regime: many people share complete valuation types, while indivisible bundles, envy comparisons, welfare, and transfers retain the paper’s core question.
The only anchor is Theorem 5.4, and it is a real computational result: for additive valuations, it gives a polynomial-time algorithm achieving a welfare target with bounded transfers. A plausible mirror uses recurring copies of a fixed set of goods, a finite set of complete valuation-vector types, and rational masses. Each person still receives an integral bundle; masses may be divided among bundle and payment classes, which must jointly satisfy supply, payment-balance, and envy-freeness constraints.
The strongest objection is that the proposed mirror changes the theorem’s transfer guarantee. The paper bounds total transfers by \(n(\alpha\max_i v_i(A_i^*)+2)\), and calls them negligible because the bound is independent of the number of goods \(m\). If supplies scale with the population to keep the continuum nondegenerate, then \(m\) and \(n\) both grow, and this bound can grow linearly with \(m\). Dividing by \(n\) yields a bounded *per-capita* transfer cost, which may be a sensible continuous objective, but it is not the paper’s negligible-total-transfer guarantee. Keeping the total supply fixed instead makes supply per capita vanish in the continuum.
There is also no immediate compressed-input algorithm in the theorem. Its algorithm takes an explicit finite market. Replicating a rational mass instance to a finite market can require a common denominator exponential in the masses’ bit length; the runtime polynomial in the expanded population does not imply runtime polynomial in \(\tau\) and the input bit length. A continuous algorithm would need to handle a potentially enormous collection of integral bundle configurations and express envy constraints across the bundle and payment classes compactly. Fractional masses alone do not provide that algorithm.
Those objections weaken the claim that Theorem 5.4 already supplies a continuous result. They do not defeat the repaired mirror. A per-capita budget is natural for a population distribution, and finding a compact algorithm for that market is a legitimate computational question. The cohort scenario is plausible, types can include complete valuation vectors, and the paper’s allocation objective does not depend on personal identities beyond those types. I cannot make an honest case that no worthwhile continuous mirror exists here; the negative case is strongest against calling the proposed formulation a direct continuization of the theorem’s original guarantee.
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.