d4-conf-sagt-2010-0002

The strongest positive case is narrow: a continuous high-multiplicity version of the paper’s two-buyer equilibrium characterization. The paper gives no named P, NP-hardness, or parameterized-complexity result. Its useful computational anchor is Lemma 15, proved here: for a two-buyer market, after ordering goods so that \(u_{1j}/u_{2j}\ge u_{1,j+1}/u_{2,j+1}\), the Nash equilibrium strategy profiles are exactly
\[ \mathcal S_{NE}=\{(\alpha,\alpha):\alpha\in\mathcal B\},\qquad \mathcal B=\bigcup_{k=1}^{n}\mathcal B_k\ \cup\ \bigcup_{k=1}^{n-1}\mathcal B'_k. \]
Here, writing \(M_1,M_2\) for the buyers’ budgets,
\[ \begin{aligned} \mathcal B_k=\{\alpha\ge0:\;& \sum_{i<k}\alpha_i<M_1,\quad \sum_{i>k}\alpha_i<M_2,\quad \sum_{i=1}^n\alpha_i=M_1+M_2,\\ &u_{1j}\alpha_i-u_{1i}\alpha_j\le0,\quad u_{2i}\alpha_j-u_{2j}\alpha_i\le0 \quad\text{for all }i\le k,\ j\ge k\}, \end{aligned} \]
and
\[ \begin{aligned} \mathcal B'_k=\{\alpha\ge0:\;& \sum_{i\le k}\alpha_i=M_1,\quad \sum_{i>k}\alpha_i=M_2,\\ &u_{1j}\alpha_i-u_{1i}\alpha_j\le0,\quad u_{2i}\alpha_j-u_{2j}\alpha_i\le0 \quad\text{for all }i\le k,\ j\ge k+1\}. \end{aligned} \]
The \(\alpha_i\) can be read as equilibrium prices. Thus the lemma describes *all* two-buyer equilibria as a union of \(2n-1\) explicitly specified sets, rather than merely giving necessary conditions.

Here is the continuous problem I think that result can honestly anchor. Take \(n\) divisible goods, two buyer types \(r\in\{1,2\}\), and rational masses \(\lambda_r>0\) summing to one. Members of type \(r\) share a complete template \((u_r,b_r)\): the same linear utility vector and per-person budget. A type-level purchasing authority submits one common nonzero utility report for its whole cohort. The cohort’s aggregate budget is \(M_r=\lambda_r b_r\); its aggregate allocation is \(x_{rj}\), with \(\sum_r x_{rj}=1\) for each good. Its total true utility is \(\sum_j u_{rj}x_{rj}\), equivalently its members’ common per-person utility multiplied by \(\lambda_r\). Market prices and allocations follow the paper’s Fisher-market rules, including its equilibrium-allocation payoff selection. Two-Cohort Fisher-Game Equilibrium Enumeration asks: given the goods, rational type masses, budgets, and utilities, describe *all* pure Nash equilibrium report pairs, with their prices and induced allocations. A solution is an exact description of the equilibrium set, not just one equilibrium. Normalize total budget to one and the paper’s \(\mathcal B_k,\mathcal B'_k\) description applies with the cohort aggregate budgets \(M_r\).

The regime is many buyers in only two templates: for example, large purchasing cooperatives whose members have the same preferences and budgets and whose common authority submits the report. If the population has \(N\) members, \(N\) can grow while the support stays at \(\tau=2\). Aggregating identical members gives exactly the two-buyer Fisher market with budgets \(M_1,M_2\); the utility reports, price manipulation, market clearing, and Nash deviations remain central to the question. The authors could plausibly recognize this as their two-buyer game at cohort scale.

I expect this mirror to be tractable: Lemma 15 supplies a polynomial-size exact description—\(2n-1\) sets with \(O(n^2)\) linear constraints apiece. That supports a polynomial-time construction in \(n\) and the rational input bit length, although the paper does not state a complexity bound. This case covers Lemma 15’s two-buyer characterization only; it does not extend the result to arbitrary numbers of strategic buyers. Natural next questions are whether the polyhedral description extends to \(\tau\ge3\) strategic cohorts, and what happens when cohorts may only partially coordinate.

The weak point is also the central modeling choice: a type acts as a coordinated bloc. That is plausible for a purchasing consortium, but it does not follow from high multiplicity alone. Under ordinary individual Nash behavior in an atomless population, one person has zero influence on market prices; the price-manipulation mechanism in this paper can disappear. So I regard the cohort model as a credible, limited continuous mirror of the two-buyer result, not as the standard nonatomic Nash version of the paper’s game.