Mansour Y., Computational Game Theory Lctn.pdf

(1896 KB) Pobierz
Computational Learning Theory
Spring Semester, 2003/4
Lecture 1: March 2
Lecturer: Yishay Mansour
Scribe: Gur Yaari, Idan Szpektor
1.1
Introduction
Several fields in computer science and economics are focused on the analysis of Game theory.
Usually they observe Game Theory as a way to solve optimization problems in systems where
the participants act independently and their decisions affect the whole system.
Following is a list of research fields that utilize Game Theory:
•
Artificial Intelligence (AI) - Multiple Agents settings where the problem is usually a
cooperation problem rather than a competition problem.
•
Communication Networks - Distribution of work where each agent works indepen-
dantly.
•
Computer Science Theory - There are several subfields that use Game Theory:
–
Maximizing profit in bidding
–
Minimum penalty when using distributional environment
–
Complexity
–
Behavior of large systems
1.2
Course Syllabus
•
Basic definitions in Game Theory, concentrating on Nash Equilibrium
•
Coordination Ratio
–
Comparison between global optimum and Nash Equilibrium
–
Load Balancing Models
•
Computation of Nash Equilibrium
–
Zero Sum games (Linear Programming)
–
Existence of Nash Equilibrium in general games
1
2
Lecture 1: March 2
•
Regret - playing an “unknown” game. Optimizing a player’s moves when the player
can only view her own payoff
•
Vector Payoff - the Payoff function is a vector and the target is to reach a specific
target set
•
Congestion and Potential games - games that model a state of load
•
Convergence into Equilibrium
•
Other...
1.3
Strategic Games
A strategic game is a model for decision making where there are
N
players, each one choosing
an action. A player’s action is chosen just once and cannot be changed afterwards.
Each player
i
can choose an action
a
i
from a set of actions
A
i
. let
A
be the set of all
possible action vectors
×
j∈N
A
j
. Thus, the outcome of the game is an action vector
a
∈
A.
All the possible outcomes of the game are known to all the players and each player
i
has
a preference relation over the different outcomes of the game:
a
i
b
for every
a, b
∈
A.
The
relation stands if the player prefers
b
over
a,
or has equal preference for either.
Definition
A
Strategic Game
is a triplet
N,
(A
i
), (
i
) where
N
is the number of players,
A
i
is the finite set of actions for player
i
and
i
is the preference relation of player
i.
We will use a slightly different notation for a strategic game, replacing the preference
relation with a payoff function
u
i
:
A
→
R.
The player’s target is to maximize her own
payoff. Such strategic game will be defined as:
N,
(A
i
), (u
i
) .
This model is very abstract. Players can be humans, companies, governments etc. The
preference relation can be subjective evolutional etc. The actions can be simple, such as “go
forward” or “go backwards”, or can be complex, such as design instructions for a building.
Several player behaviors are assumed in a strategic game:
•
The game is played only once
•
Each player “knows” the game (each player knows all the actions and the possible
outcomes of the game)
•
The players are rational. A rational player is a player that plays selfishly, wanting to
maximize her own benefit of the game (the payoff function).
•
All the players choose their actions simultaneously
1.4. PARETO OPTIMAL
3
1.4
Pareto Optimal
An outcome
a
∈
A
of a game
N,
(A
i
), (u
i
) is Pareto Optimal if there is no other outcome
b
∈
A
that makes every player at least as well off and at least one player strictly better off.
That is, a Pareto Optimal outcome cannot be improved upon without hurting at least one
player.
Definition
An outcome
a
is
Pareto Optimal
if there is
no
outcome
b
such that
∀
j∈N
u
j
(a)
≤
u
j
(
b)
and
∃
j∈N
u
j
(a)
< u
j
(
b).
1.5
Nash Equilibrium
A Nash Equilibrium is a state of the game where no player prefers a different action if the
current actions of the other players are fixed.
Definition
An outcome
a
∗
of a game
N,
(A
i
), (
i
) is a
Nash Equilibrium
if:
∀
i∈N
∀
b
i
∈A
i
(a
∗
, b
i
) (a
∗
, a
∗
).
−i
−i
i
(a
−i
, x)
means the replacement of the value
a
i
with the value
x.
We can look at a Nash Equilibrium as the best action that each player can play based
on the given set of actions of the other players. Each player cannot profit from changing her
action, and because the players are rational, this is a “steady state”.
Definition
Player
i
Best Response
for a given set of other players actions
a
−i
∈
A
−i
is
the set:
BR(a
−i
) :=
{b ∈
A
i
| ∀
c∈A
i
(a
−i
, c)
i
(a
−i
, b)}.
Under this notation, an outcome
a
∗
is a Nash Equilibrium if
∀
i∈N
a
∗
∈
BR(a
∗
).
i
−i
1.6
Matrix Representation
A two player strategic game can be represented by a matrix whose rows are the possible
actions of player 1 and the columns are the possible actions of player 2. Every entry in the
matrix is a specific outcome and contains a vector of the payoff value of each player for that
outcome.
For example, if
A
1
is
{r1,r2}
and
A
2
is
{c1,c2}
the matrix representation is:
r1
r2
c1
c2
(w1,
w2)
(x1,
x2)
(y1,
y2)
(z1,
z2)
4
Where
u
1
(r1,
c2)
=
x1
and
u
2
(r2,
c1)
=
y2.
Lecture 1: March 2
1.7
Strategic Game Examples
The following are examples of two players games with two possible actions per player. The
set of deterministic Nash Equilibrium points is described in each example.
1.7.1
Battle of the Sexes
Sports
(2, 1)
(0, 0)
Opera
(0, 0)
(1, 2)
Sports
Opera
There are two Nash Equilibrium points: (Sports, Opera) and (Opera, Sports).
1.7.2
A Coordination Game
Attack
Retreat
(10, 10)
(−10,
−10)
(−10,
−10)
(0, 0)
Attack
Retreat
There are two Nash Equilibrium outcomes: (Attack, Attack) and (Retreat, Retreat).
A question that raises from this game and its equilibria is how the two players can move
from one Equilibrium point, (Retreat, Retreat), to the better one (Attack, Attack). Another
the way to look at it is how the players can coordinate to choose the preferred equilibrium
point.
1.7.3
The Prisoner’s Dilemma
There is one Nash Equilibrium point: (Confess, Confess). Here, though it looks natural that
the two players will cooperate, the cooperation point (Don’t Confess, Don’t Confess) is not
a steady state since once in that state, it is more profitable for each player to move into
’Confess’ action, assuming the other player will not change its action.
Strategic Game Examples
5
Don’t Confess
Confess
Don’t Confess
(−1,
−1)
(0,
−4)
Confess
(−4, 0)
(−3,
−3)
1.7.4
Dove-Hawk
Dove
Hawk
Dove Hawk
(3, 3) (1, 4)
(4, 1) (0, 0)
There are two Nash Equilibrium points: (Dove, Hawk) and (Hawk, Dove).
1.7.5
Matching Pennies
Head
Tail
Head
Tail
(1,
−1)
(−1, 1)
(−1, 1) (1,
−1)
In this game there is no Deterministic Nash Equilibrium point. However, there is a Mixed
1
Nash Equilibrium which is (
1
,
1
), (
1
,
2
) This is a zero sum game (the sum of the profits of
2 2
2
each player over all possible outcomes is 0).
1.7.6
Auction
There are
N
players, each one wants to buy an object.
•
Player
i
’s valuation of the object is
v
i
, and, without loss of generality,
v
1
> v
2
> ... >
v
n
>
0.
•
The players simultaneously submit bids -
k
i
∈
[0,
∞).
The player who submit the
highest bid -
k
i
wins.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin