Answer: The uniform welfare bound holds. With natural logarithms, \(C=10\) works for every admissible \(k\geq4\). After every activation of bidder \(2\), \(W_t/W^*\leq(\log_2 k+4)/k\).
Theorem 4.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor every positive integer $k \in \mathbb{N}_{>0}$ there exists an instance with $n = 2$ players, $m = 2^k-1$ items, and subadditive valuations $v = (v_1,v_2)$ such that in every best-response dynamics in which players do not overbid on the grand bundle there exist infinitely many time steps $t$ at which \[ SW(b^t) \leq \frac{1}{\Omega\left(\frac{\log m}{\log\log m}\right)} \cdot OPT(v).
statement extracted from the paper’s text layer; consult the paper for the exact wording
For fixed \(k\), take a rational mass of identical copies of the paper's two-bidder instance \(\mathcal I_k\), with \(m=2^k-1\) local items per copy, and synchronize copies at the same bid profile and update step. Under local best-response dynamics that do not overbid on the grand bundle, must aggregate welfare be at most \(O(\log\log m/\log m)\) times aggregate optimum in infinitely many rounds?
Let \(k=2^r\) with integer \(r\geq2\), \(m=2^k-1\), and \(M=\mathbb F_2^k\setminus\{0\}\). Define \(S_a=\{x\in M:a\cdot x=1\}\) for \(a\in M\); \(v_1(T)\) is the minimum number of these sets covering \(T\), including \(v_1(\varnothing)=0\).
Set \(d=k-\log_2 k\), \(\rho=4k/m\), and \(\mathcal D=\{U\setminus\{0\}:U\leq\mathbb F_2^k,\ \dim U=d\}\). Define \(v_2(T)=\rho\max_{D\in\mathcal D}w_D(T)\), where \(w_D(T)=0\) if \(T\cap D=\varnothing\), \(w_D(T)=|D|/2\) if \(0<|T\cap D|<|D|\), and \(w_D(T)=|D|\) if \(D\subseteq T\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here the two bidder types \(v_1,v_2\) each have mass \(q\in\mathbb Q_{>0}\), paired into mass \(q\) of identical two-bidder auctions; masses need not sum to one. Each copy has its own local items, with no transfers or competition between copies.
Use simultaneous second-price item auctions with nonnegative real bids, quasi-linear utilities, and arbitrary fixed item tie-breaking identical across copies. At every integer step, the same bidder role in every copy chooses the same exact best response against the other role's unchanged bids; best responses maximize utility over all nonnegative bids. Each role is activated infinitely often, and initial bids and every subsequent profile satisfy \(\sum_{j\in M}b_{i,j}^t\leq v_i(M)\) for \(i\in\{1,2\}\).
For the local winning bundles \(A_1^t,A_2^t\), define aggregate welfare \(W_t=q\bigl(v_1(A_1^t)+v_2(A_2^t)\bigr)\) and aggregate optimum \(W^*=q\max_{T\subseteq M}\bigl(v_1(T)+v_2(M\setminus T)\bigr)\). Any running times are measured in \(m,\tau,L,k\), where \(L\) is the binary input length.
Does there exist a universal constant \(C>0\) such that, for every sufficiently large admissible \(k\), every positive rational mass \(q\), every fixed tie-breaking rule, and every admissible synchronized dynamic, infinitely many steps satisfy \(W_t\leq C\frac{\log\log m}{\log m}W^*\), or does this uniform welfare bound fail?
The discrete two-bidder construction has an \(O(\log\log m/\log m)\) welfare upper bound at infinitely many steps of every fair best-response dynamic without grand-bundle overbidding. [Discrete welfare bound](https://eprints.lse.ac.uk/106607/2/br_geb.pdf).
No separate result for this exact synchronized mass formulation was located.
The uniform welfare bound holds. In fact, immediately after every activation of bidder \(2\),
\(\displaystyle \frac{W_t}{W^*}\leq \frac{\log_2 k+4}{k}.\)
Since bidder \(2\) is activated infinitely often, this proves the requested conclusion. The proof below makes the real-bid and tie-breaking details explicit and then transfers the bound to arbitrary positive mass.
The underlying subspace argument appears in Section 4.1 of [Dütting and Kesselheim’s paper](https://eprints.lse.ac.uk/106607/2/br_geb.pdf).
Write \(r=\log_2 k\), so \(d=k-r\). Every member of \(\mathcal D\) has the same cardinality
\(\displaystyle N=2^d-1=\frac{2^k}{k}-1.\)
Define
\(\displaystyle H=\rho N=\frac{4(2^k-k)}{2^k-1}.\)
Thus \(0<H<4\), and the definition of \(v_2\) gives \(v_2(T)\leq H\) for every bundle \(T\). Moreover:
We also have \(v_1(M)=k\). Indeed, the \(k\) coordinate vectors define sets covering every nonzero vector, proving \(v_1(M)\leq k\). Conversely, if fewer than \(k\) vectors \(a_1,\ldots,a_s\) defined a cover, the linear map
\(\displaystyle x\longmapsto(a_1\cdot x,\ldots,a_s\cdot x)\)
would have a nonzero kernel vector by rank-nullity. That vector belongs to none of the proposed covering sets, a contradiction.
Allocating all items to bidder \(1\) therefore proves
\(\displaystyle W^*\geq qk.\)
Let \(p_x\geq0\) satisfy \(\sum_{x\in M}p_x\leq k\), and write \(p(D)=\sum_{x\in D}p_x\).
Choose \(D\) uniformly from the finite family \(\mathcal D\). Every nonzero vector has the same inclusion probability: an invertible linear transformation taking one nonzero vector to another induces a bijection of \(\mathcal D\). Since every member has cardinality \(N\), that probability is \(N/m\). Consequently,
\(\displaystyle \mathbb E[p(D)]=\frac{N}{m}\sum_{x\in M}p_x\leq\frac{kN}{m}=\frac H4.\)
Some \(D\in\mathcal D\) therefore satisfies \(p(D)\leq H/4\).
Fix any activation of bidder \(2\), and let \(p_x\) be bidder \(1\)’s unchanged bids. The grand-bundle condition and Section 1 give \(\sum_xp_x\leq k\). Choose a cheap \(D\) as in Section 2.
Consider the following deviation by bidder \(2\): bid \(p_x+\varepsilon\) on every \(x\in D\), and zero elsewhere, where \(\varepsilon>0\).
This deviation wins all of \(D\), regardless of tie-breaking. Outside \(D\), it can win only items with opposing bid zero; any such additional items cost zero. Its winning bundle thus has value \(H\), and its total payment is exactly \(p(D)\). Its utility is at least
\(\displaystyle H-p(D)\geq\frac{3H}{4}>\frac H2.\)
This is an actual finite real-bid deviation. It can even satisfy the grand-bundle bid condition: choosing
\(\displaystyle \varepsilon=\frac{H-p(D)}{2N}>0\)
makes its total bid \((H+p(D))/2<H=v_2(M)\).
Because the prescribed update is an exact best response, its utility is also greater than \(H/2\). If its winning bundle contained no member of \(\mathcal D\), its value would be at most \(H/2\), and its nonnegative payments would make its utility at most \(H/2\). This contradicts optimality.
Therefore, after every activation of bidder \(2\), its winning bundle contains some \(D'\in\mathcal D\).
Write \(D'=U\setminus\{0\}\), where \(\dim U=d\). Under the standard nondegenerate dot product, the orthogonal complement \(U^\perp\) has dimension \(k-d=r\). Choose a basis \(a_1,\ldots,a_r\) of \(U^\perp\).
The common kernel of these linear forms is \((U^\perp)^\perp=U\). Hence every \(x\in M\setminus D'\) satisfies \(a_\ell\cdot x=1\) for at least one index \(\ell\). The sets \(S_{a_1},\ldots,S_{a_r}\) cover \(M\setminus D'\), proving
\(\displaystyle v_1(M\setminus D')\leq r.\)
After the activation considered above, the winning bundles are disjoint and \(D'\subseteq A_2^t\). Thus \(A_1^t\subseteq M\setminus D'\). The cover valuation is monotone, because any cover of a bundle also covers each subset. It follows that
\(\displaystyle v_1(A_1^t)+v_2(A_2^t)\leq r+H<r+4.\)
Copies have separate items and identical synchronized local play. Their welfare therefore scales by the positive factor \(q\), exactly as specified in the question. Multiplying the preceding local bound by \(q\) and using \(W^*\geq qk\) gives
\(\displaystyle \frac{W_t}{W^*}\leq\frac{r+H}{k}<\frac{r+4}{k}.\)
This argument applies after every activation of bidder \(2\), so fairness supplies infinitely many such steps. The factor \(q\) cancels; neither its magnitude nor its binary encoding affects the conclusion.
For an explicit constant, interpret the unsubscripted logarithms as natural logarithms. For \(k\geq4\),
\(\displaystyle \frac{k}{2}\leq\log m<k,\qquad \log\log m\geq\log(k/2)\geq\frac12\log k.\)
Also \(r+4\leq3r=3\log k/\log2\), because \(r\geq2\). Therefore,
\(\displaystyle \frac{r+4}{k}\leq\frac{3}{\log2}\frac{\log k}{k}\leq\frac{6}{\log2}\frac{\log\log m}{\log m}<10\frac{\log\log m}{\log m}.\)
Thus \(C=10\) works for every admissible \(k\geq4\), every positive rational mass, every fixed item tie-breaking rule, and every admissible synchronized dynamic.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned welfare question. It establishes the stronger assertion that immediately after every activation of bidder \(2\),
\[
\frac{W_t}{W^*}<\frac{\log_2 k+4}{k}.
\]
Fairness therefore gives infinitely many qualifying steps. The constant \(C=10\), with natural logarithms, is valid for every admissible \(k\geq4\).
No major or minor mathematical issues were found.
For admissible \(k=2^r\) with \(r\geq2\), the dimension \(d=k-r\) is positive and at most \(k\), so \(\mathcal D\) is nonempty. Its members have cardinality
\[
N=2^d-1=\frac{2^k}{k}-1>0.
\]
The computation
\[
H=\rho N=\frac{4(2^k-k)}{2^k-1}
\]
is correct, and \(0<H<4\).
The definition of \(w_D\) directly gives all the asserted bounds on \(v_2\): its maximum is \(H\), attained whenever the bundle contains a member of \(\mathcal D\); otherwise its value is at most \(H/2\). In particular, \(v_2(M)=H\).
The proof that \(v_1(M)=k\) is complete. The coordinate forms supply a cover of size \(k\). For any proposed cover using fewer than \(k\) forms, rank-nullity supplies a nonzero common kernel vector, which is uncovered. This reasoning does not require the proposed forms to be independent.
Allocating all items to bidder \(1\) is feasible, so \(W^*\geq qk>0\). Dividing by \(W^*\) later is therefore legitimate.
The uniform distribution over \(\mathcal D\) is well-defined because the family is finite and nonempty. Invertible linear transformations preserve its members and act transitively on nonzero vectors. Thus the stated equal inclusion probabilities are justified.
Since every member has size \(N\), the inclusion probability is \(N/m\). Linearity of expectation gives
\[
\mathbb E[p(D)]
=\frac{N}{m}\sum_{x\in M}p_x
\leq\frac{kN}{m}
=\frac H4.
\]
The conclusion that some member satisfies \(p(D)\leq H/4\) follows from this finite average. No independence assumption is needed.
At an activation of bidder \(2\), the opposing bids are nonnegative and sum to at most \(v_1(M)=k\), so the preceding argument applies.
Bidding \(p_x+\varepsilon\) on \(D\) wins every item of \(D\) strictly, independently of tie-breaking. A zero bid outside \(D\) can win only against an opposing zero bid. Any such extra items have zero second-price payment.
Consequently, the deviation has value exactly \(H\), payment exactly \(p(D)\), and utility
\[
H-p(D)\geq\frac{3H}{4}>\frac H2.
\]
These are attained utility values, not limiting values or a supremum argument.
The proposed choice
\[
\varepsilon=\frac{H-p(D)}{2N}
\]
is positive and finite. Its total bid is correctly calculated as
\[
p(D)+N\varepsilon=\frac{H+p(D)}2<H=v_2(M).
\]
Thus the deviation even obeys the grand-bundle bid restriction, although best responses in the task are defined over all nonnegative bids.
Every exact best response must attain at least this deviation’s utility. A bundle containing no member of \(\mathcal D\) has value at most \(H/2\); nonnegative payments cannot increase its utility. Therefore every prescribed best response by bidder \(2\) wins a complete member of \(\mathcal D\).
The proof uses only the exact-best-response property stipulated for the dynamic. No additional existence or bid-selection claim is needed.
For \(D'=U\setminus\{0\}\), the nondegenerate standard dot product gives
\[
\dim U^\perp=k-d=r,
\qquad
(U^\perp)^\perp=U.
\]
The chosen basis vectors of \(U^\perp\) are nonzero, so they index allowed covering sets.
Every item in \(M\setminus D'\) lies outside \(U\), hence fails at least one of the basis kernel conditions. Over \(\mathbb F_2\), that means the corresponding dot product equals \(1\). The stated \(r\) sets therefore cover \(M\setminus D'\).
Disjoint winning bundles and \(D'\subseteq A_2^t\) imply \(A_1^t\subseteq M\setminus D'\). Monotonicity of the cover valuation then yields
\[
v_1(A_1^t)+v_2(A_2^t)\leq r+H<r+4.
\]
This remains valid when bidder \(1\)’s bundle is empty.
Identical local bids and identical fixed tie-breaking give identical local allocations across copies. The specified aggregate welfare is therefore exactly the local welfare multiplied by \(q\).
Combining the local bound with \(W^*\geq qk\) gives the claimed ratio. Positivity of \(q\) justifies cancellation; neither normalization of masses nor integrality of the number of copies is used.
Bidder \(2\)’s infinitely many activations occur at infinitely many integer steps. The proof therefore establishes the required temporal quantifier for every admissible dynamic, regardless of the activation schedule or which exact best response is selected.
All stated logarithmic estimates hold for \(k\geq4\):
\[
\frac{k}{2}\leq\log m<k,
\qquad
\log\log m\geq\log(k/2)\geq\frac12\log k.
\]
Also, \(r+4\leq3r\) holds because \(r\geq2\). Their combination gives the displayed inequality chain, and \(6/\log2<10\). Thus \(C=10\) is justified throughout the claimed range.
The reference to [Dütting and Kesselheim’s paper](https://eprints.lse.ac.uk/106607/2/br_geb.pdf) supplies attribution; the submitted argument establishes the needed facts internally and does not depend on an unstated theorem from that paper.
No clarification or repair is required. The output proves the uniform welfare bound but makes no computational-complexity classification. Accordingly, the required continuous_status is "unresolved" solely for that classification field; the mathematical welfare question is resolved.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.