This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Gradwohl, R. Articles by Yehudayoff, A.

Players' Effects Under Limited Independence

Kellogg School of Management, Northwestern University, Evanston, Illinois 00208
Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, 76100 Israel
Statistical Laboratory, DPMMS, Cambridge CB3 0WB, United Kingdom
School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
r-gradwohl{at}kellogg.northwestern.edu, http://www.kellogg.northwestern.edu/faculty/directory/gradwohl_ronen.aspx
omer.reingold{at}weizmann.ac.il, http://www.wisdom.weizmann.ac.il/reingold
yadin{at}statslab.cam.ac.uk, http://www.statslab.cam.ac.uk/ariel
amir.yehudayoff{at}gmail.com

In a function that takes its inputs from various players, the effect of a player measures the variation he can cause in the expectation of that function. In this paper we prove a tight upper bound on the number of players with large effect, a bound that holds even when the players' inputs are only known to be pairwise independent. We also study the effect of a set of players, and show that there always exists a "small" set of players that, when eliminated, leaves every small set with little effect. Finally, we ask whether there always exists a player with positive effect, and show that, in general, the answer is negative. More specifically, we show that if the function is nonmonotone or the distribution is only known to be pairwise independent, then it is possible that all players have zero effect.

Key Words: games; effect; influence
History: Received: March 4, 2008; revision received: May 10, 2009;