Software:Imputation (game theory)

From HandWiki

In fully cooperative games players will opt to form coalitions when the value of the payoff is equal to or greater than if they were to work alone.[1] The focus of the game is to find acceptable distributions of the payoff of the grand coalition. Distributions where a player receives less than it could obtain on its own, without cooperating with anyone else, are unacceptable - a condition known as individual rationality. Imputations are distributions that are efficient and are individually rational.

Theory

For 2-player games the set of imputations coincides with the core, a popularly studied concept due to its stability against group deviations.[2] The core is a solution concept of cooperative games and consists of multiple imputations, a set of distributions as a result of a game. The core cannot be improved upon by any coalition.[3] However, problems will arise when it comes to selecting a set of imputations, it will require bargaining.

Solutions

Nash bargaining theory, a type of cooperative bargaining, is used to solve this problem for 2-player games but will fail to yield any results for any games that are using more than two players,[2] this solution aims to maximise the pay off for both of the players.[3] Two more methods for calculating a resolution to these games are The Shapley Value and Schmeidler's Nucleolus.[2]

Both of these calculations have problems with their result. Results calculated from Shapley's Value contain the possibility of sitting outside the constraints of the core. Schmeidler's Nucleolus cannot be calculated when the core is null. However, Schmeidler's Nucleolus is calculated by assuming that there is equal bargaining power which is unrealistic in most situations as it does not account for differences in bargaining power that originate from outside influences.[2] Schmeidler's Nucleolus refers to the imputation that minimizes the maximum excess, a min-max function. However, the definition of Schmeidler's Nucleolus can also be extended to other functions by minimizing an increasing aggregation function of the excess in a game.[2]

Other solutions include the Kalai-Smorodinsky solution and the Egalitarian solution of Kalai. The Kalai-Smorodinsky calculates the pay off which is proportional to the ideal gains of the players whereas Kalai's Egalitarian solution equalizes the gains of the players.[3]

Time consistency in dynamic games

An important problem in the theory of cooperative dynamic games is the time-consistency of a given imputation function (in Russian literature it is termed dynamic stability of optimality principle). Let say that a number of players has made a cooperative agreement at the start of the game. Obviously, a rational player will leave the agreement if he/she can achieve a better outcome by abandoning, no matter what was announced before. The condition, which guarantees the sustaining of the cooperative agreement is known as time consistency. A number of regularization methods (integral and differential) based upon the IDP (imputation distribution procedures) was proposed.

Example

Mrs. Arnold and Mrs. Bauer are knitting gloves. The gloves are one-size-fits-all, and two gloves make a pair that they sell for €5. They have each made 3 gloves. How do they share the proceeds from the sale? The problem can be described by a characteristic function form game with the following characteristic function: Each lady has 3 gloves, that is 1 pair with a market value of €5. Together, they have 6 gloves or 3 pair, having a market value of €15. Then a distribution of this sum is an imputation provided that none of the ladies gets less than €5, the amount they can achieve on their own. For instance (7.5, 7.5) is an imputation, but so is (5, 10) or (9, 6).

The example can be generalized. Suppose Mrs. Carlson and Mrs. Delacroix are also part of the club where each lady has made 3 gloves. Now the total is 12 gloves (six pairs) which nets €30. At the same time, one of the ladies on her own can still only make €5. Thus, imputations share €30 such that no-one gets less than €5. The following are possible imputations: (7.5, 7.5, 7.5, 7.5), (10, 5, 10, 5), (5, 15, 5, 5) or (7, 5, 9, 9).

References

  1. "game theory | Definition, Facts, & Examples" (in en). https://www.britannica.com/science/game-theory. 
  2. 2.0 2.1 2.2 2.3 2.4 McCain, Roger A. (2013). Value Solutions in Cooperative Games. pp. 105–17. 
  3. 3.0 3.1 3.2 Durlauf, Steven N (2010). Game Theory. pp. 130–140. 
  • Brams, Steven J. and Davis, Morton D.. Game Theory: Encyclopedia Britannica, 2021, https://www.britannica.com/science/game-theory
  • Durlauf, Steven N. and Blume, Lawrence E.. Game Theory, 2010, pp. 130–140
  • McCain, Roger A. Value Solutions in Cooperative Games, 2013, pp. 105–107
  • Myerson Roger B.: Game Theory: Analysis of Conflict, Harvard University Press, Cambridge, 1991, ISBN:0-674-34116-3
  • Petrosjan, Leon A. Differential games of pursuit, World Scientific, Singapore, London, 1993, pp. 340.
  • Yeung, David W.K. and Petrosyan, Leon A. Cooperative Stochastic Differential Games (Springer Series in Operations Research and Financial Engineering), 2006, Springer pp. 242. ISBN:978-1441920942.
  • Zaccour, Georges. Time Consistency in Cooperative Differential Games: A Tutorial. INFOR: Information Systems and Operational Research, Volume 46(1), 2008. ISSN 0315-5986.