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
