| paper | d4-conf-wine-2010-0027 |
| 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 \(\mathrm{P}\), with bit running time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2.1
statement extracted from the paper’s text layer
Given \(m\) goods of unit supply and a finite support \(T\) of buyer types, with rational total population mass \(N>0\), type proportions \(\mu_t\ge 0\) summing to \(1\), and rational per-buyer budgets \(b_t\), utilities \(u_{tj}\), and transaction costs \(c_{tj}\), find prices \(p_j\ge\epsilon\) and per-member allocations \(x_{tj}\ge 0\) such that \(\sum_j(p_j+c_{tj})x_{tj}=b_t\) for every type \(t\); \(\sum_t N\mu_t x_{tj}\le 1\) for every good \(j\), with \(\sum_t N\mu_t x_{tj}\ge 1/(1+\epsilon)\) whenever \(p_j>\epsilon\); and \(x_{tj}>0\) only if \(u_{tj}\ge\alpha_t(p_j+c_{tj})/(1+\epsilon)\), where \(\alpha_t=\max_j u_{tj}/(p_j+c_{tj})\).
A society is a distribution \(\mu\) over complete buyer types, with type \(t\) carrying mass \(N\mu_t\). The decision variables are equilibrium prices and per-member type allocations; goods consumption is weighted by type mass. There is no separate optimization objective: the task is to find an \(\epsilon\)-approximate equilibrium. Aggregating each type into one buyer with budget \(N\mu_t b_t\) gives the paper's finite-buyer formulation.
The mirror covers approximate-equilibrium computation in Theorem 2.1. It leaves Theorem A.1's convex-program characterization and uniqueness claim, along with the discussion of distributed convergence and other utility classes, unassessed.
My lead mirror is Continuous-Type Fisher-\(\epsilon\)-Equilibrium with Transaction Costs. The usable anchor is Theorem 2.1, proved in this paper. It says that for a Fisher market with \(n\) buyers, \(m\) goods of unit supply, linear utilities, budgets \(B_i\), and arbitrary nonnegative transaction costs \(c_{ij}\), an algorithm computes \(\epsilon\)-approximate equilibrium prices and allocations in \(O\!\left(\frac{1}{\epsilon}(n+\log m)mn\log(B/\epsilon)\right)\) operations, where \(B=(1+\epsilon)\sum_i B_i\). The paper’s supplied text has no numbered hardness result to anchor; this algorithmic result is therefore the right anchor, though it does not create a hardness-dissolution story.
Here the population has total mass \(N\), divided among a finite support \(T\) of buyer types. A type \(t\) specifies the complete data the market uses: a per-buyer budget \(b_t\), utilities \(u_{tj}\), and transaction costs \(c_{tj}\). Its population mass is \(N\mu_t\), where \(\mu_t\ge 0\) and \(\sum_t\mu_t=1\). Goods still have supply one, as in the paper. One plausible regime is a large wholesale or capacity market with many small buyers on standardized contracts: buyers share valuation, budget, and delivery-cost profiles, perhaps determined by region and contract class. There might be millions of buyers but only dozens or hundreds of distinct types. This is an instance regime, not a claim that every market has few types.
Given rational \(N,\mu_t,b_t,u_{tj},c_{tj}\) and \(0<\epsilon<1\), the problem asks for prices \(p_j\ge\epsilon\) and per-buyer allocations \(x_{tj}\ge0\). Let \(\alpha_t=\max_j u_{tj}/(p_j+c_{tj})\). A solution must satisfy, for every type \(t\), \(\sum_j(p_j+c_{tj})x_{tj}=b_t\); for every good \(j\), \(\sum_tN\mu_tx_{tj}\le1\), with \(\sum_tN\mu_tx_{tj}\ge1/(1+\epsilon)\) whenever \(p_j>\epsilon\); and \(x_{tj}>0\) only if \(u_{tj}\ge\alpha_t(p_j+c_{tj})/(1+\epsilon)\). The allocation is per member of the type, so the population-weighted sum is the amount of the good actually consumed. The price lower bound matches the paper’s algorithm, which initializes prices at \(\epsilon\) and never lowers them.
This is the same market-equilibrium question with the population represented by masses. In a finite instance with \(N\mu_t\) identical buyers of type \(t\), they can be symmetrized: if each receives \(x_{tj}\), the group uses \(N\mu_tx_{tj}\) units and spends \(N\mu_tb_t\). Conversely, an aggregate allocation to the group can be divided uniformly among its members. Thus the type-mass version is a genuine continuous extension of the finite-buyer model, including fractional group sizes. The fact that the goods are already divisible is not my reason for calling it continuous; the population is the object being continuized.
The computational connection is direct. Replace each type group by one aggregate buyer with budget \(N\mu_tb_t\), utilities \(u_{tj}\), and costs \(c_{tj}\). Applying Theorem 2.1 to those \(\tau=|T|\) aggregate buyers gives the operation bound \(O\!\left(\frac{1}{\epsilon}(\tau+\log m)m\tau\log\!\frac{(1+\epsilon)N\sum_t\mu_tb_t}{\epsilon}\right)\). This is the theorem’s arithmetic-operation bound after aggregation; a bit-complexity claim would need separate accounting for rational arithmetic. The expected direction is tractable: for fixed \(\epsilon\), the bound is polynomial in \(m,\tau\) and the logarithm of the population scale, rather than in the number of individual buyers.
I expect the authors to recognize this as their problem: it computes their prices and allocations under the same utility, budget, supply, and transaction-cost conditions. The mirror covers Theorem 2.1’s approximate equilibrium computation, not the paper’s discussion of distributed convergence or its extensions to other utility classes.
The weak point is that identical buyers can already be aggregated in the finite model, so the algorithmic payoff may look like a straightforward high-multiplicity reduction rather than a new structural result. And since the anchor is already an algorithmic result, this mirror says little about where discrete hardness disappears. The useful follow-on questions are whether the bound can be made polynomial in the full binary input length, and how accurately a continuous type-mass market can be approximated by a finite market with rounded integer multiplicities.
The only anchor is Theorem 2.1, so the “no named computational result” objection does not apply. The strongest case against is that the proposed finite-support mirror introduces no distinct market problem. Write \(q_t=N\mu_t\) for the mass of type \(t\). Replace that type group by one synthetic buyer with budget \(q_t b_t\), the same utilities \(u_{tj}\), and the same transaction costs \(c_{tj}\). If \(x_{tj}\) is the per-person allocation, the synthetic buyer gets \(X_{tj}=q_t x_{tj}\). Its budget constraint, demand conditions, and contribution to each good’s market clearing are exactly those of the type group. Fractional \(q_t\) causes no difficulty: the paper already permits divisible bundles and arbitrary budgets. Thus every stated continuous instance is an instance of the paper’s finite-buyer model with \(n=\tau\), after a direct change of variables.
That makes the proposed computational question an exact reformulation of the paper’s own market model, rather than a new continuous optimization problem for the programme to chart. The paper’s theorem already takes the number of buyers as a parameter, and its input places no restriction preventing these synthetic buyers. This is the best argument against spending research effort on this particular mirror: the population masses add a representation, but no new market constraints or computational structure.
The argument has a limit under the programme’s rules. The paper itself models a finite list of buyers, not a society given as a distribution; the reduction is a known answer to a well-posed mirror, and a known answer alone does not invalidate the question. Nor does existing high-multiplicity work count against it. If supplies scale with population, the model is simply scaled throughout; if supplies stay fixed, population growth changes market scarcity, but still gives a meaningful sequence of markets. A genuinely continuous distribution over heterogeneous budgets, utilities, and costs could also be a sensible extension, though it would need a representation for that distribution and would move beyond the paper’s finite input model.
So I cannot honestly defeat this anchor across all plausible scenarios. The negative case is that the natural finite-support mirror appears to be fully subsumed by the paper’s own formulation, leaving little independent computational work. That weakens its research value, but it does not establish that no worthwhile 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.