Transcription
DefinitionsStability notionsOther solution conceptsSubclassesAn Introduction to Cooperative Game TheoryMaria SernaFall 2016AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesReferencesG. Chalkiadakis, E. Elkind, M. WooldridgeComputational Aspects of Cooperative Game TheoryMorgan & Claypool, 2012 Wikipedia.G. OwenGame Theory3rd edition, Academic Press, 1995AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclasses1Definitions2Stability notions3Other solution concepts4SubclassesAGT-MIRITU characteristic function gamesOutcomesImputationsCooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsNon-Cooperative versus cooperative GamesNon-cooperative game theory model scenarios where playerscannot make binding agreements.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsNon-Cooperative versus cooperative GamesNon-cooperative game theory model scenarios where playerscannot make binding agreements.Cooperative game theory model scenarios, whereAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsNon-Cooperative versus cooperative GamesNon-cooperative game theory model scenarios where playerscannot make binding agreements.Cooperative game theory model scenarios, whereagents can benefit by cooperating, andbinding agreements are possible.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsNon-Cooperative versus cooperative GamesNon-cooperative game theory model scenarios where playerscannot make binding agreements.Cooperative game theory model scenarios, whereagents can benefit by cooperating, andbinding agreements are possible.In cooperative games, actions are taken by groups of agents,coalitions, and payoffs are given toAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsNon-Cooperative versus cooperative GamesNon-cooperative game theory model scenarios where playerscannot make binding agreements.Cooperative game theory model scenarios, whereagents can benefit by cooperating, andbinding agreements are possible.In cooperative games, actions are taken by groups of agents,coalitions, and payoffs are given tothe group, that has to divided it among its members:Transferable utility games.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsNon-Cooperative versus cooperative GamesNon-cooperative game theory model scenarios where playerscannot make binding agreements.Cooperative game theory model scenarios, whereagents can benefit by cooperating, andbinding agreements are possible.In cooperative games, actions are taken by groups of agents,coalitions, and payoffs are given tothe group, that has to divided it among its members:Transferable utility games.individuals: Non-transferable utility games.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsNon-Cooperative versus cooperative GamesNon-cooperative game theory model scenarios where playerscannot make binding agreements.Cooperative game theory model scenarios, whereagents can benefit by cooperating, andbinding agreements are possible.In cooperative games, actions are taken by groups of agents,coalitions, and payoffs are given tothe group, that has to divided it among its members:Transferable utility games.individuals: Non-transferable utility games.For the moment we focus on TU gamesAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsNon-Cooperative versus cooperative GamesNon-cooperative game theory model scenarios where playerscannot make binding agreements.Cooperative game theory model scenarios, whereagents can benefit by cooperating, andbinding agreements are possible.In cooperative games, actions are taken by groups of agents,coalitions, and payoffs are given tothe group, that has to divided it among its members:Transferable utility games.individuals: Non-transferable utility games.For the moment we focus on TU gamesNotation: N, set of players, C , S, X N are coalitions.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function GamesA characteristic function game is a pair (N, v ), where:N {1, ., n} is the set of players andv : 2N R is the characteristic function.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function GamesA characteristic function game is a pair (N, v ), where:N {1, ., n} is the set of players andv : 2N R is the characteristic function.for each subset of players C N, v (C ) is the amount that themembers of C can earn by working togetherAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function GamesA characteristic function game is a pair (N, v ), where:N {1, ., n} is the set of players andv : 2N R is the characteristic function.for each subset of players C N, v (C ) is the amount that themembers of C can earn by working togetherusually it is assumed that v isAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function GamesA characteristic function game is a pair (N, v ), where:N {1, ., n} is the set of players andv : 2N R is the characteristic function.for each subset of players C N, v (C ) is the amount that themembers of C can earn by working togetherusually it is assumed that v isnormalized: v ( ) 0,non-negative: v (C ) 0, for any C N, andmonotone: v (C ) v (D), for any C , D such that C DAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function GamesA characteristic function game is a pair (N, v ), where:N {1, ., n} is the set of players andv : 2N R is the characteristic function.for each subset of players C N, v (C ) is the amount that themembers of C can earn by working togetherusually it is assumed that v isnormalized: v ( ) 0,non-negative: v (C ) 0, for any C N, andmonotone: v (C ) v (D), for any C , D such that C DA coalition is any subset of NAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function GamesA characteristic function game is a pair (N, v ), where:N {1, ., n} is the set of players andv : 2N R is the characteristic function.for each subset of players C N, v (C ) is the amount that themembers of C can earn by working togetherusually it is assumed that v isnormalized: v ( ) 0,non-negative: v (C ) 0, for any C N, andmonotone: v (C ) v (D), for any C , D such that C DA coalition is any subset of NN itself is called the grand coalition.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function Games vs.Partition Function GamesAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function Games vs.Partition Function GamesIn general TU games, the payoff obtained by a coalitiondepends on the actions chosen by other coalitionsthese games are also known as partition function games (PFG)AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function Games vs.Partition Function GamesIn general TU games, the payoff obtained by a coalitiondepends on the actions chosen by other coalitionsthese games are also known as partition function games (PFG)Characteristic function games (CFG): the payoff of eachcoalition only depends on the action of that coalitionin such games, each coalition can be identified with the profitit obtains by choosing its best actionAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsCharacteristic Function Games vs.Partition Function GamesIn general TU games, the payoff obtained by a coalitiondepends on the actions chosen by other coalitionsthese games are also known as partition function games (PFG)Characteristic function games (CFG): the payoff of eachcoalition only depends on the action of that coalitionin such games, each coalition can be identified with the profitit obtains by choosing its best actionWe focus on characteristic function games, and use the termTU games to refer to such gamesAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsBuying Ice-Cream GameAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsBuying Ice-Cream GameWe have a group of n children, each has some amount ofmoney the i-th child has bi dollars.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsBuying Ice-Cream GameWe have a group of n children, each has some amount ofmoney the i-th child has bi dollars.There are three types of ice-cream tubs for sale:AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsBuying Ice-Cream GameWe have a group of n children, each has some amount ofmoney the i-th child has bi dollars.There are three types of ice-cream tubs for sale:AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsBuying Ice-Cream GameWe have a group of n children, each has some amount ofmoney the i-th child has bi dollars.There are three types of ice-cream tubs for sale:Type 1 costs 7, contains 500gType 2 costs 9, contains 750gType 3 costs 11, contains 1kgAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsBuying Ice-Cream GameWe have a group of n children, each has some amount ofmoney the i-th child has bi dollars.There are three types of ice-cream tubs for sale:Type 1 costs 7, contains 500gType 2 costs 9, contains 750gType 3 costs 11, contains 1kgThe children have utility for ice-cream but do not care aboutmoney.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsBuying Ice-Cream GameWe have a group of n children, each has some amount ofmoney the i-th child has bi dollars.There are three types of ice-cream tubs for sale:Type 1 costs 7, contains 500gType 2 costs 9, contains 750gType 3 costs 11, contains 1kgThe children have utility for ice-cream but do not care aboutmoney.The payoff of each group is the maximum quantity ofice-cream the members of the group can buy by pooling theirmoneyAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsBuying Ice-Cream GameWe have a group of n children, each has some amount ofmoney the i-th child has bi dollars.There are three types of ice-cream tubs for sale:Type 1 costs 7, contains 500gType 2 costs 9, contains 750gType 3 costs 11, contains 1kgThe children have utility for ice-cream but do not care aboutmoney.The payoff of each group is the maximum quantity ofice-cream the members of the group can buy by pooling theirmoneyThe ice-cream can be shared arbitrarily within the group.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsIce-Cream Game: Characteristic FunctionAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsIce-Cream Game: Characteristic FunctionCharlie: 6Marcie: 4AGT-MIRICooperative Game TheoryPattie: 3
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsIce-Cream Game: Characteristic FunctionCharlie: 6Marcie: 4Pattie: 3w 500w 750w 100p 7p 9p 11AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsIce-Cream Game: Characteristic FunctionCharlie: 6Marcie: 4Pattie: 3w 500w 750w 100p 7p 9p 11v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 750, v ({C , P}) 750, v ({M, P}) 500v ({C , M, P}) 1000AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsOutcomesAn outcome of a game Γ (N, v ) is a pair (CS, x), where:AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsOutcomesAn outcome of a game Γ (N, v ) is a pair (CS, x), where:CS (C1 , ., Ck ) is a coalition structure, i.e., partition of Ninto coalitions: ki 1 Ci NCi Cj , for i 6 jAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsOutcomesAn outcome of a game Γ (N, v ) is a pair (CS, x), where:CS (C1 , ., Ck ) is a coalition structure, i.e., partition of Ninto coalitions: ki 1 Ci NCi Cj , for i 6 jx (x1 , ., xn ) is a payoff vector, which distributes the valueof each coalition in CS:xPi 0, for all i Ni C xi v (C ), for each C CS,AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsOutcomesAn outcome of a game Γ (N, v ) is a pair (CS, x), where:CS (C1 , ., Ck ) is a coalition structure, i.e., partition of Ninto coalitions: ki 1 Ci NCi Cj , for i 6 jx (x1 , ., xn ) is a payoff vector, which distributes the valueof each coalition in CS:xPi 0, for all i Ni C xi v (C ), for each C CS, feasibilityAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsOutcome:exampleSuppose v ({1, 2, 3}) 9 and v ({4, 5}) 4AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsOutcome:exampleSuppose v ({1, 2, 3}) 9 and v ({4, 5}) 4(({1, 2, 3}, {4, 5}), (3, 3, 3, 3, 1)) is an outcomeAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsOutcome:exampleSuppose v ({1, 2, 3}) 9 and v ({4, 5}) 4(({1, 2, 3}, {4, 5}), (3, 3, 3, 3, 1)) is an outcome(({1, 2, 3}, {4, 5}), (2, 3, 2, 3, 3)) is NOT an outcome astransfers between coalitions are not allowedAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function tive Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsImputationsAn outcome (CS, x) is called an imputation if it satisfies individualrationality:xi v ({i}),for all i N.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesTU characteristic function gamesOutcomesImputationsImputationsAn outcome (CS, x) is called an imputation if it satisfies individualrationality:xi v ({i}),for all i N.Notation: we denotePi Cxi by x(C )AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclasses1Definitions2Stability notions3Other solution concepts4SubclassesAGT-MIRICore and variationsFairness: Shapley valueComputational IssuesCooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?The solutions of a game should provide good outcomes.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?The solutions of a game should provide good outcomes.Let us present some stability notions related to outcomes orimputations.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?The solutions of a game should provide good outcomes.Let us present some stability notions related to outcomes orimputations.To simplify the presentation we consider superadditive games.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesSuperadditive GamesA game G (N, v ) is called superadditive ifv (C D) v (C ) v (D),for any two disjoint coalitions C and DAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesSuperadditive GamesA game G (N, v ) is called superadditive ifv (C D) v (C ) v (D),for any two disjoint coalitions C and DExample: v (C ) C 2v (C D) ( C D )2 C 2 D 2 v (C ) v (D)AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesSuperadditive GamesAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesSuperadditive GamesIn superadditive games, two coalitions can always mergewithout losing money; hence, we can assume that players formthe grand coalitionAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesSuperadditive GamesIn superadditive games, two coalitions can always mergewithout losing money; hence, we can assume that players formthe grand coalitionConvention: in superadditive games, we identify outcomeswith payoff vectors for the grand coalitionAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesSuperadditive GamesIn superadditive games, two coalitions can always mergewithout losing money; hence, we can assume that players formthe grand coalitionConvention: in superadditive games, we identify outcomeswith payoff vectors for the grand coalitioni.e., an outcome is a vector x (x1 , ., xn ) with x(N) v (N)AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?Charlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?Charlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?Charlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750This is a superadditive game, so outcomes are payoff vectors!AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?Charlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750This is a superadditive game, so outcomes are payoff vectors!How should the players share the ice-cream?AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?Charlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750This is a superadditive game, so outcomes are payoff vectors!How should the players share the ice-cream?(200, 200, 350)?AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?Charlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750This is a superadditive game, so outcomes are payoff vectors!How should the players share the ice-cream?(200, 200, 350)?Charlie and Marcie can get more ice-cream by buying a 500g tubon their own, and splitting it equallyAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesWhat Is a Good Outcome?Charlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750This is a superadditive game, so outcomes are payoff vectors!How should the players share the ice-cream?(200, 200, 350)?Charlie and Marcie can get more ice-cream by buying a 500g tubon their own, and splitting it equally(200, 200, 350) is not stable!AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesThe coreAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesThe coreThe core of a game Γ is the set of all stable outcomes, i.e.,outcomes that no coalition wants to deviate fromAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesThe coreThe core of a game Γ is the set of all stable outcomes, i.e.,outcomes that no coalition wants to deviate fromcore(Γ) {(CS, x) x(C ) v (C ) for any C N}AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesThe coreThe core of a game Γ is the set of all stable outcomes, i.e.,outcomes that no coalition wants to deviate fromcore(Γ) {(CS, x) x(C ) v (C ) for any C N}each coalition earns at least as much as it can make on its own.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesThe coreThe core of a game Γ is the set of all stable outcomes, i.e.,outcomes that no coalition wants to deviate fromcore(Γ) {(CS, x) x(C ) v (C ) for any C N}each coalition earns at least as much as it can make on its own.Example: v ({1, 2, 3}) 9, v ({4, 5}) 4, v ({2, 4}) 7AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesThe coreThe core of a game Γ is the set of all stable outcomes, i.e.,outcomes that no coalition wants to deviate fromcore(Γ) {(CS, x) x(C ) v (C ) for any C N}each coalition earns at least as much as it can make on its own.Example: v ({1, 2, 3}) 9, v ({4, 5}) 4, v ({2, 4}) 7(({1, 2, 3}, {4, 5}), (3, 3, 3, 3, 1)) is NOT in the coreAGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesThe coreThe core of a game Γ is the set of all stable outcomes, i.e.,outcomes that no coalition wants to deviate fromcore(Γ) {(CS, x) x(C ) v (C ) for any C N}each coalition earns at least as much as it can make on its own.Example: v ({1, 2, 3}) 9, v ({4, 5}) 4, v ({2, 4}) 7(({1, 2, 3}, {4, 5}), (3, 3, 3, 3, 1)) is NOT in the coreas x({2, 4}) 6 and v ({2, 4}) 7AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesThe coreThe core of a game Γ is the set of all stable outcomes, i.e.,outcomes that no coalition wants to deviate fromcore(Γ) {(CS, x) x(C ) v (C ) for any C N}each coalition earns at least as much as it can make on its own.Example: v ({1, 2, 3}) 9, v ({4, 5}) 4, v ({2, 4}) 7(({1, 2, 3}, {4, 5}), (3, 3, 3, 3, 1)) is NOT in the coreas x({2, 4}) 6 and v ({2, 4}) 7no subgroup of players can deviate so that each member ofthe subgroup gets more.AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesIce-cream game: CoreCharlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesIce-cream game: CoreCharlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750(200, 200, 350)AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesIce-cream game: CoreCharlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750(200, 200, 350) is not in the core: v ({C , M}) x({C , M})AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesIce-cream game: CoreCharlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750(200, 200, 350) is not in the core: v ({C , M}) x({C , M})(250, 250, 250)AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesIce-cream game: CoreCharlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750(200, 200, 350) is not in the core: v ({C , M}) x({C , M})(250, 250, 250) is in the core: alone or in pairs do not getmore.(750, 0, 0)AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesIce-cream game: CoreCharlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750(200, 200, 350) is not in the core: v ({C , M}) x({C , M})(250, 250, 250) is in the core: alone or in pairs do not getmore.(750, 0, 0) is also in the core:AGT-MIRICooperative Game Theory
DefinitionsStability notionsOther solution conceptsSubclassesCore and variationsFairness: Shapley valueComputational IssuesIce-cream game: CoreCharlie: 4Marcie: 3Pattie: 3Ice-cream pots: w (500, 750, 100) and p ( 7, 9, 11)v ( ) v ({C }) v ({M}) v ({P}) 0v ({C , M}) 500, v ({C , P}) 500, v ({M, P}) 0v ({C , M, P}) 750(200, 200, 350) is not in the core: v ({C , M}) x({C , M})(250, 250, 250) is in the core: alone or in pairs do not getmore.(750, 0, 0) is also in the core:Marcie and Pattie cannot get more on their own!AGT-MIRICooperative G
Non-cooperative game theory model scenarios where players cannot make binding agreements. Cooperative game theory model scenarios, where agents can bene t by cooperating, and binding agreements are possible. In cooperative games, actions are taken by groups of agents, coalitions, and payo s
