Take Action

Home | Faculty & Research Overview | Research

Research Details

Players' Effects under Limited Independence, Mathematics of Operations Research


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 a 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.




Ronen Gradwohl, Omer Reingold, Ariel Yadin, Amir Yehudayoff

Date Published



Gradwohl, Ronen, Omer Reingold, Ariel Yadin, and Amir Yehudayoff. 2009. Players' Effects under Limited Independence. Mathematics of Operations Research. 34(4): 971-980.


Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more


Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.


Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more

Take Action