| paper | d4-conf-ijcai-2017-0576 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: All limits exist. Their additive approximation is deterministically computable in time polynomial in \(m,\tau,L,1/\varepsilon\) for every fixed \(k\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5.4
statement extracted from the paper’s text layer
Given a finite compatibility graph \(H=(T,F)\) with \(\mathrm{tw}(H)\le k\) and rational population shares \(\mu_t>0\) summing to \(1\), form \(G_q\) for each \(q\) with \(q\mu_t\in\mathbb{Z}\) by creating \(q\mu_t\) agents of each type and joining agents whose types are adjacent in \(H\). For each type \(t\), let \(\phi_{q,t}\) be the Shapley payoff of any one of its agents. Does \(\lambda_t=\lim_{q\to\infty}\phi_{q,t}\) exist, and, for fixed \(k\), can it be approximated within additive error \(\varepsilon\) in time polynomial in \(|T|\), the bit length of \(\mu\), and \(1/\varepsilon\)?
A matching market with a finite set of complete compatibility types \(T\), rational type masses \(\mu\), and compatibility graph \(H\). Replicate agents in the stated proportions, retain the paper’s exact matching-game worth and Shapley rule at every finite population size, and compute the limiting payoff per agent of each type.
The replicated agent graph can have unbounded treewidth even when the compatibility graph on types has bounded treewidth, so the paper’s algorithm provides no direct tractability guarantee for the proposed limit.
fatal: False
The mirror covers the Shapley and Banzhaf value-computation questions for fixed-support matching-market families as population limits. It does not carry over the paper’s algorithm for graphs of bounded agent-graph treewidth, its implementation results, or the general-graph hardness cited as background.
The strongest honest lead is Theorem 5.4, proved in this paper: *the Shapley value can be computed in polynomial time on matching games defined over any class of graphs having bounded treewidth.* The paper’s numbered result is an algorithm, not a hardness theorem; its statement that the general problem is \(\#\mathrm P\)-complete is background attributed to Aziz and de Keijzer, not a numbered anchor.
A natural high-multiplicity setting is a matching market with many agents but few complete compatibility profiles: for example, workers and positions grouped by credentials and requirements, where compatibility depends only on the two profiles. Let \(H=(T,F)\) be the compatibility graph on the finite set of types, with fixed \(\mathrm{tw}(H)\le k\), and let \(\mu_t\in\mathbb Q_{>0}\), \(\sum_t\mu_t=1\), be the population share of type \(t\). For a coalition containing mass \(x_t\) of each type, its worth is the maximum mass of compatible pairs:
\[ v_H(x)=\max\left\{\sum_{\{t,u\}\in F}y_{tu}: y_{tu}\ge 0,\quad \sum_{u:\{t,u\}\in F}y_{tu}\le x_t\ \text{for every }t\right\}. \]
Here \(y_{tu}\) is the mass matched across types \(t\) and \(u\). This is the matching game’s same worth question with mass capacities; the fractional matching is the co-modification required when agents become divisible mass.
I would pose the lead continuous problem as Limit-Shapley Matching Allocation. For every integer \(q\) such that \(q\mu_t\) is integral for all \(t\), create \(q\mu_t\) agents of type \(t\). Join every pair of agents whose types form an edge of \(H\), and let \(G_q\) be the resulting graph. Let \(\phi_{q,t}\) be the Shapley payoff of any one type-\(t\) agent in this matching game. The question is: for each type, does
\[ \lambda_t=\lim_{q\to\infty}\phi_{q,t} \]
exist, and can it be approximated within additive error \(\varepsilon\), in time polynomial in \(|T|\), the mass bit length, and \(1/\varepsilon\), for fixed \(k\)? The answer is a per-agent allocation \(\lambda_t\); type \(t\)’s aggregate allocation per unit of population is \(\mu_t\lambda_t\). The finite game uses the paper’s exact Shapley definition, so the limit supplies the continuous semantics rather than substituting an unrelated fairness rule.
This is plausible as their problem: it retains the matching-game worth and the Shapley distribution of that worth, and the authors themselves point to matching markets as an application. The large-agent, few-profile regime is sensible there: agents with the same profile have identical compatibility and other problem-relevant attributes. My expectation for bounded-treewidth \(H\) is Class A, though it is a conjecture for this mirror, not a consequence of Theorem 5.4. The mass worth is a finite matching LP; the challenge is computing the limiting marginal payoffs, especially at ties between optimal match structures. The paper’s bounded-treewidth techniques suggest a route to handling that structure. Further questions are whether the limit always exists, what changes when \(k\) is not fixed, and whether the limiting allocation has a useful characterization through optimal LP solutions.
A worthwhile second anchor is Theorem 5.5, also proved here: *the Banzhaf value can be computed in linear time on matching games defined over any class of graphs having bounded treewidth.* It supports a distinct, slightly simpler mirror, Limit-Banzhaf Matching Marginals. Use the same \(H,\mu,G_q\); for a type-\(t\) agent, let \(\beta_{q,t}\) be its expected marginal matching value when each other agent enters the coalition independently with probability \(1/2\). Ask whether \(\eta_t=\lim_{q\to\infty}\beta_{q,t}\) exists and can be approximated to error \(\varepsilon\). This is a marginal index, so the question asks for the per-agent limit rather than an efficient allocation of the grand-coalition worth. Its likely tractability comes from the same type-level matching structure, with a single sampling probability rather than the Shapley value’s averaging over predecessor-set sizes.
The main weakness is structural: the paper bounds the treewidth of the agent graph, while these mirrors bound the treewidth of the type compatibility graph. The replicated graph \(G_q\) can have unbounded treewidth even when \(H\) has bounded treewidth, so neither theorem directly proves tractability of these limits. Also, replacing matching cardinalities by mass matching alone does not determine Shapley’s limiting marginal at degenerate ratios; that limit must be analyzed. I still think this is a defensible positive case: it states a precise high-multiplicity matching-game question the authors could recognize, and treats the paper’s bounded-treewidth results as motivation for the complexity question rather than falsely claiming they already solve it. The scope is the Shapley and Banzhaf computation problems in this restricted, few-profile regime—not the paper’s implementation results or its general-graph \(\#\mathrm P\)-completeness context.
The paper has two genuine computational anchors: Theorem 5.4 for the Shapley value and Theorem 5.5 for the Banzhaf value. I would not argue that it lacks a named result. My case against both is that their tractability depends on the treewidth of the agent graph, while a meaningful finite-type population generally destroys that parameter.
Suppose a type graph \(H\) has an edge between two types \(a\) and \(b\), and each type is replicated \(q\mu_t\) times. The resulting agent graph contains \(K_{q\mu_a,q\mu_b}\), whose treewidth grows with \(q\). So bounding \(\mathrm{tw}(H)\), as the proponent proposes, does not preserve the paper’s bounded-treewidth condition. If instead we preserve the paper’s exact graph edges, agents in repeated disjoint components have different named neighbors; a complete type must record those differences, and the support grows with the population. In the fixed-support, bounded-treewidth blow-up, positive-mass types cannot have nontrivial compatibility with one another: such an edge creates the growing complete bipartite subgraph. Any matching value must then come through types whose population share vanishes, leaving a degenerate mass-scale game.
That is the problem with the proposed Shapley mirror. Its best version—compute the per-agent limit for replicated compatibility types—is plausible as a matching-market question, and the paper itself mentions assignment games. But it changes the structural parameter from the treewidth of the actual matching graph to that of a type-level compatibility graph. The paper’s MSO and coalition-counting result supplies no bridge to this new regime. The limit also requires specifying the replication process and retaining its random order: a deterministic mass matching problem does not by itself define the Shapley payoff to an infinitesimal agent.
The Banzhaf mirror has the same graph problem, and an additional interpretive one. The paper computes an unnormalized expected marginal contribution. Under continuum scaling, independent inclusion at probability \(1/2\) concentrates on half the mass of each type; to retain a per-agent Banzhaf limit, one must keep the finite-population sampling fluctuations around that composition. That is a legitimate stochastic limit question, but it is not the computation of the Banzhaf value for a society given just as a distribution. It replaces the paper’s subset-counting problem with an asymptotic probability problem on a type-based blow-up.
So my negative case is that neither anchor has a faithful fixed-support mirror that retains the paper’s bounded-treewidth setting: preserving the graph loses type compression, while preserving finite types loses bounded treewidth. The proposed dense matching-market limits remain the strongest counterexample to this case; they could be worthwhile independently. I would oppose them as mirrors of these theorems because their tractability question turns on a different input structure and a different limiting computation. That is where the negative case is weakest: the authors might recognize the new regime as their problem even though this paper does not support it.
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.