| paper | d4-conf-wine-2015-0015 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: \(\text{Polynomial-time solvable in the stated exact oracle model}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given slot categories \(J\), mediators \(I\), advertiser types \(\Theta\) with mediator map \(i(\theta)\), binary-rational masses \(\mu_\theta\) summing to \(1\), per-unit supplies \(q_j\), and gross-substitutes valuations \(v_\theta:2^J\to\mathbb{Q}_{\ge 0}\), find a three-party equilibrium. A unit of type mass receives an integral bundle \(S\subseteq J\), while its mass may be divided among bundles. For each mediator \(i\), define \(V_i(z)\) as the maximum of \(\sum_{\theta:i(\theta)=i}\sum_{S\subseteq J}x_{\theta,S}v_\theta(S)\), subject to \(\sum_S x_{\theta,S}=\mu_\theta\), \(\sum_{\theta,S:j\in S}x_{\theta,S}\le z_j\), and \(x_{\theta,S}\ge0\). Find central prices \(r\), mediator quantities \(y_i\), local prices \(p_i\), and assignments \(x\) such that \(\sum_i y_{ij}=q_j\), each \(y_i\) maximizes \(V_i(z)-r\cdot z\), and \(x_{\theta,S}>0\) only when \(S\) maximizes \(v_\theta(S)-p_{i(\theta)}(S)\). Require local use not to exceed \(y_i\), \(p_i\ge r\), and \(p_{ij}=r_j\) wherever mediator \(i\)'s acquired supply is locally unallocated; use the componentwise-minimum envy-free local prices. Valuations may be accessed by demand oracles, with oracle cost stated separately.
A distribution over complete advertiser types \(\theta\), each with a fixed mediator and gross-substitutes valuation, competes for slot-category supply \(q\) that scales with population mass. Variables \(x_{\theta,S}\) assign type mass to integral bundles; \(y_i\) records each mediator’s acquired quantities; \(r\) and \(p_i\) are central and local prices. Mediators’ aggregate or-values \(V_i\) determine their central demand, while type-level demand and reserve-price conditions define local envy-freeness.
The paper studies one impression, so the scaled batch market requires assumptions excluding cross-impression constraints such as advertiser frequency limits; the proposed repeated-visit scenario does not establish that independence.
fatal: False
The mirror covers Theorem 4.1 and the gross-substitutes equilibrium computation in §4.3; it leaves the general existence results, non-gross-substitutes cases, and the small-item runtime improvements aside.
The strongest positive case is the gross-substitutes equilibrium computation. The paper gives no named hardness result to anchor a “hardness dissolves” story. Its closest named computational anchor is Theorem 4.1, proved here: when a mediator’s bidders all have gross-substitute valuations, the mediator’s demand at central prices equals the demand of an or-player over those bidders’ valuations; for any demanded item set, the allocation in the mediator’s virtual auction is an optimal or-player allocation, and conversely. The theorem itself is a structural equivalence, not a numbered “in P” statement. The paper’s explicit polynomial-time claim appears in the abstract and §4.3: using that equivalence and a polynomial-time gross-substitutes equilibrium algorithm, it computes a three-party equilibrium in polynomial time with demand-oracle access. That distinction matters, but Theorem 4.1 is the named result that makes the computation work.
A credible high-multiplicity setting is a large batch of similar page visits: many advertisers or campaigns compete for standardized ad-slot categories, and a relatively small set of complete advertiser profiles recurs across the batch. A type \(\theta\) includes its mediator and its entire valuation over slot bundles, so members of a type are identical in every respect the model uses. If there are \(N\) advertisers but only \(\tau\) such types, then \(\tau\ll N\) is the regime of interest. Slot supply scales with the batch: \(q_j\) is the amount of slot category \(j\) per unit of advertiser mass. Each advertiser still receives an integral bundle; fractions describe how the mass of a type is divided among bundles.
My lead mirror is Continuous Three-Party Equilibrium for Gross-Substitutes Advertiser Types. An instance has a finite set \(J\) of \(k\) slot categories, mediators \(I\), advertiser types \(\Theta\), rational masses \(\mu_\theta\ge 0\) summing to \(1\), and rational supplies \(q_j\). Each type \(\theta\) belongs to one mediator \(i(\theta)\) and has a gross-substitutes valuation \(v_\theta:2^J\to\mathbb{Q}_{\ge0}\). The input can provide valuations through demand oracles, as in the paper.
For each type and bundle, let \(x_{\theta,S}\) be the mass assigned bundle \(S\subseteq J\). For mediator \(i\), define its aggregate or-value for a quantity vector \(z\) by
\[
V_i(z)=\max \sum_{\theta:i(\theta)=i}\sum_{S\subseteq J}x_{\theta,S}v_\theta(S),
\]
subject to \(\sum_S x_{\theta,S}=\mu_\theta\), \(\sum_{\theta,S:j\in S}x_{\theta,S}\le z_j\), and \(x_{\theta,S}\ge0\). The question is to find central prices \(r\), mediator quantities \(y_i\), local prices \(p_i\), and assignments \(x\) that form a three-party equilibrium: all supply clears, \(\sum_i y_{ij}=q_j\); each mediator’s \(y_i\) maximizes \(V_i(z)-r\cdot z\); and each type receives only bundles that maximize \(v_\theta(S)-p_{i(\theta)}(S)\). Local prices satisfy \(p_i\ge r\), equal \(r_j\) for locally unallocated supply, and are the componentwise-minimum envy-free prices consistent with the local outcome. The assignment for each mediator attains the maximum defining \(V_i(y_i)\). A solution is these prices, quantities, and type-to-bundle masses satisfying those conditions. The computational objective is to find an equilibrium, not to maximize total welfare. To mirror the paper’s §4.3 selection as well, one can select among minimum-bidder-price equilibria the split that maximizes aggregate mediator rent.
I expect this mirror to be Class A, subject to proving the continuous extension. The type-to-bundle allocation is a configuration LP over masses, and its pricing questions are type-level demand queries. The paper’s Theorem 4.1 supplies the central bridge from the mediator’s local auction to an or-value, while §4.3 shows the finite-agent computation is polynomial under gross substitutes. A plausible target bound is polynomial in \(k,\tau\), and the rational bit length \(L\), with demand-oracle cost stated separately. The mirror covers the paper’s gross-substitutes equilibrium computation and its mediator-demand equivalence; it does not claim to cover the paper’s full model or establish a continuous analogue of an unproved hardness result.
The weakest point is the market regime. The paper models a single impression with a small set of slots and leaves behavior over time as future work. A batch with per-capita supply is a meaningful high-multiplicity extension, but it requires advertisers’ valuations and mediator affiliations to repeat across many comparable opportunities. If nearly every campaign has a distinct valuation, then \(\tau\) approaches \(N\) and the high-multiplicity benefit fades. A second open question is whether the minimum-price local outcome and the or-player demand equivalence persist in this mass-allocation model with the claimed bit complexity. Those are the proof obligations; they do not make the equilibrium question a different problem from the one the paper computes.
The best case against this mirror is the gap between the paper’s market and the population limit. Its formal model is one impression auction with \(k\) slots. If the number of advertisers grows while slot supply stays fixed, only a vanishing fraction can receive anything; the nondegenerate proposal instead scales supply too, turning the market into a batch of impressions. That is a natural extension, but it brings in frequency limits and cross-impression constraints that the paper explicitly leaves for future work. The paper’s own high traffic is therefore traffic across auctions, not necessarily a large population inside one auction.
The stronger mirror still has a plausible regime: many advertisers with identical valuations and mediator affiliations competing for standardized slot capacity. But exact type equality means identical values for every bundle and the same mediator. In realistic campaign markets, targeting, eligibility, budgets, and creative differences may make the support nearly as large as the advertiser population. This is a reason to doubt the regime’s empirical relevance, not to rule it out: the paper’s model abstracts away those distinctions, and a repeated standardized advertiser type is possible.
I can’t dismiss Theorem 4.1 as lacking a computational anchor. It is a named structural result that supports the paper’s polynomial time equilibrium algorithm in §4.3. Nor does the paper text establish that a continuous treatment already answers its question. The proposed mass model has a coherent extension: allocate each type’s mass fractionally among bundles and use the resulting aggregate valuation in the mediator’s demand. Gross substitutes make that extension look tractable. So the honest negative case is weak: it questions whether the scaled supply model is a worthwhile mirror of this particular paper, but it does not defeat the credible repeated-type scenario or show that no useful continuous question remains.
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.