J. Math. Anal. Appl. 343 (2008) 1098–1102 www.elsevier.com/locate/jmaa
Approximate equilibria for Bayesian games ✩ Lina Mallozzi a , Lucia Pusillo b,∗ , Stef Tijs b,c a Department of Mathematics and Applications, University of Naples Federico II, via Claudio 21, 80125 Naples, Italy b Department of Mathematics, University of Genoa, via Dodecaneso 35, 16146 Genoa, Italy c CentER and Department of Econometrics and Operations Research, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands
Received 30 November 2006 Available online 9 February 2008 Submitted by J.A. Filar
Abstract In this paper the problem of the existence of approximate equilibria in mixed strategies is central. Sufficient conditions are given under which approximate equilibria exist for non-finite Bayesian games. Further one possible approach is suggested to the problem of the existence of approximate equilibria for the class of multicriteria Bayesian games. © 2008 Elsevier Inc. All rights reserved. Keywords: Non-cooperative games; Bayesian equilibria; Approximate equilibria
1. Introduction The theory of strategic games with complete information starts with the works of J. von Neumann [10] and J. Nash [5]. Harsanyi in [3] introduces games with incomplete information, i.e. games where players are not completely informed about the real-valued payoff functions of the other players. He proves the existence of Bayesian equilibria (BE for short) for the case when the pure strategy spaces are finite. In this paper we consider situations where one of the players may have an infinite set of pure strategies, one criterium and a finite number of types and we are interested in the existence of approximate equilibria (-BE for short). The work of A. Wald [13] indicates already that it is difficult to obtain general equilibrium results if more than one player has a large strategy space. At the end of the paper we give a suggestion to study equilibria (approximate and exact) for multicriteria Bayesian games (MB-games for short). The outline of the paper is as follows. In Section 2 we introduce the Bayesian games (B-games) and the natural equilibrium concept of Bayesian equilibrium. We recall that in case when the type spaces and action spaces are finite there exists a BE in mixed strategies. In Section 3 we study B-games with finite type spaces and all but one finite action spaces. An upper boundedness condition guarantees then the existence of -B equilibria. ✩
Supported by MUR (Ministero Università e Ricerca, Italy).
* Corresponding author.
E-mail addresses:
[email protected] (L. Mallozzi),
[email protected] (L. Pusillo),
[email protected] (S. Tijs). 0022-247X/$ – see front matter © 2008 Elsevier Inc. All rights reserved. doi:10.1016/j.jmaa.2008.01.102
L. Mallozzi et al. / J. Math. Anal. Appl. 343 (2008) 1098–1102
1099
In Section 4 we consider multicriteria Bayesian games and we give some suggestions for further research. 2. Bayesian games A Bayesian game (B-game for short) models a conflict situation with incomplete information. The incomplete information is described with the aid of a type space for each player and a probability distribution on the set of type space profiles. In this paper we restrict our attention to finite type spaces. To be more concrete an n-person B-game is a tuple: Γ = N, A1 , A2 , . . . , An , T1 , T2 , . . . , Tn , p, u1 , u2 , . . . , un , for short: Γ = N, A, T , p, u. Here – – – –
N = {1, 2, . . . , n} is the set of players; for each i ∈ N the action space is Ai , and A = i∈N Ai , the type space is Ti ; p is a probability distribution on the set T = i∈N Ti of type profiles; ui : A × T → R is the payoff function which assigns to player i the payoff ui (a1 , a2 , . . . , an , t1 , t2 , . . . , tn ) given that the players 1, 2, . . . , n have type t1 , t2 , . . . , tn and choose actions a1 , a2 , . . . , an respectively.
A play of such a game proceeds as follows: before the types are announced each player i chooses a strategy xi ∈ ATi i (where then action xi (ti ) is chosen if ti turns out to be the type of player i). Each type profile t results then for player i in a payoff ui (x1 (t1 ), . . . , xn (tn ), t1 , . . . , tn ). The a priori expected payoff for player i, if the players use strategies x1 , . . . , xn equals: Ui (x1 , . . . , xn ) = p(t)ui x1 (t1 ), x2 (t2 ), . . . , xn (tn ), t . t∈T
Let > 0. An approximate Bayesian equilibrium (for short -BE) of N, A, T , p, u is a strategy profile (xˆ1 , xˆ2 , . . . , xˆn ) ∈ AT1 1 × AT2 2 × · · · × ATnn such that for each i ∈ N , each xi ∈ ATi i , Ui (xˆ1 , xˆ2 , . . . , xˆn ) Ui (xˆ−i , xi ) − . Here (xˆ−i , xi ) := (xˆ1 , . . . , xˆi−1 , xi , xˆi+1 , . . . , xˆn ), the profile which we obtain when player i deviates from xˆi to xi . Remark 2.1. If in Γ the type spaces are trivial, i.e. |T1 | = |T2 | = · · · = |Tn | = 1 then we can write N, A, u and we obtain a classical game in strategic form with complete information (C-game for short) and an -BE boils down to an -NE (approximate Nash equilibrium). We will need the notion of f -mixed extension of a B-game for existence results of equilibria. The letter “f ” in f -mixed extension stands for finite because we allow only finite mixtures of pure strategies to avoid convergence problems. Let Γ = N, A1 , A2 , . . . , An , T1 , T2 , . . . , Tn , p, u1 , u2 , . . . , un . Then the f -mixed extension of Γ is the B-game Γ˜ = N, A˜ 1 , A˜ 2 , . . . , A˜ n , T1 , T2 , . . . , Tn , p, u˜ 1 , u˜ 2 , . . . , u˜ n . Here A˜ i is the family of probability measures s (on the σ -algebra of all subsets of Ai ) with finite support. Such prob= ability measures are of the form μ i k=1 pk eak where a1 , a2 , . . . , as ∈ Ai , pk 0, for all k ∈ {1, 2, . . . , s} and s k=1 pk = 1, where 1 if B ⊂ Ai , ak ∈ B, eak (B) = 0 if B ⊂ Ai , ak ∈ / B. Further u˜ i (μ1 , μ2 , . . . , μn , t) = ui (a1 , a2 , . . . , an , t) dμ1 (a1 ) dμ2 (a2 ) . . . dμn (an ) for all i ∈ N and (μ1 , μ2 , . . . , μn ) ∈ A˜ = i∈N A˜ i . A B-game is called a finite game if the action spaces A1 , A2 , . . . , An are finite sets. For finite C-games Γ , Nash in [5] proves that the f -mixed extension Γ˜ possesses an equilibrium point and for finite B-game Γ , Harsanyi in [3] proves the existence of Bayesian equilibrium for the mixed extension Γ˜ . In both proofs fixed point theorems are used.
1100
L. Mallozzi et al. / J. Math. Anal. Appl. 343 (2008) 1098–1102
3. Almost finite B-games and approximate equilibria We will call a B-game Γ = N, A1 , A2 , . . . , An , T1 , T2 , . . . , Tn , p, u1 , u2 , . . . , un almost finite if (i) N, A1 , A2 , . . . , An−1 , T1 , T2 , . . . , Tn are finite sets and An is infinite, (ii) un : A × T → R is an upper bounded function. Let > 0. We are interested in the existence of -BE for Γ˜ . Our main result in this section is: Theorem 3.1. Let Γ be an almost finite game. Then for each > 0 there is an -BE for Γ˜ . Proof. (i) Take > 0. The proof is based on the following claim which we prove at the end of this section. Claim. Given Γ , there is a finite B-subgame Γ () of Γ with
Γ () = N, A1 , . . . , An−1 , An (), T1 , T2 , . . . , Tn , p, u1 , . . . , un , where An () is a finite subset of An such that for each an ∈ An there is an an () ∈ An () such that for all t ∈ T , a−n ∈ A−n = n−1 i=1 Ai , we have un a−n , an () , t un (a−n , an ), t − . (3.1) [So an () is -almost as good as an for player n.] We call Γ () an -approximation of Γ . (ii) Using the above claim we prove that the f -mixed extension Γ˜ () of Γ () is an -approximation of Γ˜ , i.e. for each ν = (νtn )tn ∈Tn ∈ A˜ Tnn there is a ν = (νtn )tn ∈Tn ∈ (A˜ n ())Tn such that for all t ∈ T , μ−n ∈ A˜ −n , we have u˜ n μ−n , νtn , t u˜ n (μ−n , νtn , t) − . (3.2) For the proof note that the Claim implies that we can define a selection β : An → An () such that β(a) = a for each a ∈ An () and un a−n , β(an ) , t un (a−n , an ), t − (3.3) for each t ∈ T , a−n ∈ A−n , an ∈ An \ An (). Given ν ∈ A˜ Tnn and t ∈ T , νt is a finite sum of the form νtn {a} ea . a∈An
Take νtn =
ν(a): β(a) = b eb . b∈An ()
a∈An
Then (νtn )tn ∈Tn ∈ (A˜ n ())Tn , and (3.2) follows from (3.3).
n−1 × A˜ n ()Tn of (iii) By Harsanyi’s theorem we can find a mixed B-equilibrium (ˆν1 , νˆ 2 , . . . , νˆ n ) ∈ A˜ T1 1 × · · · × A˜ n−1 the mixed extension Γ˜ () of the finite game Γ (). Define for each μ ∈ A˜ n ()Tn the mixed strategy α(μ) by α(μ)(C) = μ(C ∩ An ()) for each finite C ⊂ An . We prove that (ˆν1 , νˆ 2 , . . . , νˆ (n−1) , (α((ˆνn )tn ))tn ∈Tn ) is an -B equilibrium of Γ˜ . In the following we shall write U˜ i for the a priori expected payoff of player i in the mixed extension Γ˜ of Γ .
T
L. Mallozzi et al. / J. Math. Anal. Appl. 343 (2008) 1098–1102
1101
First, note that for each i ∈ N \ {n}, μi ∈ A˜ Ti i we have U˜ i (ˆνk )k∈N \{i,n} , μi , α (ˆνn )tn t ∈T = p(t)u˜ i νˆ k (t) k∈N \{i,n} , μi (t), α (ˆνn )tn , t n
n
t∈T
=
p(t)u˜ i νˆ k (t) k∈N \{i,n} , μi (t), νˆ n (t), t
t∈T
= U˜ i (ˆνk )k∈N \{i,n} , μi , νˆ n U˜ i (ˆνk )k∈N , where the last inequality follows from the fact that νˆ is a mixed B-equilibrium of Γ˜ (). So, deviation from νˆ i to μi does not pay for player i ∈ N \ {n}. Secondly, note that for player i = n deviation from α((ˆνn )t )t∈T to μn ∈ A˜ Tnn pays at most 2 because p(t)u˜ n νˆ k (t) k∈N \{n} , μn (t), t U˜ n (ˆνk )k∈N \{n} , μn =
t∈T
p(t)u˜ n νˆ k (t) k∈N \{n} , μn (t) t∈T , t +
t∈T
p(t)u˜ n νˆ k (t) k∈N , t + 2
t∈T
= U˜ n (ˆνk )k∈N \{n} , α (ˆνn )t t∈T + 2, where the first inequality follows from (3.2) and the second inequality from the fact that (ˆν1 , νˆ 2 , . . . , νˆ n−1 , νˆ n ) is an -B equilibrium of Γ˜ (). 2 It remains to prove the Claim in the proof of Theorem 3.1. For this objective the following two theorems are helpful. A proof of Theorem 3.2 can be found in [9]. Theorem 3.2 (Finite covering property by orthants for upper bounded sets in a Euclidean space). For each upper bounded set V in Rn and each > 0, there is a finite subset W of V such that
V⊂ O(w, ) s.t. w ∈ W , where O(w, ) is the orthant
x ∈ Rm s.t. xi wi + ∀i ∈ {1, 2, . . . , m} . (We shall say that W -dominates V .) A direct consequence of this theorem is the next Theorem 3.3, which one can also find in [8, Lemma 4.3]. For convenience of the reader we give also the proof. Theorem 3.3. Let E be a finite set, > 0 and let F be an upper bounded family of real-valued functions on E. Then there exists a finite subfamily G of F which -dominates F , i.e. ∀f ∈ F ∃g ∈ G ∀x ∈ E f (x) g(x) + . Proof. Let E = {a1 , a2 , . . . , am }. For each f ∈ F let α(f ) be the vector (f (a1 ), f (a2 ), . . . , f (am )) in Rm . Since F is an upper bounded family of functions, the set V = {α(f ) | f ∈ F} is an upper bounded subset of Rm . In view of Theorem 3.2 we can find a finite subset W of V , which -dominates V . But then G = {f ∈ F | α(f ) ∈ W } is a finite subfamily of F which -dominates F . 2 Now we are able to give the Proof of the Claim in Theorem 3.1. Given > 0 and the almost finite game Γ = N, A1 , . . . , An−1 , An , T1 , T2 , . . . , Tn , p, u1 , . . . , un
1102
L. Mallozzi et al. / J. Math. Anal. Appl. 343 (2008) 1098–1102
an : E → R we note that E = ( n−1 i=1 Ai ) × T is a finite set. For each an ∈ An we define the upper bounded function f by f an (a1 , a2 , . . . , an−1 , t) = un (a1 , a2 , . . . , an , t)
for each (a1 , a2 , . . . , an−1 , t) ∈ E.
= {f an
The family F | an ∈ An } is an upper bounded family of real functions on E. By Theorem 3.3 we can find a subfamily G of F which -dominates F . Clearly, each element g ∈ G corresponds to an element bn ∈ An , i.e. g = f bn . Let us denote the set {bn ∈ An | ∃g ∈ G [f bn = g]} by An (). The -dominance of F by G implies that for each f an in F there is an f bn ∈ G such that for all (a−n , t) ∈ E: b f n (a−n , t) f an (an , t) − , or, equivalently, un (a−n , bn ), t un (a−n , an ), t − . (3.4) By taking an () = bn in (3.4) we obtain (3.1).
2
4. Concluding remarks We established the existence of approximate Bayesian equilibria in mixed strategies for finite B-games. Using the covering theorem and then the approximation with finite games, the existence of -B equilibria is established for almost finite B-games with upper bounded payoff functions. There are many topics for further research. First of all one can tackle the problem of the existence of approximate equilibria for Bayesian multicriteria games (BM-games). BM-games are Bayesian games where the players have vector-valued objective functions. As a first approach to the problem of existence of approximate equilibria for BM-games we could transform such a BM game Γ into a B-game Γ1 by replacing the criteria of each player by one criterium by taking as utility function for a player a weighted average of the utility function for the various criteria of that player. Then an approximate equilibrium of Γ1 can be seen as an approximate equilibrium of Γ . A more interesting sophisticated approach to BM-games can be interesting (see [1,6,7]). Further it could be interesting to study B-games where all (or all but one) strategy spaces are compact sets and the payoff functions satisfy suitable continuity and concavity properties guaranteeing approximate B-equilibria (or -B equilibria). For a subclass of strategic games such a research was done in [8]. Another topic for further research could be the study of BM-games with a potential [2,4,11,12]. Some of these topics are work in progress. Acknowledgments We thank Fioravante Patrone and Rodica Branzei for helpful comments.
References [1] P.E.M. Borm, S.H. Tijs, J.C.M. van den Aarssen, Pareto equilibria in multiobjective games, Methods Oper. Res. 60 (1988) 303–312. [2] G. Facchini, F. van Megen, P.E.M. Borm, S.H. Tijs, Congestion models and weighted Bayesian potential games, Theory and Decision 42 (1997) 193–206. [3] J. Harsanyi, Games with incomplete information played by Bayesian players, Management Sci. 14 (1967–1968) 159–182, 320–334, 486–502. [4] D. Monderer, L.S. Shapley, Potential games, Games Econom. Behav. 14 (1996) 124–143. [5] J.F. Nash Jr., Equilibrium points in n-person games, Proc. Natl. Acad. Sci. USA 36 (1950) 48–49. [6] L.S. Shapley, Equilibrium points in games with vector payoffs, Naval Res. Logist. Quart. 6 (1959) 57–61. [7] R.E. Steuer, L.R. Gardiner, J. Gray, A bibliographic survey of the activities and international nature of multiple criteria decision making, J. Multi-Criteria Decision Anal. 5 (1996) 195–217. [8] S.H. Tijs, Nash equilibria for noncooperative n-person games in normal form, SIAM Rev. 23 (1981) 225–237. [9] S. Tijs, H. Reijnierse, Finite covering by cones and an application in multiobjective programming, Positivity 7 (2003) 61–72. [10] J. von Neumann, Zur Theorie der Gesellschaftsspiele, Math. Ann. 100 (1928) 295–320. [11] M. Voorneveld, Equilibria and approximate equilibria in infinite potential games, Econom. Lett. 56 (1997) 163–169. [12] M. Voorneveld, Potential games and interactive decisions with multiple criteria, PhD thesis CentER, Center Dissertation Series 61, Tilburg University, 1999. [13] A. Wald, Generalization of a theorem by Neumann concerning zero sum two-person games, Ann. of Math. 46 (1945) 281–286.
