d4-conf-aaai-2014-0011

Theorem 8 analyzes equilibrium welfare but does not assert an algorithm for computing that welfare ratio or a hardness result. The proposed atomless optimization is statable, but its equilibrium is price-taking, unlike the paper's finite game where each buyer can affect prices; that change breaks the proposed connection to the anchored result.

The objection that survived

In the atomless model, unilateral reports leave prices unchanged, whereas finite buyers in the paper influence prices; the proposed equilibrium and PoA therefore concern a different strategic game.

What the mirror covers

The proposed question concerns only the Cobb–Douglas welfare ratio in Theorem 8; it leaves the equilibrium-existence results and the linear and Leontief PoA results aside.

Open questions for a prover

The case FOR (proponent)

The strongest anchor is Theorem 8. It proves that, in the normalized Fisher market game with Cobb–Douglas utilities, the Price of Anarchy is \(\Theta(1/\sqrt n)\), where \(n\) is the number of buyers. Here PoA is the welfare of the worst pure Nash equilibrium divided by the maximum welfare over strategy profiles. The theorem is proved in this paper: its lower-bound argument adapts a technique of Zhang (2005), while its upper-bound construction is supplied here. This is a named efficiency result, though the paper gives no algorithmic runtime or hardness classification. I would choose it over the existence theorems because it gives a tight bound and an explicit low-welfare construction.

A plausible regime is a platform allocating ad slots to many small advertisers with equal credits. Advertisers may share one of a modest number of preference templates over the slots. In the paper’s bad-instance construction, \(n=m^2+m\) buyers occupy only \(m+1\) types: one specialist type per good and one generalist type. Thus the number of buyers can be much larger than the number of distinct types.

Here is a specific extension, Atomless Cobb–Douglas Fisher PoA. An instance has \(m\) goods of unit supply and a finite distribution \(\mu\) over types \(t\). Type \(t\) has mass \(\mu_t\), with \(\sum_t\mu_t=1\), and a unit-sum true valuation vector \(a_t\in\Delta_m\). Each unit of population has budget \(1\), so total budget is also \(1\). A type is the complete preference description used by this game; mass is the fraction of advertisers with that description.

An infinitesimal advertiser reports a normalized Cobb–Douglas vector \(q\in\Delta_m\). For a report profile, market prices are the aggregate reported expenditure shares,
\[ p_j=\int q_j\,d\mu, \]
and an advertiser reporting \(q\) receives \(x_j=q_j/p_j\), with zero-demand goods treated by the paper’s removal convention. Its true utility is \(u_t(x)=\prod_j x_j^{a_{tj}}\). Define \(W_{\rm eq}\) as the worst equilibrium welfare and \(W_{\rm opt}\) as the maximum welfare over report profiles. The problem is: given binary-rational \(\mu\) and \(a_t\), approximate \(R(\mu)=W_{\rm eq}/W_{\rm opt}\) within additive \(\epsilon\), with running time measured in \(m,\tau,L,1/\epsilon\).

This has a concrete connection to Theorem 8. With an atomless population, an individual deviation leaves prices fixed, so a type-\(t\) advertiser’s best report is \(q=a_t\). Hence the equilibrium welfare is explicit. For the optimum, it suffices to consider one report \(q_t\) per type: prices depend only on the average report within a type, and Cobb–Douglas utility is concave in the resulting bundle. The remaining optimization is
\[ p_j(q)=\sum_t\mu_tq_{tj},\qquad W(q)=\sum_t\mu_t\prod_j\left(\frac{q_{tj}}{p_j(q)}\right)^{a_{tj}}. \]
The denominator in the PoA is therefore a concrete, finite-dimensional optimization over type reports and endogenous prices.

The paper’s witness survives this population model. Let \(n=m^2+m\), give each specialist type mass \(1/n\), and give the uniform generalist type mass \(m^2/n\). At truthful equilibrium \(p_j=1/m\): each specialist receives \(m\) units per capita and each generalist receives one unit of every good per capita. Thus \(W_{\rm eq}=2m/(m+1)\). A report profile matching the paper’s construction gives welfare at least \(m-1\), so
\[ R(\mu)\le \frac{2m}{(m-1)(m+1)}=O(1/m). \]
Since \(\tau=m+1\) and \(n=m(m+1)\), this reproduces the low-welfare scale of Theorem 8’s construction in a society with far fewer types than buyers. It does not establish a matching lower bound in terms of \(\tau\).

My provisional expectation is Class C for exact computation of this continuum PoA: after the equilibrium numerator is calculated, the central optimization still couples every type’s report through shared endogenous prices. Theorem 8 provides no hardness result to transfer, and the nonconvex-looking formula is not itself a hardness proof. The key open questions are whether that optimization admits a convex reformulation, what the sharp worst-case PoA is as a function of \(m\) and \(\tau\), and when finite clone markets converge to this atomless value.

The weakest point is the equilibrium notion. In the continuum, a unilateral deviation cannot move prices, so the numerator is a price-taking equilibrium; in the paper’s finite game, each buyer can affect the market outcome. The explicit bad-instance welfare gap survives, but that alone does not prove that the finite and continuum PoA problems agree in general. I would present this as an author-recognizable extension of Theorem 8, not as a direct equivalence.

The case AGAINST (opponent, writing after the proponent)

Theorem 8 is a welfare bound, not a computational result: it gives the asymptotic Price of Anarchy as a function of the number of buyers, but states no algorithm or complexity classification for computing an equilibrium or the ratio. The other main results concern equilibrium existence. The efficient computation of ordinary Fisher market equilibria is background cited by the paper, and the goods being divisible does not make its population continuous. Under ChoCo’s stated gate, there is no named computational result here to mirror.

The proposed advertiser setting is plausible, and the type masses do preserve the paper’s low-welfare construction. I would not object that high multiplicity is unreasonable, or that divisible goods count as population continuity. The problem is what the proposed computational task adds. In an atomless market, one buyer’s report cannot change prices. With positive prices, a type \(t\)’s best report is \(q=a_t\), since it maximizes \(\sum_j a_{tj}\log(q_j/p_j)\) over the report simplex. The equilibrium numerator is therefore explicit. The proposed algorithmic work lies in maximizing welfare over *all* report profiles. That is a coherent new optimization problem, but Theorem 8 does not study its computation; it gives a worst-equilibrium welfare bound.

The distinction matters because the finite game’s subject is strategic buyers whose reports affect market prices. An atomless version is a price-taking game. One can preserve finite buyers’ influence by keeping clone markets finite, or preserve price influence by treating each type mass as a coordinated player, but the latter changes the strategic unit. The atomless extension is a natural model in its own right; it is not automatically a computational continuation of the paper’s equilibrium result.

So I would reject this as a ChoCo mirror of Theorem 8, while conceding that computing the proposed ratio could be worthwhile as a separate market-optimization question. That is the limit of the negative case: the paper offers no computational anchor, but the material does not establish that the new optimization question is uninteresting.

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.