| paper | Complexity of Probabilistic Inference in Random Dichotomous Hedonic Games |
| authors | — |
| venue | AAAI 2023 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 10
statement extracted from the paper’s text layer
Given finite worker and employer type sets with rational initial masses, optional reserve masses, complete type-level approval or compatibility data, per-unit addition costs, and a budget B, can one choose added masses y and matching masses x so that all selected mass is perfectly matched along acceptable type pairs within budget B? The optimization version minimizes the addition cost.
A finite-type bipartite mass-matching model: initial and optional cohort masses, fractional additions y, compatible matching flows x, and a min-cost-flow or feasibility objective.
Theorem 10's hard instances may have essentially unique individual compatibility neighborhoods, while the proposed model assumes repeated worker and employer types and adds divisible cohort supplies and recruitment costs.
fatal: False
The mirror covers the perfect-partition constructive-control component of Theorem 10; it does not cover the paper's Nash-stability result, probabilistic counting results in Theorems 3 and 9, or the remaining complexity classifications.
I think there is a genuine positive case, but it is strongest when framed as a high-multiplicity mirror of the paper’s control and welfare problems—not as a literal \(N\to\infty\) limit of its Bernoulli participation probabilities. With finitely many types and fixed participation probabilities, normalized attendance concentrates, so the exact probability often collapses to \(0\) or \(1\). The continuous questions below preserve the underlying coalition-formation problem while replacing indivisible agents by masses.
My lead anchor is Theorem 10, proved in the paper. It states that in marriage games, Perfect-∃CCAUP(-m) and deciding whether \(\Pr[\mathrm{PFG}_{G'}]>0\) are NP-complete. The proof is by reduction from MinMaxMatch, whose hardness is cited from Horton and Kilakos.
The natural scenario is a large two-sided market: millions of workers and employers, but only a few dozen or few hundred recurring types. A type includes the side of the market, its complete preference order, its acceptable partners, location or qualification class, and any participation or addition cost. Thus many agents are genuinely interchangeable, rather than merely being given the same label.
The corresponding problem is:
Continuous Perfect-Matching Control. An instance consists of finite worker and employer type sets \(W,F\), current masses \(\mu_t\), available reserve masses \(\rho_t\), a set \(E\subseteq W\times F\) of mutually acceptable type pairs, per-unit addition costs \(\kappa_t\), and a budget \(B\). Choose added masses \(0\le y_t\le\rho_t\) and matching masses \(x_{uv}\ge0\) such that
\[ \sum_v x_{uv}=\mu_u+y_u \quad(u\in W), \qquad \sum_u x_{uv}=\mu_v+y_v \quad(v\in F), \]
with \(x_{uv}=0\) outside \(E\), and \(\sum_t\kappa_t y_t\le B\). The question is whether such a mass-perfect partition exists; the optimization version minimizes the addition cost.
This is recognisably the paper’s constructive control problem: current players must participate, optional players may be added, and the aim is to make a perfect outcome possible. The only change is that a cohort can be added fractionally. The continuous problem is Class A: it is a capacitated transportation or min-cost-flow LP over type masses. Rational solutions can be scaled to large discrete instances, while discrete instances with many copies of each type map back to normalized masses.
This is my strongest mirror because the hard part of Theorem 10 is precisely the indivisible selection of optional players. In a large market with repeated preference types, that indivisibility is artificial at the scale of the application. I would not claim this also mirrors the paper’s Nash-stability result without further work; the perfect-partition component alone is sufficient.
A second, more directly welfare-oriented anchor is Theorem 3, proved in the paper. It states that for \(k\)-lists with \(k\ge2\), and for polynomial-list representations, computing the probability that a specified coalition is welfare-optimal is #P-hard. The proof derives hardness from cited election-control results, specifically Theorem 3.2 of Imber and Kimelfeld and Theorem 13 of Wojtas and Faliszewski.
Here the plausible regime is a very large organization choosing among a polynomial number of coalition proposals. Each of a small number of cohorts has the same approval list—at most \(k\) proposals—and the same cost of recruitment. The continuous question is:
Continuous Welfare-Optimal Coalition Control. Given types \(t=1,\ldots,\tau\), current masses \(\mu_t\), available masses \(\rho_t\), addition costs \(\kappa_t\), candidate coalitions \(C_1,\ldots,C_r\), and a target \(C_{j^\star}\), let \(a_{jt}\in\{0,1\}\) indicate whether type \(t\) contributes an approved unit to \(C_j\). Choose \(0\le y_t\le\rho_t\) to minimize \(\sum_t\kappa_t y_t\), subject to
\[ W_{j^\star}(\mu+y)\ge W_j(\mu+y) \quad\text{for every }j, \]
where \(W_j(\mu+y)=\sum_t a_{jt}(\mu_t+y_t)\). Equivalently, decide whether the target can be made welfare-optimal within budget \(B\).
The constraints are linear, so this is again Class A. It is not the exact #P counting problem: the paper counts indivisible attendance subsets, whereas the mirror asks for the minimum mass or cost needed to make the target optimal. That is the correct high-multiplicity relaxation of the control core. The paper’s Theorem 4, also proved here, supports this interpretation: the corresponding positive-probability or existence question is already in FP, even though exact probability computation is #P-hard.
A third, cleaner geometric anchor is Theorem 9, proved in the paper. It shows that for candidate-interval preferences, the probabilities of welfare-optimal coalitions, welfare-optimal partitions, and perfect partitions are computable in polynomial time.
The continuous scenario is a population distributed along a line: residents along a transit corridor, clients ordered by geography, or users along a one-dimensional service network. There are many agents but finitely many location-and-preference types. A type specifies its mass density and which contiguous intervals it approves.
The corresponding problem is:
Continuous Interval Welfare Partition. Let \([0,1]\) carry a rational piecewise-constant population density. For every interval \([a,b]\) from a finite breakpoint set, the input specifies which population types approve that interval. A feasible outcome is a partition of \([0,1]\) into contiguous intervals. Its welfare is the total mass approving the interval containing them. Given a target partition, compute the maximum welfare over all interval partitions and decide whether the target is welfare-optimal or perfect.
For an interval \([a,b]\), its welfare is an explicitly computable integral. If \(F(b)\) is the best welfare on the prefix ending at \(b\), then
\[ F(b)=\max_{a\le b}\{F(a)+w(a,b)\}. \]
Thus this is Class A by the same dynamic-programming structure used in Theorem 9. This is a particularly credible mirror because both the ordered population and the interval coalitions survive intact; only the repeated population mass becomes continuous.
I would not extend the positive claim to the paper wholesale. Theorem 5’s independent-set reduction, Theorem 6’s kernel reduction, and Theorem 7’s X3C reductions may retain hardness when the graph or incidence structure grows with the number of types. Those are plausible Class B boundaries rather than automatic successes. Theorem 11 and Theorem 12 are asymptotic distributional results, not computational results, so they are not anchors for this programme.
The weakest point is the treatment of randomness. The paper’s central object is a probability over subsets of named agents, while the continuous mirrors above replace that by divisible participation mass. If one insists on preserving exact probabilistic inference, one could instead assign each cohort a random turnout fraction and ask for the probability that the target is welfare-optimal; that becomes a volume or integration problem over a polytope and may be continuum-specifically hard. But that random-mass model is an additional modelling choice, not the canonical high-multiplicity limit of independent Bernoulli attendance.
Subject to that qualification, the paper does admit a convincing continuous mirror: large populations with repeated preference types, continuous control over cohort mass, and LP/flow/dynamic-programming questions about perfectness and welfare optimality. The mirror covers Theorems 10, 3, and 9, with Theorem 10’s perfect-control problem as the strongest case.
The strongest negative case is that the proposed mirrors quietly replace the paper’s central object—probability over subsets of named agents—with deterministic mass intervention. That is not merely a harmless limit operation.
With finitely many high-multiplicity types, if type \(t\) contains \(N_t\) agents with independent participation probability \(p_t\), its participating mass is \(X_t/N_t\), where \(X_t\sim\mathrm{Bin}(N_t,p_t)\). As \(N_t\) grows, this converges to \(p_t\). Away from exact feasibility boundaries, probabilities of perfection or optimality therefore collapse to zero or one. At a boundary, the answer depends on \(O(\sqrt{N_t})\) fluctuations and integer rounding, so retaining the interesting probability question means retaining discrete binomial counts. Replacing them by arbitrary random mass fractions is a new uncertainty model, not the paper’s high-multiplicity limit.
This weakens the second anchor, Theorem 3, most sharply. The paper counts attendance subsets for which a particular coalition is welfare-optimal. The proposed LP instead chooses added mass to satisfy linear welfare inequalities. That is a legitimate continuous control problem, but it is not a continuous version of the #P inference problem; it is a different intervention problem whose positive-existence analogue the paper already places in FP. Moreover, the displayed welfare formula is incomplete for genuine hedonic coalitions: welfare is contributed by participating agents who belong to the candidate coalition, not by every type that approves it. A correct type must include its complete membership and approval signature across all candidate coalitions. If those signatures are retained, the model is essentially a generic linearized voting/control problem; if they are not, coalition membership has been erased.
Theorem 9 has a related problem. In candidate-interval games, an agent’s relation to a coalition depends on its exact position and on the interval’s endpoints. Thus a piecewise-constant density does not produce finitely many interchangeable types: agents at different positions in the same piece behave differently for intervals cutting through that piece. Retaining arbitrary intervals requires a continuum of positional types and an input representation for the approval relation over continuously many endpoints. Restricting endpoints to a finite breakpoint set produces a sensible finite zonal model, but no longer mirrors the paper’s general candidate-interval setting; it is a new discretized problem whose dynamic program survives by construction.
Theorem 10 is the strongest anchor, but it too only works after a substantial semantic change. The paper’s hardness comes from choosing among named optional players with a named compatibility structure. Preserving that structure makes each distinct compatibility neighbourhood part of the agent’s type; in the hard instances, there need be essentially no repeated types. Aggregating agents into worker and employer cohorts replaces the instance by a type-homogeneous market in which compatibility is between types rather than individuals. The resulting transportation LP is perfectly sensible, but it is a new large-market matching model, not obviously the high-multiplicity regime of the theorem’s NP-complete instances. The proponent also adds bilateral supply variables and per-unit recruitment costs that are not part of the stated theorem.
That said, this is where the negative case genuinely breaks. A large market with repeated worker and employer types is a plausible scenario, and fractional perfect matching is not a vacuous formal trick: in the bipartite case it faithfully represents divisible cohorts and can be scaled back to large integral markets. The programme explicitly lists matching types to types as a natural continuization. Calling this “not worthwhile” merely because the answer is a flow algorithm would violate the programme’s own standards.
So the honest conclusion is not a clean rejection. Theorem 3 and Theorem 9, as proposed, do not provide faithful mirrors of the paper’s named probabilistic results. But a repaired version of Theorem 10 survives as a credible Class A high-multiplicity matching problem. The universal claim that no worthwhile continuous mirror exists therefore cannot be sustained; the negative case is, at best, a warning that the surviving mirror is a new deterministic cohort-control model rather than a literal continuization of the paper’s probabilistic inference.
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.