| paper | d4-conf-ijcai-2019-0411 |
| 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: Polynomial-time solvable, with deterministic welfare exactly \(\mathrm{OPT}\), for both XOS and subadditive CTRs. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4.2
statement extracted from the paper’s text layer
Given rational masses \(\mu_t\) of advertiser types, where type \(t\) has bid \(b_t\) and CTR function \(\theta_t\), and per-position supply \(\rho\) across \(m\) ordered slots, find mass assignments \(x_{t,S}\) to the empty bundle or an interval \(S\), together with common total bundle prices \(p(S)\). Require \(\sum_S x_{t,S}\le\mu_t\), \(\sum_{t,S:\,j\in S}x_{t,S}\le\rho\), and that every \(S\) with \(x_{t,S}>0\) maximizes \(b_t\theta_t(S)-p(S)\), including the empty bundle. Determine whether this can be computed with the paper’s competitive-equilibrium conditions and welfare guarantees: \(1/4\) for XOS CTRs and \(O(\log\log m/\log m)\) for subadditive CTRs.
A market with a continuum of interchangeable campaign entries, grouped into \(\tau\) complete bid-and-CTR types, and repeated page inventory scaling with population. Each unit receives one integral interval of slots, while type mass can split among intervals; all units of a type face the same total price for each bundle.
The finite pricing construction assigns prices after allocating bundles to individual advertisers; it does not establish that all bundles receiving positive mass for one type maximize utility under a single common price menu.
fatal: False
Covers consecutive rich-ad welfare allocation and the approximate competitive-equilibrium pricing guarantees for XOS and subadditive CTRs; leaves the finite-bidder counterexamples for GSP pricing generalizations and non-consecutive allocation results aside.
The strongest mirror is the paper’s consecutive-slot welfare allocation problem. Take a large batch of interchangeable search-results pages, each with \(m\) ordered ad positions. A population unit is a one-placement campaign entry—for example, a local-business location or product campaign eligible for one featured placement in the batch. Its complete type \(t\) includes its bid per click \(b_t\) and CTR function \(\theta_t\). Units of the same type are identical in every feature the model uses. A plausible regime has millions of campaign entries but only hundreds or thousands of distinct bid-and-CTR types, with \(m\) small. The page inventory scales with the population: each position has \(\rho\) units of supply per unit of population. That co-modification is needed to make positive mass of assignments possible; it is part of this mirror.
Lead: continuous consecutive rich-ad welfare allocation. The anchor is Theorem 2.3, proved in this paper: Algorithm 1 gives a \(1/4\)-approximation for welfare maximization with consecutive allocations and fractionally subadditive (XOS) valuations. The continuous question is: given rational type masses \(\mu_t\), per-position supplies \(\rho\), and XOS CTR values for the feasible bundles, find a welfare-maximizing allocation of population mass to consecutive bundles.
Let \(\mathcal I_m\) be the empty bundle and all nonempty intervals of positions. Let \(x_{t,S}\) be the mass of type \(t\) assigned bundle \(S\). The problem is
\[ \max_x \sum_{t\in T}\sum_{S\in\mathcal I_m}x_{t,S}b_t\theta_t(S) \]
subject to
\[ \sum_{S\in\mathcal I_m}x_{t,S}\le \mu_t \quad(t\in T),\qquad \sum_{t\in T}\sum_{\substack{S\in\mathcal I_m\\j\in S}}x_{t,S}\le \rho \quad(j\in[m]),\qquad x_{t,S}\ge0. \]
A solution is the allocation masses \(x\), or an equivalent measurable assignment of agents to bundles. Each individual still receives one integral consecutive bundle; only a type’s mass can be split among bundles. With values listed or evaluable on the intervals, this is an LP with \(O(\tau m^2)\) allocation variables, so I expect a Class A result: exact polynomial-time optimization in \(m,\tau,L\). The finite paper needs rounding to respect indivisible agents and slots; the mass problem does not. This is a direct high-multiplicity continuation of its welfare objective.
A second, distinct question concerns pricing. Theorem 4.2, proved here using Algorithm 3 and Lemma 4.1, says the paper’s allocation-and-nonlinear-pricing rule guarantees competitive equilibrium together with a \(1/4\) approximation for XOS CTRs and the stated \(O(\log\log m/\log m)\) approximation guarantee for subadditive CTRs. The continuous mirror is: on the same mass-allocation instance, find allocation masses \(x\) and a price \(p(S)\) for each feasible bundle such that the assignment is individually rational, envy-free, market-clearing, and budget-balanced in the paper’s sense, while meeting those welfare guarantees. In particular, whenever \(x_{t,S}>0\), bundle \(S\) must maximize \(b_t\theta_t(R)-p(R)\) over feasible bundles \(R\), including the empty bundle. Prices must be common to agents of the same type. I would initially expect this to be tractable through a type-level adaptation of the paper’s pricing construction, though that is less certain than the welfare LP.
The paper’s prose says that non-consecutive allocation is NP-hard for gross-substitutes valuations, citing Lehmann et al. (2006), but that claim is not a numbered theorem proved here, so I do not use it as an anchor. The anchors above are algorithmic; I am not claiming that a named hardness result dissolves in the continuum. The mirror covers the paper’s welfare-allocation and approximate-CE results, not its finite-bidder counterexamples to particular GSP pricing rules.
The weakest point is the regime needed to make the model genuinely continuous. A single page has only \(m\) positions, so normalizing a large advertiser population while leaving that page fixed would make assigned mass vanish. The batch of repeated pages and one-placement campaign entries addresses this by scaling supply with population, as the continuization programme permits. It is also a different instance regime from one page with many competing advertisers, and exact shared types may be restrictive. The equilibrium mirror has an extra risk: the finite algorithm prices allocated bundles for individual bidders, while identical agents in a continuum must face consistent type-level prices. That is a real open condition on the mirror, not a reason to discard the welfare-allocation question.
The natural follow-ups are to formalize the finite-to-continuous rounding dictionary for type masses and slot supplies, and to determine whether the CE guarantee survives when prices must be common across every agent of a type.
The strongest objection is to Theorem 2.3: its continuous welfare mirror is already the configuration LP used inside the paper’s algorithm. Aggregate the paper’s fractional variables \(x_{i,S}\) over advertisers of type \(t\), obtaining \(y_{t,S}\). The constraints become
\[
\sum_S y_{t,S}\le \mu_t,\qquad
\sum_{t,S:\,j\in S}y_{t,S}\le \rho.
\]
Those are exactly the type-mass and per-position supply constraints in the proposed mirror, with the same objective coefficients \(b_t\theta_t(S)\). Because the feasible bundles are intervals, there are only \(O(m^2)\) of them. An atomless population can realize any such \(y\) by assigning different portions of each type to different bundles. So the continuous allocation is exactly the LP the paper already solves as a subroutine. Repeating pages and scaling supply changes the constraint bounds, not the computational question. This is a real collision with the paper’s own formulation, rather than an objection that the continuous answer would be easy or unchanged. Aggregating identical advertisers may still be useful for compressing input, but by itself it offers little new algorithmic territory.
Theorem 4.2 is harder to dismiss. Its proof prices bundles following a finite allocation; it does not establish that a type whose mass is split across bundles can face one common price per bundle while all assigned bundles remain utility-maximizing and slot supplies clear. Such a mirror needs a type-level demand condition: if \(y_{t,S}>0\), then \(b_t\theta_t(S)-p(S)\) must be maximal among feasible bundles. The paper’s finite construction does not directly provide that condition for a mass allocation. But this is not a strong objection to the best version of the mirror: in a repeated-page regime built from copies of a finite auction, the paper’s allocation and prices can be replicated across pages. That supports a continuous equilibrium for those regimes.
I therefore cannot honestly make the requested universal negative case. The welfare anchor is largely already answered by the paper’s LP, and the pricing anchor is either inherited in replicated regimes or poses a distinct common-price question in more general type-mass markets. The latter remains a plausible computational mirror; the objections here do not defeat 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.