d4-conf-ijcai-2022-0511

The strongest mirror I believe is a high multiplicity, population-normalized GSP market: a media agency manages a very large portfolio of campaigns, but only a small number \(\tau\) of complete advertiser types occur. A type records everything relevant to participation, including its value per click and its minimum acceptable utility. Its mass is the fraction of the managed portfolio with that type. The setting is plausible when many campaigns share the same valuation and outside option, and the number of campaigns is much larger than the number of types.

For the market to have a nondegenerate limit, ad-slot supply must scale with the portfolio. Let \(\kappa\) be the number of slots per unit of managed mass, and let \(\lambda(z)\) be the click-through rate at rank \(z\), given as a nonincreasing, piecewise-rational curve. External competition is a finite rational lottery over bid-mass profiles. That lottery represents uncertainty in the paper’s environment; it is not itself the continuization.

My lead anchor is Theorem 4, proved in this paper. It says that, for the limited-liability media-agency problem, for every \(\varepsilon>0\) there is an algorithm running in time polynomial in the instance size and \(1/\varepsilon\) that returns an IR solution satisfying \(\varepsilon\)-IC and having value at least \(\mathrm{OPT}-\varepsilon\), with no advertiser paid by the agency. The paper’s result applies to GSP and VCG; I take its GSP case as the mirror.

Call the continuous problem Fluid Limited-Liability GSP Coordination. Its input is a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), type values \(v_t\) and outside-utility thresholds \(a_t\), the slot-supply and click-rate curve \((\kappa,\lambda)\), and a finite rational distribution \(\nu\) over external bid-mass profiles. A bidding policy \(X\) assigns each type’s mass to bids: \(X_t\) is a measure on \([0,1]\) with total mass \(\mu_t\). The agency may randomize over such policies, using a distribution \(\Gamma\), and chooses a transfer \(q_t\geq0\) per unit of type \(t\).

For policy \(X\) and external environment \(\omega\), rank the combined bid mass in descending order, resolving ties proportionally. Let \(\rho_t^{X,\omega}\) be the rank measure of type \(t\), and let \(\rho_C^{X,\omega}=\sum_t\rho_t^{X,\omega}\) be the colluders’ rank measure. The per-capita expected click value of type \(t\) is
\[ R_t(X,\omega)=\frac{v_t}{\mu_t}\int_0^\kappa \lambda(z)\,\rho_t^{X,\omega}(dz). \]
Let \(b_{X,\omega}(z^+)\) be the bid immediately below rank \(z\). The agency’s GSP payment per unit of managed mass is
\[ P(X,\omega)=\int_0^\kappa \lambda(z)b_{X,\omega}(z^+)\,\rho_C^{X,\omega}(dz). \]
The problem is to maximize
\[ \mathbb{E}_{X\sim\Gamma,\,\omega\sim\nu} \left[\sum_{t\in T}\mu_tR_t(X,\omega)-P(X,\omega)\right] \]
subject to
\[ \mathbb{E}[R_t(X,\omega)]-q_t\geq a_t-\varepsilon \quad\text{for every }t,\qquad \sum_t\mu_tq_t\geq\mathbb{E}[P(X,\omega)],\qquad q_t\geq0. \]
A solution is the transfers and a finite-description randomized policy—finitely many bid levels and rational masses—meeting those guarantees. The concrete question is whether such a solution can be computed in time polynomial in \(\tau\), the external-profile description, the description of \(\lambda\), the input bit length, and \(1/\varepsilon\). I would expect Class A for this restricted, finite-description setting: the paper’s LP and separation approach has a natural type-mass counterpart. That is a conjecture to investigate, not a consequence of Theorem 4.

A second anchor worth keeping is Theorem 3, also proved here. It gives the same polynomial-in-instance-size-and-\(1/\varepsilon\) guarantee—\(\varepsilon\)-IC, IR, and value at least \(\mathrm{OPT}-\varepsilon\)—for arbitrary transfers. Its mirror, Fluid Arbitrary-Transfer GSP Coordination, is the same problem with \(q_t\in[-1,1]\) instead of \(q_t\geq0\). I also expect Class A, though this version does not need randomized bidding in the finite paper’s optimal solution. Theorem 4 is my lead because limited liability preserves the paper’s more delicate randomized-policy and ellipsoid story.

Both anchors are algorithmic: the paper supplies no named NP-hardness or other hardness result to anchor a “hardness dissolves” claim. The scope here is the paper’s media-agency optimization under its GSP mechanism, not every result or technical lemma in the paper. The authors could recognize the mirror: advertisers remain the agents, the agency still coordinates bids, type-level utility still enforces participation, and the transfer constraint remains central. Replacing counts by masses groups agents only when their values, outside options, and other problem-relevant attributes agree.

The main weakness is the supply scaling. With a fixed number of slots and a growing advertiser population, almost all mass receives no slot, so per-capita utility collapses. Scaling supply and representing the portfolio by a rank curve are substantial co-modifications. They are plausible for a large, recurring portfolio of comparable ad opportunities, but an author insisting on one literal auction with fixed, indivisible slots might reject this as their problem’s continuous form. The mirror also does not inherit the paper’s FPTAS automatically: the fluid weighted-utility pricing step must actually be solved.

That boundary suggests the follow-up questions: whether fluid GSP pricing has an efficient separation oracle; how accurately a finite high-multiplicity portfolio approximates this mass model; and whether the answer changes when slot supply is fixed. Those questions retain the paper’s coordination and participation problem while making the population, rather than its uncertainty, the continuous object.