Answer: —
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe optimal bidding problem is NP- hard to approximate to within an additive ξ even when: the k threshold vectors in the support of (the explicitly given distribution) D take values in {1, H}m, H = k2 · m2, v = 2 · k · m and ξ = 1 2k.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\).
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.