| paper | d4-conf-ijcai-2020-0694 |
| 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: \(\mathrm{P}\): the required inequality holds for all measurable coalitions if and only if \(m=0\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1.1
statement extracted from the paper’s text layer
Given a finite type set \(T\), a loopless compatibility graph \(H=(T,F)\), integer capacities \(b_t\), positive rational surpluses \(c_{tu}\), and rational masses \(\mu_t\ge 0\) summing to \(1\), form an atomless population \(\Omega=\bigsqcup_{t\in T}\Omega_t\) with \(|\Omega_t|=\mu_t\). Each individual of type \(t\) has capacity \(b_t\). For every measurable coalition \(S\subseteq\Omega\), let \(z_t(S)=|S\cap\Omega_t|\) and define \(\nu(S)=\max\{\sum_{\{t,u\}\in F}c_{tu}q_{tu}:q_{tu}\ge0,\ \sum_{u:\{t,u\}\in F}q_{tu}\le b_tz_t(S)\text{ for each }t\}\). Decide whether \(\nu(S)+\nu(R)\le\nu(S\cup R)+\nu(S\cap R)\) for every pair of measurable coalitions \(S,R\).
An atomless cooperative b-matching game over a population partitioned into types. Coalition values depend on type masses through aggregate partnership variables, while convexity is tested on actual measurable coalitions so their overlaps are retained.
The proposed coordinatewise min/max condition ignores that coalitions can contain disjoint pieces of one type but the same pieces of another; the faithful overlap-aware version makes the paper’s richer convexity structure disappear.
fatal: False
The mirror covers only the convexity-recognition result, Theorem 1.1; it leaves the Shapley-value algorithm in Theorem 4.6 and the cited core complexity results unmirrored.
The strongest mirror is the paper’s convexity-recognition problem, in a high-multiplicity assignment market. Imagine many buyers and sellers, each with a capacity for several deals. A type records an agent’s role, capacity, and complete compatibility and surplus profile: agents of the same type can be treated identically by the market. There may be \(N\) agents but only \(\tau\) types, with \(\tau \ll N\). This is a plausible regime for repeated buyer and seller profiles, and every finite version is a b-matching game of the kind the paper studies.
My anchor is Theorem 1.1, proved in this paper: given a b-matching game on a graph with \(n\) vertices and \(m\) edges, the authors give an \(O(n\log n+m\alpha(n))\)-time algorithm to decide whether its characteristic function is supermodular, hence whether the game is convex. The paper also discusses co-NP-hardness of core problems in its introduction, citing earlier work, but those are different problems and not a numbered result to anchor here. Theorem 1.1 is the paper’s direct, proved result about convexity.
Here is the continuous problem I would hand to a prover: Continuous Type b-Matching Convexity. An instance consists of a finite set of types \(T\), a loopless compatibility graph \(H=(T,F)\), integer capacities \(b_t\), positive rational surpluses \(c_{tu}\) for \(\{t,u\}\in F\), and rational masses \(\mu_t\ge 0\) summing to \(1\). The mass \(\mu_t\) is the fraction of the population of type \(t\). For any coalition with type masses \(z\in[0,\mu]\), define its per-capita surplus by
\[ \nu_\mu(z)= \max\left\{ \sum_{\{t,u\}\in F} c_{tu}q_{tu} \ :\ q_{tu}\ge 0,\quad \sum_{u:\{t,u\}\in F}q_{tu}\le b_tz_t\ \text{for every }t \right\}. \]
Here \(q_{tu}\) is the mass of partnerships between types \(t\) and \(u\). The instance asks whether, for all \(x,y\in[0,\mu]\),
\[ \nu_\mu(x)+\nu_\mu(y) \le \nu_\mu(x\wedge y)+\nu_\mu(x\vee y). \]
A solution is a yes/no answer; for a no instance, a pair \(x,y\) violating the inequality is a natural witness. This asks whether the coalition-value function of the continuous population is convex. The optimization inside each coalition is a fractional b-matching LP, reflecting that a nonatomic mass can be divided across deals. If the population has \(N\) agents, multiplying this normalized value by \(N\) gives total surplus, without changing the convexity question.
I expect this to be Class A, tractable, with an algorithm polynomial in the type-level input size and bit length \(L\). That is a conjecture for this mirror, not a theorem of the paper: Theorem 1.1 supplies evidence that convexity has a structural characterization, while the finite type graph keeps the population description compact. A first question is whether the paper’s branching and budget conditions yield an exact criterion for this mass-vector game. Another is whether its convexity agrees with the limiting per-capita convexity of finite replications, including cases where finite matching parity effects disappear in the limit. If the structural criterion fails to carry over, the resulting problem could instead be continuum-specifically hard.
This mirrors Theorem 1.1’s convexity-recognition result; it does not claim to continuize the paper’s core problems or its Shapley-value computation. The main weakness is that the mirror restricts the arbitrary player graph to a type-based compatibility pattern: every agent of one type interacts with every compatible type at the same surplus. Also, the paper proves its algorithm for finite graphs, not for this atomless mass-vector domain. The case survives that limitation because the restriction describes a genuine high-multiplicity regime of the paper’s assignment applications, and the continuous question is still about the same b-matching coalition value and the same convexity property.
The only anchor is Theorem 1.1, and its key object is convexity of a coalition game: the inequality must hold for every pair of player sets, using their actual intersection and union. The proposed mass-vector test replaces those operations with coordinatewise minimum and maximum. That is valid only when the two coalitions’ portions of each type are nested. In a population of interchangeable agents, they need not be.
For example, take two positive-mass types \(L\) and \(R\), with one compatible edge of unit value and unit capacity. Let \(A\) contain an \(\varepsilon\)-mass piece of each type, and let \(B\) contain a *disjoint* \(\varepsilon\)-mass piece of \(L\) but the same \(R\) piece. Then \(\nu(A)=\nu(B)=\varepsilon\), while \(\nu(A\cap B)=0\) and \(\nu(A\cup B)=\varepsilon\). The coalition convexity inequality fails. Yet the proposed coordinatewise test uses \(f(x,y)=\min(x,y)\), which is supermodular on the product lattice and labels this example convex. The discrepancy is substantive: the type-mass vectors do not determine the overlap of coalitions.
There is a natural repair: quantify over all measurable coalitions and their feasible overlaps. But in an atomless population, any positive-mass compatible type pair lets two coalitions use disjoint pieces of one type and reuse the same counterpart mass, as in the example. That collapses the paper’s rich coalition structure in the continuous setting. The other repair—keeping coordinatewise minimum and maximum—defines a property of a mass-value function, not convexity of the underlying cooperative game, so the paper’s core and Shapley consequences no longer come along. The paper’s fractional b-matching result does not resolve this: it still tests coalitions in \(2^V\), with a finite player set.
That is the strongest case against this anchor: the faithful population version makes coalition overlap central, while the proposed tractable-looking version changes the property being tested. It does not prove that no author would find the mass-lattice question useful on its own, so the universal negative remains weak at that boundary.
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.