| paper | d4-conf-aaai-2012-0238 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. The sequence always converges, and its exact rational limit is computable in polynomial time. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t=p_t/D>0\) with \(\sum_t p_t=D\), and symmetric nonnegative rational values \(w_{tu}\), form for each positive integer \(r\) the graph with \(rp_t\) vertices of type \(t\), joining every distinct pair of types \(t,u\) with weight \(w_{tu}\), including distinct same-type pairs with weight \(w_{tt}\). Compute the ordinary fractional-matching-game nucleolus at each \(r\); symmetry gives a common payoff \(a_t^{(r)}\) to each vertex of type \(t\). Determine whether \(a^{(r)}\) converges as \(r\) grows and, if it does, compute its exact limit; otherwise prove nonconvergence. State complexity in the number of types and binary input length.
The society has type masses \(\mu_t\), with pairwise collaboration values \(w_{tu}\). A coalition with type masses \(z_t\in[0,\mu_t]\) has aggregate fractional-matching value \(v(z)=\max\{\sum_{t<u}w_{tu}y_{tu}+\sum_t w_{tt}y_{tt}: 2y_{tt}+\sum_{u\ne t}y_{tu}\le z_t\ \forall t,\ y\ge0\}\). The output is a per-agent payoff \(a_t\) for each type, defined as the limit of the ordinary nucleoli on the finite replications; each finite game retains the paper’s lexicographic excess objective over all named coalitions, including their multiplicities.
Covers Theorem 3’s fractional-matching nucleolus for replicated finite-type weighted graphs; leaves the least-core results, Theorem 5’s bipartite vertex-cover games, and the edge-cover and clique generalizations untouched.
The strongest case is narrow: Theorem 3’s fractional matching games have a natural high-multiplicity regime in which the population has finitely many interaction types.
The anchor is Theorem 3, proved in this paper: *the nucleolus of a fractional matching game on a weighted graph can be computed in polynomial time.* In the underlying game, agents are graph vertices, a coalition’s value is the maximum weight of a fractional matching among its members, and the output is the unique allocation whose sorted coalition excesses are lexicographically maximized. The theorem covers arbitrary weighted graphs; it does not claim a running time polynomial in the number of types when the population is compressed.
A plausible regime is a large consortium of contributors with a fixed set of roles. A type records everything relevant to collaboration: two contributors of types \(t\) and \(u\) have the same collaboration value \(w_{tu}\), and contributors of the same type are interchangeable. The consortium may have \(r p_t\) contributors of type \(t\), for fixed positive integers \(p_t\), across \(rD\) contributors total, where \(D=\sum_t p_t\). Thus the type mass is \(\mu_t=p_t/D\), with population size growing while the number \(\tau\) of types stays fixed. This is credible when role and collaboration value determine the relevant relationships; it would not fit a network where each contributor has important individual-specific partners.
Here is the mirror I would hand to a prover: Replication-Limit Fractional-Matching Nucleolus. The input is a finite type set \(T\), rational masses \(\mu_t=p_t/D\), and symmetric nonnegative rational values \(w_{tu}\). For every positive integer \(r\), form a weighted graph \(G_r\) with \(r p_t\) agents of type \(t\), placing an edge of weight \(w_{tu}\) between each distinct pair of types \(t,u\); within a type, distinct agents have weight \(w_{tt}\). Compute the ordinary nucleolus of that finite fractional matching game. By symmetry and uniqueness, every type-\(t\) agent receives the same payoff, call it \(a_t^{(r)}\).
The question is to determine whether \(a^{(r)}=(a_t^{(r)})_{t\in T}\) converges as \(r\) grows, and, when it does, compute its exact limit. For each \(r\), the objective is exactly the paper’s: lexicographically maximize the non-decreasingly ordered excesses over all named coalitions, retaining the multiplicity of coalitions that have the same type counts. The requested answer is a limit allocation per type, together with a convergence proof, or a proof that the limit fails to exist. A complexity result should state its dependence on \(\tau\) and the binary input length \(L\).
The continuous society behind this question has mass \(\mu_t\) of each type. A coalition is described by its type masses \(z_t\in[0,\mu_t]\); its aggregate matching value is naturally
\[ v(z)=\max \left\{\sum_{t<u}w_{tu}y_{tu}+\sum_t w_{tt}y_{tt}: 2y_{tt}+\sum_{u\ne t}y_{tu}\le z_t\ \forall t,\quad y\ge0\right\}. \]
A type allocation \(a\) gives that coalition mass \(\sum_t z_t a_t\). The mirror asks for the limit of the finite games’ nucleoli under this continuous population description. It does not assume that lexicographically ordering excesses over a continuum of coalitions has an already agreed definition. The population is what becomes continuous; the type-level payoff is the per-agent limit of the allocations in the paper’s game.
I expect this question to be Class A in the fixed-type regime: the interaction data and coalition value have a finite type-level description, so structural properties of fractional matching might yield an exact computation polynomial in \(\tau\) and \(L\). That is a conjecture about the mirror, not a consequence of Theorem 3, whose polynomial bound is in the graph input size. Further questions are whether convergence always holds, whether the limit matches a canonical nucleolus defined directly for the mass game, what approximation rate relates finite replications to the limit, and when hardness returns as \(\tau\) grows with the population.
The weakest point is that the replication limit is a defensible continuous analogue, but it is not a standard continuum nucleolus supplied by the paper. Arbitrarily small coalitions and the growing multiplicity of coalitions with identical type masses may affect the limit; the theorem proves neither convergence nor a compressed algorithm. That is also why I would ask this limit question rather than casually transplant the least-core program: in a nonatomic population, tiny coalitions can make an unnormalized minimum-excess objective collapse. The case is strongest as a precise new computational question about the same game and fairness objective, not as a claim that Theorem 3 already solves it.
Theorem 3 is an eligible computational anchor: it gives a polynomial-time algorithm for the nucleolus of fractional matching games. The paper also has Theorem 5 for weighted bipartite vertex cover games. So the negative case cannot rest on there being no named computational result.
The strongest objection starts with what a type would have to encode. In an arbitrary weighted graph, an agent’s relevant data include its weighted relationships with other agents. Typically each vertex then has a distinct interaction profile, so \(\tau\) grows with the population and a mass description gives no compression. The proponent’s fixed-role consortium is the best repair: if interaction values depend only on the two roles, then a finite type set and a matrix \(w_{tu}\) describe a genuine family of larger games. That regime is restrictive, but plausible; it defeats any claim that graph agents can never have meaningful multiplicity.
There is a real problem with defining the nucleolus directly on the resulting mass society. Its finite-game objective sorts the excesses of a finite list of named coalitions. For a mass coalition \(z\), the natural excess is \(e(z,a)=\sum_t z_ta_t-v(z)\), and fractional matching value is homogeneous, so \(e(\lambda z,a)=\lambda e(z,a)\). For a core allocation, nonempty coalitions can therefore have excess arbitrarily close to zero as their mass shrinks. The first minimum becomes an unattained infimum, and the later lexicographic stages have no canonical finite list to refine. Dividing by coalition mass would avoid that collapse, but would define a different fairness objective.
That objection does not defeat the proposed mirror, because the proponent uses a replication limit rather than asserting an already-defined continuum nucleolus. For rational masses, the replication sequence can be fixed canonically; uniqueness and symmetry give one payoff per type at each finite scale. Asking whether those payoffs converge, and how to compute the limit, is a well-posed asymptotic question tied to the paper’s game and solution concept. The paper’s polynomial bound in the expanded graph size says nothing about a bound in \(\tau\) and input bit length, but that unresolved complexity is the research question, not a reason to reject it.
So the negative case is strongest against generic graphs and against a direct atomless nucleolus. It cannot honestly rule out the fixed-type replication mirror. Under the programme’s gate, that anchor survives; I would call the case against weak rather than claim there is no worthwhile 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.