Skip to main content
Top
Published in: Social Choice and Welfare 3/2018

26-03-2018 | Original Paper

The role of aggregate information in a binary threshold game

Authors: Bo Chen, Rajat Deb

Published in: Social Choice and Welfare | Issue 3/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We analyze the problem of coordination failure in the presence of imperfect information in the context of a binary-action sequential game with a tipping point. An information structure summarizes what each agent can observe before making her decision. Focusing on information structures where only “aggregate information” from past history can be observed, we characterize information structures that can lead to various (efficient and inefficient) Nash equilibria. When individual decision making can be rationalized using a process of iterative dominance (Moulin, Econometrica 47:1337–1351, 1979), we derive a necessary and sufficient condition on information structures under which a unique and efficient dominance solvable equilibrium outcome is obtained. Our results suggest that if sufficient (and not necessarily perfect) information is available, coordination failure can be overcome without centralized intervention.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
We provide a detailed discussion on the rationale and justification of the solution concept of iterated weak dominance in Sect. 4.1. In particular, we also discuss there the relationship between our dominance-solvable solution concept and the more standard solution concept of perfect Bayesian equilibrium for our game.
 
2
Granovetter (1978) studies a binary threshold model where a group of agents with different thresholds decides whether to participate in a riot. Binary threshold models have also been applied to segregation (Schelling 1969), public good games (Dawes et al. 1986), crime (Glaeser et al. 1996), etc. Chwe (2001) contains an array of social phenomena involving coordination with thresholds.
 
3
Schelling (1973) considers a similar but static model of binary choices with externalities where the agents’ preferences are given by a utility function \(g:\{1,0\}\times \{0,\ldots ,n-1\}\rightarrow \mathbb {R} \), and for \(\alpha \in \{0,\ldots ,n-1\}\), \(g(1,\alpha )\) (resp., \(g\left( 0,\alpha \right) \)) is the value of participating (resp., not participating) when \(\alpha \) other individuals participate. Our model admits a tipping point (where Schelling’s model may or may not have one) and thus our model is not more general than Schelling’s model. Nor is our model a special case as it allows for types of preferences not modeled by Schelling (see Sect. 4.1).
 
4
It is only needed for Proposition 1 and its associated footnote establishing the connection of our results to the Rawlsian maximum and utilitarian maximum.
 
5
Consequently, agent j knows how many agents from \(\{1,\ldots ,\kappa (j)\}\) have not participated. In some cases, for instance if \(\kappa (j)=1\) or if the report received is equal to \(\kappa (j)\), j is able to deduce not only how many but also who has joined the group.
 
6
If \(\kappa (j)=1\) and \(\kappa (j^{\prime })\) \(=2\), then even though by looking at her signal j knows whether 1 has joined or not joined and \(j^{\prime }\) may not, \(j^{\prime }\) will receive at least as much payoff relevant information as j does, since all that matters for payoffs is how many individuals rather than which individuals have joined.
 
7
We discuss an alternative modeling of information in Sect. 4.1.
 
8
Agent 3 in the information structure \(\mathcal {I}_{2}\) knows whether 1 has moved but does not in the structure \(\mathcal {I}_{3}\). Nevertheless agent 3 has more payoff relevant information in \(\mathcal {I}_{3}\) because the payoffs only depend on the total number of individuals participating.
 
9
If \(f_{j}=f\) is strictly quasi-concave (strictly single peaked), then the intermediate PSNEOs can be partitioned such that PSNEOs with participation levels above \(\lambda \) and below “\(\arg \max \) f” will be inefficient and those with participation levels of “\(\arg \max \) f” and above will be efficient.
 
10
The Rawlsian welfare function is defined as \(W=\max _{a}\min _{j}\left\{ u_{j}\left( a\right) \right\} \). See Sen (1977) and Hammond (1976). In addition, notice that the “utilitarian” welfare function given by the sum of utilities may or may not be maximized at the maximal PSNEO. Adding an individual adds to her utility but because of congestion it may reduce the utility of other participants. Clearly, the preferences being monotone (non-decreasing) in \(\sum b_{j}\) is sufficient for such a maximum.
 
11
As mentioned previously, our dominance solvable outcome is also closely related to the perfect Bayesian equilibrium outcome of the game. A detailed comparison of the two solution concepts in our game is provided in Sect. 4.1.
 
12
We will discuss the issue of the order of elimination in the reduction process in Sect. 4.1. In addition, we only use weak domination in our arguments and we will drop the adjective ‘weak’ hereafter.
 
13
The games in Examples 4 and 5 both have \(\lambda =m^{*}=2\) and are hence dominance solvable. The additional information that agent 2 has in Example 4 (as compared to Example 5) is of no importance in predicting the outcome of the game. In contrast, the game in Example 6 has \(\lambda =3>m^{*}=2\), and is hence not dominance solvable.
 
14
A different concern about iterated weak dominance is that iterated weak dominance is not equivalent to and cannot be grounded by assuming it is common knowledge that players do not play weakly dominated strategies. See Samuelson (1992).
 
15
We thank the referees of our paper for raising our attention on this issue.
 
16
For a justification of the use of such a non-traditional (“quasitransitive” ) preference in games, see Basu and Pattanaik (2014).
 
17
Moulin (1986) and Marx and Swinkels (1997) provide justification for using this concept. Also see Gretlein (1982) for a discussion of this procedure in voting games. The procedure of iterative elimination of weakly dominated strategies has also been applied to chess-like games and two-player strictly competitive games (Ewerhart 2000, 2002), signaling future actions by burning money (Ben-Porath and Dekel 1992), finite dynamic bargaining games (Tyson 2010), and auctions (Azrieli and Levin 2011). Epistemic conditions for the procedure of iterated elimination of weakly dominated strategies are provided in Brandenburger et al. (2008).
 
18
However, since iterated weak dominance can be applied using different orders of elimination, the two procedures (iterated weak dominance and backward induction) can lead to different outcomes and are hence different in general. See Chapter 6.6 of Osborne and Rubinstein (1994).
 
19
It is worth pointing out that a recent study (Koriyama and Núñez 2015) shows that for any finite normal-form game satisfying the TDI condition in Marx and Swinkels (1997) that is dominance solvable by weak dominance, the unique dominance-solvable outcome must coincide with the payoff of a proper equilibrium. This result justifies our dominance solvable outcome—since our game satisfies the TDI condition, our dominance solvable outcome hence also coincides with the outcome of a proper equilibrium of our threshold game. We thank Sean Horan for bringing this to our attention.
 
20
See our discussion of information structure in Sect. 4.1.
 
21
If \(\kappa (j_{2})\ge j_{1}\), \(j_{2}\) would receive the same report under both a and \(\widetilde{a}\), contradicting \(b_{j_{2}}(a)\ne b_{j_{2}}(\widetilde{a})\).
 
22
An alternative and simpler argument for (7) is the following: Given that \(\kappa \left( j_{1}\right) \ge \tilde{j}\ge n-\lambda -\tau \) and \(\kappa \left( j_{1}+1\right) \le \kappa \left( j_{2}\right) <j_{1}\), we have that \(\left\{ j:\kappa \left( j\right) =j_{1}\right\} \subset \left\{ j>j_{2}:j\notin J\right\} \), i.e., the agents whose information exactly covers \(j_{1}\) (hence such agents are not in J) belong to those who move after \(j_{2}\). The fact that the set \(\left\{ j>j_{2}:j\notin J\right\} \) has at most “\(n-\left( j_{1}+1\right) +1-\left( \tau -1\right) \)” agents directly implies (7). We thank a referee for pointing this out.
 
23
To be specific, agents \(j^{*}\) and \(\left( j^{*}+1\right) \) both observe \(\left( j^{*}-n+\lambda +\tau -1\right) \) previous agents joining before j’s deviation and \(\left( j^{*}-n+\lambda +\tau \right) \) agents joining after j’s deviation.
 
24
Since \(n-j^{*}-\tau -1\ge |\{j:\kappa \left( j\right) =j^{*}\}|,\) there are at most \((n-j^{*}-\tau -1)\) such agents.
 
25
Since \(\kappa \left( j^{\prime }\right) \ge j^{*}+1\), one is added to \(j^{\prime }\)’s information report because \(j\in J_{1}\) joins, while two is subtracted from \(j^{\prime }\)’s report because \(j^{*}\) and \(j^{*}+1\) have switched to “not join.”
 
26
The results in Lemma 1(i) are stated in the form of a set of coordinates rather than an individual coordinate. We choose this somewhat cumbersome formulation to simplify our proof for Lemma 1(ii).
 
27
For all games \(\mathcal {G}_{h}\in \{\mathcal {G}_{0},\ldots ,\mathcal {G}_{M}\} \), \(\mathcal {P\cap NP}\left( r\right) =\varnothing \) for all \(r\ge 1\) and both \(\mathcal {P}\) and \(\mathcal {NP}\left( r\right) \) are non-empty in \(\mathcal {G}_{0}\) for all possible values of \(r\ge 1\).
 
28
A similar argument cannot be applied to the PSNE with \( \sum _{N}b_{j}(a)=0\) as under certain information structure, \( a_{1}=a_{1}\left( 1\right) =0\) may no longer be a BRCA at some stage of the reduction process.
 
29
In \(\mathcal {G}_{0}\), since all strategies are possible, the set of strategies for which this is true is non-empty.
 
30
It is possible that \(\left\{ \mathcal {G}_{i}^{\lambda -k}\right\} \) is a singleton with \(\mathcal {G}_{\min }^{\lambda -k}=\mathcal {G}_{\max }^{\lambda -k}\).
 
31
It is possible for some \(j>i_{2}\) to have \(a_{j}\left( \lambda -1\right) =0\) for all \(a_{j}\in \mathcal {G}_{h}\). For example, consider agent n.
 
32
The key difference between Basis Step and Inductive Step is that an agent j (with \(j>i_{s+1}\)) may be covered by another agent \(j^{\prime }\) in Inductive Step while an agent j (with \(j>i_{2}\)) cannot be covered by any agent in Basis Step. This creates additional complications in constructing the contingency \(a_{-j}\) toward the result of \(a_{j}\left( \lambda -s\right) =0\) being a BRCA in Inductive Step.
 
33
Since \(\mathcal {G}_{1}\) belongs to this block, it is nonempty.
 
34
Observe that for the \(l{\text {th}}\) coordinate of an agent j to be reduced to 1, it must be the case that \(\kappa (j)\ge l-1\). This implies that when we have dominance solvability, the hypothesis of the non-reduction Lemma 6 is true for each of the blocks \(\left\{ \mathcal {G}_{i}^{\lambda -k}\right\} _{\lambda -1\ge k\ge 1}\).
 
35
Notice that agent \(i_{1}\) observes the aggregate participation level among all agents in \(\left\{ 1,\ldots ,i_{2}\right\} \), but not the participation outcome of i for \(i_{1}>i>i_{2}\). Given that we only focus on payoff-relevant information, there is no uncertainty about the participation history of agents in \(\left\{ 1,\ldots ,i_{2}-1\right\} \)—recall the \(\mathcal {I}\)-monotonicity Assumption 3. Hence, agent \(i_{1}\)’s beliefs in her information sets should only be on the unobservable choices of i for \(i_{1}>i>i_{2}\).
 
Literature
go back to reference Azrieli Y, Levin D (2011) Dominance-solvable common-value large auctions. Games Econ Behav 73:301–309CrossRef Azrieli Y, Levin D (2011) Dominance-solvable common-value large auctions. Games Econ Behav 73:301–309CrossRef
go back to reference Basu K, Pattanaik P (2014) Nash equilibria of games when players’ preferences are quasi-transitive. Mimeo Basu K, Pattanaik P (2014) Nash equilibria of games when players’ preferences are quasi-transitive. Mimeo
go back to reference Ben-Porath E, Dekel E (1992) Signaling future actions and the potential for sacrifice. J Econ Theory 57:36–51CrossRef Ben-Porath E, Dekel E (1992) Signaling future actions and the potential for sacrifice. J Econ Theory 57:36–51CrossRef
go back to reference Brandenburger A, Friedenberg A, Keisler HJ (2008) Admissibility in games. Econometrica 76:307–352CrossRef Brandenburger A, Friedenberg A, Keisler HJ (2008) Admissibility in games. Econometrica 76:307–352CrossRef
go back to reference Chwe MS-Y (2000) Communication and coordination in social networks. Rev Econ Stud 67:1–16CrossRef Chwe MS-Y (2000) Communication and coordination in social networks. Rev Econ Stud 67:1–16CrossRef
go back to reference Chwe MS-Y (2001) Rational ritual: culture, coordination, and common knowledge. Princeton University Press, Princeton Chwe MS-Y (2001) Rational ritual: culture, coordination, and common knowledge. Princeton University Press, Princeton
go back to reference Dawes RM, Orbell JM, Simmons RT, Van de Kragt A (1986) Organizing groups for collective action. Am Polit Sci Rev 80(4):1171–1185CrossRef Dawes RM, Orbell JM, Simmons RT, Van de Kragt A (1986) Organizing groups for collective action. Am Polit Sci Rev 80(4):1171–1185CrossRef
go back to reference Ewerhart C (2000) Chess-like games are dominance-solvable in at most two steps. Games Econ Behav 33:41–47CrossRef Ewerhart C (2000) Chess-like games are dominance-solvable in at most two steps. Games Econ Behav 33:41–47CrossRef
go back to reference Ewerhart C (2002) Iterated weak dominance in strictly competitive games of perfect information. J Econ Theory 107:474–482CrossRef Ewerhart C (2002) Iterated weak dominance in strictly competitive games of perfect information. J Econ Theory 107:474–482CrossRef
go back to reference Galeotti A, Goyal S, Jackson MO, Vega-Redondo E, Yariv L (2010) Network games. Rev Econ Stud 77:218–244CrossRef Galeotti A, Goyal S, Jackson MO, Vega-Redondo E, Yariv L (2010) Network games. Rev Econ Stud 77:218–244CrossRef
go back to reference Glaeser EL, Sacerdote B, Scheinkman JA (1996) Crime and social interactions. Q J Econ 111:507–548CrossRef Glaeser EL, Sacerdote B, Scheinkman JA (1996) Crime and social interactions. Q J Econ 111:507–548CrossRef
go back to reference Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83:1420–1443CrossRef Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83:1420–1443CrossRef
go back to reference Gretlein R (1982) Dominance solvable voting schemes: a comment. Econometrica 50:527–528CrossRef Gretlein R (1982) Dominance solvable voting schemes: a comment. Econometrica 50:527–528CrossRef
go back to reference Hammond P (1976) Equity Arrow’s conditions, and Rawls’ difference principle. Econometrica 44:793–804CrossRef Hammond P (1976) Equity Arrow’s conditions, and Rawls’ difference principle. Econometrica 44:793–804CrossRef
go back to reference Kohlberg E, Mertens JF (1986) On the strategic stability of equilibria. Econometrica 54:1003–1037CrossRef Kohlberg E, Mertens JF (1986) On the strategic stability of equilibria. Econometrica 54:1003–1037CrossRef
go back to reference Koriyama Y, Núñez M (2015) How proper is the dominance-solvable outcome? Mimeo Koriyama Y, Núñez M (2015) How proper is the dominance-solvable outcome? Mimeo
go back to reference Mailath G, Samuelson L, Swinkels J (1993) Extensive form reasoning in normal form games. Econometrica 61:273–302CrossRef Mailath G, Samuelson L, Swinkels J (1993) Extensive form reasoning in normal form games. Econometrica 61:273–302CrossRef
go back to reference Marx L, Swinkels L (1997) Order independence for iterated weak dominance. Games Econ Behav 18:219–245CrossRef Marx L, Swinkels L (1997) Order independence for iterated weak dominance. Games Econ Behav 18:219–245CrossRef
go back to reference Milgrom P, Roberts J (1990) Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica 58:1255–1277CrossRef Milgrom P, Roberts J (1990) Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica 58:1255–1277CrossRef
go back to reference Moulin H (1979) Dominance solvable voting schemes. Econometrica 47:1337–1351CrossRef Moulin H (1979) Dominance solvable voting schemes. Econometrica 47:1337–1351CrossRef
go back to reference Moulin H (1986) Game Theory for the Social Sciences, 2nd edn. New York University Press, New York Moulin H (1986) Game Theory for the Social Sciences, 2nd edn. New York University Press, New York
go back to reference Osborne MJ, Rubinstein A (1994) A course in game theory. MIT Press, Cambridge Osborne MJ, Rubinstein A (1994) A course in game theory. MIT Press, Cambridge
go back to reference Rochet JC (1980) Selection of a unique equilibrium payoff for extensive games with perfect information. D. P. CEREMADE, Université Paris IX Rochet JC (1980) Selection of a unique equilibrium payoff for extensive games with perfect information. D. P. CEREMADE, Université Paris IX
go back to reference Samuelson L (1992) Dominated strategies and common knowledge. Games Econ Behav 4:284–313CrossRef Samuelson L (1992) Dominated strategies and common knowledge. Games Econ Behav 4:284–313CrossRef
go back to reference Satterthwaite M, Sonnenschein H (1981) Strategy-proof allocation mechanisms at differentiable points. Rev Econ Stud 48:587–97CrossRef Satterthwaite M, Sonnenschein H (1981) Strategy-proof allocation mechanisms at differentiable points. Rev Econ Stud 48:587–97CrossRef
go back to reference Sen A (1977) On weights and measures: informational constraints in social welfare analysis. Econometrica 45:1539–1572CrossRef Sen A (1977) On weights and measures: informational constraints in social welfare analysis. Econometrica 45:1539–1572CrossRef
go back to reference Schelling T (1969) Models of segregation. Am Econ Rev 59:488–493 Schelling T (1969) Models of segregation. Am Econ Rev 59:488–493
go back to reference Schelling T (1973) Hockey helmets, concealed weapons, and daylight saving: a study of binary choices with externalities. J Confl Resolut 17:381–428CrossRef Schelling T (1973) Hockey helmets, concealed weapons, and daylight saving: a study of binary choices with externalities. J Confl Resolut 17:381–428CrossRef
go back to reference Tyson C (2010) Dominance solvability of dynamic bargaining games. Econ Theory 43:457–477CrossRef Tyson C (2010) Dominance solvability of dynamic bargaining games. Econ Theory 43:457–477CrossRef
go back to reference Watts D (2002) A simple model of global cascades on random networks. Proc Natl Acad Sci USA 99:5766–5771CrossRef Watts D (2002) A simple model of global cascades on random networks. Proc Natl Acad Sci USA 99:5766–5771CrossRef
Metadata
Title
The role of aggregate information in a binary threshold game
Authors
Bo Chen
Rajat Deb
Publication date
26-03-2018
Publisher
Springer Berlin Heidelberg
Published in
Social Choice and Welfare / Issue 3/2018
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-018-1122-8

Other articles of this Issue 3/2018

Social Choice and Welfare 3/2018 Go to the issue