| paper | d4-conf-wine-2014-0014 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\). The exact least-core value is \(\epsilon^*=\Theta/W(\mu)-1\), attained by \(p_i^*=y_i^*/W(\mu)\), where \(y^*\) is any optimal dual solution for the grand-coalition matching linear program. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 2 [1]
statement extracted from the paper’s text layer
Given \(\tau\) types with rational masses \(\mu_t\) summing to \(1\), nonnegative rational matching weights \(w_{ij}\), and a threshold \(\Theta\), let a coalition have masses \(q_t\in[0,\mu_t]\) and matching value \(W(q)=\max\sum_{i\le j}w_{ij}z_{ij}\), subject to \(2z_{ii}+\sum_{j\ne i}z_{ij}\le q_i\) and \(z_{ij}\ge0\). Its worth is \(1\) when \(W(q)\ge\Theta\), and \(0\) otherwise. For instances whose grand population reaches the threshold and whose core is empty, compute the least-core value and an allocation \(p_t\ge0\) satisfying \(\sum_t\mu_t p_t=1\) and maximizing \(\epsilon\) subject to \(\sum_t q_t p_t\ge v(q)+\epsilon\) for every \(q\in[0,\mu]\).
A continuum of interchangeable agents grouped into \(\tau\) types, with type mass \(\mu_t\), type-pair matching values \(w_{ij}\), and coalition matching represented by fractional pair masses \(z_{ij}\). The decision is a per-agent payoff rate \(p_t\); the objective is to maximize the least coalition excess over all mass vectors \(q\).
The mirror covers the least-core part of Proposition 2 [1] for a structured weighted regime; it does not cover the nucleolus part or the paper's own algorithmic results for unweighted TCMGs.
The strongest mirror I see is for the least-core part of Proposition 2 [1]. The paper states that, when the core is empty, computing the least-core and the nucleolus of a threshold matching game on an edge-weighted graph is NP-hard. It cites this result from Aziz, Brandt, and Harrenstein; it is not proved in this paper. I would mirror the least-core component of that result, not claim a continuous nucleolus without first defining one.
Call the proposed problem Weighted Threshold-Matching Population Least Core. Its input is a finite set of \(\tau\) agent types, rational masses \(\mu_t\ge 0\) summing to \(1\), a nonnegative rational matching weight \(w_{ij}\) for each compatible pair of types, and a threshold \(\Theta>0\). The grand population must be able to meet the threshold. A type describes everything relevant to matching: any two members of types \(i,j\) have the same matching weight \(w_{ij}\). There are many agents, but relatively few types.
A coalition is specified by masses \(q_t\in[0,\mu_t]\): it may include any fraction of each type. Its maximum matching weight is the value of this fractional matching LP:
\[ W(q)=\max \sum_{i\le j} w_{ij}z_{ij}, \qquad 2z_{ii}+\sum_{j\ne i}z_{ij}\le q_i, \qquad z_{ij}\ge 0. \]
Here \(z_{ij}\) is the mass of pairs matched across types \(i,j\); a same-type pair consumes two units of that type’s mass. The coalition’s worth is \(v(q)=1\) if \(W(q)\ge\Theta\), and \(0\) otherwise. An allocation is a vector of per-agent payoff rates \(p_t\ge0\), with \(\sum_t\mu_t p_t=1\). The question is to compute the least-core value and an allocation attaining it:
\[ \epsilon^*=\max_{p,\epsilon}\ \epsilon \quad\text{subject to}\quad \sum_t\mu_t p_t=1,\quad p_t\ge0,\quad \sum_t q_t p_t\ge v(q)+\epsilon \ \text{for every }q\in[0,\mu]. \]
For direct comparison with Proposition 2, one can restrict the input to instances with empty core.
I expect this problem to be tractable, in Class A, in \(\operatorname{poly}(\tau,L)\), where \(L\) is the input bit length. For \(\epsilon\le0\), losing coalitions satisfy the constraint automatically. To separate the winning-coalition constraints for a candidate \(p\), minimize the payout of a coalition capable of reaching the threshold. If \(d_i(z)=2z_{ii}+\sum_{j\ne i}z_{ij}\), this is the LP
\[ \min_{z\ge0}\ \sum_i p_i d_i(z) \quad\text{subject to}\quad \sum_{i\le j}w_{ij}z_{ij}\ge\Theta,\qquad d_i(z)\le\mu_i. \]
Its optimum is the least payout of any winning coalition: unused members cannot help it win and have nonnegative payoffs. A value below \(1+\epsilon\) gives a violated constraint; otherwise there is no violation. This gives an LP separation oracle with \(O(\tau^2)\) matching variables, so the ellipsoid method can optimize the least core. The fractional matching is natural here because mass can be divided among partners, just as the finite matching model allows each individual to be matched at most once.
The setting is a large market or consortium in which a coalition receives a fixed surplus once it can assemble enough weighted, disjoint partnerships. Members share a type when their compatibility and matching value with every other type are the same. That is a plausible high-multiplicity regime: the number of participants can be enormous while the number of matching types stays moderate. It preserves the paper’s underlying question—how to allocate a coalition’s surplus so that subcoalitions have less incentive to leave—while replacing individual vertices by type masses. I think the authors would recognize it as a high-multiplicity form of their weighted threshold matching game.
The main weakness is that Proposition 2 concerns arbitrary finite weighted graphs. Its hardness may rely on individual, irregular edge weights or other combinatorial features excluded by a small type set with uniform pair values. So this would test whether that hardness survives in a sensible high-multiplicity regime; it would not establish that it does. Exact comparisons at the threshold also need care when relating fractional masses to finite replicated populations, because rounding can change whether a coalition wins. Finally, the paper’s nucleolus result has no equally direct mirror here: its definition lexicographically orders finitely many coalition excesses, whereas the continuous model has uncountably many coalitions. The case is therefore deliberately narrow: it covers the least-core side of Proposition 2, where the mass-matching separation question is precise and plausibly amenable to continuous optimization.
The strongest objection is that Proposition 2 concerns arbitrary weighted graphs, where each vertex can have a distinct pattern of matching relationships. A society with a small number of types and type-pair weights is much narrower: its finite graphs are structured blow-ups, and the result would not explain the hardness of the general case.
That narrows the claim, but it does not defeat the mirror. A plausible regime is a large bipartite labor market with a small number of worker and employer types, where match value depends on the two types. The population can be represented by type masses; a coalition’s ability to reach a surplus threshold is a fractional matching question; and the least core still asks how to allocate that surplus to limit coalition departures. With rational masses, replication can recover finite markets, and bipartiteness gives a particularly clean bridge between mass flows and finite matchings. Identity-specific relationships are absent by construction because members of a type are interchangeable for the game.
So I cannot make the negative case the prompt calls for. The proponent has a well-posed, recognizable continuous-population version of the least-core problem. That it covers a structured regime rather than all weighted graphs is a limitation on scope, not a reason the question is unworthy. The anchor survives; the honest negative case is weak.
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.