| paper | d4-conf-atal-2017-0064 |
| 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 solvable in $m,\tau,L$ by an exact reduction to maximum flow. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), \(q\) indivisible good categories with rational per-capita supplies \(b_g\), binary values \(v_{tg}\), and a rational threshold \(c\), decide whether there is a nonnegative allocation measure \(\lambda_{t,z}\) over integral bundles \(z \in \mathbb{Z}_{\ge 0}^{q}\) such that \(\sum_z \lambda_{t,z}=\mu_t\), \(\sum_{t,z}\lambda_{t,z}z_g\le b_g\) for each category \(g\), and every bundle assigned positive mass to type \(t\) satisfies \(\sum_g v_{tg}z_g \ge c\sum_g v_{tg}b_g\).
Types are binary valuation vectors \(v_t \in \{0,1\}^{q}\) carrying masses \(\mu_t\); each unit of mass receives an integral bundle \(z\), represented by \(\lambda_{t,z}\). The objective is threshold feasibility for \(c\), with per-capita supply constraints \(b_g\). A rational-capacity flow routes \(\mu_t\lceil c\sum_g v_{tg}b_g\rceil\) liked units to each type, and the flow can be decomposed into integral bundles.
The mirror covers Theorem 3's binary-utility proportional-share threshold question. It leaves the fixed-agent PTAS results, scoring-vector cases, and 2-additive max-min results outside its scope.
My lead is Binary-Type Proportional-Share Feasibility, a continuous-population mirror of Theorem 3, proved in this paper. Theorem 3 says that for additive binary utilities, given a target \(k\), deciding whether \(c_P\ge k\) is polynomial-time solvable, with no fixed-agent restriction. Its proof uses total unimodularity to show that the linear relaxation of the allocation program has an integral solution. I rely on this result alone: it gives a named computational anchor and fits a many-agent regime better than the paper’s fixed-agent PTAS results.
Consider a large population receiving copies of a small set of standardized, indivisible goods. A type \(t\) is the complete binary utility vector \(v_t\in\{0,1\}^q\) over the \(q\) good categories. Let \(\mu_t\) be the fraction of the population of type \(t\), and let \(b_g\) be the per-capita supply of category \(g\). The regime is one where the number of people \(N\) is much larger than the number of types \(\tau\) and good categories \(q\): for example, many recipients with a small number of eligibility or preference profiles and standardized benefit types.
An allocation assigns each unit of population an integral bundle \(z\in\mathbb Z_{\ge0}^q\). Write \(\lambda_{t,z}\) for the mass of type \(t\) receiving bundle \(z\). It must satisfy \(\sum_z\lambda_{t,z}=\mu_t\) for every type and \(\sum_{t,z}\lambda_{t,z}z_g\le b_g\) for every good category. Only the population is continuous: each person still receives whole goods. Type \(t\)’s proportional share is \(p_t=\sum_g v_{tg}b_g\). This is exactly the finite-model share \(u_i(O)/N\) when \(N\) agents have supplies \(N b_g\) and type \(t\) values category \(g\) at \(v_{tg}\).
The continuous decision problem is: given rational \((\mu,b,v)\) and a rational target \(c\), does there exist such an allocation with \(v_t\cdot z\ge c p_t\) for every bundle \(z\) assigned positive mass to type \(t\)? A solution is the allocation measure \(\lambda\), or a compact certificate from which that measure can be constructed.
This mirror appears tractable. Set \(d_t=\lceil c p_t\rceil\), since utilities are integer-valued. Build a flow network in which type \(t\) demands \(\mu_t d_t\) units, it can receive flow only from categories it values, and category \(g\) has capacity \(b_g\). A flow saturating all type demands gives each type an average of \(d_t\) liked goods per person. Since vectors of nonnegative integer bundle counts summing to \(d_t\) have a convex hull equal to the simplex of nonnegative vectors summing to \(d_t\), that flow can be decomposed into a distribution over integral bundles, each giving its recipient exactly \(d_t\) liked goods. Conversely, any fair allocation induces such a flow. Thus max flow decides the mirror in time polynomial in \(\tau\), \(q\), and the rational input bit length \(L\): this is a Class A result.
There is also a direct high-multiplicity bridge. For rational inputs, choose a common denominator \(D\), scale to \(D\) agents and \(D b_g\) copies of each good category, and use flow integrality to obtain a finite allocation. Conversely, normalizing a finite binary-utility instance gives \((\mu,b)\). So this mirror has an exact feasibility correspondence with a potentially enormous replicated instance, while its type-level representation avoids listing every person and copy.
The authors should recognize this as their proportional-share allocation problem: agents have their original binary additive utilities, indivisible goods, and the same per-agent fairness guarantee. The setting simply groups identical agents and scales standardized good supplies with the population. The mirror covers Theorem 3’s binary-utility threshold question; it does not purport to cover the paper’s max-min results, general additive PTAS, scoring-vector cases, or 2-additive utilities.
Natural follow-ups are whether the optimal \(c_P\) can be computed efficiently rather than just tested at a given threshold; whether the same type-level formulation remains tractable for general additive values; and what finite-instance guarantees follow when supplies or masses cannot be scaled to exact integers.
The weakest point is that this is a deliberately narrow mirror of an already tractable special case. A referee might see it as a compact high-multiplicity formulation of Theorem 3 rather than a new fairness problem, and it does not reach the paper’s broader settings. Still, it is a concrete computational question in which population mass is the central object, while individual allocations remain indivisible.
Theorem 3 is the proponent’s strongest anchor, and I don’t see a sound modelling objection to it. In a population with repeated binary-utility types and standardized good categories, the guarantee for type \(t\) really does reduce to giving each recipient at least \(d_t=\lceil c p_t\rceil\) liked goods. The proposed flow captures that requirement, and its fractional assignments can be distributed over integral bundles. Grouping goods by their valuation signatures handles item-specific binary valuations without losing relevant information.
That regime can have many recipients per type, while individual identities play no role. Per-capita supplies that scale with population are an allowed co-modification, and replacing pointwise guarantees with guarantees for almost every recipient is natural for an atomless population. Scaling rational masses and supplies to a finite instance is the expected high-multiplicity bridge, not a novelty collision. Nor does the existence of Theorem 3 itself defeat the mirror: its stated algorithm is for an explicit finite instance, whereas the mirror asks for complexity in the compressed type and supply representation.
The best skeptical point is about the likely size of the contribution. In this binary setting, grouping types and good categories exposes a flow formulation closely tied to Theorem 3’s total-unimodularity argument. It may make for a compact high-multiplicity corollary rather than a substantial new complexity result. Extending the question to general additive or max-min fairness could reach further into the paper, but then the simple flow argument no longer suffices.
That is a concern about research yield, not a fundamental objection to the mirror. The model is coherent, passes the high-multiplicity test, and gives a concrete computational question. I cannot honestly make the case that no worthwhile continuous mirror survives this anchor; the negative case is weak.
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.