Functions without influential coalitions

2013/08/13 by Jeff Kahn, Gil Kalai, Kahn, Jeff +1 · 1 citation
Computer Science · Economics, Econometrics and Finance · Mathematics · #Complexity and Algorithms in Graphs #Game Theory and Voting Systems #Limits and Structures in Graph Theory #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1308.2794

13 pages

arxiv created 2013/08/13 · arxiv updated 2013/08/14

Abstract

We give counterexamples to a conjecture of Benny Chor and another of the second author, both from the late 80s, by exhibiting functions for which the influences of large coalitions are unexpectedly small relative to the expectations of the functions.

Cited by

• Influential coalitions for Boolean Functions

Related

• Influential coalitions for Boolean Functions
• KKL theorem for the influence of a set of variables
• Coalition or non-coalition: Greedy scalar equilibrium in the semi-cooperative game with the role of speculators in the game between fiscal and monetary policy-makers
• The Impact of a Coalition: Assessing the Likelihood of Voter Influence in Large Elections
• Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions