01_Combinatorial_Auctions

• we do not have complete information

• -> cannot run simple optimization problem…

• => decision making process is decentralized as we have multiple entities participating…

  
  

• market regulates itself…

• does not always hold completely true -> needs markted design etc.

• strategic behavior

• -> requires game theory…

also called simultaneous move game

-> each player chooses action

-> without knowing what the other players chose

• every player knows the payoff resulting in the choices of the different players (we know each possible outcome that can happen…)

• two people using TCP

• Congestion control

• correct implementatoin: do congestion control

• defective implementation: dont backoff with congestion control but keep / increase sending rate…

• => 2 possible strategies:

  • C (use correct implementation)

  • D (use defective -> better result if other uses correct…)

• bimatrix representation

• -> row actions user 1

• -> columns actions user 2

• rowxaction

  • C x C -> average delay 1ms

  • D x D -> delay 3 ms for both

  • C x D / D x C -> C no delay, D 4 ms delay

• row : your actions (row player)

• columns: other player (column player)

• (R x C) -> (Payoff Row player x Payoff Column Player)

bimatrix in general:

matrix of payoff tuples

• xT R y for player 1

• xT C y for player 2

-> where x is player 1s strategy and y player 2s strategy ([0,0,1,0,0,..,0]…)

• Show every players utility for every state

• -> states depending on players combined actions…

• normal form games

  • pure and mixed strategy

  • nash equilibrium

  • computation of nash equilibria

• extensive-form games

  • subgame-perfect equilibrium

• bayesian games

  • bayesian nash equilibrium

  • ex-post nash equilibrium

A (finite, n-person) normal form game is tuple (I, A, u)

• I := finite set of n players, indexed by i

• A = A1 x A2 x … x An := Ai is finite set of actions available to player i

  • vector a = (a1,…, an) element A called action profile

  • -> means, certain combinations of actions each player takes…

• u = (u1, u2, …, un) where ui : A -> R => real-valued utility (or payoff) funtion for player i…

  • -> describes the utility for each rows in a for a cetain player (outcome based on combinations of all players actions..)

• for every action profile

• all players have same payoff

• => uj(a) = ui(a) for all a element A

• each player has same utility for specific action profile

• -> players want to play as team to get maximum payoff for all players…

• => coordinate on action maximally beneficial for all…

• two car drivers in country with no driving rules

• -> can choose to drive right or left…

• => if drive on same side -> no payoff for both

• -> if drive on different sides -> payoff of 1 for both

• => want to coordinate as this is maximal beneficial for both…

• primarily meaningful for 2 players

• -> there exists a constant for each action profile A1 x A2 so that u1(a) = u2(a) = c

• => combined payoff is always the same…

• e.g. one winner or one looser with win = loss…

• pure strategy

• mixed strategy

• select single action and play it

• let (I, A, u) be normal-form game

• for any set of actions A, let Prod(A) be the set of all probability distributions over A

  • => thus not pick definite action but have certain distribution to pick different actions…

• => mixed strategies of player i : Si = PROD(ai) => the prob distribution of the different actions…

• => results in set of mixed strategies (mixed strategy profiles) S1 x S2 x … x Sn

• suppose one knows opponents mixed / pure strategy

• => calculate probable payoff for each of your actions

• => pick the one with highest payoff…

  
  

• single-agent decision theory

  • maximize agents expected payoff in given environment (optmal strategy)

• multiple agents:

  • 
    

• if a players payoff can be increased without reducing some others player payoff

• strategy profile s dominates strategy profile s’ if

• for all i element I, ui(s) >= ui(s’) (utility stays at least the same)

• and there is some j element I for which

  • uj(s) > uj(s’) -> at least one player has higher utility for strategy profile

    
    

• partial ordering over strategy profiles

• => in general, not best strategy profile only set of incomparable optima…

• strategy s if pareto optimal / strictly pareto efficient

• if there is no strategy profile s’ element S that pareto dominates s

• yes -> at least one for every game

• always play pure strategies

• zero-sum games

• view from outside,

• => view on all players…

• pareto -> look from outside at whole game

• nash -> look at games from players point of view

• we do not know strategy profile of other players

• => else -> would we would simply maximize payoff and play pure strategy…

• let s_-i be the strategy profile without i’s strategy

• player i’s best response to s_-i is mixed strategy s*_i

• so that ui(s*_i, s_-i) >= u(s_i, s_-i)

• => mixed strategy better than all pure strategies…

• player does not generally know what strategies others will adopt…

• => best response not solution concept…

• strategy profile s = (s1, s2,…, sn)

• is a nash equilibrium if

• for all agents i, s_i is best response to s_-i

• => meaning, that each player plays best response (maximize utility) for given other strategies…

• even if players would know what action other players choose

• -> would not change own action

  
  

• when at least one individual would have incentive to deviate from the outcome (in case it knows other acitons…)

• => thus, given the other players strategies, there is no strategy than increases the players utility…. (for all players)

• pure -> choose single action

• mixed -> choose mixed strategy (probabilities…)

• -> yes (see intuition of nash equilibrium)

• -> even if players would have knowledge -> would choose same strategy…

• assume other player plays 1 with p and 2 with (1-p)

• => calculate indifference

  • choose mixes strategy in such a way that the probabilities for other player are the same regardless of your choice…

• more than one equilibrium

• => no equilibrium outcome will happen if players aim at different equilibria…

• mutually beneficial for players if they choose different strategies…

• strategy profile (x,y)

• point in a (n+m-2) dimensional space

• => for each strategy profile, one can compute gradients for row and column player…

• fix points in vector field of gradient (no change…)

• every game with

  • finite number of players

  • finite number of action profiles

• has at least one (mixed) nash equilibrium

• yes…

• let S be set of tuples of mixed strategies chosen by each player

• let f(s) associate each such tuple with a new tuple where each players strategy is its best response to other players strategies in s

• then f has a fixed point in S with s element f(s)

• => basically, even knowing others strategies, all will stay at their own strategy

• => mathematical basis of nash theorem…

• can be multiple equilibria

• -> which one should you chose?

• -> how to do that

• => difficult problem!!!

• player i’s strategy s_i strictly dominates s’_i if for any

• s_-i :

• ui(s_i, s_-i) > ui(s’_i, s_-i)

• => basically:

• the strategy s leads to a real higher utility (> not >=) compared to all other possible strategies given the rest of the action profile remains the same (other players…)

strategy results in at least same utility compared to all others (given same aciton profile of other players)

and is real greater than some

• remove (strictly / weakly) dominated strategy, repeat

• => equilibrium in strictly dominant strategies necessarily unique nash equilibrium…

• iterated weak dominant

  • -> path dependent…

  • => sequence of eliinations may determine which solutions we get (if any)

• iterated strict dominance

  • path independent!!!

  
  

• yes!

• may not be only one

• not necessarily…

• sequential (pure) best response strategy…

• => start at one player and choose best response

• -> do the same for the other….

• …

• no, it might cycle…

• begin by playing sth random

• next time, play based under assumption that other player follows its empirical frequencies

• if converge -> nash equilibrium

• but can fail to converge…

• complete information

  • players know about all other players, their actions and payoffs

• perfect informaiton

  • used in extensive form games -> players know all pervious moves

• imperfect games

  • players only have beliefs about previous moves (thus have to use bayesian games)