| paper | d4-conf-ijcai-2017-0515 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.10
statement extracted from the paper’s text layer
Fix constant \(B\), a finite type set \(T\), and rational masses \(\mu_t>0\) with \(\sum_{t\in T}\mu_t=1\). Let \(\mathcal G_B=\{g\in\mathbb Z_{\ge0}^{T}:1\le\sum_t g_t\le B\}\). A type-\(t\) agent has unknown utility \(u_t(g)\) for any team profile \(g\) with \(g_t>0\). Define \(x_t(g)\) as the unique maximizer of \(u_t(x)\) over \(x\le g\) with \(x_t\ge1\); require the paper’s top-responsiveness comparison clauses on profiles, and require sampled utilities to reveal comparisons between choice profiles as in its informative-representation condition. Given samples \((h,(u_t(h))_{t:h_t>0})\) from an unknown distribution \(D\) over \(\mathcal G_B\), with team members sampled uniformly from their type populations, find an algorithm with sample and computation complexity polynomial in \(|T|\), \(1/\epsilon\), \(\log(1/\delta)\), and the input bit length that outputs rational frequencies \(q_g\ge0\) satisfying \(\sum_{g\in\mathcal G_B}g_tq_g=\mu_t\) for every \(t\), and, with probability at least \(1-\delta\) over the samples, satisfies \(\mathbb E_{h\sim D}[\prod_{t:h_t>0}p_t(h;q)^{h_t}]<\epsilon\), where \(p_t(h;q)=\mu_t^{-1}\sum_{g:u_t(h)>u_t(g)}g_tq_g\).
A population with type masses \(\mu\), partitioned into integral team profiles \(g\in\mathcal G_B\) at rational frequencies \(q_g\). Deviations are sampled team profiles; their blocking probability is the product of the population shares of each included type who prefer the deviation to their current team.
The paper’s unique choice subsets are identity-sensitive; for anonymous types the natural unique object is a profile, so the proposed analogue needs a newly specified profile-level axiom and its own PAC-stabilization proof.
fatal: False
The mirror covers only Theorem 4.10’s top-responsive PAC-stabilization guarantee; it leaves the learning and non-stabilizability results for other classes aside.
The strongest case is a narrow mirror of Theorem 4.10, proved in this paper. It says that top-responsive hedonic games with informative utility representations are efficiently PAC stabilizable. More concretely, given \(m=(2n^4+2n^3)\lceil \epsilon^{-1}\log(2n^3/\delta)\rceil\) sampled coalitions and their members’ utilities, the paper’s algorithm returns a partition that, with probability at least \(1-\delta\), is blocked by a coalition drawn from \(D\) with probability less than \(\epsilon\). The result is proved here using sampled approximations to choice sets and a top-covering procedure. This is the lead anchor: it concerns computing a stable outcome under uncertainty, the paper’s central computational question.
Here is a continuous-population version I think the authors could recognize as the same problem. Fix a finite set \(T\) of complete preference types, with \(\tau=|T|\), and rational masses \(\mu_t>0\) summing to \(1\). A plausible regime is a very large population of workers repeatedly assigned to small project teams: millions of people, but only a modest number of preference types. Take a fixed maximum team size \(B\). A team is described by an integral type-count vector \(g\in\mathcal G_B=\{g\in\mathbb Z_{\ge0}^{T}:1\le\sum_t g_t\le B\}\). Each type \(t\) has one preference ordering over these team profiles, represented by a utility \(u_t(g)\). Require top responsiveness on this bounded profile domain, with the informative representation assumption from the paper.
Call the problem Bounded-Team Type-Mass PAC Stabilization. Its instance consists of \(\mu\), \(B\), an unknown game in that class, accuracy and confidence parameters \(\epsilon,\delta\), and samples from an unknown distribution \(D\) over team profiles. A sample reports \(h\in\mathcal G_B\) and the utility \(u_t(h)\) for each type present in the team. Assume the sampling is exchangeable within types: conditional on \(h\), its members are drawn uniformly from the corresponding populations. The output is a vector of rational team frequencies \(q_g\ge0\), where \(q_g\) is the number of teams of profile \(g\) per population member, satisfying \(\sum_g g_tq_g=\mu_t\) for every \(t\).
This \(q\) is a population partition in the high-multiplicity sense: in a finite society of size \(N\), \(Nq_g\) members’ worth of teams have profile \(g\). Teams remain integral; it is their frequency that is continuous. For a proposed deviation profile \(h\), the fraction of type-\(t\) members who prefer it to their current team is
\[
p_t(h;q)=\frac{\sum_{g:u_t(h)>u_t(g)}g_tq_g}{\mu_t}.
\]
In the large-population limit, the probability that a uniformly sampled team of profile \(h\) blocks \(q\) is \(\prod_{t:h_t>0}p_t(h;q)^{h_t}\). Thus a solution must give an allocation \(q\) for which
\[
\mathbb E_{h\sim D}\!\left[\prod_{t:h_t>0}p_t(h;q)^{h_t}\right]<\epsilon
\]
with probability at least \(1-\delta\) over the training samples. The question is whether this can be done with sample and computation complexity polynomial in \(\tau\), \(1/\epsilon\), \(\log(1/\delta)\), and the input bit length. For fixed \(B\), the number of team profiles is polynomial in \(\tau\).
I would expect this bounded-type version to be tractable, in the spirit of Class A. The paper already supplies a sample-based route to PAC stability for this preference class; a type-level analogue could work over the finite set of team profiles and output frequencies rather than named agents. That is a conjecture about the mirror, not a consequence of Theorem 4.10: its algorithm runs in \(n\), and the paper does not prove that it can be compressed to \(\tau\) types. In particular, the blocking probability above is a product of linear expressions in \(q\), so a type-level optimization and generalization argument still needs to be found.
The high-multiplicity scenario is the reason this is a mirror rather than just a fractional-outcome variant. Type means indistinguishability for everything used by the problem; \(\mu_t\) is population share; and \(q\) aggregates many integral team assignments. The objective remains core resistance under sampled uncertainty. I am only mirroring Theorem 4.10, not the paper’s separate learnability and non-stabilizability results.
The weakest point is the regime restriction. The model assumes bounded team sizes and exchangeable sampling within types; arbitrary identity-dependent sampling or preferences may require so many types that the population compression disappears. Removing the size bound is a natural next question, as is proving a finite-population rounding guarantee that transfers the continuous PAC bound back to large discrete instances. If the authors require unrestricted coalition sizes and non-exchangeable \(D\) for the mirror to count, this proposal is too narrow; under the stated recurring-team regime, it preserves their underlying PAC-stability problem.
Theorem 4.10 is a genuine computational anchor, so the case against cannot rest on the paper lacking a result to mirror. The strongest objection is that its algorithm depends on information that a high-multiplicity model generally cannot compress: the identities in each agent’s most-preferred subset.
For a player \(i\), the paper’s choice set \(\operatorname{ch}(i,S)\) is a subset of the named members of coalition \(S\). The algorithm approximates these sets from sampled coalitions, then uses them to build the stable partition. If we preserve that object and the full class of top-responsive games, a type must capture how an agent evaluates coalitions containing particular other agents. In a generic game, that can make every agent a distinct type, leaving \(\tau=n\) and no useful population compression.
The proposed rescue is anonymous preferences over bounded team profiles. It gives a plausible recurring-team scenario, but it changes the theorem’s key structure. If two teammates have the same type, an agent who prefers a coalition containing exactly one of them has two equally good subsets, contrary to the paper’s requirement that the choice set be unique. Preserving top-responsiveness under this symmetry therefore restricts choice sets to include all or none of each type. One could define a new axiom in terms of type-count profiles, but the paper’s sampled-intersection argument does not establish PAC stabilization for that axiom; it needs a new result.
The bound \(B\) also restricts which deviations count. The paper’s core ranges over coalitions of any size. Bounded teams may be sensible in a workplace or project setting, but the resulting question is PAC stability against bounded-size deviations, not the theorem’s unrestricted stability question. Removing the bound brings back the identity problem: in a continuum, a choice set would need to be represented by a mass profile, and many distinct subsets have the same profile. That is another model requiring its own definition and analysis.
These objections defeat a direct lift of Theorem 4.10 and make the proposed mirror a new, narrower anonymous-team problem. They do not defeat that problem as a worthwhile mirror if the authors would recognize it: recurring teams with type-based preferences are plausible, and the type-mass formulation is coherent. The negative case is therefore weak on the universal claim. The paper also already uses a distribution over coalitions for PAC uncertainty, but that is not continuous population and does not count as prior continuous treatment. I would argue against treating the stated construction as an established mirror of Theorem 4.10, while conceding that a recognized anonymous-team version could survive the programme’s gate.
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.