d4-conf-wine-2010-0052

The strongest mirror is continuous UFL core existence, grounded in the paper’s strong-equilibrium result for uncapacitated facility location.

The anchor is Corollary 5, proved in this paper using Goemans and Skutella’s result [18] and the paper’s core–equilibrium equivalence: *deciding whether a given UFL strategic game has a strong equilibrium is NP-complete.* The connection matters because the paper also proves that a UFL game has a strong equilibrium exactly when its associated coalitional game has a nonempty core. So a continuous core question follows the same stability question the authors study, rather than borrowing UFL merely as a convenient optimization problem.

For the mirror, let \(F\) be facilities and \(T\) the supported terminal types. A type \(t\) is a complete connection-cost vector \((d_{tf})_{f\in F}\): agents of that type have the same costs to every facility. The population has scale \(N\), type proportions \(\mu_t\), and masses \(w_t=N\mu_t\). This describes, for example, a large population of customers with a modest number of distinct travel-cost profiles to service locations.

Opening facility \(f\) costs \(a_f\). A feasible service plan chooses binary \(y_f\) and assigns mass \(x_{tf}\) so that \(\sum_f x_{tf}=w_t\) and \(x_{tf}\le w_t y_f\). Its cost is \(\sum_f a_f y_f+\sum_{t,f}d_{tf}x_{tf}\). Each person still uses one facility; only the type-level average assignment \(x\) can be fractional.

Here is the continuous question I would hand to a prover: given these rational data, does there exist a stable per-unit cost allocation? A solution is a vector of type prices \(\pi_t\) such that the grand population pays exactly its minimum service cost, and no subpopulation would pay more by arranging service on its own. Formally, for every mass vector \(q\) with \(0\le q_t\le w_t\), let \(c(q)\) be the minimum facility-opening and connection cost for serving that subpopulation. The required conditions are \(\sum_t w_t\pi_t=c(w)\) and \(\sum_t q_t\pi_t\le c(q)\) for every \(q\). Since members of a type are interchangeable, type-uniform prices are the natural certificate; averaging equivalent members’ shares is the continuous counterpart of symmetrizing a finite core allocation.

These infinitely many coalition inequalities have a finite description, though potentially an exponential one. For each facility set \(S\), let \(d_t(S)=\min_{f\in S}d_{tf}\) for types \(S\) can serve. The core conditions are equivalent to requiring \(\sum_t w_t[\pi_t-d_t(S)]_+\le\sum_{f\in S}a_f\) for every such \(S\). This makes the computational question concrete: find feasible prices, or show none exist, while the separation task searches over facility sets.

I expect hardness to transfer for this precise core-existence problem. The hard choices in UFL include which facilities to open and how opening costs trade off against the whole connection-cost matrix; they are not just about having many separately named terminals. There is also a direct high-multiplicity reduction. Starting from a finite UFL instance with \(n\) terminals, make each terminal’s cost vector one type of mass \(n\), and multiply every facility opening cost by \(n\). The resulting population has \(N=n^2\) units and only \(\tau=n\) types. A finite core allocation gives the same per-unit prices in the continuous instance. For any facility set \(S\), the subpopulation that most challenges its core inequality consists of all \(n\) units of each type with \(\pi_t>d_t(S)\); the original finite core inequality for that subset gives the required scaled bound. Conversely, testing continuous coalitions that take all \(n\) units of each type in a chosen subset recovers every finite core inequality. Grand costs scale by \(n\) as well. Thus core existence is preserved, and Corollary 5’s hardness transfers to this continuous core problem. The paper’s finite UFL equivalence then explains why this is a faithful mirror of its equilibrium-existence result.

My weakest point is the bridge from the core to the strategic game. The paper proves that bridge for its finite UFL games; it does not prove that every continuous core allocation can be implemented as a measurable resource-by-resource strong equilibrium against all positive-mass coalitions. That equivalence is a natural follow-up theorem, not something I would assume. The reduction also scales facility opening costs with population size, which is less natural for some service settings than for infrastructure whose cost grows with the market it serves. Those caveats limit the claim to this UFL cost-sharing regime, not the paper’s other games. They do not undermine the continuous core question itself: it has a clear population interpretation, a precise stability certificate, and an exact hardness-preserving high-multiplicity construction.