02_Futhre_GT_and_Social_Choice

• static:

  • players take actions simultaneously

  • complete known payoffs

  • sense of equilibrium or stable outcomes

• dynamic:

  • take actions in turns…

• extensive (or tree) form

• -> makes temporal structure explicit…

• -> different actions and what is done based on these actions…

• much larger

• equilibria in normal form might be counterintuitive

• tree

  • nodes represent choice of one of the players

  • edge represents possible action

  • leaves represent final outcomes over which each player has a utility function

• complete specifictaion

• of which deterministic action to take

• at every node belonging to that player

• tuple (N, H, A, u)

• N =: set of players

• H := (Union _i elenent N(H_i)) Union T

  • partitioned set of histories

  • elements are the sequence of actions taken by players

  • Hi are the sequences after which player i takes an action while the set T of terminal leaf nodes are the set of outcomes

• A := A1 x A2 x … x An

  • set of pure action profiles

  • each ai element Ai

  • is a function ai : hi element Hi -> ai (hi) -> specifying action taken by player i for every history they move

• u := (ui:T->R) -> payoffs to the players for each outcome of the game

• we have set of players N

• the union of histories of each player

  • where the individual histories i denote the sequences after which a player takes the next turn…

  • unioned with possible outcomes

  • => sub-trees…

• action profiles that map histories to next actions

• and utility function over al possible outcomes for each player

• specify the different actions the players can take (e.g. first player C, W; second player CC, CW, WC, WW)

• -> build matrix from it (even if it theoretically does not make sense to combine C and WC…)

• => assign the outcomes based on action of player 1 and second action of player 2 (right of the actoins is player 1s action (e.g. WC -> player 1 wait, player 2 cross)

• does not really take temporal relation into consideration

• -> we can have equilibria depending on non-credible threats (meaning player 1 chooses sth to avoid a bad outcome, like crossing the street, as it knows that crossing is the best action for player 2… (unless player 1 starts to cross) => which should be captured as we have temporal hierarchy in dynamic game…

• given perfect information extensive form game G

• -> sub game of G rooted at h

• -> is restriction of game G to the descendants of h

• => set of subgames consist of all subgames of G rooted at some node in G (-> basically a sub-tree…)

• only consider sub-game perfect equilibria

• all strategy profiles of game G

• such that for any sumgame G’ of G

• the restriction of s to G’

• is nash equilibrium of G’

=> basically prune sub-trees from non-nash equilibria…

=> so for SGE strategy s holds, that s is nash equilibrium in sub-tree (of course considering the removed actions corresponding to the part not in the sub-tree)

at least 1 subgame perfect equilibrium

• yes -> as G is a subtree of itself !!

• method to find SPE (subgame perfect equilibria) from bottom up…

• identify equilibria in botto-most subgame trees

  • assume they’ll be played

• back up in larger tree

• label upper node where i plays with utility vector of its children (basically choose highest utility for current player and use this utility for the previous node and than repeat for higher layers while marking the edge that was taken each time…

• what to do with ties?

• multiple equilibria possible -> can again face equilibrium selection problem…

• players are uncertain about game being played

• represent this uncertainty as probability distribution over set of possible games (or payoffs of players)

1. all gmes have same number of agents and same strategy space

   • only payoff (types) can be different

2. common prior assumption

   • probability distribution over games is common knowledge…

• tuple (I, A, Sigma, F, u)

• I := set of agents

• A = A1 x A2 x … x An -> ai set of actions available to player i

• Sigma = Sigma 1 x … x Sigma n

  • sigma i is type space of player i (each player has probability distribution of what type it is…)

• F: Sigma -> [0,1]

  • common prior over types (known probability distribution over types…)

• u = (u1, …, un) where ui : A x Sigma -> R => utility function for player i based on the action and player type

• straigth forward extension by sigma and F

• => bayes nash equilibrium (BNE) also straightforward extension of NE

  
  

• players maximize expected ex-ante (before the event) utility given types and strategies of other players

  
  

• yes

• probability distribution for actions of each player

• => condition action on realization of their type

• => no player should have incentive to deviate even after knowing their type

• bi-matrix for every sigma combination…

• matrix with each type and action combinations for all types for a player

  • e.g. type (1,2) aciton (U,D)

  • -> rows :

    • 1U2U

    • 1U2D

    • 1D2U

    • 1D2D

  • => columns same for player 2

• => calculate expected utility for each combination…

• (do this by calculating sum of each utility times probability…)

• blows up…

• players wont deviate, even after knowing the other players types… (-> probability distribution of types doesnt matter…. could be one for a specific type…)

• BNE -> wont deviate even if they know their own type…

• ex-post -> wont deviate even when knowig other players types…

• no

• type -> knowledge of utility function about outcomes

• common known prior distribution over types (compared: probability being type 1 is common knowledge, actual utliity being type1 is private informatino…)

  
  

• on their type

  • 2 actions, based on what type they will get… => pure strategies..

  
  

• each players strategy (for every type) is best response to other players strategies

  • -> in expectation with respect to the prior…

• stable coalition formation

• coaliions are useful as

  • can achieve things they cannot alone

  • can be more efficient than single ones

• but must be strategically stable

  • no sub-coalition could do better by breaking off…

• N set of agents

• Each subset (or coalition) S of agents -> can work together leading to various utliities for the agents

• => cooperative theory studies which outcome will/should materialize

• key criteria:

  • stabiility: no coalition of agents should want to deviate from solution and go their own way

  • fairness: agents should be rewarded for what they contribute to the group

• they have a specification of what each coalition of agents can achieve

• -> transferable and non-transferable utilitiy

• transferable:

  • each coalition has a single value for utility

  • => can freely distribute the utility among the members of the coalition

  • e.g. {A,B} coalition has value of 4 -> can divide among themselves

• nontransferable:

  • each coalitoin has set of utility possibility vectors

  • e.g. {A,B} has vectors (1,2) and (3,1) -> fixed distribution of utility among members…

• pair (N,v)

• N is finite set of players, indexed by i

• v : 2^N -> R associates each coalition S (subset of N) a real-valued payff v(S) that coalitional members can distribute among themselves

• v is called characteristic funtion with v(empty set) = 0

• its worth

• which coalition will form?

• how should that coalition divide its payoff among its members?

• coalitional game has a single coalition of all members….

• different parties (each with different number of representatives)

• vote e.g. on spending bill and how control of it is split among the parties

• majority vote required to pass legislation

• if bill doesnt pass (each outcome has less thatn 50 votes) -> every party gets 0

generallly:

• set of agents N

• set of coalitions w subset 2^N that are winning coalitions

  • -> coalitions sufficient for passage of the bill if all its members choose to do so…

• each coalition S element W we assign v(S) = a

• all others v(S) = 0

• superadditive and additive

• payoff of union of disjunct coalitions is greater than sum of individual payoff

  • => coalitions can always work together without negative interference and possibly positive interference

  • => grand coalition has highest payoff among all coalitional structures

• no inference among disjoitn coalitions

• => sum of payoff of union of disjoint coalitions is equal the sum of the individual payoffs

• => no benefit by working together…

• additive: working together does not incrase total payoff

• superadditive: working together can potentially increase overall payoff

• 
  

• how to divide the payoff to the grand coalition among the agents?

• many of most studiet games are superadditive

  • -> grand coalition achieves highest payoff from superadditive games

    • expet it to form…

  • agents may be forced to join - e.g. public projects often must include al participants…

• dreizack(N,v) -> vecror giving shares of agents in grand coalition payoff

• => as agents are indiced with i

• -> x is payoff distribution vector and xi (i-th element in x) is the share of agent i elemen N

• each coalition simply has a value…

• which coalition will form

• how should that coalition divide its payoff among its members…

• set of agents N

• set of coalitions W (subset) 2 ^N -> that are winning coalitions (only those coalitions that actually ahve enough votes…)

• each coalition S element W gets assigned v(S) = 1 and the others v(S) = 0

• superadditive -> there are positive effects when non-overlapping coalitions work together (their combined payoff is at least as much as the sum of their individual one…)

  • => grand coalition has highest payoff

• no (positive or negative) interference among disjoint coalitions…

  
  

• => given S, T (subset) N and S (schnitt) T = Empty set

• superadditive: v(S U T) >= v(S) + v(T)

• addditive: v(S U T) = v(S) + v(T)

  
  

• contains all payoff vectors which don’t distribute more than the worth of the grand coaliiton…

• => {x | SUM x_i < v(N)}

  • => as grand coalition has highest payoff… individuals cannot gain more when working individually than the whole grand coalition would get…

  • 
    

• set of feasible payoffs that are efficient…

• -> efficient := distribute the entire worht of the grand coalition…

• => {x | SUM x_i = v(N)}

• conatins all payoffs in P (per-imputation set) where each agent gets at least what he would get when working alone (singleton coalition…)

• C = {x € P | Forall i €N, x_I >= v({i})}

• => imputation set

• => when payment profiles are drawn from the core, agents have an incentive to form the grand coalition…

• Forall S (subset) N, Sum (i in S) x_i >= v(S)

• => thus, agents in each coalitoin get together at least as much as they would get alone….

• linear programming

• => promblem: number of constraints is exponential in number of players…

• => there is a set of theorems we can use…

• a concept of stability…

  
  

• can be empty or contani more than one payoff vector

• Parties A (45), B(25), C(15), D(15)

• Sum of payoffs to B,C and D is <100M, this set of agents has incentive to deviate and form coalition with A

• but if B,C and D get entire 100M, (A gets 0) -> A has incentive to form coalition with whichever of B,C and D got the least…

• => Core is empty, as grand coalition would not be stable, but parties would deviate from it…

=> No, core may not define unique payoff vector…

• 80% majority required

• A(45), B(25), C(15), D(15)

• -> Winning coalitions are {A,B,C}, {A,B,D}

• -> all winning coalitions must have support of A and B

• -> Any complete distributino of the 100M among A and B belongs to core -> as they HAVE to be in winning coalition…

• ( might be counerintuitive but formal definition holds… (alhgouth C and D would get nothing, but still at least as much as they would get alone (also 0)))

• every non additive constant sum game has an empty core

• every convex game has a nonempty core

• in a simple game, the core is empty iff there is no veto player

• V(N\{I}) = 0

• => coalitons can only win when including the veto player…

  
  

• Sum of worths of 2 coalitions that partition N equals worth of grand coalitino

• => partitioning grand coalition also partitions the wirht of the grand coalitino…

=> Forall S (subset) N

• v(S) + v(N\S) = v(N)

• NO

• but every additive game is constant sum…

• superadditive game with added condition

  • if subsets S,T of N do overlap

  • worth of their combination still at least as great as sum of their worths alone

  • even when we subtract awaay the worth of their overlap…

• v(S U T) > v(S) + v(T) - v(𝑺 ∩ 𝑻)

• coalitions payoff is either 0 or 1…

• => used to model voting simulations (e.g. pass or dont pass… (binary outcome))

• Game Theory

  • how do self-interested agend behave strategically in a game to maximize their utility?

• Social Choice Theory

  • How can we aggregate preferences to reach a collective decision?

• Mechanism Design

  • reverse game theory

  • how to design game which

    • knowing that all participants are self-interested agents

    • implements certain objectives in equilibrium (maximizes social welfare)

    • restricts the domain of preferences (e.g. payoff maximizatino)

• voting rules

  
  

• input:

  • n voters and m alternatives

  • preference profile by each voter (ordered vector ranking of aletarnatives)

• output:

  • winning candidate

  • or aggregate ranking of all candidates

• vote does not need complete ranking -> may only consist of single alternative (what to vote for)

• -> outcome is single winnner which is ranked 1st by number of votes

• -> used in many countries to vote… (majority voting…)

• input: voters specify subset of alternatives they approve (ranking irrelevant)

• winner: alternative with highest approval score

• => compared to plurality voting -> more than one choice possible…

• input: complete ranking (e.g. eurovision)

• -> for each vote, each alternative receives m-1 points for 1, m-2 for second rank etc….

• -> winner: alternative with greatest borda score vote

• Candidate is condorcet winner -> if wins in pairwise comparision against all other alternatives (but might not win in pluarlity vote…)

• => and does not always exist…

• pairwise election winners might induce cycle in societal rankings… (no total ordering possible)

• if candidate ranked first by majority of votes -> candidate should win

• => not satisfied by all rules (e.g. borda…)

• if alternative is chosen from set of alternatives

• -> then it is also chosen from al its subsets

• => e..g apple over oranges -> also holds for each voter…

• => plurality voting is not consistent…

• pluraility with 2 candidate runoff

  • -> do regular plurality votind and then again vote with only previous first and secons place as legit alternative…

• egalitarian (maximize minimum voters rank)

• tournament solutions (based on pairwise majority relations)

• “2 alternatives are easy”

• -> some properties are desirable in voting rules

  • -> anonymous -> names of voters irrelevant

  • -> neutral -> name of candidates irrelevant

  • -> monotonicity -> if particular candidate wins -> if voter improves its vote towards this candidate, the candidate still wins

Theorem:

• with 2 candidates, voting rule is anonymous, neutral and monotonic if and only if it is the plurality vote

• given:

  • let O denote finite set of outcomes (or alternatives…)

  • let L^n be the set of preference orderings of a set I of n voters

• social choice functoin:

  • over I and O

  • C: L^n -> O (produces outcome from set of prefecences of set of I voters)

• social choice correspondence

  • over I and O

  • C: L^n -> 2^O

  • returns set of canidates instead of single one

• social welfare function

  • over I and O

  • W: L^n -> L

  • takes orderings from different voters and returns single total ordering on set of alternatives O

• pareto efficiency (or unnaimity)

  • if al votes rank a above b -> then rule ranks a above b

• independence of irrelevant alternatives (or IIA)

  • if rule ranks a above b for current voters

  • and if we then cnahge votes but do not change relative ordering of a and b in changed votes then a should still be ranked ahead of b

• non-dictatorship

  • there does not exist a voter such that the rule simply always copies that voters ranking

• assume at least 3 alternatives

• every social welfare funciton that satisfies pareto efficiency and IIA is dictatorial

• voter prefers A > B > C

• -> with truthful voting, B and C are tied

• -> Thus, if voting with B > A > C, the voter can swing the outcome so that at least its second preffered choice wins…

• supporse at least 3 candidates/alternatives

• there exists no rule that is simultaneously:

  • onto (for every candidate there are some votes that would make that candidate win)

  • non dictatorial

  • and non manipulable (i.e. dominant strategy truthful)

• proved taht all voting schemes can work badly at some timems -> most not work badly all of the time

• domain covered is unrestricted but ordinal and mechanism deterministic (preference list )

  • -> cardinal voting schemes not covered (e.g. score voting)

  • => cardinal conveys more informaiton than rank orders and may satisfy monotonicity, ocnsistency and IAA

• => Arrows consider only social welfare funcitons

• relax the properties

  • i.e. IIA, pareto optimality or consistency

• randomization

  • rendom serial dictatorship

• limit the domain

  • only two candidates

    • then plurailty vote is best after mays theorem

  • single peaked votes

  • allow for monetrary transfers and assume qualilinear utility funcitons (comes later in other lecture…)