Imputation (game theory)

Last updated

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.

Contents

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).

Related Research Articles

<span class="mw-page-title-main">Game theory</span> Mathematical models of strategic interactions

Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed two-person zero-sum games, in which a participant's gains or losses are exactly balanced by the losses and gains of the other participant. In the 1950s, it was extended to the study of non zero-sum games, and was eventually applied to a wide range of behavioral relations. It is now an umbrella term for the science of rational decision making in humans, animals, and computers.

<span class="mw-page-title-main">Shapley value</span> Concept in game theory

The Shapley value is a solution concept in cooperative game theory. It was named in honor of Lloyd Shapley, who introduced it in 1951 and won the Nobel Memorial Prize in Economic Sciences for it in 2012. To each cooperative game it assigns a unique distribution of a total surplus generated by the coalition of all players. The Shapley value is characterized by a collection of desirable properties. Hart (1989) provides a survey of the subject.

In game theory, a cooperative game is a game with groups of players who form binding “coalitions” with external enforcement of cooperative behavior. This is different from non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing.

In game theory, a non-cooperative game is a game in which there are no external rules or binding agreements that enforce the cooperation of the players. A non-cooperative game is typically used to model a competitive environment. This is stated in various accounts most prominent being John Nash's 1951 paper in the journal Annals of Mathematics.

In cooperative game theory, the core is the set of feasible allocations or imputations where no coalition of agents can benefit by breaking away from the grand coalition. One can think of the core corresponding to situations where it is possible to sustain cooperation among all agents. A coalition is said to improve upon or block a feasible allocation if the members of that coalition can generate more value among themselves than they are allocated in the original allocation. As such, that coalition is not incentivized to stay with the grand coalition.

Hobart Peyton Young is an American game theorist and economist known for his contributions to evolutionary game theory and its application to the study of institutional and technological change, as well as the theory of learning in games. He is currently centennial professor at the London School of Economics, James Meade Professor of Economics Emeritus at the University of Oxford, professorial fellow at Nuffield College Oxford, and research principal at the Office of Financial Research at the U.S. Department of the Treasury.

Cooperative bargaining is a process in which two people decide how to share a surplus that they can jointly generate. In many cases, the surplus created by the two players can be shared in many ways, forcing the players to negotiate which division of payoffs to choose. Such surplus-sharing problems are faced by management and labor in the division of a firm's profit, by trade partners in the specification of the terms of trade, and more.

<span class="mw-page-title-main">Alvin E. Roth</span> American academic (born 1951)

Alvin Eliot Roth is an American academic. He is the Craig and Susan McCaw professor of economics at Stanford University and the Gund professor of economics and business administration emeritus at Harvard University. He was President of the American Economic Association in 2017.

In economics, philosophy, and social choice theory, a person's entitlement refers to the value of goods they are owed or deserve, i.e. the total value of the goods or resources that a player would ideally receive. For example, in party-list proportional representation, a party's seat entitlement is equal to its share of the vote, times the number of seats in the legislature.

<span class="mw-page-title-main">Michael Maschler</span> Israeli mathematician (1927-2008)

Michael Bahir Maschler was an Israeli mathematician well known for his contributions to the field of game theory. He was a professor in the Einstein Institute of Mathematics and the Center for the Study of Rationality at the Hebrew University of Jerusalem in Israel. In 2012, the Israeli Chapter of the Game Theory Society founded the Maschler Prize, an annual prize awarded to an outstanding research student in game theory and related topics in Israel.

<span class="mw-page-title-main">Ehud Kalai</span> American economist

Ehud Kalai is a prominent Israeli American game theorist and mathematical economist known for his contributions to the field of game theory and its interface with economics, social choice, computer science and operations research. He was the James J. O’Connor Distinguished Professor of Decision and Game Sciences at Northwestern University, 1975–2017, and currently is a Professor Emeritus of Managerial Economics and Decision Sciences.

David Schmeidler was an Israeli mathematician and economic theorist. He was a Professor Emeritus at Tel Aviv University and the Ohio State University.

<span class="mw-page-title-main">Jean-François Mertens</span> Belgian game theorist (1946–2012)

Jean-François Mertens was a Belgian game theorist and mathematical economist.

<span class="mw-page-title-main">Leon Petrosyan</span>

Leon Petrosjan is a professor of Applied Mathematics and the Head of the Department of Mathematical Game theory and Statistical Decision Theory at the St. Petersburg University, Russia.

Olga Nikolaevna Bondareva was a distinguished Soviet mathematician and economist. She contributed to the fields of mathematical economics, especially game theory.

The Kalai–Smorodinsky (KS) bargaining solution is a solution to the Bargaining problem. It was suggested by Ehud Kalai and Meir Smorodinsky, as an alternative to Nash's bargaining solution suggested 25 years earlier. The main difference between the two solutions is that the Nash solution satisfies independence of irrelevant alternatives, while the KS solution instead satisfies resource monotonicity.

<span class="mw-page-title-main">Elena Yanovskaya</span> Soviet and Russian mathematician and economist

Elena Yanovskaya is a Soviet and Russian mathematician and economist known for her contributions to cooperative game theory.

In cooperative game theory, the nucleolus of a cooperative game is the solution that maximizes the smallest excess of a coalition. Subject to that, the nucleolus satisfies the second-smallest excess; and so on, in the leximin order. The nucleolus was introduced by David Schmeidler.

A minimum-cost spanning-tree game is a kind of a cooperative game. In an MCST game, each player is a node in a complete graph. The graph contains an additional node - the supply node - denoted by s. The goal of the players is that all of them will be connected by a path to s. To this end, they need to construct a spanning tree. Each edge in the graph has a cost, and the players build the minimum cost spanning tree. The question then arises, how to allocate the cost of this MCST among the players?

References

  1. ↑ "game theory | Definition, Facts, & Examples". Encyclopedia Britannica. Retrieved 2021-04-25.
  2. 1 2 3 4 5 McCain, Roger A. (2013). "Value Solutions in Cooperative Games": 105–17.{{cite journal}}: Cite journal requires |journal= (help)
  3. 1 2 3 Durlauf, Steven N (2010). "Game Theory": 130–140.{{cite journal}}: Cite journal requires |journal= (help)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.