| paper | d4-conf-ijcai-2018-0518 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorem 2 is a computational result for a finite-bidder Bayesian game. The proposed marked-bidder limit is concrete, but it removes each bidder's effect on aggregate allocation and changes the strategic problem to a nonatomic price-taking game. The finite-game regret guarantee therefore has no surviving continuous analogue as stated.
fails bit b-changes — the continuum limit changes the question
A single bidder's mass vanishes in the limit, so the bidder's allocation response becomes price-taking; moreover, pointwise payoff limits need not preserve the supremum over deviations.
fatal: True
The attempted mirror covers Theorem 2 and Algorithm 1 for first-price auctions; it leaves the payment-rule results and finite-game experiments without a continuous-population counterpart.
The strongest mirror is the paper’s Theorem 2, proved in the paper. It says that, for a combinatorial auction with a non-decreasing payment rule, Algorithm 1 returns a strategy profile \(s\) and a number \(\epsilon\) such that \(s\) is an \(\epsilon\)-BNE: every bidder, at every valuation, can gain at most \(\epsilon\) by changing their bid. The guarantee accounts for deviations across the full action space, even though the algorithm builds strategies from finitely many bids. The corrigendum says Theorem 2 remains valid; I would instantiate it with the first-price rule, whose non-decreasing property is established in the paper. This is an algorithmic anchor, not a polynomial-time result: the theorem certifies the returned profile, but does not guarantee that every requested tolerance can be reached or bound the running time polynomially. The paper contains no comparable named hardness result to anchor instead.
Here is the population mirror I would ask authors to consider. Call it Mass-CA \(\epsilon\)-BNE Search. An instance has \(m\) goods, a finite family of packages, and \(\tau\) bidder types. A type \(\theta\) completely specifies the bidder’s value vector over the packages, eligible packages, and any other relevant constraints. Each type has rational population mass \(\mu_\theta\), with \(\sum_\theta\mu_\theta=1\). Members of a type are interchangeable for the auction. The auction sells \(q_j\) units of good \(j\) per capita, for rational \(q_j\); in a finite replication with \(N\) bidders, there are \(N\mu_\theta\) bidders of type \(\theta\) and \(Nq_j\) units of good \(j\). Each bidder still receives an integral package. A type-level allocation can be fractional because it describes what fraction of that type receives each package.
For a bid profile \(\beta\), the mass allocation is the welfare-maximizing solution to the winner-determination LP. If \(z_{\theta K}\) is the fraction of type \(\theta\) assigned package \(K\), its objective is \(\sum_{\theta,K}\mu_\theta z_{\theta K}\beta_\theta(K)\), with one package per bidder and the per-capita supply constraints \(\sum_{\theta,K:j\in K}\mu_\theta z_{\theta K}\le q_j\). Under first-price payments, a bidder assigned \(K\) pays their bid \(\beta_\theta(K)\).
A candidate solution is a bid vector \(\beta_\theta\) for each type and a certified bound \(\epsilon\) on regret. Define a type’s payoff from a unilateral deviation by inserting one marked bidder who changes their bid while all other bidders keep following \(\beta\), then taking the expected-payoff limit in the finite replications as \(N\) grows. Fix the auction’s tie-breaking rule, and restrict the problem to instances where these limits exist. The profile is an \(\epsilon\)-BNE if, for every type \(\theta\), no marked bidder can improve their limiting expected utility by more than \(\epsilon\) with any package-bid vector. The target-tolerance search problem is: given \(\bar\epsilon\), find such a profile with \(\epsilon\le\bar\epsilon\), or report that none exists. This gives a prover a concrete population model, strategic deviation, payoff, and success condition.
A plausible regime is a large online advertising exchange with many small advertisers, each bidding on packages of placements. Advertisers with the same package values and constraints form one type; the exchange’s inventory grows with the advertiser population. In that regime \(N\) can be very large while \(\tau\), the number of distinct valuation schedules, stays modest. The package allocation and per-capita supply are co-modified because the population has become the continuous object. This retains the paper’s core question—how package bids and payment rules shape incentives—rather than merely making values or outcomes continuous.
My initial expectation would be Class A for fixed package dimension and fixed tolerance, with the dependence on the number of packages left open. The mass allocation is an LP, and the paper’s utility-plane method suggests a route to certify deviations. A result would need to control the size of the deviation regions and the equilibrium search, not just solve the allocation LP. The follow-up questions are whether the marked-bidder limit preserves the paper’s cell-vertex structure, whether finite-replica equilibria approximate mass equilibria with a bound, and what running time is possible in \(m,\tau,L\), package dimension, and \(1/\bar\epsilon\).
The weakest point is also central: an individual bidder’s deviation has vanishing effect on the aggregate allocation in the limit. The paper’s finite-player best-response geometry, including its treatment of ties, may therefore fail to carry over. The marked-bidder limit makes the proposed question precise, but it does not establish that the authors’ theorem or algorithm extends to it. The case for the mirror is that this is a natural large-auction regime for their incentive-computation problem, and the limit’s failure—or preservation—of their structural guarantee is itself a sharp computational question.
Theorem 2 is a genuine anchor, and its first-price case survives the corrigendum. But it certifies regret in a finite-bidder Bayesian game: for each bidder and each valuation, it compares that bidder’s possible bids against the random bids generated by the other bidders’ strategies. The utility-plane algorithm uses how one bidder’s bid changes their allocation among the finite set of goods. Its guarantee says the reported \(\epsilon\) is sound; it does not guarantee a requested tolerance can be reached or give a running-time bound for doing so.
In the proposed mass model, the allocation LP records fractions of each type assigned to each package. A unilateral deviation by one bidder has zero mass, so it leaves that aggregate allocation unchanged. Treating a positive fraction of a type as deviating would preserve an effect on the LP, but that is a group-deviation question rather than the paper’s individual BNE question. The natural repair is to mark one bidder in finite replications. That gives the bidder an allocation and payoff, but those depend on microscopic tie-breaking and on how the finite market approaches its limit.
Even existence of a payoff limit for every fixed bid does not settle the equilibrium question. The paper’s regret takes a supremum over all bids, and the most profitable deviation can vary with market size. In general,
\[
\lim_{N\to\infty}\sup_b u_N(v,b)
\ne
\sup_b\lim_{N\to\infty}u_N(v,b).
\]
Near a market-clearing tie, for example, a bid just above the finite-market cutoff can win while a bid at the limiting cutoff receives only a fraction of the allocation. Capturing that distinction requires control of the finite-size boundary behavior, not just the aggregate mass LP.
A direct continuum game can instead define an infinitesimal bidder against a fixed market-clearing allocation. That is a coherent model, but it removes the bidder’s effect on aggregate allocation and changes the strategic problem to a price-taking limit with threshold responses. Under first-price payments, a bidder may prefer to bid arbitrarily close above a cutoff, so an exact best response need not exist. Approximate regret still makes sense, but whether the paper’s cell-vertex guarantee survives is then a new question about that limit game, not a continuation of its finite-player result.
This is the strongest negative case, not an airtight one. Large markets with growing inventory are plausible, and a computational study of price-taking equilibria or finite-size corrections could be worthwhile to these authors. The weakness is that the marked-bidder construction can preserve a recognizable incentive question; the case against rests on its singular limit and uncertain computational payoff, not on showing that no sensible mirror can be posed.
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.