w5 cooperative games/ coalitional games

Question 1

what are cooperative games

Answer 1

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

Question 2

why are cooperative games also called coaliation games

Answer 2

to emphasize the formatino of coalitions

the only requirment is that players can make and commit to decisions

Question 3

what is the real number v(S) mean

Answer 3

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

Question 4

what is the coalition of all players called

Answer 4

it is called the grand coalition

Question 5

what does a coalition need in order to form

Answer 5

it needs the agreements of all its memebers to form

Question 6

t/f when two coalitions are formed, we assume theyer disjoint.

Answer 6

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

Question 7

what is a superadditive game

Answer 7

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

Question 8

example of a superadditive game

Answer 8

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

Question 9

what is a simple coalitional game

Answer 9

a game is simple if the worth of any coalition is either 1 or 0 ie wining or losing

Question 10

what is a weighted majority game example

Answer 10

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

Question 11

what are weighted majority games

Answer 11

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)

Question 12

how can coalitions be structured example

Answer 12

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

Question 13

what is a outcome coalation structure cs

Answer 13

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

Question 14

what is a payoff vector

Answer 14

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

Question 15

what is an outcome of a coalitional game

Answer 15

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.

Question 16

when is a payoff vector efficent

Answer 16

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

Question 17

what does it mean when a payoff vector is individually rational

Answer 17

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

Question 18

when is a vector x called an imputation

Answer 18

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

Question 19

what are stability and fairness in coalition

Answer 19

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

Question 20

what is a core

Answer 20

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

Question 21

what happens if x(S) is < v(S)

Answer 21

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

Question 22

what happens if x(S) >= v(S)

Answer 22

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

Question 23

for core of superadditive games, what does the set of vector x need to staisfy

Answer 23

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.

Question 24

can games have an empty core?

Answer 24

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

Question 25

what is the shapley value

Answer 25

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

Question 26

what is the marginal contirbution of an agent

Answer 26

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

Question 27

what is a dummy player and how does the shapley value relate to it

Answer 27

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

Question 28

when are two players symetric in a coaltion game

Answer 28

if they contribute equally to each coaltition

Question 29

what are the properties of a shapeley value

Answer 29

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.