When is an action dominant?

it always yields strictly more utility

than every other action of the same player

-> fixed strategy of other player…

When is an outcome pareto dominated?

there exists other outcome

in which every player is better off

How are normal-form games informally defined?

players choose actoin simultaneously and independently

utility defined for every combinations of actions

How are normal form games formally defined?

tuple

(N, Ai_ieN, ui_ieN)

where N = {1,…,n} set of players

Ai = {ai1, …, aik} set of actions for player i

ui : A -> R utility (payoff) function

Action Profile A = A1 x … x An

A _-i = A1 x A2 x … A_i-1 x A_i+1 x An (-> Action profile without actoin i)

outcomes (utility vectors)

(u1(a), …, un(a))

How are normal form games typically represented?

action player 1 -> row

action player 2 -> column

utilties for action combinations for different players in squares…

=> payoff matrix / bimatrix

exists other outcome

in which all players obtain

at least as much utility

and one player is strictly better of

=> sometimes called weak pareto dominance

When is an outcome pareto-optimal?

if it is not pareto dominated

-> no outcome where a player is better off

without decreasing utility of another player

Are all outcomes in the prisoners dilemma pareto-optimal?

no!

-> (1,1) (defect, defect) not

as (2,2) (cooperate, cooperate) yields higher utility for both…

When does an action ai (strictly) dominates another bi?

-> for fixed action profile A_-i

-> ai yields higher utility than bi

-> for every action profile…!!!

=> ai is always best choice…

When does ai weakly dominate bi?

ai yields at least as much utility for fixed action profile than other actions

in at least one action profile

it yields higher utility than all other actions

When does ai very weakly dominate bi?

Important thing of remembering when dealing with dominance?

COMPARE INDIVIDUALLY TO FIXED ACTION PROFILE

IF IT IS BEST STRATEGY FOR ALL ACTION PROFILES

-> DOMINATES!

What is a mixed strategy?

Lottery over actions

-> probability that a specific action will be chosen…

ai played with probability si(ai)

How is the support of a strategy si defined?

set of actions

that have a positive probabiltiy (not 0) to be played

How is the expected utility in mixed strategy games calculated?

given strategy profile

Sum over utilites of actions

times probability that this action is played (multiplicative probability over all strategy profiles)

assumed to be a vNM utility function!

What are pure strategies?

degenerate strategy lotteries

-> strategy where one action has probaility of 1…

How do we extend dominance to mixed strategies? What is a problem?

carries over from regular actions to strategies

-> use expected utility of strategy and compare to other strategies…

=> infinite number of strategies of other players possible!!!

=> S_-i infinite…!!!

How can we overcome the problem of mixed dominance?

expected utility takes extreme values in pure strategies (vertices of S_-i)

=> only have to check pure strategies of opponents when computing mixed dominance…

When is a strategy si a best response to the strategyprofile s_i-1?

best response denoted as

if

=> s_-i admits one or infinitely many best responses

What theorem did we discuss for iterated dominance in two-player games?

si is never a best response

iff it is dominated!!!

Are never best responses important for rational players?

no -> can disregard them…

What means iterated dominance?

way to find out dominant strategy (i.e. best response)

=> by eliminating dominated actions…

=> order is irrelevant

When is an action rationalizable?

action is rationalizable

if ratioal player could justifiably play it

against rational opponents

when rationality of all players is common knowledge

What is the set of rationalizable actions in two-player games?

all actions that survive the

iterated elimination of dominated actions

What is the complexity (O) of iterated dominance?

polynomial-time

-> as total number of actions is polynomial…

How can we efficiently check wether an action is dominated by some mixed strategy?

linear programming…!

What is the standard form in LPs?

How can we bring e.g. minimization of equalities in standard form?

minimization:

max -cTx (instead of min cTx)

equalities:

ax <= b and -ax <= -b

instead of ax = b

What are some LP algos and their worst-case running times?

simplex

exponential worst-case running time

ellipsoid

polynomial worst-case running time

interior-point

Is LP NP-hard?

no

-> P complete

-> every problem in P can be solved by a linear program

Name some LP solvers

glpk (GNU linear programming kit)

CPLEX (IBM)

Gurobi

How is an LP formulated to find wether ai is dominated ?

iff there is strategy si such that

the following LP has a solution with positive value

-> sum over all actions in strategy

-> probability of action times utility of action for given action profile A_-i

-> is larger than utility of ai (which we want to show that is dominated) for same action profile A_-i

-> where probabilities (si(bi)) >= 0

-> and sum over probabilites is 1

-> introduction of epsilon to show difference between left and right side

-> if negative, right is larger… => not dominated

always yields strictly more utility

-> fixed action of other player…

Last changeda year ago