Abstract
In Bayesian games, standard equilibrium concepts often fail to account for coordinated collusion, while traditional strong equilibrium concepts are frequently too restrictive to exist in practice. This paper introduces two new solution concepts—ex-ante Bayesian $k$-strong equilibrium ($k$-EBSE) and Bayesian $k$-strong equilibrium ($k$-BSE)—to model strategic collusion within groups of limited size $k$. By applying these concepts to peer prediction mechanisms, the authors derive exact mathematical thresholds for collusion robustness, offering a quantitative metric for designing systems resilient to group-level cheating.
Introduction
Game theory typically relies on the Bayesian Nash Equilibrium to predict outcomes where players have private information. However, this model assumes players act strictly in their own individual interest, ignoring the possibility of collusion. While "strong" or "coalitional" equilibrium concepts exist, they often assume that any group of any size can coordinate perfectly. In many practical applications like crowdsourcing or voting, this leads to "non-existence" results where no strong equilibrium can be found.
In reality, collusion is often bounded by group size—small botnets or groups of friends coordinating to game a system. This paper bridges the gap between individual rationality and infinite collusion by studying games where the maximum size of a deviating group is capped at an integer $k$.
Proposed Solution Concepts
The authors propose two distinct ways to define robustness against bounded collusion:
- Ex-ante Bayesian $k$-strong equilibrium ($k$-EBSE): A group of size $\le k$ will not deviate if they cannot improve their joint expected utility before they receive their private signals.
- Bayesian $k$-strong equilibrium ($k$-BSE): A more conservative concept where a group will not deviate unless the move is profitable for every member after receiving their signals, regardless of what those signals are.
Because $k$-BSE requires a deviation to be universally beneficial across all possible signal realizations, it is a "weaker" requirement for equilibrium than $k$-EBSE, making mechanisms naturally more robust under this definition.
Analysis of Peer Prediction Mechanisms
The core application of these concepts is in Peer Prediction Mechanisms, which are used to elicit honest information (e.g., image labels) when no ground truth is available. The authors use convexity arguments to identify the exact "tipping point" $k$—the maximum number of colluders a mechanism can withstand before truth-telling is no longer an equilibrium.
As shown in the figure above, the equilibrium space is defined by linear boundaries related to the conditional probabilities of signals ($q(l|h)$, $q(h|h)$, etc.). For truth-telling to be maintained, the expected reports of others must fall within the region where agents with either signal ($h$ or $l$) lack the incentive to deviate. The paper provides explicit formulas for these thresholds based on the number of agents $n$, the common prior distribution, and the scoring rule employed.
Key Results and Robustness
The paper establishes a clear dichotomy: for any group size larger than the calculated threshold $k$, truth-telling fails to be an equilibrium; for any size smaller or equal to $k$, it remains stable. This allows the value of $k$ to serve as a "security parameter" for mechanism designers.
Furthermore, the research highlights that robustness is highly sensitive to the choice of scoring rule. For instance, the Log scoring rule may provide higher collusion thresholds than the Brier scoring rule in specific environments. Beyond peer prediction, these concepts provide fine-grained insights into other strategic environments, such as Private Blotto games and voting systems, where $k$ represents the level of coordination among participants.
Limitations and Future Work
While the current analysis provides a robust framework for binary signal spaces, extending these results to multi-signal environments remains a key area for future research. Additionally, the model currently assumes a "common prior" and perfect coordination within the deviating group. Future work could explore the impact of heterogeneous beliefs and communication constraints on the stability of these bounded strong equilibria.
Summary updated