Joshua LetchfordJoshua Letchford - Duke University

CPS 296.1

LP and IP in Game theory

(Normal-form Games, Nash Equilibria

and Stackelberg Games)

Joshua Letchford

Rock-paper-scissors ¨C Seinfeld variant

MICKEY: All right, rock beats paper!

(Mickey smacks Kramer's hand for losing)

KRAMER: I thought

h

h paper coveredd rock.

k

MICKEY: Nah, rock flies right through paper.

KRAMER: What beats rock?

MICKEY: (looks at hand) Nothing beats rock

rock.

0 0 1,

0,

1 -1

1 1,

1 -1

1

-1,

1 1 0,

0 0 -1,

1 1

-1, 1 1, -1 0, 0

Dominance

? Player i¡¯s strategy si strictly dominates si¡¯ iff

¨C for any s-ii, ui(si , s-ii) > ui(si¡¯, s-ii)

? si weakly dominates si¡¯ if

-i = ¡°the player(s) other

than i¡±

¨C for any s-ii, ui(si , s-ii) ¡Ý ui(si¡¯, s-ii); and

¨C for some s-i, ui(si , s-i) > ui(si¡¯, s-i)

strict dominance

weak dominance

0 0 1,

0,

1 -1

1 1,

1 -1

1

-1,

1 1 0,

0 0 -1,

1 1

-1, 1 1, -1 0, 0

Mixed strategies

? Mixed strategy for player i = probability

distribution over player i¡¯s (pure) strategies

? E.g.,1/3

E g 1/3

, 1/3

, 1/3

? Example

p of dominance by

y a mixed strategy:

gy

1/2

1/2

3, 0 0, 0

0, 0 3, 0

1 0 1,

1,

1 0

Usage:

¦Òi denotes a mixed

strategy,

si denotes a pure

strategy

Checking for dominance by mixed strategies

? Linear program for checking whether strategy si* is

strictly dominated by a mixed strategy:

? maximize ¦Å

? such that:

¨C for any s-i, ¦²si psi ui(si, s-i) ¡Ý ui(si*, s-i) + ¦Å

¨C ¦²si psi = 1

? Li

Linear program ffor checking

h ki whether

h th strategy

t t

si* is

i

weakly dominated by a mixed strategy:

? maximize

i i ¦²s-i[(¦²si psi ui(s

( i, s-i)) - ui(s

( i*,

* s-i)]

? such that:

¨C for any s-i, ¦²si psi ui(si, s-i) ¡Ý ui(si*, s-i)

¨C ¦²si psi = 1

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download