Computing Solution Concepts of Normal Form Games

E
C
E
7
0
0
.
0
7
:
 
G
a
m
e
 
T
h
e
o
r
y
 
w
i
t
h
E
n
g
i
n
e
e
r
i
n
g
 
A
p
p
l
i
c
a
t
i
o
n
s
Seyed Majid Zahedi
L
e
c
t
u
r
e
 
4
:
 
C
o
m
p
u
t
i
n
g
 
S
o
l
u
t
i
o
n
 
C
o
n
c
e
p
t
s
 
o
f
N
o
r
m
a
l
 
F
o
r
m
 
G
a
m
e
s
O
u
t
l
i
n
e
Brief overview of (mixed integer) linear programs
Solving for
Dominated strategies
Minimax and maximin strategies
Nash equilibrium
Correlated NE
Readings:
MAS Appendix B, and Sec. 4
L
i
n
e
a
r
 
P
r
o
g
r
a
m
 
E
x
a
m
p
l
e
:
R
e
p
r
o
d
u
c
t
i
o
n
 
o
f
 
T
w
o
 
P
a
i
n
t
i
n
g
s
 
Painting 1 sells for $30
Painting 2 sells for $20
We have 16 units of 
blue
, 8 
green
, 5
red
Painting 1 requires 4 
blue
, 1 
green
, 1
red
Painting 2 requires 2 
blue
, 2 
green
, 1
red
S
o
l
v
i
n
g
 
L
i
n
e
a
r
 
P
r
o
g
r
a
m
 
G
r
a
p
h
i
c
a
l
l
y
M
o
d
i
f
i
e
d
 
L
P
 
 
 
Optimal solution: x = 2.5, y =
2.5
Objective = 7.5 + 5 = 12.5
Can we sell half paintings?
 
I
n
t
e
g
e
r
 
L
i
n
e
a
r
 
P
r
o
g
r
a
m
M
i
x
e
d
 
I
n
t
e
g
e
r
 
L
i
n
e
a
r
 
P
r
o
g
r
a
m
 
Optimal MILP
solution: x=2.75,
y=2
(objective 12.25)
S
o
l
v
i
n
g
 
M
i
x
e
d
 
L
i
n
e
a
r
/
I
n
t
e
g
e
r
 
P
r
o
g
r
a
m
s
 
Linear programs can be solved efficiently
Simplex, ellipsoid, interior point methods, etc.
(Mixed) integer programs are 
NP-hard
 to solve
Many standard NP-complete problems can be modelled as MILP
Search type algorithms such as branch and bound
Standard packages for solving these
Gurobi, MOSEK, GNU Linear Programming Kit, CPLEX, CVXPY, etc.
LP relaxation of (M)ILP: remove integrality constraints
Gives upper bound on MILP (~admissible heuristic)
E
x
e
r
c
i
s
e
 
I
 
i
n
 
M
o
d
e
l
i
n
g
:
 
K
n
a
p
s
a
c
k
-
t
y
p
e
 
P
r
o
b
l
e
m
 
We arrive in room full of precious objects
Can carry only 30kg out of the room
Can carry only 20 liters out of the room
Want to maximize our total value
Unit of object A: 16kg, 3 liters, sells for $11 (3 units available)
Unit of object B: 4kg, 4 liters, sells for $4 (4 units available)
Unit of object C: 6kg, 3 liters, sells for $9 (1 unit available)
What should we take?
E
x
e
r
c
i
s
e
 
I
I
 
i
n
 
M
o
d
e
l
i
n
g
:
 
C
e
l
l
 
P
h
o
n
e
s
 
(
S
e
t
 
C
o
v
e
r
)
 
We want to have a working phone in every continent (besides
Antarctica) but we want to have as few phones as possible
Phone A works in NA, SA, Af
Phone B works in E, Af, As
Phone C works in NA, Au, E
Phone D works in SA, As, E
Phone E works in Af, As, Au
Phone F works in NA, E
E
x
e
r
c
i
s
e
 
I
I
I
 
i
n
 
M
o
d
e
l
i
n
g
:
 
H
o
t
-
d
o
g
 
S
t
a
n
d
s
 
We have two hot-dog stands to be placed in somewhere along
beach
We know where groups of people who like hot-dogs are
We also know how far each group is willing to walk
Where do we put our stands to maximize #hot-dogs sold? 
(price
is fixed)
C
h
e
c
k
i
n
g
 
f
o
r
 
S
t
r
i
c
t
 
D
o
m
i
n
a
n
c
e
 
b
y
 
M
i
x
e
d
S
t
r
a
t
e
g
i
e
s
 
C
h
e
c
k
i
n
g
 
f
o
r
 
W
e
a
k
 
D
o
m
i
n
a
n
c
e
 
b
y
 
M
i
x
e
d
S
t
r
a
t
e
g
i
e
s
P
a
t
h
 
D
e
p
e
n
d
e
n
c
y
 
o
f
 
I
t
e
r
a
t
e
d
 
D
o
m
i
n
a
n
c
e
 
Iterated weak dominance is 
path-dependent
Sequence of eliminations may determine which solution we get (if any)
 
 
 
 
 
Iterated strict dominance is 
path-independent
:
Elimination process will always terminate at the same point
T
w
o
 
C
o
m
p
u
t
a
t
i
o
n
a
l
 
Q
u
e
s
t
i
o
n
s
 
f
o
r
 
I
t
e
r
a
t
e
d
D
o
m
i
n
a
n
c
e
 
1.  Can any 
given strategy 
be eliminated using iterated
dominance?
2.  Is there some path of elimination by iterated dominance such
that only 
one strategy per player 
remains?
For strict dominance (with or without dominance by mixed
strategies), both can be solved in polynomial time due to path-
independence
Check if any strategy is dominated, remove it, repeat
For weak dominance, both questions are NP-hard (even when
all utilities are 0 or 1), with or without dominance by mixed
strategies 
[Conitzer, Sandholm 05], and weaker version proved by [Gilboa, Kalai, Zemel 93]
M
i
n
i
m
a
x
 
a
n
d
 
M
a
x
i
m
i
n
 
V
a
l
u
e
s
L
P
 
f
o
r
 
C
a
l
c
u
l
a
t
i
n
g
 
M
a
x
i
m
i
n
 
S
t
r
a
t
e
g
y
 
a
n
d
 
V
a
l
u
e
M
i
n
i
m
a
x
 
T
h
e
o
r
e
m
 
[
v
o
n
 
N
e
u
m
a
n
n
 
1
9
2
8
]
 
Each player’s NE utility in any finite, two-player, zero-sum game
is equal to her maximin value and minimax value
 
 
Minimax theorem does not hold with pure strategies only
(example?)
E
x
a
m
p
l
e
 
What is maximin value of agent 1 with and without mixed
strategies?
What is minimax value of agent 1 with and without mixed
strategies?
What is NE of this game?
S
o
l
v
i
n
g
 
N
E
 
o
f
 
T
w
o
-
P
l
a
y
e
r
,
 
Z
e
r
o
-
S
u
m
 
G
a
m
e
s
 
Minimax value of agent 1
 
Maximin value of agent 1
 
NE is 
expressed as LP
, which means equilibria can be computed in
polynomial time
M
a
x
i
m
i
n
 
S
t
r
a
t
e
g
y
 
f
o
r
 
G
e
n
e
r
a
l
-
S
u
m
 
G
a
m
e
s
 
Agents could still play minimax strategy in general-sum games
I.e., pretend that the opponent is only trying to hurt you
But this is not rational:
 
 
 
 
If A2 was trying to hurt A1, she would play Left, so A1 should play
Down
In reality, A2 will play Right (strictly dominant), so A1 should play Up
H
a
r
d
n
e
s
s
 
o
f
 
C
o
m
p
u
t
i
n
g
 
N
E
 
f
o
r
 
G
e
n
e
r
a
l
-
S
u
m
G
a
m
e
s
 
Complexity was open for long time
“together with factoring […] the most important concrete open question
on the boundary of P today” 
[Papadimitriou STOC’01]
Sequence of papers showed that computing any NE is PPAD-
complete (even in 2-player games) 
[Daskalakis, Goldberg, Papadimitriou 2006;
Chen, Deng 2006]
All known algorithms require 
exponential time 
(in worst case)
H
a
r
d
n
e
s
s
 
o
f
 
C
o
m
p
u
t
i
n
g
 
N
E
 
f
o
r
 
G
e
n
e
r
a
l
-
S
u
m
G
a
m
e
s
 
(
c
o
n
t
.
)
 
What about computing NE with 
specific property
?
NE that is not Pareto-dominated
NE that maximizes expected social welfare (i.e., sum of all agents’
utilities)
NE that maximizes expected utility of given agent
NE that maximizes expected utility of worst-off player
NE in which given pure strategy is played with positive probability
NE in which given pure strategy is played with zero probability
All of these are 
NP-hard
 (and the optimization questions are
inapproximable assuming P != NP), even in 2-player games
[Gilboa, Zemel 89; Conitzer & Sandholm IJCAI-03/GEB-08]
S
e
a
r
c
h
-
B
a
s
e
d
 
A
p
p
r
o
a
c
h
e
s
 
(
f
o
r
 
T
w
o
-
P
l
a
y
e
r
G
a
m
e
s
)
S
o
l
v
i
n
g
 
f
o
r
 
N
E
 
u
s
i
n
g
 
M
I
L
P
 
(
f
o
r
 
T
w
o
-
P
l
a
y
e
r
G
a
m
e
s
)
[
S
a
n
d
h
o
l
m
,
 
G
i
l
p
i
n
,
 
C
o
n
i
t
z
e
r
 
A
A
A
I
0
5
]
S
o
l
v
i
n
g
 
f
o
r
 
C
o
r
r
e
l
a
t
e
d
 
E
q
u
i
l
i
b
r
i
u
m
 
u
s
i
n
g
 
L
P
(
N
-
P
l
a
y
e
r
 
G
a
m
e
s
!
)
Q
u
e
s
t
i
o
n
s
?
 
A
c
k
n
o
w
l
e
d
g
e
m
e
n
t
This lecture is a slightly modified version of ones prepared by
Vincent Conitzer [
Duke CPS 590.4
]
Slide Note
Embed
Share

Lecture 4 of ECE700.07 covers topics such as solving for dominated strategies, minimax and maximin strategies, Nash equilibrium, and correlated NE. It includes examples of linear programming, graphical solutions, and optimal solutions. The lecture delves into Integer Linear Programs, Mixed Integer Linear Programs, and their solutions. Additionally, it explores the complexities of solving Mixed Linear/Integer Programs and provides insights into modeling problems with a knapsack-type scenario.

  • Normal Form Games
  • Linear Programming
  • Optimization
  • Nash Equilibrium
  • Mixed Integer Programs

Uploaded on Feb 22, 2025 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. ECE700.07: Game Theory with Engineering Applications Lecture 4: Computing Solution Concepts of Normal Form Games Seyed Majid Zahedi

  2. Outline Brief overview of (mixed integer) linear programs Solving for Dominated strategies Minimax and maximin strategies Nash equilibrium Correlated NE Readings: MAS Appendix B, and Sec. 4

  3. Linear Program Example: Reproduction of Two Paintings Painting 1 sells for $30 Painting 2 sells for $20 We have 16 units of blue, 8 green, 5 red Painting 1 requires 4 blue, 1 green, 1 red Painting 2 requires 2 blue, 2 green, 1

  4. Solving Linear Program Graphically 8 6 Optimal solution: ? = 3, ? = 2 (objective: 13) 4 2 0 2 4 6 8

  5. Modified LP Optimal solution: x = 2.5, y = 2.5 Objective = 7.5 + 5 = 12.5 Can we sell half paintings?

  6. Integer Linear Program 8 Optimal ILP solution: ? = 2, ? = 3 (objective 12) 6 Optimal LP solution: ? = 2.5, ? = 2.5 (objective 12.5) 4 2 0 2 4 6 8

  7. Mixed Integer Linear Program 8 Optimal ILP solution: ? = 2, ? = 3 (objective 12) 6 Optimal LP solution: ? = 2.5, ? = 2.5 (objective 12.5) 4 Optimal MILP solution: x=2.75, y=2 (objective 12.25) 2 0 2 4 6 8

  8. Solving Mixed Linear/Integer Programs Linear programs can be solved efficiently Simplex, ellipsoid, interior point methods, etc. (Mixed) integer programs are NP-hard to solve Many standard NP-complete problems can be modelled as MILP Search type algorithms such as branch and bound Standard packages for solving these Gurobi, MOSEK, GNU Linear Programming Kit, CPLEX, CVXPY, etc. LP relaxation of (M)ILP: remove integrality constraints Gives upper bound on MILP (~admissible heuristic)

  9. Exercise I in Modeling: Knapsack-type Problem We arrive in room full of precious objects Can carry only 30kg out of the room Can carry only 20 liters out of the room Want to maximize our total value Unit of object A: 16kg, 3 liters, sells for $11 (3 units available) Unit of object B: 4kg, 4 liters, sells for $4 (4 units available) Unit of object C: 6kg, 3 liters, sells for $9 (1 unit available) What should we take?

  10. Exercise II in Modeling: Cell Phones (Set Cover) We want to have a working phone in every continent (besides Antarctica) but we want to have as few phones as possible Phone A works in NA, SA, Af Phone B works in E, Af, As Phone C works in NA, Au, E Phone D works in SA, As, E Phone E works in Af, As, Au Phone F works in NA, E

  11. Exercise III in Modeling: Hot-dog Stands We have two hot-dog stands to be placed in somewhere along beach We know where groups of people who like hot-dogs are We also know how far each group is willing to walk Where do we put our stands to maximize #hot-dogs sold? (price is fixed) Group 5 location: 15 #customers: 3 willing to walk: 2 Group 1 location: 1 #customers: 2 willing to walk: 4 Group 2 location: 4 #customers: 1 willing to walk: 2 Group 3 location: 7 #customers: 3 willing to walk: 3 Group 4 location: 9 #customers: 4 willing to walk: 3

  12. Checking for Strict Dominance by Mixed Strategies LP for checking if strategy ?? is strictly dominated by any mixed strategy

  13. Checking for Weak Dominance by Mixed Strategies LP for checking if strategy ?? is weakly dominated by any mixed strategy

  14. Path Dependency of Iterated Dominance Iterated weak dominance is path-dependent Sequence of eliminations may determine which solution we get (if any) 0, 1 1, 0 1, 0 1, 0 1, 0 0, 1 0, 1 1, 0 1, 0 1, 0 1, 0 0, 1 1, 1 1, 0 0, 0 0, 0 1, 0 1, 1 Iterated strict dominance is path-independent: Elimination process will always terminate at the same point

  15. Two Computational Questions for Iterated Dominance 1. Can any given strategy be eliminated using iterated dominance? 2. Is there some path of elimination by iterated dominance such that only one strategy per player remains? For strict dominance (with or without dominance by mixed strategies), both can be solved in polynomial time due to path- independence Check if any strategy is dominated, remove it, repeat For weak dominance, both questions are NP-hard (even when all utilities are 0 or 1), with or without dominance by mixed strategies [Conitzer, Sandholm 05], and weaker version proved by [Gilboa, Kalai, Zemel 93]

  16. Minimax and Maximin Values Maximin strategy for agent ? (leading to maximin value for agent ?) Minimax strategy of other agents (leading to minimax value for agent ?)

  17. LP for Calculating Maximin Strategy and Value Objective of this LP, ?, is maximin value of agent ? Given ???, first constraint ensures that ? is less than any achievable expected utility for any pure strategies of opponents

  18. Minimax Theorem [von Neumann 1928] Each player s NE utility in any finite, two-player, zero-sum game is equal to her maximin value and minimax value Minimax theorem does not hold with pure strategies only (example?)

  19. Example Agent 2 Left Right Agent 1 Up (20, -20) (0, 0) Down (0, 0) (10, -10) What is maximin value of agent 1 with and without mixed strategies? What is minimax value of agent 1 with and without mixed strategies? What is NE of this game?

  20. Solving NE of Two-Player, Zero-Sum Games Minimax value of agent 1 Maximin value of agent 1 NE is expressed as LP, which means equilibria can be computed in polynomial time

  21. Maximin Strategy for General-Sum Games Agents could still play minimax strategy in general-sum games I.e., pretend that the opponent is only trying to hurt you But this is not rational: Agent 2 Left Right Agent 1 Up (0, 0) (3, 1) Down (1, 0) (2, 1) If A2 was trying to hurt A1, she would play Left, so A1 should play Down In reality, A2 will play Right (strictly dominant), so A1 should play Up

  22. Hardness of Computing NE for General-Sum Games Complexity was open for long time together with factoring [ ] the most important concrete open question on the boundary of P today [Papadimitriou STOC 01] Sequence of papers showed that computing any NE is PPAD- complete (even in 2-player games) [Daskalakis, Goldberg, Papadimitriou 2006; Chen, Deng 2006] All known algorithms require exponential time (in worst case)

  23. Hardness of Computing NE for General-Sum Games (cont.) What about computing NE with specific property? NE that is not Pareto-dominated NE that maximizes expected social welfare (i.e., sum of all agents utilities) NE that maximizes expected utility of given agent NE that maximizes expected utility of worst-off player NE in which given pure strategy is played with positive probability NE in which given pure strategy is played with zero probability All of these are NP-hard (and the optimization questions are inapproximable assuming P != NP), even in 2-player games [Gilboa, Zemel 89; Conitzer & Sandholm IJCAI-03/GEB-08]

  24. Search-Based Approaches (for Two-Player Games) We can use (feasibility) LP, if we know support ?? of each player ? s mixed strategy I.e., we know which pure strategies receive positive probability Thus, we can search over possible supports, which is basic idea underlying methods in [Dickhaut & Kaplan 91; Porter, Nudelman, Shoham AAAI04/GEB08]

  25. Solving for NE using MILP (for Two-Player Games) [Sandholm, Gilpin, Conitzer AAAI05] ??? is binary variable indicating if ?? is in support of ? s mixed strategy, and ? is large number

  26. Solving for Correlated Equilibrium using LP (N-Player Games!) Variables are now ?? where ? is profile of pure strategies (i.e., outcome)

  27. Questions?

  28. Acknowledgement This lecture is a slightly modified version of ones prepared by Vincent Conitzer [Duke CPS 590.4]

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#