Answer: \(\mathrm{P}\)
Theorem 3.7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing the social welfare optimum is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite location set \(L\), an integer \(k\), and a finite catalogue \(\mathcal A\) of baker access-set types with rational masses \(\beta_A\ge0\) satisfying \(\sum_{A\in\mathcal A}\beta_A=1\), choose \(S\subseteq L\) with \(|S|\le k\) and maximize \(\sum_{A:A\cap S\ne\varnothing}\beta_A\), equivalently the mass assignable to selected locations via feasible variables \(x_{A,\ell}\).
Definitions. An instance has finite \(L\), baker types \(r\) of rational mass \(\beta_r>0\) and feasible sets \(A_r\subseteq L\), unrestricted miller mass \(M>0\), and rational \(K\). A feasible allocation satisfies \(x_{r\ell}\ge0\), \(x_{r\ell}=0\) for \(\ell\notin A_r\), \(\sum_{\ell\in A_r}x_{r\ell}=\beta_r\), \(y_\ell\ge0\), and \(\sum_{\ell\in L}y_\ell=M\); write \(B_\ell=\sum_r x_{r\ell}\).
At \(\ell\), baker and miller payoffs are respectively \(y_\ell/B_\ell\) and \(B_\ell/y_\ell\), with payoff \(+\infty\) for zero same-side mass and positive opposite-side mass, and payoff \(0\) at an empty location or with zero opposite-side mass. A Wardrop equilibrium is a feasible allocation such that every location receiving positive mass of a type maximizes that type's payoff among that type's feasible locations. Its coverage is \(W_\infty(x,y)=\sum_{r,\,\ell:y_\ell>0}x_{r\ell}\).
Target. Is deciding whether a Wardrop equilibrium with \(W_\infty(x,y)\ge K\) exists in \(\mathrm{P}\), or is it NP-hard?
Nearest known results. In the discrete restricted-location Bakers and Millers Game, computing a pure Nash equilibrium of maximum coverage is NP-hard. No result for the nonatomic mass version above is assumed.
Let \(R\) denote the finite set of baker types, and define the total baker mass
\[ T=\sum_{r\in R}\beta_r. \]
First assume \(T>0\) and \(A_r\neq\varnothing\) for every \(r\), so feasible allocations exist.
For every Wardrop equilibrium \((x,y)\) and every location \(\ell\),
\[ B_\ell>0\quad\Longleftrightarrow\quad y_\ell>0. \]
Suppose first that \(B_\ell>0\) but \(y_\ell=0\). A miller moving to \(\ell\) would obtain payoff \(+\infty\).
Since \(\sum_j y_j=M>0\), some location \(j\) satisfies \(y_j>0\). The miller payoff at \(j\) is finite: it is \(B_j/y_j\) if \(B_j>0\), and \(0\) if \(B_j=0\). Thus \(j\) cannot maximize the miller payoff, contradicting the Wardrop condition for the positive miller mass at \(j\). Hence \(B_\ell>0\) implies \(y_\ell>0\).
Conversely, suppose \(y_\ell>0\) but \(B_\ell=0\). The miller payoff at \(\ell\) is \(0\). Because \(T>0\), some location \(h\) has \(B_h>0\). By the first implication, \(y_h>0\), so the miller payoff at \(h\) is \(B_h/y_h>0\). Therefore \(\ell\) is not payoff-maximizing, again contradicting the Wardrop condition. Thus \(y_\ell>0\) implies \(B_\ell>0\). \(\square\)
At every Wardrop equilibrium,
\[ y_\ell=\frac{M}{T}B_\ell \]
for every \(\ell\in L\).
Let \(S=\{\ell:B_\ell>0\}=\{\ell:y_\ell>0\}\), where equality follows from Lemma 1.
All locations in \(S\) receive positive miller mass. Hence the miller Wardrop condition implies that their payoffs are equal to a common value \(q>0\):
\[ \frac{B_\ell}{y_\ell}=q \]
for every \(\ell\in S\). Consequently \(B_\ell=qy_\ell\) on \(S\). Summing and using feasibility gives
\[ T=\sum_{\ell\in L}B_\ell =q\sum_{\ell\in L}y_\ell =qM. \]
Thus \(q=T/M\), and therefore \(y_\ell=(M/T)B_\ell\) on \(S\). Both sides are zero outside \(S\), proving the assertion everywhere. \(\square\)
Let \(x\) be any feasible baker allocation, with aggregate masses \(B_\ell\). Define
\[ y_\ell=\frac{M}{T}B_\ell. \]
Then \((x,y)\) is a Wardrop equilibrium.
The miller allocation is feasible because
\[ \sum_{\ell\in L}y_\ell =\frac{M}{T}\sum_{\ell\in L}B_\ell =M. \]
At every occupied location \(B_\ell>0\), both sides are positive and the payoffs are
\[ \frac{y_\ell}{B_\ell}=\frac{M}{T}, \qquad \frac{B_\ell}{y_\ell}=\frac{T}{M}. \]
At every unoccupied location, \(B_\ell=y_\ell=0\), so both payoffs are \(0\).
Every baker uses only occupied locations and therefore receives the positive payoff \(M/T\). Any other feasible location has either the same payoff \(M/T\), if occupied, or payoff \(0\), if empty. Hence every used location maximizes that baker type’s payoff.
Similarly, every miller uses a location with payoff \(T/M>0\), while every empty location offers payoff \(0\). Thus the miller Wardrop condition also holds. \(\square\)
Every Wardrop equilibrium has coverage exactly
\[ W_\infty(x,y)=T. \]
By Lemma 1, every location with positive baker mass has positive miller mass. Therefore
\[ W_\infty(x,y) =\sum_{\ell:y_\ell>0}B_\ell =\sum_{\ell\in L}B_\ell =T. \]
Existence follows from Lemma 3. For example, choose one location \(a_r\in A_r\) for each baker type, put all mass \(\beta_r\) at \(a_r\), and set \(y_\ell=(M/T)B_\ell\). \(\square\)
For a valid instance with \(T>0\) and all \(A_r\neq\varnothing\), the answer is therefore “yes” exactly when
\[ K\leq T=\sum_r\beta_r. \]
Computing \(T\) and comparing two binary-encoded rationals takes polynomial time. The displayed equilibrium construction also uses rational numbers of polynomial encoding length.
If some \(A_r=\varnothing\), no feasible allocation exists, so the answer is “no.” If there are no baker types, then \(T=0\); provided \(L\neq\varnothing\), any feasible miller allocation is an equilibrium of coverage \(0\), so the answer is “yes” exactly when \(K\leq0\).
Thus the problem is polynomial-time solvable. The discrete maximum-coverage hardness disappears because the miller mass can split proportionally across every baker-occupied location, while the infinite-payoff convention prevents an equilibrium from leaving any positive baker mass uncovered.
⟨structured verdict parsed — rendered above⟩
The prover’s central argument is correct. For every nondegenerate feasible instance with positive baker mass, the equilibrium supports must coincide, miller mass must be proportional to baker mass, and consequently every equilibrium has full coverage equal to the total baker mass \(T\). This yields a polynomial-time decision rule.
There is one minor omission: the decision algorithm does not explicitly handle the case where there are no baker types and \(L=\varnothing\). Since \(M>0\), no feasible miller allocation exists in that case, so the answer must be “no.” This is a routine edge-case repair and does not undermine the polynomial-time classification.
The proof first treats \(T>0\) with every \(A_r\neq\varnothing\). Under these assumptions, a feasible baker allocation exists. Because \(T>0\), there is at least one baker type, and a nonempty feasible set for that type also implies \(L\neq\varnothing\), so a feasible miller allocation can be constructed.
This reduction is valid.
For the implication \(B_\ell>0\Rightarrow y_\ell>0\):
This correctly contradicts the Wardrop condition.
For the reverse implication \(y_\ell>0\Rightarrow B_\ell>0\):
This is also correct. The use of the first implication inside the reverse implication is logically sound.
The common support \(S\) is nonempty because \(T>0\). Every location in \(S\) receives positive miller mass, so the Wardrop condition makes every such location a global payoff maximizer. Their payoffs must therefore equal a common finite positive value \(q\).
The calculation
\[ T=\sum_{\ell}B_\ell=q\sum_{\ell}y_\ell=qM \]
is correct because both \(B_\ell\) and \(y_\ell\) vanish outside \(S\). It follows that \(q=T/M\) and \(y_\ell=(M/T)B_\ell\). The conclusion outside \(S\) follows because both quantities are zero there.
No gap is present.
For any feasible baker allocation, the proposed miller allocation is nonnegative and satisfies
\[ \sum_\ell y_\ell=\frac{M}{T}\sum_\ell B_\ell=M. \]
At every location with \(B_\ell>0\), both sides are positive and their payoffs are respectively \(M/T\) and \(T/M\). At every location with \(B_\ell=0\), the construction gives \(y_\ell=0\), so both payoffs are \(0\).
Every location used by a baker type necessarily has positive aggregate baker mass and therefore gives payoff \(M/T>0\). Every other feasible location gives either the same payoff or \(0\). Thus the baker Wardrop condition holds.
Likewise, every location used by millers gives payoff \(T/M>0\), while every unused location gives \(0\). The unrestricted miller Wardrop condition therefore holds.
The lemma is correct.
By Lemma 1, every location with positive baker mass has positive miller mass. Therefore
\[ W_\infty(x,y) =\sum_{\ell:y_\ell>0}B_\ell =\sum_{\ell\in L}B_\ell =T. \]
The first equality is exactly the definition of coverage after summing over baker types, and the second uses support coincidence. The equilibrium construction is valid because every \(A_r\) is nonempty.
Thus all equilibria in the positive-baker-mass case have full coverage.
The criterion \(K\leq T\) is correct for feasible instances with \(T>0\). Summing and comparing binary-encoded rationals is polynomial-time. The constructed rational masses also have polynomial encoding length: rational addition and multiplication increase bit length by at most a polynomial amount over finitely many input rationals.
If some positive-mass baker type has \(A_r=\varnothing\), no feasible allocation exists, so returning “no” is correct.
If there are no baker types and \(L\neq\varnothing\), the claim is also correct:
The only omitted branch is \(T=0\) and \(L=\varnothing\). Because \(M>0\), the constraint \(\sum_{\ell\in L}y_\ell=M\) is impossible, so the answer is “no.” The write-up says only “provided \(L\neq\varnothing\)” and never states the complementary decision.
Add one sentence to the edge-case discussion:
If there are no baker types and \(L=\varnothing\), no feasible allocation exists because \(M>0\), so the answer is “no.”
No new mathematical argument is otherwise required.
⟨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.