Core (Game Theory)
1
Core(Game Theory)
Definition
Gametheory is defined by Peters (2008) as a “formal, mathematicaldiscipline which studies situations of competition and cooperationbetween several involved parties”. This is deﬁnition may beconsidered too general but is reliable with its numerousapplications. Such applications are in economic struggles, tacticalquestions in conflicts at the same time has a wide coverage but isnot limited to simple games to governmental voting schemes.
AGame
Agame is “a formal representation of a situation in which a numberof individuals interact in a setting of strategic interdependence.”That means one’s benefit is not just determined by his actions.Additionally, his best move for himself is dependent on hisexpectation of the move of the other player. Four concepts describesa strategic interaction situation. First are the players, which arethe one involved in the situation. Second is the rules. This answersthe questions, “who moves when?”, “what can they do?”, and“what do they know when they move?” Another is the concept of theoutcomes. For every probable set of actions done by the players ofthe game, there is a corresponding outcome on it. Last is thepayoffs. These are the preferences of the players of the game overthe probable results. (Mascollel, Whinston and Green, 1995)
Tofurther understand these, it is much better to site an example. Thissample illustrates a situation the four concepts mentioned above.
Jeland Ruth wants to play a game wherein the want to match pennies. Theyboth have a coin and at the same time show if it’s a head or atail. If the two coins will match, Jel will give the coin to Ruth onthe other hand, if the two coins do not match, Ruth will give hercoin to Jel.
Inthis example, the players are Ruth and Jel. The rule is, each one ofthem will at the same time lays a penny down. They can choose betweenheads and tails. The outcome is, if there is a match on the twopennies (both heads or both tails), Jel will give Ruth the penny orelse, Ruth will pay a penny to Jel. The payoffs here is the moneyRuth or Jel wins or loses.
Anotherexample is the TickTackToe game. Suppose there are two players, Xiand Oh. The rule of the game is are, first, the two of them will facea board which has nine squares – three rows and three columns. Thefirst player will put a mark (an X or an O) on an unoccupied square.The players will take turns. They will both observe all selectionsformerly made. The outcomes will be the first player, either Xi orOh, who will have three marks either diagonally, vertically orhorizontally will win the game. It can be that the winner willacquire a price such as money for this game. In the case that no onewins, it will be considered deuce thus there will be no price orpayment to be acquired by Xi or Oh. Like the first example, thepayoff of this is the amount of money a player can gain or lose.
TheExtensive Form Representation of a Game
Thefour concepts, players, rules, payoffs and outcomes can correctlysignify a game commonly called extensive form. This form captures aplayer’s actions he can take, a player’s time of movement, thethings the players know when they decided to move, their outcomebased on the actions taken by its players, and their payoffs for eachprobable outcome. This extensive form depend on on the intangibleapparatus called a game tree. To demonstrate it, it would be veryuseful to use again the abovementioned examples.
Figure1. The Extensive form for the Matching Pennies example.
Source:Mascollel,Whinston and Green, 1995
Thevariation of this case is that Ruth and Jel will not move at the sametime, rather, they will show the face of the coin consecutively. Ruthwill show her penny first then followed by Jel. This became a bettergame for the second player, Jel. The extensive form representation ofthis example is showed in Figure 1. The game started at an initialdecision node as denoted by an open circle, where the first player,Ruth, will decide her move. The possible choices of Ruth is denotedby a branch from the initial decision mode. At the end of thisbranches is another set of decision node (a solid dot) wherein thesecond player, Jel, has again two choices, either a heads up or tailsup. After the node of the second player, the game will end. At theend of the node, their payoffs can be listed arising from thesuccession of moves up to the end node. Figure 1 is an example of agame tree – an illustration of connected branches from the initialor root node up to each point on the tree.
TheTickTackToe game also has its extensive form. Figure 2 shows itsextensive form. Some parts have been removed for conservation ofspace. Each path from the initial node embodies a one of a kind orderof moves from the players. For example, when a specific boardposition is acquired with the aid of various dissimilar series ofmoves, each of these series is represented distinctly in the gametree. Nodes do not just represent the current position but also theroute it takes in order to reach it.
Inboth of the example, before a player decides his or her next move,this player can know first everything of her rival’s former moves,thus, they are “games of perfect information”. The idea of a setof information are a subgroup of a certain player’s decision nodes. It can be interpreted that by the time of the game that reached adecision node given a set of information and at the same time theopportunity of this player to move, the player actually do not knowwhich of these nodes she is at. (Mascollel, Whinston and Green,1995)
Figure2. The game tree of the TickTackToe Game
Source:Mascollel,Whinston and Green, 1995
Strategiesand the Normal Form Game Representation
Thecore concept of the game theory is the idea of a player’s tactic orstrategy. This is the “complete contingent plan, or decision rule,that specifies how the player will act in every possibledistinguishable circumstance in which he or she might be called uponto move”. For a strategy to be a complete contingent plan, itshould also state moves for the player given an information setswhich may not be touched in the real game. For example, in theTickTackToe game, Xi’s strategy illustrates her initial move ifOh starts the game by putting a mark on the center square of theboard. But on the real game, Xi has the possibility of not making herfirst move on the center. She can alternatively place her first markon either of the corner squares, thus, this information is nowirrelevant to Oh’s plan or strategy.
Forfurther understanding, the strategies on the first example, theexample of matching pennies will be enumerated. A player (mostespecially the first player, Ruth) possesses two probable strategies– either they play tails (T) or heads (H). For the second player,her specific strategy will depend on the move of the first player(Ruth). Thus, the second player (Jel) has four probable strategies.
1^{st}strategy: Go for Heads up (H) if the Ruth decided to play H. Play Hif Ruth is also T.
2^{nd}strategy: Go for H if Ruth plays H, play T if Ruth is also T.
3^{rd}strategy: Go for T if Ruth plays H, play H if Ruth plays T.
4^{th}strategy: Go for T if Ruth plays H, play T if Ruth is also T.
Thegame also can be represent using a strategic or normal form, which isa summarized form of the extensive form. In this representation,there is no need to note the distinct moves connected with eachstrategy. As an alternative, the numerous probable strategies of aplayer can be noted as S_{n},wherein “n” refers to the number of the strategy. An illustrationof these is in Figure 3, which is a normal form illustration of theMatching Pennies example. The rows of the boxes on Figure 3 links tothe strategies of the first player and its columns are the strategiesof the second player. This illustration is commonly called a “gamebox”.
Figure3. The normal form of the Mathing Pennies example.
Source:Mascollel,Whinston and Green, 1995
RandomizedChoices
Theassumption of the player’s moves above is that they decide theirmoves in confidence. On the other hand, there is a possibility thatthe player’s move is randomized when encountered with a choice. Onsituations that players randomized their strategies, the promptedoutcome is then random, resulting to a possibility distribution overthe terminal nodes of the game.
The
Inthe theory, the core is the set of achievable distributions thatcannot be enhanced by a coalitionor subset of the economy`s buyers. A coalition is believed to enhanceuponor blocka possible sharing if the fellows of that alliance are “better offunder another feasible allocation” which is alike to the former notincluding that each fellow of the alliance has a dissimilarconsumption package that is portion of an collective consumptionpackage that can be built from openly accessible technology and theprimary donations of every customer in the alliance. “An allocationis said to have the corepropertyif there is no coalition that can improve upon it and the core is theset of all feasible allocations with the core property”.(Wikipedia)
Originof the core
Thecore concept previously seemed in the works of Edgeworthin 1881 at the period denoted to as “the contractcurve” according to Kannai(1992). Even though Morenstern and vonNeumann reflected it a remarkable idea, the two operated onlywith zerosum games wherein its core is considered “always empty”.The contemporary definition of the concept of core is owed to Gillies(1959).
Definitionof core
Accordingto Wikipedia, thinkthrough a “transferableutility cooperativegame” denoted as (N, v) where N signifies the set of gamers orplayers of the game and v represents the “characteristicfunction”. An assertion(imputation) is subject by one more imputation (y) if there is an existence of acoalition denoted by C, that every player in the coalition C prefersy, officially: x_{i}≤_{}y_{i}forall and there occurs in a way that x_{i}<y_{i }andC can apply y (by intimidating to leave the impressivealliance or coalition to arrange C),
formally:.An imputation (x) is conqueredif an imputation of y exist controlling it. “The coreis the set of imputations that are not dominated”. (Wikipedia,2014)
Propertiesof the core.
Analternative definition, correspondingto the definition mentioned above, is said that “the core is a setof payoff allocations" sustainingthe following:

Efficiency:

Coalitional rationality (for all subsets (coalitions) )
Otherproperties of the core is that, it is continually “welldefined”but it can also be an empty core. It is also a set which fulfils ascheme of “weak linear inequalities”. Thus, this core is convexand closed. According to the Bondareva–Shapleytheorem, “The core of a game is nonempty if and only if thegame is balanced.” (Bondareva1963,Shapley1967).
Anotherproperty is that every Walrasianequilibrium has this “core property”, but a “core property”do not necessary a Walrasian equilibrium. The “Edgeworthconjecture: say that, given supplementary conventions, theboundary of this core is the number of costumers goes to endlessness.It is then a set of Walrasian equilibria.
Lastproperty is stated as: let there be nplayers, where thenumber nis an odd number. A game that suggests to split a unit of a goodbetween the alliance that has at least (n+1)/2fellows is considered to have an “empty core”. Thus, there is anexistence of an unstable coalition.
Examplesof the core
1^{st}Example (Miners)
Thereexist a group of miners (number of members is n) who found big chunksof gold. Assuming two miners can bring a piece of this found gold,then, the “payoff” of the group (S) can be said to be
Inthe case that there are two or more miners and their number is even,their core comprises just a single payoff but every miner just getshalf. In the case that the number of the miners is an odd number,then, their core is considered empty.
2^{nd}Example (Shoes)
Forthis situation, disregard the shoe sizes. A pair of shoe comprises aone right and one left shoe. These can be sell amounting to €10.Now, study a game consisting 2001 players, 1001 of them has a rightshoe and the rest, with one left shoe. The core of this game becameslightly startling. Its core comprises of one imputation thatresulted to 10 for the players that have a (scare) left shoe and azero (0) for that who possess an (overprovided) right shoe. Toconfirm this case and to explain further why it became so, take notethat every pair of a right and a left shoe can be one coalition.Their pairing can be sold for ten euro (€10). Thus, a single pairwhich will be less than the stated will “block” the imputation.If this imputation is in the core, and we’ll try to list down thepairing, the result will be 1000 pairs, and a total income of 10,000euro. This gives a right shoe owner 0 pay. In the case that there areplayers less than ten who possess leftshoe, for example 9, then itcan link this deprived player, trade their shoes, offer him one, andsave 9 to herself. This is a better option. For firmness such aleftshoe owner cannot exist: all left shoe owners get already 10.According to the source, Wikipedia, “The message remains the same,even if we increase the numbers as long as left shoes are scarcer andthe core has been criticized for being so extremely sensitive tooversupply of one type of player.”
3^{rd}Example (Gloves)
Considertwo ladies, Ms R and Ms J. They have knitting gloves and this glovesare a free size gloves, which means that this only size fits all. Ofcourse, two of it makes a pair and a pair costs five euro (€5).Each of the two ladies made three of these gloves. The problem is thesharing of the profit of the trade.
Thisproblem is defined to be in a “characteristic function form”situation. The solution will be as follows, since they made threeeach, a total of 6 gloves has been made. The three pair of glovescost fifteen euro (€15). “Since the singleton coalitions(consisting of a single lady) are the only nontrivial coalitions ofthe game all possible distributions of this sum belong to the core,provided both ladies get at least €5, the amount they can achieveon their own. For instance (7.5, 7.5) belongs to the core, but sodoes (5, 10) or (9, 6).”
Thecore in universal equilibrium theory
“TheWalrasian equilibria” of an interchange economy in a universalequilibrium model, will be in the core of the collaboration gameamongst the agents. In detail, and in an agent which has two, thecore is the group of points on the curve which is contract. This isthe group of Pareto optimal distributions) going amid every agents`insignificance curves distinct at the early benefactions.
Thecore in voting theory
Whensubstitutes are allocations, it is normal to adopt that to someextent “nonempty subsets of individuals” can slab a certaindistribution. When substitutes are public, in a way that the total ofa certain communal good, nevertheless, it is much more suitable toadopt that merely the alliances or coalitions that are big enough canslab a given substitute. The group of that large ("winning")alliance is known as “a simplegame”.“The coreof a simple game with respect to a profile of preferencesis based on the idea that only winning coalitions can reject analternative infavor of another alternative”.An essential and enough situation for the core to be considered anonempty core for the entire summary of inclinations, is delivered inexpressions of the Nakamuranumber for “the simple game”.
References:
Barron,E. N. (2013). Gametheory: an introduction.Hoboken, New Jersey: John Wiley & Sons, Inc.
Binmore,K. G. (2007). Gametheory: a very short introduction.Oxford New York: Oxford University Press.
Gilles,R. P. (2010). TheCooperative Game Theory of Networks and Hierarchies.Theory and Decision Library: Series C: Game Theory, MathematicalProgramming and Operations Research, vol. 44.
Grabisch,M., & Sudhölter, P. (2012). The bounded core for games withprecedence constraints. AnnalsOf Operations Research,201(1),251264. doi:10.1007/s1047901212289
LeytonBrown,K., & Shoham, Y. (2008). Essentialsof game theory: a concise, multidisciplinary introduction.California: Morgan & Claypool Publishers.
MasColell,A., Whinston, M., & Green, J. R. (1995). Microeconomictheory.New York: Oxford University Press.
MomoKenfack, J., & Tchantcho, B. (2014). On the nonemptiness of theonecore and the bargaining set of committee games. OperationsResearch Letters,42(2),113118. doi:10.1016/j.orl.2013.12.010
Peters,H. (2008). Gametheory: a multileveled approach. Berlin:Springer.
Scarf,H. E. (1997). The Core of an N Person Game. In O. F. Hamouda, J. R.Rowley (Eds.) , Economicgames, bargaining and solutions(pp. 211230). Elgar Reference Collection. Foundations ofProbability, Econometrics and Economic Games, vol. 3.
Shubik,M., & Shapley, L. S. (1999). The Assignment Game 1: The Core. InM. Shubik (Ed.), Theselected essays of Martin Shubik. Volume 1. Political economy,oligopoly and experimental games(pp. 520538). Economists of the Twentieth Century series.
Wikipedia(2014). Core (game theory). Retrieved February 5, 2014, fromhttp://en.wikipedia.org/wiki/Core_%28game_theory%29
Recent Comments