We introduce the class of pay or play games, which captures scenarios in which each decision maker is faced with a choice between two actions: one with a fixed payoff and an- other with a payoff dependent on others selected actions. This is, arguably
, the simplest setting that models selection among certain and uncertain outcomes in a multi-agent system. We study the properties of equilibria in such games from both a game-theoretic perspective and a computational perspective. Our main positive result establishes the existence of a semi-strong equilibrium in every such game. We show that although simple, pay of play games contain a large variety of well-studied environments, e.g., vaccination games. We discuss the interesting implications of our results for these environments.
Correlated equilibrium (Aumann, 1974) generalizes Nash equilibrium to allow correlation devices. Aumann showed an example of a game, and of a correlated equilibrium in this game, in which the agents surplus (expected sum of payo s) is greater than th
eir surplus in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature (Koutsoupias & Papadimitriou, 1999;Papadimitriou, 2001) this suggests the study of two major measures for the value of correlation in a game with non-negative payoffs: 1. The ratio between the maximal surplus obtained in a correlated equilibrium to the maximal surplus obtained in a mixed-strategy equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the maximal surplus to the maximal surplus obtained in a correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games (Rosenthal,1973), a class of games that received a lot of attention in the recent literature.
We consider an environment where sellers compete over buyers. All sellers are a-priori identical and strategically signal buyers about the product they sell. In a setting motivated by on-line advertising in display ad exchanges, where firms use secon
d price auctions, a firms strategy is a decision about its signaling scheme for a stream of goods (e.g. user impressions), and a buyers strategy is a selection among the firms. In this setting, a single seller will typically provide partial information and consequently a product may be allocated inefficiently. Intuitively, competition among sellers may induce sellers to provide more information in order to attract buyers and thus increase efficiency. Surprisingly, we show that such a competition among firms may yield significant loss in consumers social welfare with respect to the monopolistic setting. Although we also show that in some cases the competitive setting yields gain in social welfare, we provide a tight bound on that gain, which is shown to be small in respect to the above possible loss. Our model is tightly connected with the literature on bundling in auctions.
