| paper | d4-conf-aaai-2023-0472 |
| 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: \(\text{polynomial-time solvable}\) · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given a finite type set \(\mathcal T\) of size \(\tau\), rational masses \(\mu_t\geq 0\) summing to \(1\), per-buyer budgets \(b_t\), per-population-unit supplies \(q_j\), and efficiently evaluable \(C^2\), concave, degree-one homogeneous utilities \(u_t:\mathbb R^m_+\to\mathbb R_+\), compute an \(\epsilon\)-competitive equilibrium consisting of prices \(p\geq 0\) and per-buyer bundles \(x_t\). Require each type's budget-constrained utility regret, each supply violation in \(\sum_t\mu_t x_{tj}\leq q_j\), and each market-clearing residual \(p_j(q_j-\sum_t\mu_t x_{tj})\) to be at most \(\epsilon\); is this possible in time polynomial in \(m,\tau\), the input bit length, and \(1/\epsilon\)?
A continuum population represented by \(\tau\) buyer types with masses \(\mu_t\), per-buyer budgets \(b_t\), and common per-buyer bundles \(x_t\). With no influence terms, market demand is \(\sum_t\mu_t x_t\); equivalently, type \(t\) is an aggregate Fisher buyer with budget \(\mu_t b_t\) and bundle \(\mu_t x_t\).
The opponent's cohort aggregation shows that the surviving mirror can be collapsed to a finite \(\tau\)-buyer Fisher market, so it carries no influence-specific equilibrium structure; this limits its coverage, though the programme treats a high-multiplicity formulation as a valid population mirror.
fatal: False
It covers Theorem 9's approximate equilibrium computation in the high-multiplicity ordinary Fisher-market subcase; it leaves computation with genuine social influence and the paper's influence-specific pseudo-game and Stackelberg analysis outside.
The strongest mirror I see is Mass-Type Influence Fisher Equilibrium. Imagine a large marketplace with many buyers but relatively few complete buyer types: a type records a buyer’s budget, utility, and pattern of social influence. Its mass \(\mu_t\) is the fraction of buyers of that type. This fits settings such as a large platform where users fall into a small number of budget and preference classes and their choices are influenced by the average consumption of connected classes.
For a precise version, let \(\mathcal T\) be the finite set of types, with rational masses \(\mu_t\geq 0\) summing to one. Give each type a per-buyer budget \(b_t\), and each good a supply \(q_j\) per unit of population. Let \(W_{ts}\) describe type \(t\)’s exposure to type \(s\)’s average bundle. The decision for type \(t\) is its per-buyer bundle \(x_t\); its objective is to maximize \(U_t(x_t,(W_{ts}x_s)_{s\in\mathcal T})\), taking the other types’ bundles and prices as fixed. A solution is a price vector \(p\geq0\) and bundles \(x_t\) such that each type maximizes its utility subject to \(p\cdot x_t\leq b_t\), total use satisfies \(\sum_t\mu_t x_{tj}\leq q_j\), and Walras’ law holds. The utilities and \(W\) have finite rational descriptions; \(\tau=|\mathcal T|\) may be small while the represented population is large. Goods are already divisible in the paper; the population mass and per-capita supply are the continuous parts of this mirror.
My anchor is Theorem 9, proved in this paper. It says that, under Assumption 8—continuous utilities concave and homogeneous in each buyer’s own allocation, jointly concave and twice continuously differentiable in that buyer’s allocation and their neighbors’ allocations—methods converge in last iterates to competitive-equilibrium allocations at rate \(O(1/T)\), and approximate competitive-equilibrium allocations can be computed in polynomial time. This is the paper’s strongest named computational anchor for the mirror; the paper does not give a comparable named hardness result for this equilibrium problem.
I would hand a prover the following question: given the rational masses, budgets, supplies, influence data, and efficiently evaluable utilities in the stated smooth class, compute an \(\epsilon\)-competitive equilibrium of the mass-type market in time polynomial in \(m,\tau\), the input bit length, and \(1/\epsilon\). The output is the type bundles and prices, with each type’s budget-constrained utility regret, supply violation, and market-clearing residual at most \(\epsilon\). I expect Class A, through the paper’s monotone variational-inequality approach applied to the \(\tau\) representative types. The result concerns competitive equilibrium in a socially influenced market, rather than a new aggregate welfare objective.
The main weakness is substantial: the paper’s theorem is about finitely many buyers, and the type-level influence model is a mean-field version of its buyer-to-neighbor interactions. The authors could reasonably ask for a proof that compressing repeated buyers into types preserves the relevant equilibrium conditions and complexity bounds. More sharply, Assumption 8 may leave no genuine influence in the smooth case. For a \(C^2\), jointly concave utility homogeneous of degree one in its own bundle \(x\), the Hessian has a radial null direction in \(x\); joint concavity then forces the cross-derivative in the neighbor variables to vanish, while homogeneity implies the utility’s derivative with respect to those variables vanishes. If that argument holds on the paper’s domain, Theorem 9 covers only the high-multiplicity Fisher-market subcase, not genuine influence. That narrows the positive case, but leaves a well-posed continuous-population equilibrium question anchored in the theorem the paper actually proves.
The case against is strongest at Theorem 9, the one computational anchor the proponent gives. Its assumptions appear to remove the social influence the proposed mirror is meant to preserve. Fix a buyer’s own bundle \(x\) and neighbors’ bundles \(y\). If \(u(x,y)\) is \(C^2\), jointly concave, and homogeneous of degree one in \(x\), then Euler’s identity gives
\[
x^\top \nabla^2_{xx}u\,x=0
\quad\text{and}\quad
x^\top \nabla^2_{xy}u=\nabla_y u.
\]
The joint Hessian is negative semidefinite. Since its quadratic form is zero in direction \((x,0)\), that direction is in its null space, so \(\nabla^2_{yx}u\,x=0\). Together these identities imply \(\nabla_y u=0\) in the interior; continuity extends the conclusion to the boundary. Thus utility cannot actually depend on neighbors’ allocations under Assumption 8. Theorem 9’s polynomial-time result, and the later algorithmic results under the same assumptions, cover the no-influence Fisher-market case.
That makes the proposed type-mass market a poor mirror of the paper’s computational contribution. With influence removed, each type cohort can be represented as one Fisher-market buyer with aggregate budget \(\mu_t b_t\) and aggregate allocation \(\mu_t x_t\). Degree-one homogeneity makes this aggregation preserve budget-constrained choices, and market clearing becomes the usual aggregate supply constraint. The proposed question is then a support-compressed version of standard Fisher-market equilibrium computation; its social-influence matrix \(W\) does no work.
There is a better way to retain influence: use a typed block network or an influence kernel, so each type responds to other types’ average allocations. That can describe a sensible large-market regime, but it changes the interaction model into a mean-field one. The paper’s general existence result permits influence, yet the computational theorems do not cover that genuinely coupled case. Dropping joint concavity or homogeneity to restore influence may yield a worthwhile new question, but it no longer mirrors Theorem 9’s algorithmic guarantee.
This is not an airtight argument that no continuous mirror is worthwhile. Dense typed networks are plausible, and the high-multiplicity regime is defensible. The negative case is narrower: the paper’s strongest computational anchor loses influence under its own assumptions, while a mirror that keeps influence has no computational result here to anchor it.
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.