Game theory and its applications

Levente Buttyán
Laboratory of Cryptography
and System Security (CrySyS)
Budapest University of
Technology and Economics
buttyan@crysys.hu

© 2009 Levente Buttyán

Brief introduction to Game Theory

ƒ Discipline aiming at modeling situations in which actors have
to make decisions which have mutual, possibly conflicting,
consequences
ƒ Classical applications: economics, but also politics, biology,
and recently, networking protocols!
ƒ Example: should a company invest in a new plant, or enter a
new market, considering that the competition may make
similar moves?
ƒ Most widespread kind of game: non-cooperative (meaning
that the players do not attempt to find an agreement about
their possible moves)

Game theory and its applications 2/28

1
 The Prisoner’s Dilemma
ƒ game formulation: G = (P, S, U)
– P: set of players
– S: set of strategies
– U: set of utility (payoff) functions
ƒ players are rational Æ they try to maximize their payoff
ƒ strategic-form representation:

Green
Blue Confess Don’t confess
Confess (-7, -7) (0, -10)
Don’t confess (-10, 0) (-1, -1)

Game theory and its applications 3/28

Solving the Prisoner’s Dilemma

ƒ strict dominance:
a strategy si of player i is strictly dominant, if for any other strategy
si’, we have
ui(si, s-i) > ui(si’, s-i) for all s-i in S-i
where ui() is player i’s payoff function, and s-i is a strategy profile
containing strategies for all players except i

ƒ in the Prisoner’s Dilemma, Confess strictly dominates Don’t

Confess for both players
Green
Blue Confess Don’t confess
Confess (-7, -7) (0, -10)
Don’t confess (-10, 0) (-1, -1)

Game theory and its applications 4/28

2
 Hawks and Doves

Green
Blue Fight Surrender
Fight (-100, -100) (1, -1)
Surrender (-1, 1) (0, 0)

ƒ no strictly dominant strategy

ƒ but consider the following:
– if Blue fights, then the best response of Green is to surrender
– if Green surrenders, then the best response of Blue is to fight
Æ (Fight, Surrender) is an equilibrium in the sense that no player has
an incentive to unilaterally deviate (Nash equilibrium)

Game theory and its applications 5/28

Solving the Hawks and Doves game

ƒ Nash equilibrium:
a strategy profile (si*) is a Nash equilibrium, if for every player i and
for any strategy si ≠ si*, we have
ui(si*, s-i*) ≥ ui(si, s-i*)

ƒ the Hawks and Doves game has two Nash equilibria

Green
Blue Fight Surrender
Fight (-100, -100) (1, -1)
Surrender (-1, 1) (0, 0)

Game theory and its applications 6/28

3
 Pareto optimality and stability
ƒ Pareto optimality
– an outcome of the game is Pareto optimal, if no player can increase
its payoff without hurting some other player

ƒ stability
– an equilibrium is stable if a change in any player’s strategy leads to a
situation where:
• the player who did not change has no better strategy in the new
circumstance
• the player who did change is now playing with a strictly worse strategy
(if these cases are both met, then the player who changed his
strategy will return immediately to the previous equilibrium)

ƒ when there are multiple Nash equilibria, Pareto optimality

and stability may be considered as selection criteria

ƒ example: in the Hawks and Doves game, both NEs are

Pareto optimal and instable
Game theory and its applications 7/28

The Jamming game

Green
Blue C1 C2
C1 (-1, 1) (1, -1)
C2 (1, -1) (-1, 1)

ƒ Green is a jammer who wants to destroy Blue’s transmission

ƒ there are two channels C1 and C2
ƒ the game is a zero-sum game: successful jamming is good
for Green and bad for Blue, while successful transmission is
bad for Green and good for Blue

Game theory and its applications 8/28

4
 Solving the Jamming game
ƒ there’s no pure strategy Nash equilibrium
ƒ mixed strategies:
– a mixed strategy is defined by a probability distribution p(si) that
assigns a probability to each strategy of player i
– when player i plays a mixed strategy it chooses strategy si with
probability p(si)
– in this case, we are interested in the expected payoff of the players

ƒ in the Jamming game, the mixed strategy profile ((1/2, 1/2),

(1/2, 1/2)) is a Nash equilibrium
– when Blue chooses the channel uniformly at random, the jammer
Green has no better move than choosing his channel uniformly at
random, and vice versa

ƒ Nash theorem (1950): Every finite game has a mixed

strategy Nash equilibrium.

Game theory and its applications 9/28

Extensive games
Definition: G = < P, Q, p, ( Ii )i∈P , ( ≤i )i∈P >
P : set of players
Q : set of action sequences (set of terminal action sequences is Z )
p : player function ( p : Q\Z Æ P )
Ii : information partition of player i
≤i : preference relation of player i on Z (often represented by payoffs)

Example

P = {1, 2}
Q = {ε, A, B, A.L, A.R,…}
p(ε) = 1, p(A) = p(B) = 2, …
I1 = {{ε}, {A.L}, {B.R}}
I2 = {{A, B}}
B.L ≤1 A.L.D ≤1 A.L.C …
B.L ≤2 B.R.F ≤2 B.R.E …

Game theory and its applications 10/28

5
 Strategy of player i
Definition: A strategy of player i is a function that assigns an action to every non-
terminal action sequence q such that
– it is i’s turn to move after q (i.e., p(q) = i )
– q is consistent with earlier moves defined by the strategy
with the restriction that the same action must be assigned to q and q’ whenever
q and q’ belong to the same information set of i

Example

Game theory and its applications 11/28

Example applications

ƒ modeling software protection as game

– it turns out that in certain cases, software firms can achieve higher
payoff by not protecting their software against piracy

ƒ modeling exchange protocols

– the concept of rational exchange – strongly related to the concept of
Nash equilibrium – can yield efficient exchange protocols with similar
properties to fairness

Game theory and its applications 12/28

6
 Model
ƒ there are two firms, A and B
ƒ they produce two software packages for price pA and pB
ƒ consumers gain extra utility σ from the support provided by the software
firms to those customers who pay for the software
ƒ illegal software users cannot obtain support from an independent
supplier
ƒ consumers are of two types:
– type 1 – support-oriented consumers
– type 2 – support-independent consumers
ƒ the populations of support-oriented and support-independent consumers
have the same size, and the total population size is 2 units
ƒ in addition, consumers rank the two software packages differently
– ranking is represented by a value x between 0 and 1, where a value closer to
0 means preference for software A, and a value closer to 1 means preference
for software B
ƒ the distribution of consumers is uniform over the set of all possible ranks

Game theory and its applications 13/28

Possible moves and their payoff

ƒ each consumer has 5 possible moves:
– buy software A
– buy software B
– pirate software A
– pirate software B
– do not use any software
ƒ number of consumers using software A (legally and illegally) is nA
similarly, number of consumers using software B is nB
ƒ payoff is increased with an increase in the number of other consumers
using the same software package (network externality)

Game theory and its applications 14/28

7
 Further notation
ƒ for a given price pair (pA, pB) let
– xA^ be the support-oriented consumer who is indifferent between
buying software A and not buying any software

– xB^ be defined similarly

– yA^ be the support-independent consumer who is indifferent between
pirating software A and not using any software

– yB^ be defined similarly

– x^ be the support-oriented consumer indifferent between software A
and B

Game theory and its applications 15/28

The game
ƒ two stages:
– stage 1: the two firms set their software price
– stage 2: consumers make their moves

ƒ solution concept: subgame perfect Nash equilibrium

– we are looking for strategy profiles that induce a Nash equilibrium in each subgame of
the game

ƒ an equilibrium of the second stage subgame is a partition between those who

buy software A, who buy software B, who pirate software A, who pirate software
B, and who don’t use any software, such that no individual would be better off by
changing his behavior

note: if µ > 1/2, then there’s no pure strategy Nash equilibrium in software
prices in which both firms sell strictly positive amounts and earn strictly positive
profits
Æ hence, we will assume that µ < 1/2

Game theory and its applications 16/28

8
 Solving the subgame

Game theory and its applications 17/28

Solving the subgame

solving for nA and nB:

substituting into the expression of x^:

Game theory and its applications 18/28

9
 Nash equilibrium in software prices
ƒ firm A chooses pA to maximize
ƒ firm B chooses pB to maximize

ƒ best response functions:

ƒ equilibrium prices and profit levels:

Game theory and its applications 19/28

The game with software protection

ƒ piracy is not possible Æ consumers must choose between
buying the software or not using it

Game theory and its applications 20/28

10
 Nash equilibrium in software prices
ƒ firm A chooses pA to maximize
ƒ firm B chooses pB to maximize

ƒ best response functions:

ƒ equilibrium prices and profit levels:

Game theory and its applications 21/28

Comparison of profit levels

ƒ no protection:

ƒ protection:

ƒ when µ < ½ (as this was assumed), the firms make less
profit if they use software protection ( (3-4µ) < (5-8µ)2 )

Game theory and its applications 22/28

11
 Rational exchange – informal definition
ƒ A misbehaving party cannot gain any advantages
Æ Misbehavior is uninteresting and should happen only
rarely.

ƒ few rational exchange protocols proposed in the literature

– Jakobsson’s coin ripping protocol
– Sandholm’s unenforced exchange
– Syverson’s rational exchange protocol
ƒ they seem to provide weaker guarantees than fair exchange
protocols, but …
ƒ they are usually less complex than fair exchange protocols
Æ trade off between complexity and fairness
Æ interesting solutions to the exchange problem

Game theory and its applications 23/28

Rational exchange – formal definition

Rationality ~ Nash equilibrium
ƒ Rationality: a misbehaving party cannot gain any advantages
ƒ Nash equilibrium: a deviating party cannot gain a higher payoff (given
that the other parties do not deviate)

Formal definition of rationality

ƒ protocol: π = { π1, π2, π3 }
ƒ protocol game: Gπ
ƒ each program πi is represented by a strategy si* in Gπ
ƒ the network has a single strategy snet*
ƒ we consider the restricted protocol game Gπ |s ,
where s = (s3*, snet*)
ƒ the protocol is rational iff
– (s1|s*, s2|s*) is a Nash equilibrium in Gπ |s
– both players 1 and 2 prefer the outcome of (s1|s*, s2|s*) to any other Nash
equilibrium in Gπ |s

Game theory and its applications 24/28

12
 An example: a rational payment protocol

U Æ V : m1 = U, V, tid, val, h(rnd), SigU(U, V, tid, val, h(rnd))

V Æ U : m2 = srv
U Æ V : m3 = rnd
if V received m1 and m3 : B : charges U with val
V Æ B : m4 = m1, m3, SigV( m1, m3 ) credits V with val

if V received only m1 :
B : charges U with val
V Æ B : m’4 = m1, SigV( m1 )

Brief informal analysis

ƒ no fairness, but …
ƒ none of the parties gain any financial advantages by cheating
ƒ needs a TTP (the bank), but …
ƒ the bank is needed anyway to maintain accounts
ƒ it performs the same operations as in any check based payment system

Game theory and its applications 25/28

An application: micropayment schemes

PayWord
ƒ chain of hash values
wn wn-1 = h( wn ) wn-2 = h( wn-1 ) … w0 = h( w1 )

ƒ commitment
C = { V, certU , w0 , exp, data }PrKU

ƒ protocol

User ( U ) Vendor ( V )
C
1, w1
first part of service
2, w2
second part of service
Broker ( B ) :
…

x, wx If ( C, x, wx ) then
- charge U with x units;
last part of service
- pay V x units;

Game theory and its applications 26/28

13
 An application: micropayment schemes
Our improvement to PayWord
ƒ hash chain size is doubled
( wn’ wn ) ( wn-1’ wn-1 ) … ( w1’ w1 ) w0’
ƒ commitment
C = { V, certU , w0’ , exp, data }PrKU

ƒ protocol
User ( U ) Vendor ( V )
C
1, w1
first part of service
2, w1’ Broker ( B ) :
3, w2
If ( C, 2x, wx’ ) then
second part of service - charge U with x units;
4, w2’ - pay V x units;
…

2x-1, wx If ( C, 2x-1, wx ) then

- charge U with x units;
last part of service - pay V x-1 units;
2x, wx’

Game theory and its applications 27/28

Summary
ƒ Game Theory was invented to analyze situations where
parties with potentially conflicting interests are interacting
Æ this is the case in many e-commerce applications

ƒ Game Theory has been successfully used to analyze

incentives and explain some phenomena in the field of
security engineering (see Anderson’s work on the Economics
of Security)

ƒ a related field is Mechanism Design (Reverse Game Theory)

which is concerned with designing games with certain
properties (e.g., truthfulness) Æ interesting direction for
research on e-commerce protocol design

Game theory and its applications 28/28

14