DOC PREVIEW
Duke CPS 296.1 - Cooperative/coalitional game theory

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CPS 296.1 Cooperative/coalitionalCooperative/coalitional game theoryVincent Conitzer [email protected]/coalitional game theoryTh i t f t N•There is a set of agents N• Each subset (or coalition) S of agents can work together in various ways leading to various utilities fortogether in various ways, leading to various utilities for the agents•Cooperative/coalitional game theory studies which pgyoutcome will/should materialize• Key criteria:–Stability: No coalition of agents should want to deviate from the solution and go their own way–Fairness: Agents should be rewarded for what they aessge s s ou d be e a ded o a eycontribute to the group•(“Cooperative game theory”is the standard name (distinguishing it from( Cooperative game theory is the standard name (distinguishing it from noncooperative game theory, which is what we have studied so far). However this is somewhat of a misnomer because agents still pursue their own interests. Hence some people prefer “coalitional game theory.”)ExampleTh t {1 2 3} t f I di Chi•Three agents {1, 2, 3} can go out for Indian, Chinese, or Japanese food•u1(I) = u2(C) = u3(J) = 4•u1(C) = u2(J) = u3(I) = 2•u1(J) = u2(I) = u3(C) = 0Each agent gets an additional unit of utility for each other agent•Each agent gets an additional unit of utility for each other agent that joins her• Exception: going out alone always gives a total utility of 0• If all agents go for Indian together, they get utilities (6, 2, 4)• All going to Chinese gives (4, 6, 2), all going to Japanese gives (2 4 6)(2, 4, 6)• Hence, the utility possibility set for {1, 2, 3} is {(6, 2, 4), (4, 6, 2), (2, 4, 6)}F th liti {1 2} th tilit ibilit t i {(5 1) (3 5)•For the coalition {1, 2}, the utility possibility set is {(5, 1), (3, 5), (1, 3)} (why?)Stability & the core(I)(C)(J) 4•u1(I) = u2(C) = u3(J) = 4•u1(C) = u2(J) = u3(I) = 2•u1(J) = u2(I) = u3(C) = 01()2()3()• V({1, 2, 3}) = {(6, 2, 4), (4, 6, 2), (2, 4, 6)}• V({1, 2}) = {(5, 1), (3, 5), (1, 3)}Sh didllfJ h•Suppose the agents decide to all go for Japanese together, so they get (2, 4, 6)• 1 and 2 would both prefer to break off and get Chinese pgtogether for (3, 5) – we say (2, 4, 6) is blocked by {1, 2}– Blocking only occurs if there is a way of breaking off that would make allmembers of the blocking coalition happier• The core [Gillies 53] is the set of all outcomes (for the grand coalition N of all agents) that are blocked by no coalition•In this example the core isempty(why?)•In this example, the core is empty(why?)• In a sense, there is no stable outcomeTransferable utilityN th t tilit itfblif•Now suppose that utility is transferable: you can give some of your utility to another agent in your coalition (e.g., by making a payment)• Then, all that we need to specify is a value for each coalition, which is the maximum total utility for the coalition– Value function also known as characteristic function• Any vector of utilities that sums to the value is possible• Outcome is in the core if and only if: every coalition receives a total utility that is at least its valuetotal utility that is at least its value– For every coalition C, v(C) ≤ Σi in Cu(i)• In above example, – v({1, 2, 3}) = 12, – v({1, 2}) = v({1, 3}) = v({2, 3}) = 8,–v({1}) = v({2}) = v({3}) = 0({ }) ({ }) ({ })• Now the outcome (4, 4, 4) is possible; it is also in the core (why?) and in fact the unique outcome in the core (why?)Emptiness & multiplicity• Let us modify the above example so that agents receive no utility from being together (except being alone still gives 0)–v({1, 2, 3})=6,v({1, 2, 3}) 6, – v({1, 2}) = v({1, 3}) = v({2, 3}) = 6,– v({1}) = v({2}) = v({3}) = 0•Now the core is empty!•Now the core is empty!• Conversely, suppose agents receive 2 units of utility for each other agent that joins–v({1, 2, 3}) = 18, – v({1, 2}) = v({1, 3}) = v({2, 3}) = 10,– v({1}) = v({2}) = v({3}) = 0• Now lots of outcomes are in the core – (6, 6, 6), (5, 5, 8), …• When is the core guaranteed to be nonempty?•What about uniqueness?•What about uniqueness?Superadditivity•v is superadditive if for all coalitions A, B with A∩B = Ø, v(AUB) ≥ v(A) + v(B)• Informally, the union of two coalitions can always act as if they were separate, so should be able to get at least what they would get if they were separateleast what they would get if they were separate• Usually makes sense•Previous examples were all superadditive•Previous examples were all superadditive• Given this, always efficient for grand coalition to formConvexityAiif f ll liti A B (AUB)(B)•A game is convexif for all coalitions A, B, v(AUB)-v(B) ≥ v(A)-v(A∩B) (i.e., v is supermodular)•One interpretation: themarginal contributionof an•One interpretation: the marginal contributionof an agent is increasing in the size of the set that it is added to• Previous examples were not convex (why?)• In convex games, core is always nonempty• One easy-to-compute solution in the core: agent i gets u(i) = v({1, 2, …, i}) - v({1, 2, …, i-1})–Marginal contributionscheme–Marginal contributionscheme– Works for any ordering of the agentsThe Shapley value [Shapley 1953]• The marginal contribution scheme is unfair because it depends on the ordering of the agents• One way to make it fair: average over all possible orderings• Let MC(i, π) be the marginal contribution of i in ordering π•Then i’sShapley valueisΣMC(iπ)/(n!)•Then is Shapley valueis ΣπMC(i, π)/(n!)• Always in the core for convex games• … but not in general, even when core is nonempty, e.g.gpyg– v({1, 2, 3}) = v({1, 2}) = v({1, 3}) = 1,– v = 0 everywhere elseAxiomatic characterization of the Shapley valueof the Shapley value• The Shapley value is the unique solution concept that py q psatisfies:– Efficiency: the total utility is the value of the grand coalition, Σu(i) = v(N)Σi in Nu(i) = v(N)– Symmetry: two symmetric players must receive the same utility– Dummy: if v(SU{i}) = v(S) for all S, then i must get 0– Additivity: if we add two games defined by v and w by letting (v+w)(S)=v(S) + w(S) then the utility for an agent inletting (v+w)(S) v(S) + w(S), then the utility for an agent in v+w should be the sum of her utilities in v and w• most controversial axiomComputing a solution in the core• Can use linear programming:– Variables: u(i)Di t ib ti t i tΣ(i)


View Full Document

Duke CPS 296.1 - Cooperative/coalitional game theory

Documents in this Course
Lecture

Lecture

18 pages

Lecture

Lecture

6 pages

Lecture

Lecture

13 pages

Lecture

Lecture

5 pages

Load more
Download Cooperative/coalitional game theory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Cooperative/coalitional game theory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Cooperative/coalitional game theory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?