Cooperative Game TheoryWhat is Desirable?Dominated Points and Pareto EfficiencySocial OptimumMax-Min Fair ShareNash Bargaining EquilibriumExample of Different Pareto Efficient Solutions:Nash’s Bargaining ProblemIntuitionNash’s Axiomatic Approach (1950)ResultsNash Bargaining EquilibriumSuggested ReadingsCoalitionsCore SetsExample: Core SetShapley Value: ExampleShapley Value: ExampleFair Allocation: the Shapley ValueSuggested ReadingsSummaryReferencesCooperative Game TheoryJohn Musacchio11/16/04What is Desirable?•We’ve seen that–Prisoner’s Dilemma has undesirable Nash Equilibrium.–One shot Cournot has a less than socially optimum equilibrium.•In a repeated game with threat strategies–Players can reach a more desirable equilibrium.•We now classify different types of “Desirable” Equilibria.Feasible Payoffsx1x2Feasible payoffsConsider a two player game with a Feasible region of Payoffs:Dominated Points and Pareto Efficiency•Vectors for which one player’s rewards can be increased with out decreasing the others are dominated.•Vectors which are not dominated, are Pareto Efficient.x1x2Feasible payoffsDominatedPareto EfficientSocial Optimum•A Social OptimumVector Maximizes the Sum of Player Payoffs.x1x2Feasible payoffsMax-Min Fair Sharex1•A max-minfair share vector is such that one player’s reward cannot be increased without decreasing the reward to another who already has less.Nash Bargaining Equilibriumx1x2Feasible payoffs•A Feasible Allocation Satisfying•This equilibrium maximizes the Product of Player Payoffs.•Soon, we will look at Bargaining Problem that this solves…Example of Different Pareto Efficient Solutions:•Social Optimum: (0,1/2,1/2)•Max-Min: (1/2,1/2,1/2)•NBE:(1/3,2/3,2/3) 213Nash’s Bargaining Problem•Model–Two players with interdependent payoffs U and V–Acting together they can achieve a set of feasible payoffs–The more one player gets, the less the other is able to get–And there are multiple Pareto efficient payoffs•Q: which feasible payoff would they settle on?–Fairness issue•Example (from Owen): –Two men try to decide how to split $100–One is very rich, so that U(x)@ x–The other has only $1, so V(x)@log(1+x)–log1=log(1+x)–How would they split the money?vu100log(101)Intuition•Feasible set of payoffs–Denote xthe amount that the rich man gets–(u,v)=(x, log(101–x)), xÎ[0,100]DvDuABDuDvDuDvCA fair split should satisfy| Du/u | = | Dv/v |Let D®0, du/u = –dv/vOr du/u + dv/v= 0, or vdu+udv =0, or d(uv)=0.ÞFind the allocation which maximizes U´V Þx*=76.8!Nash’s Axiomatic Approach (1950)•A solution (u*,v*)should be –Rational§(u*,v*) ³(u0,v0),where (u0,v0)is the worst payoffs that the players can get.–Feasible§(u*,v*)ÎS, the set of feasible payoffs.–Pareto efficient–Symmetric§If Sis such that (u,v)ÎS Û(v,u)ÎS, then u*=v*.–Independent from linear transformations–Independent from irrelevant alternatives§Suppose TÌ S. If (u*,v*)ÎTis a solution to S,then (u*,v*) should also be a solution to T.Results•There is a unique solution which –satisfies the above axioms–maximizes the product of two players’ additional payoffs (u–u0)(v–v0)•This solution can be enforced by “threats”–Each player independently announces his/her threat–Players then bargain on their threats–If they reach an agreement, that agreement takes effect–Otherwise, initially announced threats will be used•Different fairness criteria can be achieved by changing the last axiom (see references)Nash Bargaining Equilibrium•Maximizes Product ofNash Bargaining Equilibriumx1x2Feasible payoffsSuggested Readings•J. F. Nash. “The Bargaining Problem.”Econometrica, vol.18, 1950. – Nash’s original paper. Very well written.•X. Cao. “Preference Functions and Bargaining Solutions.”Proc. of the 21th CDC, NYC, NY, 1982. –A paper which unifies all bargaining solutions into a single framework•Z. Dziongand L.G. Mason. “Fair–Efficient Call Admission Control Policies for Broadband Networks –a Game Theoretic Framework,” IEEE/ACM Trans. On Networking, vol.4, 1996.–Applies Nash’s bargaining solution to resource allocation problem in admission control (multi-objective optimization)Coalitions•Model–Players (n>2) N form coalitions among themselves–A coalition is any nonempty subset of N–Characteristic function Vdefines a gameV(S)=payoff to Sin the game between Sand N-S, "S ÌNV(N)=total payoff achieved by all players acting togetherV(·)is assumed to be super-additive"S, T ÌN,V(S+T) ³ V(S)+V(T)•Questions of Interest–Condition for forming stablecoalitions –When will a single coalition be formed?§How to distribute payoffs among players in a fair way?Core Sets•Allocation X=(x1, …, xn)xi ³V({i}), "iÎN;SiÎNxi = V(N). •The core of a game any allocation which satisfiesSiÎSxi ³V(S), "S ÌNÞIf the core is nonempty, a single coalition can be formed•An example• A Berkeley landlord (L) is renting out a room• Al (A) and Bob (B) are willing to rent the room at $600 and $800, respectively•Who should get the room at what rent?Example: Core Set•Characteristic function of the game–These combos give no payoff: V(L)=V(A)=V(B)=V(A+B)=0 –Coalition between Land Aor Land BIf rent =x, then L’s payoff= x, A’s payoff= 600 –xsoV(L+A)=600. Similarly,V(L+B)=800–Coalition among L, Aand B:V(L+A+B)=800•The core of the game:xL+xA³600xL+xB³800xL+xA +xB=800Þcore={(xL=y , xA=0, xB=800 –y),600£y £800}•B should get the place, and the rent should be between$600 and $800ShapleyValue: Example•Consider–Landowner–2 Farm Workers•A Landowner + One Worker à C•A Landowner + Two Workers à2C•One or Two Workers +No Landowner à0•How much should each get?–We argue C for the landowner and C/2 for each worker.ShapleyValue: Example•Imagine the parties arrive in random owner, and each gets their marginal contribution.–ORDER MARGINAL CONTRIBUTION –(F,W,W) à(0,C, C)–(W,F,W) à(0,C, C)–(W,W,F) à(0,0,2C)–Farmer Avg= (1/6)( 2 X 0+ 2 X C + 2 X 2XC) = C–Worker Avg= (1/6)( 2 X C + C + 0) =C/2Fair Allocation: the Shapley Value•Define solution for player iin game V byPi(V)•Shapley’s axioms–Pi’s are independent from permutation of labels–Additive: if U and V are any two games, thenPi(U+V) = Pi(U) + Pi(V), "iÎN–Tis a carrier of Nif V(SÇT)=V(S),"S ÌN.Then for any carrier T, SiÎTPi = V(T). •Unique solution:
View Full Document
Unlocking...