| paper | d4-conf-wine-2023-0031 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 1 passes the computational-result check: it gives a welfare guarantee for a specified mechanism. But the proposed continuous version makes each agent infinitesimal, changing the finite-player Bayes–Nash game and its incentives. The finite theorem therefore does not establish or preserve the proposed atomless question.
fails bit b-changes — the continuum limit changes the question
The atomless limit changes the equilibrium concept and strategic incentives; Theorem 1 gives no guarantee for equilibria of that changed game.
fatal: True
The proposed market concerns Theorem 1’s nonnegative-values welfare guarantee. It leaves the inspection and hypergraph results and the negative-values stability results aside; the proposed atomless version does not survive as a mirror of Theorem 1.
The strongest mirror I see is the paper’s positive-values result. Theorem 1, proved in this paper, says that on a general graph with nonnegative values and nonnegative bids, every Bayes–Nash equilibrium of the \(1/4\)-rebate Marshallian Match has expected social welfare at least \(1/8\) of the expected welfare of the optimal matching with realized values. The guarantee is over the prior on types and equilibrium randomization. The paper proves it using a truthful-deviation smoothness argument. This is a named computational game-theoretic result, though it is a welfare guarantee rather than a classification such as \(P\) or NP-hardness. The paper has no numbered theorem asserting such a complexity classification.
A plausible regime is a large market assigning businesses to standardized municipal sites. There may be hundreds of thousands of businesses and sites, but far fewer complete types: a type records a business’s values for each site class, or a site’s values for each business class, along with feasibility. Members of a type are indistinguishable in every market attribute the model uses. Their mass is their fraction of the market; matching a mass of \(x\) from one type to another represents \(xN\) matches in a market of size \(N\). This uses the paper’s positive-values setting and avoids relying on its separate job-market motivation, where values may be negative.
I would call the mirror Atomless Marshallian Match PoA. An instance has finite sets of business and site types, a feasible bipartite type graph, rational masses \(\mu_t\) and \(\nu_u\), and nonnegative type-pair values \(v_{tu}\) and \(v_{ut}\). A feasible continuous matching is a flow \(x_{tu}\geq0\) satisfying \(\sum_u x_{tu}\leq\mu_t\) and \(\sum_t x_{tu}\leq\nu_u\). For each realization of values, the first-best benchmark is the maximum of \(\sum_{tu}x_{tu}(v_{tu}+v_{ut})\) over those flows.
The mechanism uses the paper’s descending price and \(1/4\)-rebate rule. An agent bids over time for each feasible partner type; eligible type pairs are matched as the price descends, subject to the remaining masses. Because several type pairs may become eligible at once, the continuous version must specify a mass-flow tie rule—for example, a fixed priority over type pairs. The question is whether, for every such typed society and every Bayes–Nash equilibrium of this atomless game, expected welfare is at least \(1/8\) of the expected first-best flow welfare. A proof is a positive solution; a typed instance and equilibrium below that ratio is a counterexample. The type-level optimum is an LP with at most \(|B||A|\) variables, so its benchmark is tractable in the support size.
I expect the smoothness guarantee to transfer, making this a positive, tractable-style case: the proof’s inequalities are per-pair and should extend to mass flows by integration. The mirror covers Theorem 1’s nonnegative-values welfare guarantee, not the paper’s negative-values stability results or its group-formation extension. Further questions include whether \(1/8\) is tight, whether the bound holds for every admissible tie rule, and how equilibrium outcomes behave as the type support grows.
The soft spot is substantial: the paper’s mechanism matches named individuals, whereas this mirror matches masses. In particular, a continuum version needs a well-defined pairing rule and equilibrium notion, and those choices could affect incentives. Taking a limit of finite replicated markets makes the bound follow from Theorem 1 at every finite size, but that risks making the mirror a restatement rather than a new result; a genuinely atomless game is more interesting and harder to justify as the authors’ same problem. This is also a weaker fit for ChoCo’s complexity landscape than a hardness or algorithmic-complexity anchor would be.
Theorem 1 is the proponent’s only anchor, and the business–site example makes a credible high-multiplicity setting. I would not reject it on the grounds that matching is inherently individual: with complete types and type-to-type flows, the proposed population model is sensible.
My objection is that Theorem 1 does not pose a computational problem in ChoCo’s sense. It bounds the welfare of every Bayes–Nash equilibrium of a mechanism. It gives no running-time, algorithmic, or complexity claim about an encoded society. The proposed mirror asks whether the same welfare bound holds in an atomless game. That is a legitimate question in nonatomic mechanism design, but it does not chart the complexity of a computational social-choice problem. The type-level first-best benchmark is already a maximum-weight flow LP; the paper’s theorem neither computes an equilibrium nor claims that doing so is tractable.
The strongest version of the mirror—finite types, rational masses, measurable bids, and a specified matching flow—does not fix that mismatch. It makes the nonatomic game precise, but it still asks for an equilibrium-welfare theorem. Treating cohorts as strategic players to preserve their ability to affect market clearing would instead change the game. A finite replication is covered by the paper’s theorem; taking a limit may require work, but that work concerns convergence of games and equilibria, not the computational landscape ChoCo is mapping. A new question about computing equilibria or best responses could be computationally interesting, but it would not be a mirror of Theorem 1.
So my case against this anchor is a scope objection, not a claim that the population model is implausible or that the theorem’s answer is uninteresting. It is a strong objection only if ChoCo requires a computational problem as its anchor. If the programme also counts nonatomic price-of-anarchy analysis as computational social choice, the proponent’s mirror survives. I cannot honestly support the broader claim that no worthwhile continuous mirror exists in any scenario.
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.