Transition Models of Equilibrium Assessment in Bayesian Game
1 like966 views
This document summarizes a presentation on modeling the dynamics of equilibrium assessment in Bayesian games. The presentation introduces a static Bayesian game with two players and two actions. It then derives a novel condition for a Bayesian Nash equilibrium involving polynomials. This condition allows discovering a discrete-time dynamical system whose state involves an equilibrium assessment. The dynamics map one equilibrium assessment to another over time. Simulation results confirm the states converge over time.
![Introduction
3
Strategic game enabling to consider uncertainties in player¡¯s decisions.
player: a reasonable decision maker
action: what a player chooses
utility: a player¡¯s preference over the actions
type: a label of player¡¯s private valuation (what the player really feels)
belief: a probability distribution over the types
(degree of feeling, tendency, proclivity,¡)
Static Bayesian Game[1]
[1] Harsanyi, 1967. [2] Alpcan and Basar, et al., 2011, 2013. [3] Roy, et al., 2010. [4] Liu, et al., 2006. [5] Akkarajitsakul, et al., 2011.
A Bayesian game used in engineering problems to analyze a Bayesian
Nash equilibrium or to design a game mechanism.
network security[2,3], intrusion detection[4,5,6], belief learning[7]
electricity pricing[8,9], mechanism design[10]
[6] Sedjelmachi, et al., 2014, 2015. [7] Nachbar, 2008. [8] Li, et al., 2011, 2014. [9] Yang, et al., 2013. [10] Tao, et al., 2015.](https://image.slidesharecdn.com/151215cdcequibaessdynamics-151218124546/85/Transition-Models-of-Equilibrium-Assessment-in-Bayesian-Game-3-320.jpg)
![Introduction
4
Insufficient tools and concepts[11]
Bayesian Nash equilibrium plays key roles in game analysis & design.
equilibrium analysis: for given belief, find a Bayesian Nash Equilibrium(BNE).
belief learning: for given BNE, find a corresponding belief.
mechanism design: for given utility, find rules to achieve a desired BNE.
Objective of this talk
Derive a dynamical state-space model whose state involves a BNE.
derive a novel condition related to the BNE,
discover a map (discrete-time system) defined by the novel condition,
confirm a time response of the map.
[11] Powell, 2011.
Challenge: prepare tools & concepts to apply our model-based fashion
to analysis and design of the game.](https://image.slidesharecdn.com/151215cdcequibaessdynamics-151218124546/85/Transition-Models-of-Equilibrium-Assessment-in-Bayesian-Game-4-320.jpg)
![Bayesian Nash Equilibrium
7
Equilibrium assessment
definitions of Bayesian Nash Equilibrium(BNE)
using an ex-ante expected utility:
using a best response to opponent strategy:
EUi(si, s i) EUi(s0
, s i) 8s0
i 2 Si, s0
i 6= si
is denoted as the Bayesian Nash equilibrium.
A strategy profile , satisfying , is also a BNE.s = (si, s i)
Given a prior common probability , for any , the strategy satisfyingi 2 N sp(?)
si 2 BRi(s i, ?) 8i 2 N
the pair of considered as key variables of the Bayesian game.
Equilibrium Assessment : a pair of a belief and the corresponding BNE.(??, ?s)
(?, s)
equilibrium analysis[10]: find a BNE .?s9 ??,
[10] Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009.](https://image.slidesharecdn.com/151215cdcequibaessdynamics-151218124546/85/Transition-Models-of-Equilibrium-Assessment-in-Bayesian-Game-7-320.jpg)
![Given an initial EA, if there exists such that the game satisfies
the following condition w.r.t. utility matrices: ,
Dynamics in Equilibrium Assessment
10
Main result
Theorem
?
1 1
?
Ui(?i, ?)
?
1
1 1
= 0
?
1 1
?
Ui(?i, ??)
?
2
1 2
= 0
8?i 2 ?i8i 2 N
??(k + 1) = diag(A1, A2)??(k)
?s(k + 1) = A (ci(k))?si(k)
ci(k) :=
??i(?i, k + 1)
??i(?i, k)
, and is a row stochastic matrix.Ai 2 <2?2
8i 2 N
= [ 1 2]T
2 <2
then a nonlinear autonomous system in terms of the equilibrium assessment:
transfers from an EA to another EA , where(??(k), ?s(k)) (??(k + 1), ?s(k + 1))
ci(k) ! 1
A (1) = I
ci(k) :=
??i(?i, k + 1)
??i(?i, k)??(k + 1) = diag(A1, A2)??(k) ?s(k + 1) = A (ci(k))?si(k)
??(k)
??(k + 1)
stable linear system: time-varying system:
¡¤
?s(k)
??(k)](https://image.slidesharecdn.com/151215cdcequibaessdynamics-151218124546/85/Transition-Models-of-Equilibrium-Assessment-in-Bayesian-Game-10-320.jpg)
More Related Content
Similar to Transition Models of Equilibrium Assessment in Bayesian Game (20)
More from Kiminao Kogiso (10)
Recently uploaded (20)
Transition Models of Equilibrium Assessment in Bayesian Game
- 1. December 18 Fri., 2015, 09:10-09:30, Regular Session: Modeling 1, Frb04.3 @ 802 Transition ?Models ?of ?Equilibrium ? Assessment ?in ?Bayesian ?Game Kiminao Kogiso University of Electro-Communications Tokyo, Japan The 54 Conference on Decision and Control Osaka International Convention Center, Osaka, Japan December 15 to 18, 2015 Supported by JSPS Grant-in-Aid for Challenging Exploratory Research 2014 to 2016
- 2. Outline 2 Introduction ? Static ?Bayesian ?Game ? Novel ?Form ?in ?Bayesian ?Nash ?Equilibrium ? Dynamics ?in ?Equilibrium ?Assessment ? Simulation ? Conclusion
- 3. Introduction 3 Strategic game enabling to consider uncertainties in player¡¯s decisions. player: a reasonable decision maker action: what a player chooses utility: a player¡¯s preference over the actions type: a label of player¡¯s private valuation (what the player really feels) belief: a probability distribution over the types (degree of feeling, tendency, proclivity,¡) Static Bayesian Game[1] [1] Harsanyi, 1967. [2] Alpcan and Basar, et al., 2011, 2013. [3] Roy, et al., 2010. [4] Liu, et al., 2006. [5] Akkarajitsakul, et al., 2011. A Bayesian game used in engineering problems to analyze a Bayesian Nash equilibrium or to design a game mechanism. network security[2,3], intrusion detection[4,5,6], belief learning[7] electricity pricing[8,9], mechanism design[10] [6] Sedjelmachi, et al., 2014, 2015. [7] Nachbar, 2008. [8] Li, et al., 2011, 2014. [9] Yang, et al., 2013. [10] Tao, et al., 2015.
- 4. Introduction 4 Insufficient tools and concepts[11] Bayesian Nash equilibrium plays key roles in game analysis & design. equilibrium analysis: for given belief, find a Bayesian Nash Equilibrium(BNE). belief learning: for given BNE, find a corresponding belief. mechanism design: for given utility, find rules to achieve a desired BNE. Objective of this talk Derive a dynamical state-space model whose state involves a BNE. derive a novel condition related to the BNE, discover a map (discrete-time system) defined by the novel condition, confirm a time response of the map. [11] Powell, 2011. Challenge: prepare tools & concepts to apply our model-based fashion to analysis and design of the game.
- 5. Bayesian Game Player set Action set Type set Utility Strategy (mixed) Belief Static Bayesian Game: General 5 Two-player two-action Bayesian game w/ two types G(N, A, ?, u, ?, S) N := {1, 2} A := A1 ? A2 ? := ?1 ? ?2 u := (u1, u2) ? := (?1, ?2) S := (S1, S2) ai 2 Ai := {a, ?a} 8i 2 N ?i 2 ?i := {?, ??} 8i 2 N ?i 2 ?(?i) 8i 2 N Si : ?i ! ?(Ai) 8i 2 N si 2 Si(?i) 8i 2 N ?(X) : a probability distribution over a finite set X Ui(?i, ? i) := ? ui(a, a, ?i, ? i) ui(a, ?a, ?i, ? i) ui(?a, a, ?i, ? i) ui(?a, ?a, ?i, ? i) : utility matrix8i 2 N, 8? 2 ? ui : A ? ? ! < 8i 2 N i 2 N
- 6. Static Bayesian Game: Example 6 Service of tennis 2, 2 0, 1 1, 21, 1 flat spin flat spin 0, 1 1, 2 0, 11, 2 flat spin flat spin sideline 1, 0 1, 1 2, 00, 1 flat spin flat spin 1, 3 1, 2 0, 32, 2 flat spin flat spin centerline s1(a|?) s1(?a|?) s1(?a|??) s1(a|??) s2(a|??) s2(?a|??)s2(?a|?)s2(a|?) center line ? side line ?? ??? ?a ?a ?a ?a ?a ?a ?a?aa a a a ?1(?) ?1(??) ?2(??)?2(?) a a a a type belief
- 7. Bayesian Nash Equilibrium 7 Equilibrium assessment definitions of Bayesian Nash Equilibrium(BNE) using an ex-ante expected utility: using a best response to opponent strategy: EUi(si, s i) EUi(s0 , s i) 8s0 i 2 Si, s0 i 6= si is denoted as the Bayesian Nash equilibrium. A strategy profile , satisfying , is also a BNE.s = (si, s i) Given a prior common probability , for any , the strategy satisfyingi 2 N sp(?) si 2 BRi(s i, ?) 8i 2 N the pair of considered as key variables of the Bayesian game. Equilibrium Assessment : a pair of a belief and the corresponding BNE.(??, ?s) (?, s) equilibrium analysis[10]: find a BNE .?s9 ??, [10] Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009.
- 8. then the pair is an Equilibrium Assessment, where ,? := ? 1 1 ? (??, ?s) Novel Form Satisfying BNE 8 If the game satisfies the following condition (simultaneous polynomial in ): Sufficient condition to be BNE Lemma 8?i 2 ?i, 8i 2 N G ??i(?s i, ?i) (?i)p(??) = 0 ?i(?s i, ?i) := ? Ui(?i, ?)?s i(?) Ui(?i, ??)?s i(??) ? , (?) := ? 1 0 0 0 0 1 0 0 , (??) := ? 0 0 1 0 0 0 0 1 . idea: derived from KKT condition of BNE by cancelation of Lagrangian variables. point: # of the polynomials: 4, # of the variables: 6; D.O.F. in determining their values. note: a BNE (mixed strategy) holds the above equation, but some of pure strategy BNEs do not hold it. ?? all of EAs
- 9. Discover Dynamics! 9 Map from EA to EA Idea to derive dynamics in EA all of EAs ? EA (??, ?s) satisfying the Lemma all of EAs ? EA (?? + ??, ?s + ?s) satisfying the Lemma
- 10. Given an initial EA, if there exists such that the game satisfies the following condition w.r.t. utility matrices: , Dynamics in Equilibrium Assessment 10 Main result Theorem ? 1 1 ? Ui(?i, ?) ? 1 1 1 = 0 ? 1 1 ? Ui(?i, ??) ? 2 1 2 = 0 8?i 2 ?i8i 2 N ??(k + 1) = diag(A1, A2)??(k) ?s(k + 1) = A (ci(k))?si(k) ci(k) := ??i(?i, k + 1) ??i(?i, k) , and is a row stochastic matrix.Ai 2 <2?2 8i 2 N = [ 1 2]T 2 <2 then a nonlinear autonomous system in terms of the equilibrium assessment: transfers from an EA to another EA , where(??(k), ?s(k)) (??(k + 1), ?s(k + 1)) ci(k) ! 1 A (1) = I ci(k) := ??i(?i, k + 1) ??i(?i, k)??(k + 1) = diag(A1, A2)??(k) ?s(k + 1) = A (ci(k))?si(k) ??(k) ??(k + 1) stable linear system: time-varying system: ¡¤ ?s(k) ??(k)
- 11. Simulation 11 Trajectory of equilibrium assessment 0.3 0.4 0.5 0.6 0.7 10 0.2 0.4 0.6 0.8 probabilityprobability step 0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 s1( )a|¦È?? s1( )a|¦È? ? s1( )a|¦È ? ? s1( )a|¦È ?? s2( )a|¦È?? s2( )a|¦È? ? s2( )a|¦È ? ? s2( )a|¦È ?? 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 the proposed model the computation of the best respose (4) 10 expectedutilityvalue step 0 1 2 3 4 5 6 7 8 9 EU1 EU2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 10 step 0 1 2 3 4 5 6 7 8 9 valueofci()¦Èi c ( )1 ¦È? c ( )1 ¦È ? c ( )2 ¦È? c ( )2 ¦È ? 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10 probability step 0 1 2 3 4 5 6 7 8 9 1( )¦Ç ¦È? 1( )¦Ç ¦È ? 2( )¦Ç ¦È? 2( )¦Ç ¦È ? belief strategy c expected utility
- 12. Conclusion 12 Introduction Static Bayesian Game two-players two-actions game with two-types New Form in Bayesian Nash Equilib. polynomial conditions in equilibrium assessment Dynamics in Equilibrium Assessment discrete-time autonomous time-varying system convergence of the EA (stability) Simulation confirms states updated become EA and converge. Future works estimate player¡¯s belief for a given BNE, and realize a control-theoretic mechanism design method. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10 probability step 0 1 2 3 4 5 6 7 8 9 1( )¦Ç ¦È? 1( )¦Ç ¦È ? 2( )¦Ç ¦È? 2( )¦Ç ¦È ? belief 0.3 0.4 0.5 0.6 0.7 10 0.2 0.4 0.6 0.8 probabilityprobability step 0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 s1( )a|¦È?? s1( )a|¦È? ? s1( )a|¦È ? ? s1( )a|¦È ?? s2( )a|¦È?? s2( )a|¦È? ? s2( )a|¦È ? ? s2( )a|¦È ?? strategy ??(k + 1) = diag(A1, A2)??(k) ?s(k + 1) = A (ci(k))?si(k) Dynamics in EA: