| paper | The stable fixtures problem with payments |
| authors | P. Biró, W. Kern, D. Paulusma, Péter Wojuteczky |
| venue | GEB 2018 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: Polynomial-time solvable in \(m,\tau,L\), with exact rational separation certificates supported on at most two types whenever a coalition inequality fails. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 13
statement extracted from the paper’s text layer
Given a finite bipartite type graph \(H=(T_L\cup T_R,F)\), rational masses \(\mu_t\ge0\) with \(\sum_t\mu_t=1\), and rational per-agent allocations \(q_t\), decide whether \(q\) is in the continuous core: \(\sum_t\mu_tq_t=V(\mu)\) and \(\sum_tz_tq_t\ge V(z)\) for every \(0\le z\le\mu\), where \(V(z)\) is the maximum \(\sum_{(t,u)\in F}x_{tu}\) subject to \(\sum_u x_{tu}\le3z_t\), \(\sum_t x_{tu}\le3z_u\), and \(x_{tu}\ge0\); if not, output a violating \(z\) and feasible \(x\).
A nonatomic high-multiplicity bipartite matching game in which type \(t\) carries mass \(\mu_t\), each unit has three contract slots, \(x_{tu}\) is matched mass, and separation maximizes \(\sum_{(t,u)\in F}x_{tu}-\sum_tq_tz_t\) over \(0\le z\le\mu\) and the capacitated-flow constraints.
It mirrors Theorem 13’s co-NP-complete core-membership result for \(b\equiv3\), \(w\equiv1\), and bipartite graphs, while leaving the stable-fixture algorithms, structural characterizations, lattice results, and other cooperative-game questions unmirrored.
The strongest honest positive case is a single anchor: Theorem 13, and its continuous analogue is likely Class A.
Theorem 13, proved in this paper (with the Cubic Subgraph hardness source cited from Plesník [38]), states that deciding whether an allocation belongs to the core of a multiple partners assignment game is co-NP-complete even when the underlying graph is bipartite, every vertex capacity is \(b(i)=3\), and every edge has weight \(w(e)=1\). More precisely, for a bipartite graph \(G=(N,E)\), define \(v(S)\) as the maximum weight \(3\)-matching in the subgraph \(G[S]\). Given an allocation \(p\) with \(p(N)=v(N)\), the question is whether \(p(S)\ge v(S)\) for every coalition \(S\subseteq N\). The theorem says that this core-membership problem is co-NP-complete. The hardness proof reduces from Cubic Subgraph and constructs, around each original vertex, a \(K_{3,3}\)-type gadget.
My lead mirror would be:
Continuous 3-Capacity Core Membership. The population consists of finitely many seller and buyer types \(T=L\cup R\), with rational masses \(\mu_t\ge0\) satisfying \(\sum_t\mu_t=1\). A type includes its side and its compatibility neighbourhood; agents of types \(t\in L\) and \(u\in R\) can form a unit-value coalition exactly when \((t,u)\) belongs to a given type graph \(H\). Every agent can participate in at most three coalitions. The input also contains a rational per-capita allocation \(q_t\) for each type.
A coalition is now a mass vector \(z\), with \(0\le z_t\le\mu_t\). Its value is the maximum mass of compatible contracts:
\[ V(z)=\max\left\{\sum_{(t,u)\in E(H)}x_{tu}: \sum_u x_{tu}\le 3z_t,\ \sum_t x_{tu}\le 3z_u,\ x_{tu}\ge0\right\}. \]
The question is whether \(q\) is in the continuous core: whether \(\sum_t\mu_tq_t=V(\mu)\) and \(\sum_tz_tq_t\ge V(z)\) for every coalition mass vector \(z\). If not, a solution is a violating coalition \(z\), together with a feasible mass matching \(x\) such that \(\sum_tz_tq_t<V(z)\).
This is a genuine population continuization. The population is the continuous object; \(x_{tu}\) records how much mass of one type contracts with another. The value \(3z_t\) is the per-capita capacity scaling forced by replacing \(n_t\) named agents with mass \(\mu_t\). The model is not merely using fractional outcomes while retaining a finite society.
The separation problem has a direct LP formulation. After checking grand-coalition efficiency, maximize
\[ \Delta(\mu,q)= \max\left\{ \sum_{(t,u)\in E(H)}x_{tu}-\sum_tq_tz_t: \sum_u x_{tu}\le3z_t,\ \sum_t x_{tu}\le3z_u,\ 0\le z_t\le\mu_t,\ x_{tu}\ge0 \right\}. \]
The allocation is in the continuous core exactly when \(\Delta(\mu,q)\le0\). Thus the mirror is polynomial-time solvable by one rational LP of size polynomial in the number of types and compatibility pairs. The expected classification is therefore Class A: the discrete co-NP-hardness disappears because a coalition can select arbitrary fractions of each repeated type, and its best deviation becomes a flow problem rather than an integral subgraph problem.
The high-multiplicity bridge is concrete. If \(n_t\) named agents share type \(t\), set \(\mu_t=n_t/n\). A coalition containing \(k_t\) agents corresponds to \(z_t=k_t/n\). Under sufficiently large replication, the mass-flow constraints are exactly the normalized \(3\)-matching constraints: the extra restriction that two named agents cannot use the same edge becomes irrelevant once each type contains many interchangeable agents. Conversely, any rational violating mass vector can be scaled to a finite replicated market, and bipartite matching integrality turns its rational flow into a discrete matching. This gives a meaningful two-way dictionary rather than a purely verbal analogy.
The regime is plausible in the paper’s own market language: a large two-sided contracting or course-allocation market with many sellers and buyers in finitely many qualification classes, each with three identical service slots or purchasing slots. Compatibility and unit surplus depend on type, not identity. The paper already interprets multiple partners assignment games through sellers, buyers, identical objects, capacities, and core allocations, so the authors should recognize this as their problem with repeated agents aggregated into masses.
The scope is deliberately narrow: I am mirroring Theorem 13’s core-membership result, not claiming to continuize every result about stable fixtures, competitive equilibria, or the nucleolus. That one result is enough: it asks whether a supplied allocation withstands every coalition, and the continuous version asks exactly the same question over measurable mass coalitions.
The weakest point is that Theorem 13 allows a coalition to choose an integral subset of named vertices, whereas my mirror allows a fraction of a type to defect. That is precisely the high-multiplicity assumption, but it is still a substantive modelling choice. If the application requires entire cohorts to move together, or if every vertex in the hardness gadget has a unique compatibility signature, the discrete hardness may survive and the mirror becomes much less useful. The right follow-up is therefore to locate the boundary: which cohort-indivisibility, type-pair capacity, or non-bipartite restrictions restore co-NP-hardness, and what finite-population rounding guarantees relate the LP answer back to the original core-membership problem?
The strongest negative argument is that the proposed mirror silently changes the game. Theorem 13 concerns an arbitrary graph of individually specified players. Its hardness depends on selecting an integral vertex subset and then finding a matching in the induced subgraph. Replacing each vertex by a mass of clones with identical neighbourhoods turns the graph into a complete type-level blow-up. The resulting value function is not the original \(v(S)\) with notation changed; it is a new nonatomic assignment game in which coalitions may split every type fractionally.
That objection is real, but it does not defeat the mirror under the programme’s rules. A type is allowed to include the whole compatibility neighbourhood and allocation, and the paper’s own seller–buyer interpretation explicitly supplies a plausible high-multiplicity regime: many interchangeable sellers and buyers in finitely many qualification classes, each with three identical slots. In that regime, complete blow-up is not an arbitrary mathematical repair; it is the natural high-multiplicity model. The fact that the original soccer-team story is identity-sensitive is irrelevant once the market interpretation is used.
The finite-to-continuous dictionary is also imperfect at small population sizes. In a simple graph, two particular agents cannot form multiple copies of the same edge, whereas the mass-flow formulation permits up to \(3z_t\) units between type pairs. But this restriction disappears under replication once every positive-mass type contains sufficiently many agents, and rational mass flows can then be implemented by integral \(b\)-matchings after scaling. That is exactly the sort of high-multiplicity asymptotic bridge the programme is meant to study, not a fatal mismatch.
A second negative line is that the proposed separation LP is almost immediate: it jointly chooses a coalition mass \(z\) and a capacitated flow \(x\). One might say that this produces a generic flow exercise rather than a substantive continuation of the paper’s core theory. But that is not an admissible objection here. The discrete theorem is co-NP-complete, the continuous question is computationally distinct, and a clean Class A result obtained by replacing integral coalition structure with mass flow is precisely a worthwhile continuization.
The only defensible reservation is that the mirror studies a restricted, type-homogeneous market rather than the paper’s full arbitrary-player model. That affects how broadly the result should be advertised, but not whether the question is meaningful. Since Theorem 13 is a named computational result and admits a credible high-multiplicity interpretation, I cannot honestly defeat this anchor. The universal “no worthwhile mirror in any scenario” case is therefore weak; this paper has at least one strong continuous 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.