w5 cooperative games/ coalitional games Flashcards
learn about superadditive games, simple games, weighted majority games, shapely value
what are cooperative games
games where players may create agreements that impose certain rules/behaviour on to other players and themselves
which groups will agree to make contracts
which agreements are reasonable and which aren’t
why are cooperative games also called coaliation games
to emphasize the formatino of coalitions
the only requirment is that players can make and commit to decisions
what is the real number v(S) mean
it is called the worth of the coalition
if the members of coalition S agree to form a group then they can expect to recieve utility v(S)
utility can be transferred between players
what is the coalition of all players called
it is called the grand coalition
what does a coalition need in order to form
it needs the agreements of all its memebers to form
t/f when two coalitions are formed, we assume theyer disjoint.
true
when two coaltions S and T are formed we assume they are disjoint and have nothing in common
the value of a coalition does not depend on players that are not in the coalition or other external coalitions
what is a superadditive game
the value of teams working seperatly is less or equal than the value of them working together
v(S) + v(T) <= v(S & T) union
there is no reason to form seperate coalitions
so agents generally will form a grand coalition in superadditive games
example of a superadditive game
Bill wade and tom are business men
bill estimates his profits of $170k
wade wants to make a new business which can yield an extra 150k
tom can make another company which can make 180k
together they would be unstopable B]
while they can work in pairs and make some money, (shown in example slide 8)
if they all work together, they can make the most money
what is a simple coalitional game
a game is simple if the worth of any coalition is either 1 or 0 ie wining or losing
what is a weighted majority game example
a special case of simple games
ex government voting
gov has 650 members
a group needs 326 supporters to form a goverment (majority)
1 = worth of being in the governing coalition
0 = worth of being an opp
in order to reach majority, at least two parties need to form a coalition
what are weighted majority games
a game is a weighted majority consists of a quota greater than 0 and each player has a weight.
the worth of each coalition is either 1 or 0 depending on if the sum of player weights in a team hit the quota (1) or dont (0)
how can coalitions be structured example
if we have 3 players 1, 2 ,3
then there are 7 possible non empty coalitions
1 2 3
1, 2
2,3
3,1
1,2,3
and five coalition structures
all seperate,
group of 2 and group of 1
all together
what is a outcome coalation structure cs
A coalition structure is a way of organizing the players in a game into disjoint coalitions (teams) such that each player is part of exactly one coalition. The outcome of the game depends on how these coalitions are formed and how they interact.
No overlap: Each player belongs to only one coalition.
Coalitions: A set of players who can coordinate their actions for mutual benefit.
the outcome of a game is formated into a coaltion structure where all the colatiosn are included and in each subset of coalitions there is no overlap between teams
what is a payoff vector
a solution that allocates the value of a grand coalition among players in a cooperative game. In other words, it’s a way to distribute the value of the grand coalition
we can write
x(S) = the sum of x for all i (players) in the coaltion
to denoate the total payoff of a coalition
A payoff vector is a solution in a cooperative game that allocates the total value of the grand coalition (all players cooperating) among the individual players.
In simpler terms, it’s a way to distribute the total value generated by cooperation among the players in a fair way.
a vector x
what is an outcome of a coalitional game
a pair (CS, x) where CS is a coalition structure of players and x is a payoff vector
Together, the pair
(CS,x) represents how the total value of the grand coalition is distributed among the players, considering their possible collaborations.
when is a payoff vector efficent
if x(S) = v(S)
a pay off vector is efficent for a coalition if every coalition gets exactly their worth
because when players form teams, we can assume they split the team’s worth among themselves
note: they cannot assign themselves more than their worth nor less than the total which would waste a part of their worth
what does it mean when a payoff vector is individually rational
x >= v{i}
each player i can gaurntee themselves v{x}
its logical to think that a player will join a team if they can get at least as much as they would alone
when is a vector x called an imputation
if it is efficent for a coalition structure (CS) and is individually rational
players want to join a coalition where they gain more than being alone and the team gets the worth they were suppposed to.
players will generalyl only consider joining a team if vector x is an imputation
what are stability and fairness in coalition
stability: what are the incentives for a player to stay in the team
fairness: how well each agents payoff reflects their team contribution
we uses these for evaluating outcomes
what is a core
a solution concept,
the set of feasible allocations where no coalition can gain more value by breaking away from the grand coalition
if this condition is met then the core is stable
what happens if x(S) is < v(S)
the agents in coalition S could do better by abandoning the team and making their own group
so this set up (called a core) is unstable
what happens if x(S) >= v(S)
the core of a team game is denoted by (N,v)
this is a stable core because no players have an incentive to deviate because they cannot do better alone
for core of superadditive games, what does the set of vector x need to staisfy
Xi >= 0 for all i belong to N
x(N) = v(N)
x(S) >= v(S) for all S
Non-negative payoffs: Every player must receive a non-negative payoff, meaning no player should be left out or penalized.
Grand coalition allocation: The total payoff for the entire group of players (grand coalition) must match the value that the coalition can generate collectively.
Coalition rationality: Any subset of players (a coalition) must receive at least as much value as they could achieve on their own, ensuring that no smaller group has an incentive to break away from the grand coalition.
can games have an empty core?
In a superadditive game, the core is based on the grand coalition, but it can be empty if there is no payoff allocation that satisfies all the conditions of stability and rationality.
Specifically, when the efficiency requirement (the total value of the grand coalition) contradicts the coalition rationality condition (where smaller coalitions have an incentive to break away), the core can be empty.
This situation arises when no distribution of the total value satisfies both individual coalition’s self-interest and the grand coalition’s efficiency.
yes, consider a super additive game so the outcome is based on the grand coalition
look at slide 26
but when it contradicts the efficency requirment the core is empty
what is the shapley value
a solution that tries to capture fairness
it mainly deals with the grand coalition and it assigns every coaltion game an imputation
its based on the idea that the reward each agent gets should match their contirbution
what is the marginal contirbution of an agent
please look at slide 31 for the formula week 5
measures how much i (a player) increases the value of the coaliton after it joints the team
what is a dummy player and how does the shapley value relate to it
if a player doesnt contirbute (ie the worth of the team is still the same after they join) then the shaply value does not give them a reward
Sh(N,v) = 0
when are two players symetric in a coaltion game
if they contribute equally to each coaltition
what are the properties of a shapeley value
efficency, dummy player, symmetry, additivity
Efficiency: The total value generated by the grand coalition is fully allocated to the players, meaning the sum of individual payoffs equals the total value of the grand coalition.
additivity For two games, the Shapley value of the combined game is the sum of the Shapley values from the individual games.
