Players' effects under limited independence

Ronen Gradwohl*, Omer Reingold, Ariel Yadin, Amir Yehudayoff

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)971-980
Number of pages10
JournalMathematics of Operations Research
Volume34
Issue number4
DOIs
StatePublished - Nov 1 2009

Keywords

  • Effect
  • Games
  • Influence

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Players' effects under limited independence'. Together they form a unique fingerprint.

Cite this