| paper | d4-conf-sagt-2010-0009 |
| 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 for \(\tau=2\); an exact rational maximizing allocation can be computed. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given two types with rational masses \(\mu_i>0\), \(\sum_i\mu_i=1\), linear per-person utilities \(u_{ij}\), disagreement utilities \(c_i\), and one unit of each good per unit of population, find a feasible per-type allocation \(q_{ij}\) maximizing \(\sum_{i=1}^2\mu_i\log(\sum_j u_{ij}q_{ij}-c_i)\), subject to \(\sum_i\mu_i q_{ij}\le1\).
A two-type society with mass \(\mu_i\) of type \(i\), per-capita bundle \(q_{ij}\), and per-capita utility \(\sum_j u_{ij}q_{ij}\); maximize the mass-weighted Nash objective over allocations feasible under population-scaled supplies.
The mirror covers ADNB2 as solved by Theorem 10, for two types. It does not extend the result to more types, all of NB2, Theorems 8–9, or the circle game.
The strongest mirror is a two-cohort linear bargaining market. Imagine a provisioning cooperative with hundreds of thousands of members but only two standardized profiles of linear utilities and disagreement utilities. Type \(i\) is the complete profile \((u_{i1},\ldots,u_{ig},c_i)\); its rational mass \(\mu_i>0\) is its fraction of the population, with \(\mu_1+\mu_2=1\). Divisible resource supply scales with population, so there is one unit of each good per unit of population.
Let \(q_{ij}\) be the bundle received per person of type \(i\). Feasibility requires \(\sum_i\mu_iq_{ij}\le1\), and type \(i\)’s per-person utility is \(v_i=\sum_j u_{ij}q_{ij}\). Assuming both types can strictly exceed their disagreement utilities, ask for a feasible allocation maximizing
\[ \sum_{i=1}^2 \mu_i\log(v_i-c_i). \]
The solution is the per-type allocation and resulting utility vector. This is the population’s normalized log Nash product. In a finite society with \(n_i\) identical agents of each type, it corresponds to maximizing \(\prod_i(v_i-c_i)^{n_i}\). Because goods are divisible, averaging allocations within each type preserves feasibility and, by concavity of the log, weakly improves the product. So the type-level model captures that replicated society exactly.
My anchor is Theorem 10: “There is a combinatorial strongly polynomial algorithm for solving ADNB2.” The theorem is proved in this paper; its reduction to a flexible-budget market draws on Vazirani [Vaz09]. ADNB2 has two players, divisible goods with one unit of each good, linear utilities \(v_i=\sum_j u_{ij}x_{ij}\), disagreement utilities \(c_i\), and positive integer clouts \(w_i\). It asks for an allocation with \(\sum_i x_{ij}\le1\) maximizing \(\sum_i w_i\log(v_i-c_i)\). Theorem 10 gives a combinatorial strongly polynomial algorithm for solving it.
The connection is exact. Set \(z_{ij}=\mu_iq_{ij}\), so \(\sum_i z_{ij}\le1\) and \(v_i=\sum_j(u_{ij}/\mu_i)z_{ij}\). Choose a common denominator \(D\) for the masses and set \(w_i=D\mu_i\). Multiplying the continuous objective by \(D\) leaves its maximizer unchanged and yields the ADNB2 objective with utilities \(u_{ij}/\mu_i\). Clearing rational denominators by scaling each player’s utilities and disagreement value preserves the maximizer, since it adds a constant to the log objective. Thus this two-type problem is tractable, via the paper’s strongly polynomial algorithm. Its support size is \(\tau=2\); the other main input dimensions are the number of goods and the bit lengths of the rational data.
The authors have a strong reason to recognize this as their problem: ADNB2 is already a linear allocation problem, and the paper explicitly interprets clout as replication of a player. Here that replication is written as population mass, with allocations expressed per capita. The paper contains no comparable numbered hardness result for this problem, so an algorithmic anchor is the right one. The mirror covers ADNB2 and its two-cohort population interpretation; it does not extend the claim to all of NB2 or to bargaining with more than two types.
My weakest point is that the paper itself studies two bargaining players, not a large society directly. The cohort construction groups identical agents behind each player and reduces back to the paper’s weighted problem. That makes the mirror narrow, but the paper’s clout interpretation gives a concrete high-multiplicity regime rather than a new story imposed from outside. Natural next questions are whether the model remains tractable with \(\tau>2\) types, and whether that extension is hard for continuum-specific reasons. The paper’s two-player result does not settle those questions.
The strongest case against this anchor is that it is already the paper’s weighted problem in population notation. For rational cohort masses \(\mu_1,\mu_2\), choose a common denominator \(D\) and set \(w_i=D\mu_i\). With aggregate allocation \(z_{ij}=\mu_i q_{ij}\), feasibility becomes \(\sum_i z_{ij}\le1\), and type \(i\)’s per-capita utility is \(\sum_j (u_{ij}/\mu_i)z_{ij}\). The population objective is therefore ADNB2’s weighted log objective, multiplied by \(D\). Clearing the utility denominators by scaling a player’s utilities and disagreement value together changes the objective only by an additive constant. Theorem 10 covers the resulting instance.
This is more than an argument that the answer happens to be known. The paper itself says clout \(w_i\) represents \(w_i\) copies of player \(i\). The proposed masses are normalized copy counts, and the aggregate variables recover the cohort allocation. The mirror adds a useful population interpretation, but no distinct computational model or complexity question: the paper’s own theorem already ranges over the corresponding instances. That is the best case for calling this a model collision.
The objection is narrow. The two-cohort model is sensible, and the paper’s clout interpretation supports it; there is no good argument that mass loses relevant identity or makes the objective degenerate. A model with three or more types could pose a separate question, but it would leave the ADNB2 result that anchors this case. So this argument defeats the proposed mirror as new work on this paper; it does not establish the universal claim that no worthwhile continuous mirror exists.
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.