1) Coalitional Game Theory Flashcards
The Shapley Value: Axioms and Properties
Efficient
Fair way of dividing the grand coalitions payment
Members receive payoff proportional to their marginal contributions
> Interchangeability
Symmetry
Dummy Player
Additivity
Example: Voting Game
The Shapley Value function
Ways the Set S / Coalition could have formed prior to player I addition (S!)
Ways the remaining players could be added
Summing over all possible combinations of coalitions that are there before I
Average dividing by 1/N!
The Core: Propoerties
Analogous to Nash Equilibrium (no profitable deviations) but for GROUPS of agents
> A set, assigning a unique payoff distribution
> efficient
< individual rational
coalitional rational
Example: Voting Game with 80% majority
simple game
for all coalitions, the value is either 0 or 1
In a simple game, the core is empty if there is no veto player,
if there is one, the core consists of all payoff vectors in which non veto players get 0
Convex Game
Stronger assumptions than superadditivity
Accounts for overlap
The value of the union of two sets is at least as big as their values alone minus their intersection
Here, The Shapley Value is in the core
The Nucleolus
Assigns a unique payoff distribution
The payoffs assigned are within the core
always unique
MAking the largest dissatisfaction as small as possible
(Excesses)
Imputations
The payoff distributions for N that are
Efficient and
individually rational
Excess
a measure of dissatisfaction f the coalition Se with the Imputation x
> The difference between what S can contain on its own and what it receives from x
If excesses is positive contains less than its own worth
Nucleolus procedure
1: Find the imutations for which maximal excess among all coalitions as small as possible
- -> if there is a unique one, it’s the core baby
2: If not: Determine the coalitions for which maximal excess can not be increased further.
3. Continue with remaining coalitions and find the iputations for which excess among remaining coalitions as small as possible –> if unique imputation –> the Nucleolus if unique
Nash Bargaining Solution
Unqiue solution to a two player bargaining problem,
satisfying the axioms:
Assigning a feasible point to every bargaining problem
1) Invariance of Scale
2) Pareto optimality
3) Independence of irrelevant alternatives
4) Symmetry
BArgaining Problem
is a pair (S, d)) with the deasible set, S and the disagreement point, d.
> Convex
closed and bounded
Game ends in d if they do not reach an agreement
Symmetry
Allocates equal (symmetric) payments to symmetric players
Scale Covariance
in a bargaining problem,
two utilties that are linear transformation should represent or results in the same preferences.
Independence of irrelevant alternatives
If a is preffered option in S and T is a subset of S then the preference should still hold in T
