| paper | The Bakers and Millers Game with Restricted Locations |
| authors | — |
| venue | AAMAS 2025 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.7
statement extracted from the paper’s text layer
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}\).
A high-multiplicity market with baker types \(A\subseteq L\), mass \(\beta_A\), and \(k\) indivisible miller sites \(S\); the objective is covered baker mass \(\sum_{A:A\cap S\ne\varnothing}\beta_A\), with optional assignment variables \(x_{A,\ell}\).
The mirror's substantive optimization remains discrete weighted Maximum \(k\)-Coverage, so continuity contributes coefficient compression rather than a mass-transfer or equilibrium phenomenon; this limits the mirror's scope but does not invalidate it under a population-only continuization.
fatal: False
The mirror covers Theorem 3.7 and its Maximum \(k\)-Coverage reduction; it leaves the full equilibrium construction, Lemma 2.4's harmonic potential, Theorems 3.8–3.9, and the price-of-anarchy and price-of-stability results untreated.
The strongest honest case is a narrow but real yes. The best anchor is Theorem 3.7 (Social Welfare Optimum), proved in this paper. It states that computing a strategy profile of maximum coverage is NP-hard, by reduction from Maximum \(k\)-Coverage. This result has a clean high-multiplicity mirror whose hardness remains for exactly the reason the ChoCo programme expects: the combinatorics live in the locations and access-incidence structure, not in named individuals.
Consider a market with a finite set \(L\) of possible mill locations and many baker-customers. A baker type is an access set \(A\subseteq L\): all bakers of type \(A\) can use exactly the locations in \(A\). Let \(\beta_A\in\mathbb Q_{\ge0}\) be the mass of that type. Thus \(\mathcal A\), the explicit list of distinct access sets, is the type catalogue, while \(\sum_{A\in\mathcal A}\beta_A\) is the baker population. The natural regime is many bakeries or purchasing customers, perhaps millions, distributed over a few dozen or few hundred repeated delivery/access profiles, with \(k\) millers choosing among more locations than they can occupy.
The continuous problem is:
\[ \textsc{Mass-Max-k-Coverage}_{\infty} \]
Given \(L\), \(\mathcal A\), rational masses \((\beta_A)_{A\in\mathcal A}\), and \(k\), choose a set \(S\subseteq L\) with \(|S|\le k\), representing the locations occupied by at least one miller, and a feasible baker-mass assignment \(x=(x_{A,\ell})\) satisfying
\[ x_{A,\ell}\ge0,\qquad x_{A,\ell}=0\ \text{if }\ell\notin A,\qquad \sum_{\ell\in A}x_{A,\ell}=\beta_A. \]
Maximize the covered mass
\[ W_\infty(S,x)= \sum_{A\in\mathcal A}\sum_{\ell\in S}x_{A,\ell}. \]
Equivalently, the optimum value is
\[ \max_{S\subseteq L,\ |S|\le k} \sum_{A:A\cap S\ne\varnothing}\beta_A. \]
This is not an arbitrary weighted reformulation. In the paper’s welfare objective, once the miller locations \(S\) are fixed, every baker type with \(A\cap S\ne\varnothing\) can be assigned to a selected accessible location and is covered; the remaining type mass cannot be covered. Individual baker identities and the exact assignment are therefore redundant in the optimum. The continuous problem keeps the paper’s locations, access restrictions, number of miller sites, and coverage objective intact, while replacing repeated baker individuals by mass.
The reduction in the proof of Theorem 3.7 survives verbatim. Given a Maximum \(k\)-Coverage instance, make one baker type \(A_e\) for each item \(e\), where \(A_e\) is the set of locations corresponding to sets containing \(e\), and assign it mass \(\beta_{A_e}=1\), or any common rational mass. Then the value of \(W_\infty\) is exactly the number, or normalized mass, of covered items. Replacing each type by \(R\) identical clones merely multiplies all masses and leaves the optimizer unchanged. Thus the mirror has exact rational-clone fidelity, and I would classify it as Class B: hardness transfers. The continuous problem is already NP-hard, even though the population is represented by a finite mass distribution.
This is a plausible problem for the authors to recognize as their own. Their reduction itself is really a coverage problem over baker access sets and miller-selected locations. The market interpretation is also natural: a large population of bakeries belongs to repeated geographic or contractual access profiles, while a limited number of mills decide which markets to serve. The obvious follow-up questions are whether the mass problem is fixed-parameter tractable in \(k\), in \(|L|\), or in \(|\mathcal A|\); whether the paper’s greedy argument yields the \(e/(e-1)\) approximation for weighted masses; and how the result changes when locations have capacities or opening costs.
A narrower second anchor is Lemma 2.4 (Potential Function Maximizer), also proved in this paper. It says that, for a fixed miller profile, the baker assignment maximizing
\[ \Phi_{t^*}(s)= \sum_{\ell\in L}M_{t^*}(\ell)H_{B_s(\ell)} \]
can be computed in polynomial time by minimum-cost flow.
Its natural high-multiplicity limit is the following problem. Let \(\beta_A\) be baker-type masses as above, let \(\eta_\ell\) be fixed miller mass at location \(\ell\), and let \(x\) be a feasible mass assignment. Write
\[ B_\ell(x)=\sum_{A:\ell\in A}x_{A,\ell}. \]
For a granularity parameter \(\delta>0\), maximize
\[ \Phi_{\infty,\delta}(x) = \sum_{\ell\in L} \eta_\ell \log\!\left(1+\frac{B_\ell(x)}{\delta}\right) \]
over all feasible \(x\). When \(\delta=1/N\), this is the continuous analogue of the harmonic potential for \(N\) clones: \(H_{NB_\ell}\) and \(\log(1+NB_\ell)\) differ only by the usual bounded asymptotic error. The problem is a separable concave maximization over an explicit flow polytope, so I expect Class A for \(\varepsilon\)-optimization by standard convex programming. An exact bit-complexity result and a combinatorial min-cost-flow analogue are worthwhile further questions.
I would not claim that the paper’s full equilibrium result, Theorem 2.1, transfers directly without qualification. In an atomless game, a single agent has zero effect on the location mass, so ordinary unilateral Nash deviations become Wardrop conditions and can substantially simplify the game. Likewise, I would not claim direct mirrors of Theorems 3.8 or 3.9, or of the price-of-anarchy and price-of-stability results, because their coverage predicate is “at least one miller.” If miller mass is fully divisible, arbitrarily small positive mass can activate arbitrarily many locations, making coverage degenerate unless one retains a discrete site-opening budget or introduces a capacity/threshold model.
That is the weakest point of the positive case: the lead mirror is continuous in the baker population but retains the discrete \(k\)-location resource. It is therefore best described as a direct high-multiplicity mirror of the welfare subproblem, not as a fully atomless two-sided version of the entire game. The reason I still regard it as a strong mirror is that the retained discreteness is precisely where Theorem 3.7’s hardness lives, while the repeated baker population is represented exactly by type masses.
The strongest negative case is that the proponent’s first mirror is not really a new continuous game. In Theorem 3.7, once the selected miller locations \(S\) are fixed, baker identities and assignments disappear: the value is simply \( \sum_{A:A\cap S\ne\varnothing}\beta_A \). The proposed \(x\)-variables are redundant, so the mirror is weighted Maximum \(k\)-Coverage with rational weights. Continuization contributes coefficient compression, but no mass-transfer, equilibrium, or genuinely continuous optimization structure.
The full atomless version is worse. If millers also become divisible mass, the “covered” condition \(M_\ell>0\) allows arbitrarily small miller mass to activate arbitrarily many locations. Coverage then becomes either all-accessible mass or a support-selection problem with no meaningful opening cost. Restoring a limit of \(k\) opened locations requires retaining indivisible millers, discrete facilities, or thresholds—so the strategically interesting part remains discrete. This is a legitimate objection to the proposed full-game mirror, though not to a one-sided high-multiplicity relaxation.
Lemma 2.4 offers a weaker anchor. The harmonic potential depends on the unit size of an individual baker. If \(B_\ell=N b_\ell\), then \(H_{B_\ell}\) approaches \(\log N+\log b_\ell\) only for positive \(b_\ell\); zero-load locations behave differently. The proposed \(\log(1+B_\ell/\delta)\) therefore introduces a hidden granularity parameter \(\delta\). Keeping \(\delta\) gives a family of regularized finite-\(N\) problems; removing it creates boundary and zero-mass conventions absent from the paper. It is not an intrinsic continuum limit of the equilibrium subroutine.
Those points make the case against a full continuous Bakers and Millers Game fairly strong. They do not, however, defeat the first anchor under ChoCo’s stated standard. The access-set interpretation is a perfectly credible high-multiplicity regime: many customers can share geographic or contractual access profiles. Theorem 3.7 is a named computational result, its reduction survives exact cloning, and the resulting weighted problem is a legitimate Class B mirror even though the hardness remains in the discrete locations. The programme explicitly treats such hardness transfer as valuable.
Nor can the fact that the weighted problem is standard be used as a decisive objection: existing high-multiplicity work is supporting evidence, and a dull continuous answer is still an answer. Likewise, retaining \(k\) discrete miller sites is allowed because only the population—not every modelling component—must be continuized.
So the honest negative verdict is limited: the paper does not support a compelling fully atomless equilibrium mirror, and Lemma 2.4’s continuum limit is somewhat artificial. But the universal claim that no worthwhile mirror exists cannot be sustained. Theorem 3.7 supplies a narrow, exact, and defensible high-multiplicity mirror.
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.