| paper | d4-conf-atal-2010-0069 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the problem belongs to \(\mathrm P\), with running time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 8
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), a weighted undirected compatibility graph on types, a threshold \(q\), nonnegative type payoff rates \(r_t\) with \(\sum_{t\in T}\mu_t r_t=1\), and \(\varepsilon\geq 0\), decide whether every coalition mass vector \(x\) with \(0\leq x_t\leq\mu_t\) satisfies \(\sum_{t\in T}r_t x_t\geq v_q(x)-\varepsilon\). Here \(v_q(x)=1\) exactly when a matching flow using mass from coalition \(x\) reaches value at least \(q\), with a same-type pair consuming two units of that type; otherwise \(v_q(x)=0\).
A society has rational mass \(\mu_t\) in each compatibility and payoff type \(t\). For a coalition mass vector \(x\), matching variables \(z_e\geq 0\) obey the type supply constraints, with same-type edges consuming two units, and the coalition wins if \(\sum_e w_e z_e\geq q\) is attainable. Minimize \(\sum_t r_t x_t\) over winning coalition masses and compare the minimum with \(1-\varepsilon\); this is a linear program.
Cloning the reduction's endpoint types creates complete-bipartite compatibility blocks, allowing matchings absent from its one-edge-per-item graph; this prevents treating the mirror as a literal limit of that reduction.
fatal: False
Covers Proposition 8's \(\textsc{IN-}\varepsilon\textsc{-CORE}\) question for threshold matching games with repeated compatibility types; leaves the paper's length results and its other solution concepts and game classes outside this mirror.
My strongest positive case is Continuous Threshold-Matching \(\varepsilon\)-Core Membership, a mirror of Proposition 8.
Proposition 8, proved in this paper, states that deciding \(\textsc{IN-}\varepsilon\textsc{-CORE}\) is NP-hard for threshold matching games. In this problem, the input includes a weighted graph, a matching-value threshold, a payoff vector and \(\varepsilon\); the question is whether every coalition’s payoff is at least its game value minus \(\varepsilon\). The paper proves hardness via minimum knapsack: for item weights \(w_i\), costs \(p_i\), and demand \(d\), it builds a threshold matching game on \(2n\) vertices with one disjoint edge of weight \(w_i\) per item. Each endpoint of that edge receives payoff \(p_i/(2P)\), where \(P=\sum_i p_i\). The minimum cost of a set of items reaching demand determines the worst excess, and an \(\textsc{IN-}\varepsilon\textsc{-CORE}\) oracle would recover that value.
Here is the continuous problem I would hand to a prover. The instance is a finite set \(T\) of agent types, rational masses \(\mu_t\geq 0\) summing to \(1\), a weighted compatibility graph \(H=(T,E)\), a threshold \(q\), and a nonnegative per-capita payoff rate \(r_t\) for each type, with \(\sum_t\mu_t r_t=1\). Assume the grand coalition can reach the threshold. A coalition is a mass vector \(x\) with \(0\leq x_t\leq\mu_t\). Let \(z_e\) be the mass of pairs formed along compatibility edge \(e\), and let \(w_e\) be that edge’s value. Its matching value is the maximum of \(\sum_e w_e z_e\) subject to each type supplying no more matched mass than it contains; a same-type pair consumes two units of that type’s mass. The coalition’s threshold-game value is \(1\) if its matching value is at least \(q\), and \(0\) otherwise. The question is whether the payoff rates are in the continuous \(\varepsilon\)-core: does every coalition satisfy
\[
\sum_{t\in T} r_t x_t \geq v_q(x)-\varepsilon?
\]
A solution is yes or no; on a no instance, it can include a violating coalition mass vector.
This membership question reduces to one LP: minimize \(\sum_t r_t x_t\), subject to \(0\leq x_t\leq\mu_t\), nonnegative matching masses \(z_e\), the type-capacity constraints, and \(\sum_e w_ez_e\geq q\). Compare the optimum with \(1-\varepsilon\). Because payoff rates are nonnegative, losing coalitions satisfy the core inequality automatically; the LP finds the least-paid winning coalition. The problem is therefore tractable in the number of types, compatibility edges, and input bit length.
The regime is a large matching market with repeated cohorts: for example, many workers or contractors sharing the same compatibility and contract-value profiles, with a coalition’s value determined by the best set of pairings it can support. The type records all the information the problem uses, including compatibility, edge values, and payoff rate. A market might have millions of agents but only hundreds or thousands of such profiles. This is a recognizable threshold matching game, with mass replacing individual membership and type-level matching flows replacing discrete pairings. In the paper’s knapsack construction, cloning the endpoints of each item edge gives this kind of repeated cohort; fractional mass then allows a fraction of an item’s two endpoint populations to be matched.
I expect this mirror to be Class A. It preserves the threshold, matching value, and core-membership question. The discrete reduction’s item-by-item inclusion choice becomes fractional selection of matched mass, so the minimum winning-coalition payment is an LP. This is a specific high-multiplicity version of the authors’ underlying problem, not a claim that the whole paper continuizes: the other length, least-core, and cost-of-stability results are outside this mirror.
The weakest point is that the mirror describes populations with repeated compatibility profiles, so it does not represent every arbitrary graph in which every vertex has a unique neighborhood. It also permits splitting mass among partners, as a continuum model should. I think the authors could accept it because the game and the \(\varepsilon\)-core test remain intact, the types include every relevant attribute, and Proposition 8’s own disjoint-edge construction has a natural repeated-cohort version.
Proposition 8 is a genuine computational result, so the negative case cannot dismiss this paper for lack of an anchor. Its \(\textsc{IN-}\varepsilon\textsc{-CORE}\) question has a clear continuous counterpart: find the least-paid winning coalition of mass, then compare its payment with \(1-\varepsilon\). For type-based matching, that is an LP.
The strongest objection is fidelity to the paper’s matching games. In the Proposition 8 reduction, each item is represented by one designated edge between two individual players. Cloning those endpoints does not preserve the original graph if each clone can match any member of the opposite type: that creates complete bipartite compatibility, so some coalitions gain matches they could not form in the disjoint-edge construction. Preserving the designated pairings would require types that encode partner identities, undermining the repeated-type regime. Thus the proponent’s model does not continuously mirror every threshold matching game in the paper.
That objection narrows the mirror, but it does not defeat the better version. A matching market with repeated worker and employer profiles, uniform compatibility and value between profiles, and type-level payoff rates is a natural instance regime. Its mass matching flows capture the coalition’s attainable value; scaling the threshold and payoffs per capita gives the model consistent units. The authors could reasonably recognize this as a continuous threshold matching game, even though it does not preserve every coalition value in the paper’s disjoint-edge reduction. The LP result is also not a reason to reject the question: tractability after continuization is exactly the kind of result the programme seeks.
So the honest negative case is weak. The anchor is narrower than the paper’s unrestricted graph model, but it survives as a sensible continuous-population computational question. I would not argue that no worthwhile mirror exists.
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.