| paper | d4-conf-ijcai-2020-0724 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time computable for every fixed \(T\) and \(\epsilon\in(0,1]\); the algorithm also works without a fixed bound on \(\tau\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
For fixed \(T\) and fixed \(\epsilon>0\), given rational type masses \(\mu_t>0\) summing to \(1\), integer additive values \(v_{tj}\), and rational per-capita supplies \(\rho_j\), can one compute in time polynomial in the binary input length a polynomially encoded list of feasible plans? A plan assigns mass \(x_{t,b}\geq 0\) of type \(t\) to integral bundles \(b\in\mathbb Z_{\geq 0}^{q}\), with \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_jx_{t,b}=\rho_j\). Writing \(u_t(b)=\sum_jv_{tj}b_j\), \(E(x)=\min_{t,b:x_{t,b}>0}u_t(b)\), and \(W(x)=\sum_{t,b}x_{t,b}u_t(b)\), the list must contain, for every finite-support feasible plan \(y\), a plan \(x\) with \(E(x)\geq(1-\epsilon)E(y)\) and \(W(x)\geq(1-\epsilon)W(y)\).
A continuum of households with \(T\) complete valuation types and mass \(\mu_t\) per type, supplied with \(\rho_j\) units of each good per capita. Each household receives an integral bundle; decision variables \(x_{t,b}\) specify the mass of each type receiving each bundle. The objectives are the minimum utility over positively represented bundles and average utilitarian welfare.
Theorem 3 covers the fixed-agent-type frontier, and Theorem 1 also has a fixed-item-type mirror; the paper's other fairness notions and min-max result in Theorem 2 are not covered.
The strongest mirror is Fixed-Type Continuous Fair-Efficiency Frontier, anchored in Theorem 3. Theorem 3 is proved in this paper: for every fixed constant \(\epsilon\in(0,1]\), it constructs in polynomial time an \(\epsilon\)-Pareto set for max-min fairness and utilitarian efficiency when the number of agent types is constant. The setting is additive valuations and indivisible goods; the guarantee is that for every feasible allocation, the set contains one whose egalitarian and utilitarian welfare are each at least a \(1-\epsilon\) fraction of that allocation’s welfare.
A plausible regime is a recurring large-scale allocation of standard goods—say, aid packages to many households. The households have identical valuations when they agree on their values for every resource category, so a type is a complete valuation vector, not a loose demographic label. There may be millions of households but a fixed number \(T\) of such profiles. Supplies scale with the cohort: there are \(\rho_j\) units of resource category \(j\) per unit of population. That scaling matters; holding a finite stock fixed while the population grows would describe a different regime.
Here is the continuous problem I would hand to a prover. An instance has positive rational type masses \(\mu_t\), summing to \(1\), nonnegative integer values \(v_{tj}\) for each type \(t\) and resource category \(j\), and rational per-capita supplies \(\rho_j\). A plan assigns mass \(x_{t,b}\geq 0\) of type \(t\) to each of finitely many bundles \(b\in\mathbb Z_{\geq0}^{q}\), with
\[
\sum_b x_{t,b}=\mu_t,\qquad
\sum_{t,b} b_jx_{t,b}=\rho_j.
\]
Each unit of mass receives an integral bundle; only the mass receiving each bundle can be fractional. Its utility is \(u_t(b)=\sum_jv_{tj}b_j\). Define \(E(x)\) as the minimum utility among bundles receiving positive mass, and \(W(x)=\sum_{t,b}x_{t,b}u_t(b)\), the per-capita utilitarian welfare. The question is whether, for fixed \(\epsilon\) and fixed \(T\), one can output a polynomial-size list of feasible plans such that every feasible plan \(y\) is matched by a listed plan \(x\) with \(E(x)\geq(1-\epsilon)E(y)\) and \(W(x)\geq(1-\epsilon)W(y)\). The plans should have rational masses so they can be encoded.
This preserves the paper’s problem: additive values, indivisible bundles, the same two welfare measures, and the same approximate Pareto-set goal. It changes the population representation and scales supply with it. For a finite instance with \(N\) agents and \(N\rho_j\) copies of each category, normalizing bundle counts by \(N\) gives such a plan; conversely, rational plan masses can be scaled to a finite cohort. The paper’s cited high-multiplicity fair-allocation work supports treating this regime as sensible; its finite-agent results are not already the continuous model.
I expect this fixed-type question to be Class A, though Theorem 3 does not prove that answer for the continuous input. Its few-type configuration structure is a good starting point, and continuous masses may help with allocation among types, while bundle integrality remains. A prover would need a polynomial algorithm in the binary encoding of the masses and supplies, rather than an algorithm whose runtime is polynomial only in an explicitly expanded population.
A second, worthwhile anchor is Theorem 1, also proved here. It says that for every fixed \(\epsilon\in(0,1]\), an \(\epsilon\)-Pareto set for the same fairness and efficiency criteria can be computed in polynomial time when the number of item types is constant. Its mirror is the same continuous allocation problem, now with fixed \(q\) and potentially many agent types \(\tau\). The regime could be a large program distributing a few standardized resource categories among households with diverse valuation profiles, where \(N\gg\tau\). I also expect this version to be Class A: a fixed number of resource dimensions is promising for approximating the fairness-efficiency frontier. But, again, the paper’s dynamic program takes explicit finite counts as input; a new argument is needed for binary-encoded per-capita supplies.
The supplied paper has no numbered hardness theorem to anchor a claim that hardness dissolves in the continuum. These are positive algorithmic anchors, not evidence that a particular NP-hardness result disappears. My weakest point is that both discrete algorithms are polynomial in an explicitly listed finite instance, while these proposed questions use compact rational masses and scaled inventories. The conversion between those input formats can be large, so the theorems do not automatically transfer. There is also a modeling choice about stock: if the authors regard a fixed finite set of goods as essential, they may reject the scaled-supply regime. I think the recurring-cohort allocation is a credible case they would recognize, but the compact-input complexity is the actual new question the mirror must answer.
The best case against is that these are not two independent continuous research opportunities. Both mirrors lead to the same mass assignment over integral bundles, with type-mass and resource-supply constraints. Theorem 1’s fixed-item-type case is especially close to a standard configuration LP: for a fixed fairness threshold, variables represent mass assigned to each integral bundle, and the constraints track type masses and the \(q\) supplies. With \(q\) fixed, pricing over bundles is fixed-dimensional integer optimization. That makes this anchor look like a likely generic extension, rather than a distinct complexity landscape.
Theorem 3 is harder to dismiss. Its continuous counterpart still has integral bundles, so fixing the number of agent types does not remove the combinatorics over many goods. The paper’s rounding argument would not transfer wholesale: continuous masses remove some agent-count integrality, while the bundle and resource structure remains. But that is a reason the mirror asks a new question, not a reason it is uninteresting. The resulting configuration problem could expose exactly where the continuous model helps and where it stops helping.
There are repairable issues in the proposed formulation. An \(\epsilon\)-Pareto set needs an encoding for its plans; a continuous plan may use many possible bundles, and its minimum utility is sensitive to any positive mass receiving a poor bundle. A stronger formulation would require sparse rational-support plans and define fairness by the essential minimum utility. Those choices make the computational question clearer, but they do not eliminate it. They also do not invalidate the scaled-supply cohort: each person can still receive an integral bundle while type mass is divided among bundles.
So I cannot honestly defeat both anchors. Theorem 1 may be a weak incremental case because it seems to fit a standard fixed-dimensional pricing approach. Theorem 3 remains a credible mirror: the theorem is computational, its agent types are already the relevant high-multiplicity structure, and the paper’s cited high-multiplicity allocation work supports that regime. The negative case is therefore weak precisely where the universal claim needs to be strong.
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.