Core (game theory)

Last updated

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.

Contents

An allocation is said to be in the core of a game if there is no coalition that can improve upon it. The core is then the set of all feasible allocations.

Origin

The idea of the core already appeared in the writings of Edgeworth (1881), at the time referred to as the contract curve. [1] Even though von Neumann and Morgenstern considered it an interesting concept, they only worked with zero-sum games where the core is always empty. The modern definition of the core is due to Gillies. [2]

Definition

Consider a transferable utility cooperative game where denotes the set of players and is the characteristic function. An imputation is dominated by another imputation if there exists a coalition , such that each player in weakly-prefers ( for all ) and there exists that strictly-prefers (), and can enforce by threatening to leave the grand coalition to form (). The core is the set of imputations that are not dominated by any other imputation. [3]

Weak core

An imputation is strongly-dominated by another imputation if there exists a coalition , such that each player in strictly-prefers ( for all ). The weak core is the set of imputations that are not strongly-dominated. [4]

Properties

  1. Efficiency: ,
  2. Coalitional rationality: for all subsets (coalitions) .

Example

Example 1: Miners

Consider a group of n miners, who have discovered large bars of gold. If two miners can carry one piece of gold, then the payoff of a coalition S is

If there are more than two miners and there is an even number of miners, then the core consists of the single payoff where each miner gets 1/2. If there is an odd number of miners, then the core is empty.

Example 2: Gloves

Mr A and Mr B 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 three gloves. How to share the proceeds from the sale? The problem can be described by a characteristic function form game with the following characteristic function: Each man has three gloves, that is one pair with a market value of €5. Together, they have 6 gloves or 3 pair, having a market value of €15. Since the singleton coalitions (consisting of a single man) are the only non-trivial coalitions of the game all possible distributions of this sum belong to the core, provided both men get at least €5, the amount they can achieve on their own. For instance (7.5, 7.5) belongs to the core, but so does (5, 10) or (9, 6).

Example 3: Shoes

For the moment ignore shoe sizes: a pair consists of a left and a right shoe, which can then be sold for €10. Consider a game with 2001 players: 1000 of them have 1 left shoe, 1001 have 1 right shoe. The core of this game is somewhat surprising: it consists of a single imputation that gives 10 to those having a (scarce) left shoe, and 0 to those owning an (oversupplied) right shoe. No coalition can block this outcome, because no left shoe owner will accept less than 10, and any imputation that pays a positive amount to any right shoe owner must pay less than 10000 in total to the other players, who can get 10000 on their own. So, there is just one imputation in the core.

The message remains the same, even if we increase the numbers as long as left shoes are scarcer. The core has been criticized for being so extremely sensitive to oversupply of one type of player.

The core in general equilibrium theory

The Walrasian equilibria of an exchange economy in a general equilibrium model, will lie in the core of the cooperation game between the agents. Graphically, and in a two-agent economy (see Edgeworth Box), the core is the set of points on the contract curve (the set of Pareto optimal allocations) lying between each of the agents' indifference curves defined at the initial endowments.

The core in voting theory

When alternatives are allocations (list of consumption bundles), it is natural to assume that any nonempty subsets of individuals can block a given allocation. When alternatives are public (such as the amount of a certain public good), however, it is more appropriate to assume that only the coalitions that are large enough can block a given alternative. The collection of such large ("winning") coalitions is called a simple game. The core of a simple game with respect to a profile of preferences is based on the idea that only winning coalitions can reject an alternative in favor of another alternative . A necessary and sufficient condition for the core to be nonempty for all profile of preferences, is provided in terms of the Nakamura number for the simple game.

See also

Related Research Articles

In welfare economics, a Pareto improvement formalizes the idea of an outcome being "better in every possible way". A change is called a Pareto improvement if it leaves everyone in a society better-off. A situation is called Pareto efficient or Pareto optimal if all possible Pareto improvements have already been made; in other words, there are no longer any ways left to make one person better-off, without making some other person worse-off.

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

Edgeworth's limit theorem is an economic theorem, named after Francis Ysidro Edgeworth, stating that the core of an economy shrinks to the set of Walrasian equilibria as the number of agents increases to infinity.

In mathematical economics, the Arrow–Debreu model is a theoretical general equilibrium model. It posits that under certain economic assumptions there must be a set of prices such that aggregate supplies will equal aggregate demands for every commodity in the economy.

Game theory is the branch of mathematics in which games are studied: that is, models describing human behaviour. This is a glossary of some terms of the subject.

A bankruptcy problem, also called a claims problem, is a problem of distributing a homogeneous divisible good among people with different claims. The focus is on the case where the amount is insufficient to satisfy all the claims.

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.

The Knaster–Kuratowski–Mazurkiewicz lemma is a basic result in mathematical fixed-point theory published in 1929 by Knaster, Kuratowski and Mazurkiewicz.

Competitive equilibrium is a concept of economic equilibrium, introduced by Kenneth Arrow and Gérard Debreu in 1951, appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.

The Bondareva–Shapley theorem, in game theory, describes a necessary and sufficient condition for the non-emptiness of the core of a cooperative game in characteristic function form. Specifically, the game's core is non-empty if and only if the game is balanced. The Bondareva–Shapley theorem implies that market games and convex games have non-empty cores. The theorem was formulated independently by Olga Bondareva and Lloyd Shapley in the 1960s.

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

In mathematics, a topological game is an infinite game of perfect information played between two players on a topological space. Players choose objects with topological properties such as points, open sets, closed sets and open coverings. Time is generally discrete, but the plays may have transfinite lengths, and extensions to continuum time have been put forth. The conditions for a player to win can involve notions like topological closure and convergence.

Linear production game is a N-person game in which the value of a coalition can be obtained by solving a linear programming problem. It is widely used in the context of resource allocation and payoff distribution. Mathematically, there are m types of resources and n products can be produced out of them. Product j requires amount of the kth resource. The products can be sold at a given market price while the resources themselves can not. Each of the N players is given a vector of resources. The value of a coalition S is the maximum profit it can achieve with all the resources possessed by its members. It can be obtained by solving a corresponding linear programming problem as follows.

In cooperative game theory and social choice theory, the Nakamura number measures the degree of rationality of preference aggregation rules, such as voting rules. It is an indicator of the extent to which an aggregation rule can yield well-defined choices.

<span class="mw-page-title-main">Shapley–Folkman lemma</span> Sums of sets of vectors are nearly convex

The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ross M. Starr.

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

In cooperative game theory, a hedonic game is a game that models the formation of coalitions (groups) of players when players have preferences over which group they belong to. A hedonic game is specified by giving a finite set of players, and, for each player, a preference ranking over all coalitions (subsets) of players that the player belongs to. The outcome of a hedonic game consists of a partition of the players into disjoint coalitions, that is, each player is assigned a unique group. Such partitions are often referred to as coalition structures.

<span class="mw-page-title-main">Price of anarchy in auctions</span>

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.

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.

References

  1. Kannai, Y. (1992). "The core and balancedness". In Aumann, Robert J.; Hart, Sergiu (eds.). Handbook of Game Theory with Economic Applications. Vol. I. Amsterdam: Elsevier. pp. 355–395. ISBN   978-0-444-88098-7.
  2. Gillies, D. B. (1959). "Solutions to general non-zero-sum games". In Tucker, A. W.; Luce, R. D. (eds.). Contributions to the Theory of Games IV. Annals of Mathematics Studies. Vol. 40. Princeton: Princeton University Press. pp. 47–85.
  3. As noted by Shapley, L. S.; Shubik, M. (1969). "On Market Games". Journal of Economic Theory . 1 (1): 9–25. doi:10.1016/0022-0531(69)90008-8. S2CID   153498438. due to the contribution of Mr. E. Kohlberg
  4. Yu, Chaowen (8 December 2020). "A note on the weak core of simple games with ordinary preferences and uncountable alternatives". SSRN Electronic Journal. doi: 10.2139/ssrn.3225500 .
  5. Bondareva, Olga N. (1963). "Some applications of linear programming methods to the theory of cooperative games (In Russian)". Problemy Kybernetiki. 10: 119–139.
  6. Shapley, Lloyd S. (1967). "On balanced sets and cores". Naval Research Logistics Quarterly. 14 (4): 453–460. doi:10.1002/nav.3800140404. hdl: 10338.dmlcz/135729 .

Works cited

Further reading