| paper | d4-conf-aaai-2023-0926 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.
statement extracted from the paper’s text layer
Given a finite set of types \(t=(v,\tau)\), rational masses \(\mu_t\), increasing tier click-through rates \(x_j\), and rational per-capita tier supplies \(s_j\) with \(\sum_j s_j<1\), take replications with \(N\mu_t\) advertisers and \(Ns_j\) slots. Does the MPR sequence yield a polynomial-time computable limit of type-tier assignments and prices, together with a tagged infinitesimal advertiser’s outcome under each report, that is incentive compatible for both classes, individually rational, robust, and achieves liquid social welfare at least half the feasible optimum?
A continuum market of advertiser types \(t=(v,\tau)\) with masses \(\mu_t\), tier click-through rates \(x_j\), and per-capita supplies \(s_j\). Let \(y_{tj}\) be the fraction of type \(t\) assigned to tier \(j\), with \(\sum_j y_{tj}\le 1\) and \(\sum_t\mu_t y_{tj}\le s_j\); liquid social welfare is \(W(y;\mu)=\sum_{t,j}\mu_t v_t x_j y_{tj}\). A replication limit supplies the individual allocation and price rule needed to evaluate a tagged advertiser’s deviation.
In an atomless market, a tagged deviation has zero mass, while finite MPR truthfulness depends on report-dependent allocation and pricing; the aggregate assignment by itself does not specify the deviator’s outcome.
fatal: False
The mirror tests whether MPR’s private-class \(2\)-approximation in Theorem 4 and the associated incentive properties have a fluid limit. It leaves the public-class result in Theorem 1 and the paper’s other results outside its scope; Theorem 5 does not provide a surviving computational anchor.
The strongest honest mirror is the paper’s private-class approximation problem. One caveat up front: the paper states no named NP-hardness, polynomial-time, or parameterized-complexity theorem. The closest computational anchors are its numbered approximation results. Theorem 4 gives a guarantee for an explicit algorithm; Theorem 5 gives a mechanism-design impossibility bound. Both are proved in this paper. I would not present either as a complexity-class result.
A plausible high-multiplicity setting is a large ad exchange over a fixed market window, with many campaigns sharing the same value per click and the same objective class—utility maximizer or value maximizer. A type is \(t=(v,\tau)\), where \(v\) and \(\tau\) are identical across all campaigns of that type. The regime is \(n\gg\tau\): millions of advertisers, perhaps hundreds of distinct value-and-class types. Exact common values are a demanding assumption, but shared valuation schedules within large advertiser segments make it plausible.
The slots must scale with the population too. For example, let there be \(J\) quality tiers, with CTRs \(x_j\) and supply \(s_j\) slots per advertiser; assume \(\sum_j s_j<1\), leaving some advertisers unallocated. This is the fluid version of increasing both advertisers and slots in proportion. Each individual still receives at most one ordinary slot. Only the aggregate allocation is fractional: \(y_{tj}\) is the mass of type \(t\) assigned to tier \(j\). For a population distribution \(\mu\), liquid social welfare is
\[ W(y;\mu)=\sum_{t=(v,\tau)}\mu_t v\sum_j x_j y_{tj}, \]
subject to tier capacities and the available mass of each type. This keeps the population as the continuous object; fractional type-level assignments arise because it contains many individuals.
Lead anchor — Theorem 4. It states that MPR achieves an LSW approximation ratio of at most \(2\): \(Wel_{MPR}\ge \frac12 Wel_{OPT}\). The theorem and proof are in this paper. MPR is explicitly described as an algorithm: it starts from the highest-value bidders, places value maximizers, then inserts utility maximizers into the slots they prefer at the current prices.
The corresponding question, which I would call Fluid MPR-2, is: given a finite type set \(\mathcal T\), rational masses \(\mu\), and rational tier supplies and CTRs, construct a single anonymous direct mechanism for that market. On every report distribution, it must return a feasible aggregate assignment and per-click prices; be IC for both classes when advertisers may misreport value and class; be IR; and match the VCG outcome on all-UM populations and the GSP outcome on all-VM populations. Its LSW must be at least half the optimal feasible assignment’s LSW. A solution is a rule that computes those outcomes, together with proofs of the properties for every population in the domain.
I expect this to be tractable, in the programme’s Class A sense. With finitely many types and quality tiers, the natural construction is a mass version of MPR: order type masses by value, split a cohort at a capacity boundary where needed, and update tier prices as masses are inserted. The relevant computational parameters would be the number of types \(\tau\), the number of tiers \(J\), and the rational input bit length \(L\). The paper does not prove this fluid algorithm or give a bit-complexity bound for finite MPR, so that expectation is a research question, not a result I am attributing to the authors.
A secondary anchor — Theorem 5. It proves that no IC, IR, robust mechanism can guarantee an LSW approximation ratio below \(\frac54\). The proof uses two slots with CTRs \(0.1\) and \(0.2\), and three bidders \(A,B,C\), with \(A=(\epsilon,VM)\), \(B=(2+\epsilon,VM)\), and \(C\) taking one of \((4,UM),(4,VM),(1,UM),(1,VM)\). A ratio below \(\frac54\) forces \(C\) into the higher slot when its value is \(4\), and into the lower slot when its value is \(1\). IC requires the corresponding prices \(p_h,p_l\) to satisfy \(2p_h-p_l\le4\). But in the all-VM cases, robustness fixes the GSP prices at \(p_h=2+\epsilon\) and \(p_l=\epsilon\), giving \(2p_h-p_l=4+\epsilon\), a contradiction.
The fluid counterpart, Fluid Robust-Mechanism Frontier, asks for the best worst-case LSW approximation factor over anonymous, IC, IR, robust direct mechanisms in the same two-tier market, on the four corresponding profiles. Use three equal masses, each \(1/3\), for \(A,B,C\), and tier supplies \(1/3\) each at CTRs \(0.1\) and \(0.2\). Keep \(A\) and \(B\)’s types fixed and vary \(C\)’s type among the four listed. IC is evaluated for a tagged infinitesimal advertiser against a fixed background population; a solution is either a mechanism beating \(\frac54\) on these profiles or a proof that none can.
For that restricted frontier, I expect a finite direct-mechanism optimization to be tractable, but I would not assume Theorem 5’s lower bound transfers. Its finite proof changes the value of the single bidder \(C\); in a fluid population, changing one advertiser’s report does not change a positive-mass cohort. Whether the price and allocation argument survives that difference is exactly the point to investigate. This is a useful test of where finite-agent mechanism guarantees persist under continuization.
These mirrors cover MPR’s private-class efficiency and robustness claims, especially Theorems 4 and 5; they do not attempt to continuize all of the paper, or its public-class result in Theorem 1. The underlying question remains the authors’ question—allocating scarce ad quality and setting prices truthfully for mixed UM and VM advertisers—rather than a question about fractional outcomes alone.
The weakest point is that this is computational mechanism design for advertising, not a standard voting or election-control problem in ComSoC. Also, the paper’s finite rank structure and one-bidder deviations do not automatically survive a fluid limit. The proposed mirror preserves the strategic objectives and design constraints, but a referee could reasonably ask whether proportional slot supply and aggregate tie handling make it a sufficiently faithful extension.
The strongest case against a mirror is about the paper’s strategic question, not whether many advertisers can share a type. A large market with types \(t=(v,\tau)\) is plausible, and scaling slot supply with the population is an allowed modelling choice. But the paper’s main results concern what an individual can gain by changing their report. That is where replacing a population with masses changes the question most sharply.
The proposed fluid version of Theorem 5 does not preserve its proof. In the paper, bidder \(C\)’s report changes the allocation and price comparisons used to derive \(2p_h-p_l\le4\). In an atomless population, one advertiser’s report changes no positive mass. The mechanism’s aggregate assignment for \(C\)’s cohort therefore does not switch from the value-\(4\) profile to the value-\(1\) profile when a tagged advertiser deviates. If instead the whole cohort of mass \(1/3\) changes its report, that is a coordinated deviation, not the individual incentive compatibility in the theorem. And if a tagged advertiser is given positive mass so their report can move the aggregate outcome, the model retains a discrete strategic agent; it is no longer the proposed pure continuum mirror.
There is a repair: define an individual menu or allocation rule for a zero-mass reporter against a fixed background distribution. That makes incentive compatibility meaningful, but it is additional structure that an aggregate assignment \(y_{tj}\) and price schedule do not specify, especially for a report type with zero mass. Different extensions can have the same aggregate outcomes and different incentives. The repaired model may be worth studying, but Theorem 5’s \(\frac54\) argument does not establish its frontier.
Theorem 4 is the better anchor, but it is an approximation guarantee for a mechanism, not a theorem about the complexity of a computational problem. A fluid counterpart could ask whether an MPR-like rule achieves the same welfare bound while remaining truthful for individual advertisers. Yet that requires resolving the same gap between aggregate allocations and individual deviations. If the goal is to optimize over all such fluid mechanisms, that is a new mechanism-design problem; if the goal is just to extend MPR, the paper gives no reason to expect a new complexity landscape to emerge. The finite algorithm sorts bidders and iteratively assigns slots; the theorem’s contribution is the strategic and welfare analysis, not a hard allocation problem with an unresolved pricing oracle.
The ordinary ad-auction setting also makes proportional supply a substantial modelling choice. A single page view has a small fixed number of slots. Scaling slots with advertisers means modelling a batch of placements and limiting each advertiser to one, or modelling repeated impressions and adding constraints such as budgets or exposure limits. Either can be sensible, but each changes the market represented by the paper. Keeping the original fixed inventory instead makes each winner a vanishing share of the population, so a fluid model must explain what its normalized allocation and welfare are meant to represent.
So I would not argue that no continuous auction model could be sensible. A cohort-based market might be. The negative case is narrower: neither of the proponents’ anchors survives as stated under atomless individual incentives, and repairing them leads to a new fluid mechanism-design question rather than a clear continuization of the paper’s computational results. The case is strongest against calling this a ChoCo complexity mirror; it is weaker against studying continuum advertising markets on their own merits.
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.