Abstract
This paper contains two results on influence in collective decision games. The first part deals with general perfect information coin-flipping games as defined in [3]. Baton passing (see [8]), an n-player game from this class is shown to have the following property: If S is a coalition of size at most {Mathematical expression}, then the influence of S on the game is only {Mathematical expression}. This complements a result from [3] that for every k there is a coalition of size k with influence Ω(k/n). Thus the best possible bounds on influences of coalitions of size up to this threshold are known, and there need not be coalitions up to this size whose influence asymptotically exceeds their fraction of the population. This result may be expected to play a role in resolving the most outstanding problem in this area: Does every n-player perfect information coin flipping game have a coalition of o(n) players with influence 1-o(1)? (Recently Alon and Naor [1] gave a negative answer to this question.) In a recent paper Kahn, Kalai and Linial [7] showed that for every n-variable boolean function of expectation bounded away from zero and one, there is a set of {Mathematical expression} variables whose influence is 1-o(1), where w(n) is any function tending to infinity with n. They raised the analogous question where 1-o(1) is replaced by any positive constant and speculated that a constant influence may be always achievable by significantly smaller sets of variables. This problem is almost completely solved in the second part of this article where we establish the existence of boolean functions where only sets of at least {Mathematical expression} variables can have influence bounded away from zero. © 1993 Akadémiai Kiadò.