Computing Bayes-Nash Equilibria through Support
Enumeration Methods in Bayesian Two-Player
Strategic-Form Games
Sofia Ceppi, Nicola Gatti, and Nicola Basilico
Dipartimento di Elettronica e Informazione,
Politecnico di Milano
{ceppi, ngatti, basilico}@elet.polimi.it
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Outline
• State of the Art
– What is a Bayesian game
– Why to study Bayesian games
• Original Contributions
– Extensions of existing algorithms for Bayesian games
– B-PNS algorithm
• Experimental Evaluation
• Conclusions and Future Contributions
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Bayesian Games
• What is a Bayesian Game?
– Non-cooperative game
– A game wherein information is uncertain
Player 2
d
a
2, 7
9, 4?
b
3, 5
2, 3
Type 2.1
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
ω2.1 = 0.3
Player 1
Player 1
c
Player 2
c
d
a
2, 7
9, 8
b
3, 5
1, 3
Type 2.2
ω2.2 = 0.7
Bayesian Games
• Why to study Bayesian Games?
– Most real world strategic situations present uncertainty and
therefore can be modeled as Bayesian games, e.g.,
• Negotiation settings: bilateral bargaining and auctions
• Security settings: strategic mobile robot patrolling
– The literature does not study algorithms for computing BayesNash equilibria in depth [Shoham and Leyton-Brown, 2008]
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
State of the Art
• Solution concept for Bayesian games is Bayes-Nash equilibrium
• A Bayesian game is solved by reducing it to a complete-information
game and then computing a Nash equilibrium in this game
• The literature provides a detailed comparison of the algorithms for the
computation of Nash equilibria in complete-information games
• The exact algorithms for two-player complete-information strategicform games are:
– LH: based on linear complementary programming [LemkeHowson, 1964]
– PNS: based on support enumeration [Porter et al., 2004]
– SGC: based on mixed integer linear programming [Sandholm et
al., 2005]
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Bayesian Game Peculiarities
• The experimental results provided from the literature for computing
Nash equilibria cannot be generalized to Bayesian case. The main
reasons are:
– Bayesian games can present characteristics (e.g., existence of
equilibria with small supports) different from those of completeinformation games
– The reduction to complete-information games raises several
problems in the application of algorithms for computing Nash
equilibria [Koller and Megiddo, 1996]
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Original Contributions
• Extension of the algorithms existing in the literature for the
computation of Bayes-Nash equilibrium
– PNS
→ B-PNS (the main result)
– LH
→ B-LC
– SGC
→ B-SGC
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
PNS Algorithm
• The support Si of an agent i is the set of actions played by i with nonnull probability
• The joint support S is the set of single agents’ support
STEP 1:
Choosing S
(Enumeration
Criteria)
STEP 2:
Pruning
(Conditional
Dominance)
dominated
not
dominated
STEP 3:
Equilibrium
Checking
(Feasibility
Problem)
feasible
not
feasible
• To derive the B-PNS algorithm we modified all the three parts of PNS
algorithm
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Supports
d
a
2, 7
9, 4
b
3, 5
2, 3
Type 2.1
ω2.1 = 0.3
•
•
•
•
•
c
Player 1
Player 1
c
Player 2
Player 2
d
a
2, 7
9, 8
b
3, 5
1, 3
Type 2.2
ω2.2 = 0.7
Supports for player 1:
S1=(a), S1=(b), S1=(a,b)
Supports for type 1 of player 2: S2.1=(c), S2.1=(d), S2.1=(c,d)
Supports for type 2 of player 2: S2.2=(c), S2.2=(d), S2.2=(c,d)
Joint support:
S={S1,S2.1,S2.2} → S={ (a), (d), (c,d) }
Goal: enumerate the joint supports and check if they are of
equilibrium
• How to enumerate the joint supports?
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Step 1: Heuristics
• Balance
– Non Bayesian games: |S1|-|S2| → If S1=(a), S2=(c) the balance is 0
– We call
– In Bayesian games the balance is
If S1=(a,b), S2.1=(c), S2.2=(c,d) the balance is 0
– Increasing order of balance
• Size
– The size of a player is the sum of all the actions played with non-null
probability by all the types of the player
– Increasing order of size
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Step 1: Peak Criterion (1)
• Open Issue:
– Given the values of balance and size, ranking a player’s supports
– Example:
Balance = 0
Size = 7
Player 1’s types = 3
Actions = {a,b,c,d,e}
→ S1 = { (a), (a,b,c,d,e), (c) }
→ S1 = { (a,c), (a,b,c), (c,e) }
• Peak Criterion
– Based on the size of types’ supports
– The peak is the size of the maximum possible support
– Decreasing criterion and increasing criterion
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Step 1: Peak Criterion (2)
• We use an enumeration tree to order the supports where each node
defines the size of all the types. (e.g. |S1|, |S2.1|,|S2.2|)
Size = 7 Types = 3
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Available Actions = 5
Step 2: Pruning Techniques
d
a
2, 7
9, 4
b
3, 5
2, 3
Type 2.1
ω2.1 = 0.3
c
Player 1
Player 1
c
Player 2
Player 2
d
a
2, 7
9, 8
b
3, 5
1, 3
Type 2.2
ω2.2 = 0.7
• Action a is strictly conditionally Bayesian dominated by action a’ if for
every σ-i | S-i
• The
problem
of=checking
or not an action is strictly
Given
S-i = {S2.1
(c), S2.2 =whether
(d)}
conditionally
by another action can be
EU1(a) = ω2.1 ·Bayesian
2 + ω2.2 · dominated
9
formulated as a linear feasibility problem
EU1(b) = ω2.1 · 3 + ω2.2 · 1
• In our case, it can be formulated as a fractional knapsack problem
EU1(a) > EU1(b)
and then solved in linear time in the number of variables
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Step 3: B-PNS Feasibility Problem (1)
• Linear feasibility problem used for checking if a joint support is of
equilibrium
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Step 3: B-PNS Feasibility Problem (2)
d
a
2, 7
9, 4
b
3, 5
2, 3
Type 2.1
ω2.1 = 0.3
c
Player 1
Player 1
c
Player 2
Player 2
a
2, 7
9, 8
b
3, 5
1, 3
Type 2.2
ω2.2 = 0.7
• The problem with support S = { (a), (c,d), (d) } is infeasible
• The problem with support S = { (a,b), (c), (c,d) } is feasible:
– the probabilities of the actions are:
player 1:
p(a) = 0.667 p(b)= 0.333
type 1 player 2:
p(c) = 1
p(d) = 0
type 2 player 2:
p(c) = 0.841 p(d) = 0.159
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
d
Experimental Evaluation
• We developed a tool based on GAMUT to generate Bayesian games
• We compared computational time in:
– Different configurations of B-PNS
– PNS and B-PNS
– B-PNS, B-SGC, and B-LC
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Experimental Results
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Conclusions
• We focus on the computation of equilibria in Bayesian games
• This class of game is important since most strategic real-world
situations can be modeled as a Bayesian game
• Computing Nash equilibria in complete-information games is
inefficient when the game is Bayesian
• We extend the algorithms used for the computation of Nash equilibria
for the Bayesian games
• We focus on B-PNS
• We experimentally evaluate the Bayesian algorithms
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano
Future Contributions
• Improvement of support enumeration methods using algorithms based
on local search techniques
– Non-Stochastic
– Stochastic
• Application to open problems
S. Ceppi, N. Gatti, and N. Basilico
DEI, Politecnico di Milano