| paper | d4-journals-geb-2022-0022 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Input \(m\) items, a unit-demand focal bidder of value \(v\), and a mass-one population of \(\tau\) rival bid types \(\theta^t\in\mathbb{Q}_{\ge 0}^m\), with binary-rational masses \(\mu_t>0\) summing to \(1\). Each encounter independently matches the bidder with one rival sampled according to \(\mu\), and ties are lost. For \(b\in\mathbb{Q}_{\ge 0}^m\), let \(W_t(b)=\{j:b_j>\theta^t_j\}\) and \(U_\mu(b)=\sum_{t=1}^{\tau}\mu_t\left(v\mathbf{1}\{W_t(b)\ne\varnothing\}-\sum_{j\in W_t(b)}\theta^t_j\right)\). Given rational \(\varepsilon>0\), compute a bid vector \(b\) such that \(U_\mu(b)\ge \sup_{b'\in\mathbb{Q}_{\ge 0}^m}U_\mu(b')-\varepsilon\).
A population of rival-agent types has masses \(\mu_t\), with each type submitting a fixed bid vector \(\theta^t\). A focal unit-demand bidder chooses one bid vector \(b\); its objective is expected utility \(U_\mu(b)\) over repeated random matches with one rival per encounter.
The population interpretation depends on independently sampling one rival per encounter; in an auction with many rivals, thresholds depend on coordinatewise maxima, not population-average utility. The proponent specifies random one-rival encounters, so this bounds the mirror's scope without eliminating it.
fatal: False
The mirror covers Theorem 5's offline best-response hardness for unit-demand bidders facing explicit threshold distributions, including uniform masses \(1/k\); it leaves Theorem 1's online no-regret result, Theorems 2–3's no-envy algorithms, and Corollary 4's welfare guarantee unmirrored.
I would build the positive case around Theorem 5 alone. It gives a direct hardness anchor, and its underlying optimization problem has a natural high-multiplicity market interpretation.
Theorem 5 proves here that the paper’s Optimal Bidding Problem is NP-hard to approximate within additive error \(\xi\), even when the bidder is unit-demand, values every nonempty bundle at \(v\), and \(v\) is given in unary. The distribution is an explicit uniform list of \(k\) threshold vectors, each in \(\{1,H\}^m\), where \(H=k^2m^2\); the theorem sets \(v=2km\) and \(\xi=1/(2k)\). The proof in Appendix A.1 reduces from regular set cover and uses its known approximation hardness.
Here is the mirror I would ask a prover to study: Population-Threshold Optimal Bidding. There are \(m\) items and a mass-one population of potential opponents. A type \(t\) is an opponent whose fixed bid vector is \(\theta^t\in\mathbb{Q}_{\ge 0}^m\); any other opponent attributes are fixed or irrelevant to the focal bidder’s payoff. The input lists the \(\tau\) positive-mass types and their binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). A unit-demand focal bidder has value \(v\) for any nonempty bundle and faces a two-player SiSPA in a separate encounter with an opponent drawn from this population. Ties are lost, as in the paper.
For a bid vector \(b\), let \(W_t(b)=\{j:b_j>\theta^t_j\}\). The bidder’s population-average utility is
\[ U_\mu(b)=\sum_{t=1}^{\tau}\mu_t\left(v\,\mathbf{1}\{W_t(b)\ne\varnothing\}-\sum_{j\in W_t(b)}\theta^t_j\right). \]
Given \(m,v,\{(\theta^t,\mu_t)\}_{t=1}^{\tau}\), and rational \(\varepsilon>0\), the problem is to output a bid vector \(b\) whose utility is at least \(\sup_{b'\ge 0}U_\mu(b')-\varepsilon\). The society is the pool of rival agents: \(\mu_t\) is the fraction with behavior type \(t\), and \(\tau\) is its support size. In a large pool, many distinct opponents share each type, while the focal bidder’s one bid vector is judged by its average payoff across encounters.
The authors should recognize this mirror: the paper already studies the exact offline question of choosing a bid against an explicit distribution of competing thresholds. The scenario makes those thresholds the fixed behavior types of a large opponent population; it does not simplify the bidder’s unit-demand objective or the auction rule. The continuous object is the population composition, while the items and their allocations remain indivisible.
I expect hardness transfers (Class B). The continuous problem contains the theorem’s instances: assign mass \(1/k\) to each listed threshold vector, aggregating duplicates if needed. That preserves the objective exactly. The set-cover combinatorics remain in the item and type data, not in the number of copies of an agent, so replacing headcounts with masses does not remove them. Further questions include whether the problem is fixed-parameter tractable in \(\tau\), whether small support changes the picture, and which restrictions on threshold vectors defeat the set-cover reduction.
This mirror covers Theorem 5’s offline best-response computation only. It does not claim to mirror Theorem 1’s online no-regret result, the no-envy algorithms, or the welfare guarantees.
My weakest point is also the main novelty risk: Theorem 5 already takes an explicit distribution over thresholds as input. Recasting its support weights as population masses may look like relabeling a probability distribution, which the programme treats as out of scope if that is all the mirror does. The case survives only insofar as the proposed regime is an actual high-multiplicity market of rival agents, not merely random threshold states. Even then, the resulting optimization formula is almost identical to the paper’s; this is a credible population interpretation and a clean hardness mirror, but a modest claim of novelty.
Theorem 5 is a genuine computational anchor, but it is also the point where the proposed population interpretation stops adding a continuous-population problem. The paper already asks for the best bid against an explicit distribution of threshold vectors, maximizing expected utility over auction encounters. In the proposed mirror, \(\mu_t\) is exactly the probability of encountering threshold type \(t\). Setting each mass to \(1/k\) reproduces the paper’s input and objective exactly; allowing arbitrary rational masses changes the weights in that existing distributional problem, not the model’s population.
A literal pool of many opponents does not preserve that objective. In a simultaneous second-price auction, the focal bidder faces the coordinatewise maximum of opponents’ bids. With many copies of each type, that threshold depends on which types are present and their bids—not on their population shares. In an atomless limit, positive-mass types still contribute through the support or supremum. The weighted average in the proposed mirror returns only if the focal bidder meets one randomly sampled opponent per encounter. Then the masses are probabilities over market states, and the problem is the distributional best-response problem the paper already formulates.
So the anchor has a dilemma: preserve Theorem 5’s objective and the “continuization” is a relabeling of its threshold distribution; model an actual high-multiplicity auction and the weighted objective no longer describes the bidder’s best response. The theorem’s hardness remains meaningful, but it does not establish a worthwhile continuous-population mirror. A new algorithmic study of arbitrary rational weights might be useful on its own; its motivation would be distributional best response, not continuizing the population. This is the strongest objection I see, though it does not rule out a broader market model with random rematching.
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.