| paper | Game-Theoretically Secure Distributed Protocols for Fair Allocation in Coalitional Games |
| authors | — |
| venue | AAMAS 2025 |
| filed under | coalition · wvg |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.6
statement extracted from the paper’s text layer
Given a finite type set \(T\), mass distribution \(\mu\), monotone piecewise-\(C^1\) scalable characteristic function \(V\), focal type \(h\), accuracy parameters \(\epsilon,\delta\), and \(G\ge\Gamma_h^\infty\), where \(D_h(z)=\partial_hV(z)\), \(a_h(\mu)=\int_0^1D_h(\lambda\mu)\,d\lambda\), and \(\Gamma_h^\infty=\sup_{z\le\mu}D_h(z)/a_h(\mu)\), construct a type-level random-order sampling protocol and stopping rule under the paper's rushing adversary and unknown detectable violation-rate model that returns \((\widehat a_h,\widehat\epsilon)\) satisfying \(\Pr[\widehat\epsilon\le\max\{\epsilon,4f\Gamma_h^\infty\}]=1\) and \(\Pr[\widehat a_h\ge(1-\widehat\epsilon)a_h(\mu)]\ge1-\delta\), while minimizing permutation-sample count independently of clone count.
A finite-type scalable anonymous coalitional game with society mass \(\mu\), value function \(V\), per-capita Shapley/Aumann–Shapley payoff \(a_h(\mu)\) for a focal type-\(h\) representative, samples exposing \(D_h(U\mu)\), and decision variables consisting of a stopping rule and estimator.
A \(q\)-independent procedure that samples \(U\) and evaluates \(D_h(U\mu)\) is a new density-oracle abstraction rather than an executable compression of the paper's \(q\)-player commitment protocol.
fatal: False
The mirror covers the permutation-sampling and maximin-security results in Sections 3–5, especially Theorem 4.6, but leaves arbitrary set-function Shapley computation, commitment-round complexity, and the experiments unmirrored.
The strongest honest positive case is a mirror of the paper’s permutation-sampling and maximin-security results, not of its cited \(\#P\)-hardness statement for exact Shapley values. The paper has no own numbered \(P\)/\(NP\)-hardness theorem; its eligible computational anchors are sampling-complexity theorems.
Take a large recurring consortium of data owners, sensors, or network participants. There are \(q\gg\tau\) players but only \(\tau\) complete operational types. A type includes the player’s coalition-relevant contribution profile, protocol role, local randomness, and all other parameters used by the game. Let \(\mu_t\) be the fraction of players of type \(t\).
To make the high-multiplicity limit nondegenerate, represent the typed game by a scalable characteristic function \(V\). For a clone population of size \(q\), with \(q\mu_t\) players of type \(t\), define
\[ v_q(S)=qV\!\left(\frac{|S\cap T_1|}{q},\ldots,\frac{|S\cap T_\tau|}{q}\right). \]
Assume \(V\) is monotone and piecewise-\(C^1\), with \(D_t(z)=\partial_tV(z)\). Then the marginal value of one type-\(t\) clone converges to \(D_t(z)\). The per-player continuous Shapley target is
\[ a_t(\mu)=\int_0^1D_t(\lambda\mu)\,d\lambda, \]
and the total allocation to type \(t\) is \(A_t(\mu)=\mu_ta_t(\mu)\). This is a typed Aumann–Shapley limit obtained from the paper’s own random-permutation interpretation, not an unrelated divisible-outcome model.
The lead anchor is Theorem 4.6, “Adaptive Maximin Security for Violation Rate,” proved by the authors in this paper. It says that when the violation rate \(f\) is unknown, their adaptive protocol returns \((x,\widehat\epsilon)\) with
\[ \widehat\epsilon\le \max\{\epsilon,4f\Gamma\} \]
with probability \(1\), while an honest player receives at least \((1-\widehat\epsilon)\phi_i\) with probability at least \(1-\delta\).
The corresponding continuous problem is:
Adaptive Typed-Permutation Maximin\(_\infty\). An instance consists of \(T,\mu,V\), a focal honest type \(h\), accuracy parameters \(\epsilon,\delta\), and a valid bound \(G\) on
\[ \Gamma_h^\infty = \frac{\sup_{z\le\mu}D_h(z)} {\int_0^1D_h(\lambda\mu)\,d\lambda}. \]
A sample is a random ordering of the clone population. In the limit, a randomly selected type-\(h\) representative has an unobstructed reward \(Y=D_h(U\mu)\), where \(U\sim\mathrm{Unif}[0,1]\). A rushing adversary may cause detectable violations and reduce the reward, exactly as in the paper’s model. The protocol does not know the eventual violation rate \(f\).
The task is to construct a stopping rule and estimator \((\widehat a_h,\widehat\epsilon)\) such that, for every admissible adversary,
\[ \Pr\!\left[\widehat\epsilon\le \max\{\epsilon,4f\Gamma_h^\infty\}\right]=1 \]
and
\[ \Pr\!\left[\widehat a_h\ge (1-\widehat\epsilon)a_h(\mu)\right]\ge1-\delta. \]
The objective is to minimize the number of permutation samples, with complexity depending on \(\tau\), \(G\), \(\epsilon\), \(\delta\), and the representation length of \(V\), but not on the clone count \(q\).
I expect this problem to be Class A in the explicit typed-density-oracle model. The proof mechanism is exactly the paper’s: Chernoff concentration for the honest samples plus accounting for detected violations. The continuous analogue should use the same thresholds as Algorithm 3, with \(G\) replacing \(\Gamma\). A full theorem would still need a uniform finite-\(q\) convergence bound and a precise representation theorem for \(V\).
The second anchor is Theorem 5.5, “Lower Bound,” proved by the authors, with details deferred to their full version [7]. It states that for sufficiently large \(n\), some supermodular game requires at least
\[ \frac{nC}{10\epsilon} \]
P-samples to obtain \(\epsilon\)-expected maximin security under SeqPerm, for \(1/n\le\epsilon\le0.01\) and \(1\le C\le\epsilon n\).
Its continuous counterpart is:
Expected Typed-Permutation Maximin\(_\infty\). Given \(T,\mu,V\), a focal type \(h\), a known violation budget \(C\), and \(\epsilon\), determine the minimum \(R\) for which the average reward of a focal type-\(h\) representative satisfies
\[ \inf_{\mathrm{Adv}} \mathbb E[\widehat a_h] \ge (1-\epsilon)a_h(\mu), \]
where the infimum ranges over rushing adversaries obeying the same detected-violation budget and the protocol may use SeqPerm.
The expected direction is again Class A, but with a meaningful quantitative lower-bound frontier. The paper’s Lemma 5.1 gives an upper bound of order
\[ O\!\left(\frac{\Gamma_h^\infty C}{\epsilon}\right), \]
while the continuous research question is whether a finite-type supermodular family can realize a matching lower bound. Theorem 5.5 supplies the exact reason to ask this: does its hard sampling regime survive after player identities are compressed into a smooth type-level value function? If it does, the lower bound transfers. If it does not, the collapse is itself a continuum-specific tractability phenomenon.
This mirror is recognizable to the authors because it preserves their central objects: coalitional utility, Shapley allocation, random permutations, rushing adversaries, detected violations, maximin security, and sample complexity. The high-multiplicity scenario is also credible: many recurring data owners or collaboration-network participants can share complete contribution and protocol profiles, while \(\tau\) remains moderate.
The weakest point is that the paper’s security guarantee is for an individual honest player. A literal atomless population has no pivotal individual, and aggregate random-permutation fluctuations disappear by a law-of-large-numbers effect. The proposed mirror therefore retains a uniformly selected focal member of a high-multiplicity type and scales \(v_q\) so that per-clone marginal values remain nonzero. That is an extension, not a theorem already contained in the paper. If one insists that only positive-mass aggregate security counts, the protocol’s sampling problem may largely collapse. Also, arbitrary black-box \(v:2^N\to\mathbb R_+\) does not admit this compression; the mirror requires a genuine typed, scalable \(V\).
The scope is consequently narrow but substantial: Sections 3–5, especially Theorem 4.6 and Theorem 5.5. It does not claim a continuous analogue of exact Shapley computation for arbitrary games, nor of the cryptographic commitment construction itself.
The strongest negative case is that the paper’s security guarantee is fundamentally about a named individual in a finite protocol, whereas continuization removes exactly the structure that makes the guarantee nontrivial.
Theorem 4.6 does not study a population allocation. It studies the reward of one honest player when every other named player may be controlled, may rush, and may abort. In a scalable typed family \(v_q(S)=qV(|S\cap T_1|/q,\ldots,|S\cap T_\tau|/q)\), there are only two possible limits.
If the target is the reward of a positive-mass type, then one random permutation already has an essentially deterministic aggregate effect:
\[ \frac{1}{q}\sum_{i\in T_h}\Delta_i v_q \longrightarrow \mu_h\int_0^1 D_h(\lambda\mu)\,d\lambda . \]
The fluctuations that Theorem 4.6 controls are fluctuations of one player’s rank; they disappear after aggregation. A fixed violation budget damages only \(O(1)\) players and therefore has vanishing relative effect. Scaling the budget with \(q\) produces a mass-contamination model, but then the paper’s “one honest player versus all others” security predicate has been replaced by a different adversarial model.
If the target remains one focal type-\(h\) representative, then the limit
\[ \int_0^1D_h(\lambda\mu)\,d\lambda \]
is mathematically coherent, but the representative has measure zero. The question is no longer about the continuous society’s allocation; it is about a tagged discrete particle embedded in it. Moreover, a genuine P-sample still requires \(q\) commitments, openings, and marginal-contribution evaluations. A \(q\)-independent procedure that samples \(U\) and evaluates \(D_h(U\mu)\) is not the paper’s distributed permutation protocol; it is an Aumann–Shapley-style oracle model introduced by the proposed mirror.
Thus the proponent’s version of Theorem 4.6 has a real dichotomy: aggregate the population and the security problem degenerates, or retain a tagged individual and the population has ceased to be the computational object. This is a modelling obstruction, not merely the possibility that the continuous answer is easy.
The same problem is sharper for Theorem 5.5. SeqPerm eliminates named players one at a time. There is no first player, last player, or finite sequence of individual eliminations in an atomless population. A finite-\(q\) approximation still has \(q\) protocol phases and \(q\)-scale communication; its limit is not an executable SeqPerm protocol.
The theorem’s lower bound also depends on a discrete \(n\)-player construction with a large max-to-mean ratio and a finite violation budget. In a fixed finite-type smooth model, the corresponding
\[ \Gamma_h^\infty = \frac{\sup_{z\le\mu}D_h(z)} {\int_0^1D_h(\lambda\mu)\,d\lambda} \]
is a property of \(V\), not a growing population parameter. To recover the theorem’s \(n\)-dependent lower bound, one must let \(V\), the type space, or the description of the rare high-marginal event depend on \(q\). That reintroduces the discrete combinatorial structure the continuum was meant to remove. Otherwise, one obtains a new robust-estimation question for the scalar random variable \(D_h(U\mu)\), not a continuous counterpart of the SeqPerm lower bound.
The paper’s cited \(\#P\)-hardness of exact Shapley computation cannot rescue either anchor: it is not the paper’s result, and arbitrary set functions do not admit a fixed finite type description. A type compression is valid only after imposing a new anonymous, scalable representation of \(v\), and under that representation the security target either aggregates away or becomes a tagged-agent problem.
This is not a proof that continuous cooperative-game models could never be interesting. The proposed \(V\)-based construction is a legitimate research direction. But it does not provide a worthwhile continuous mirror of these two results: Theorem 4.6 survives only by retaining a zero-mass individual and an oracle abstraction, while Theorem 5.5 survives only by retaining \(q\)-dependent discrete structure. The paper therefore offers no convincing population-continuization target for the ChoCo programme.
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.