Game Theory 21 – Arrow’s Impossibility Theorem (2)

Part 21. Arrow’s Impossibility Theorem (2) – There is No Perfect Voting

 

At the last post, we learned the basic principles and rules of Arrow’s impossibility theorem. It is hard to accept that there is no perfect decision-making method in our democratic society, but it is true and we can easily notice that this theorem applies in real worlds. Most of the democratic countries use voting to elect its governmental officials. Except the United States, most of the countries in the world use multiparty systems (especially European countries). Because of this system, these countries have three or four (even more) candidates in each constituency. However, if a government official is elected by the largest number of votes, the candidate who has only 30 percent of the vote can be a official of a province. Preventing this undemocratic situation, people of lots of countries implement the final vote system (two-round runoff system). Therefore, top two winners of the first round of the vote can have chances to enter the second (final) round of the vote. Let’s make a supposition which is based on the final vote system.

There are three candidates (Alex, Louis and Jane) of the local official election of country A. In this province, only three people (Steve, John and Catherine) have the rights to vote. Steve supports Alex in first and Louis in second. John endorses Louis in first and Jane in second. Lastly, Catherine supports Jane in first and Alex in second. So, candidate preferences of Steve, John and Catherine are like this.

	steve	john	cathernie
1st prefernce	Alex	Louis	Jane
2nd prefernce	Louis	Jane	Alex
3rd prefernce	Jane	Alex	Louis

Nevertheless, Jane recedes from the candidate of the province. So, in this situation, Steve will vote to Alex and John will vote to Louis because these candidates are their best candidates. However, Catherine will vote to Alex because Alex is her secondly supported candidate. As a result, Alex will be a official of the province, but this consequence does not mean that Alex is the most-preferred candidate in this province. Catherine is obliged to vote to Alex because her firstly endorsed candidate, Jane, already receded from her position. Therefore, this election is democratic decision-making, but it is not efficient decision-making because it does not include all people’s preferences.

This is not the final round system, but it includes the basic principle of the two-round runoff system. A lot of candidates in countries which enforce multiparty systems recedes from the candidates because of personal or political reasons. Consequently, we succeed to find the most democratic decision-making, which is voting, but it is not the most efficient decision-making; it has problems, so all people’s preferences do not include in the results of votes.

Game Theory 20 – Arrow’s Impossibility Theorem (1)

Part 20. Arrow’s Impossibility Theorem (1) – There is No Perfect Decision-making

 

In modern society, the most influential decision-making method is the majority rule: selecting the most supported opinion or strategy. Look at the Senate or the House of Representatives; when the members decide to send American army or confirm the budget proposal for the next fiscal year, they choose the majority opinion by voting. Also, elementary school students use the majority rule in many ways: choosing their student presidents, modifying rules of their school and so on. Therefore, most of the people realize that the majority rule is the most perfect decision-making strategy in modern democratic societies. However, according to Arrow’s impossibility theorem, all of the methods are not perfectly democratic or do not include everybody’s opinion.

Kenneth Arrow, who was awarded the Nobel Prize in Economic Sciences in 1951, suggested the impossibility theorem (most of the people and researchers call this theorem Arrow’s impossibility theorem to commemorate his academic achievement). This rule needs four conditions: non-dictatorship, unrestricted domain, independence of irrelevant alternatives (IIA) and Pareto efficiency. First, the society has to be a democratic society to examine Arrow’s impossibility theorem (we cannot test Arrow’s impossibility theorem in a despotic society. Secondly, the social welfare function of the society has to be complete and provide same ranking of people’s preferences. Also, the individual preferences are the only things that can control the social preference; other variables cannot affect to the social preference. Lastly, according to Pareto efficiency, if individuals prefer A to B, their society should prefer A to B.

As a result, the perfect decision-making method should be not only democratic, but also efficient to choose a society’s opinion. However, it is impossible to find this method in a real world. So, an efficient decision-making strategy is not democratic; the dictatorship enable to make decisions quickly, but it is not democratic. Paradoxically, an democratic decision-making method is not efficient; modern democratic assemblies spend a lot of time to discuss opinions. In this point, the criteria, which determines an efficient decision or not, means that a voted conclusion includes individuals’ preferences. However, democratic voting does not always guarantee efficient conclusions.

Game Theory 18 – Pareto Optimum

Part 18. Pareto Optimum – Being Impossible to Make Better Results

 

When people finished to write their essays for their classes (especially university students), they usually said that they could not write much better essays than the final version of essays. Pareto Optimum is similar situation like this; if the result cannot be changed to the better result, that status is Pareto Optimum.

We learned the game theory to make better results; however, sometimes, we could not make better results because we already arrived at “the best result in the world.” Pareto Optimum is the most efficient status which is distributed resources (such as money, time, natural or human resources). When a situation arrives at Pareto Optimum, nobody could get higher position.

Let’s make a supposition to understand Pareto Optimum easily. There are three situations.

Situation A: If one unit of resources is added, John earns $1000 and Katherine earns $500.

Situation B: If one unit of resources is added, John earns $1000 and Katherine earns $600.

Situation C: If one unit of resources is added, John earns $900 and Katherine earns $800.

So, if Situation A turns to Situation B, John earns same money ($1000), but Katherine earns more $100 ($500 to $600). Also, total income of Situation A (John’s income + Katherine’s income) is $1500, but that of Situation B is $1600. Therefore, there is any situations better than Situation B; we can call Situation B as Pareto Optimum. However, if Situation A turns to Situation C, Katherine earns more $300 and total income of Situation C is $1700, but John’s income is decreased ($1000 to $900). Therefore, we cannot call Situation C as Pareto Optimum.

Nevertheless, Pareto Optimum has a contradiction. Let’s make another supposition. There is a world which only has breads and milk. In this situation, John has all of the breads and milk but Katherine has nothing. It is very unequal situation, but if Katherine takes some amounts of breads and milk, it reduces John’s utility. Even though this act increases Katherine’s utility, it breaks Pareto Optimum. Therefore, Pareto Optimum ignores the effect of income redistribution. It is Pareto Optimum’s contradiction and a big problem.

Game Theory 16 – Parrondo’s Paradox (1)

Part 16. Parrondo’s Paradox (1) –  A Combination of Losing Strategies Becomes a Winning Strategy

 

Through the previous posts, I introduced “how to make a winning strategy.”; the game theory was a personification to solve this problem. However, according to Parrondo’s paradox, people can make a winning strategy by combining losing strategies. Nevertheless, the paradox does not always apply to all high-probability-losing-games (such as casinos, poker games, Chinese mah-jong and so on). If a person adjusts and combines the order of losing games adequately, these losing games can be changed to a winning game. The example which is described the next paragraph is a good example to explain Parrondo’s paradox.

Most of the people know how to play Monopoly which is a board-game to gain more properties and money than other players. In ordinary Monopoly games, each player gets fixed amount of money when a player finishes to turn a complete circle of the board-game. However, during the game, Carol and Julie wanted to change this banal rule. Carol suggested a new rule; players did not get fixed amount of money, but they will lose $1000 when each player completed to turn a track of the game (however, if a player had under $1000 by cash, the player had to lose all of the money). Carol’s suggestion would be beneficial to Carol because she did not have a lot of cash (she had a lot of properties and buildings). However, Julie might lose the game by this suggestion because she had more cash rather than properties and buildings. Therefore, Julie offered another proposal; players counted their money and if the number of a player’s money was even, the player got $3000. Otherwise, the player lost $5000. Carol accepted Julie’s proposal. However, Julie’s proposal would be applied first and then Carol’s suggestion will be applied next turn. Therefore, the order of offers were like this; 1st circle -> Julie’s proposal, 2nd circle -> Carol’s suggestion, 3rd circle -> Julie’s proposal, 4th circle -> Carol’s suggestion (kept repeated).

When new Monopoly game was started, Julie tried and succeeded that her money is always even number (for example, $2000, $2002, $2010). Therefore, Julie lost $1000 at second circle, but she earn $3000 at third circle; she earns $2000 in two circles. However, Carol did not think that her money is even or not. Carol always lost $1000 at odd circles, but she usually lost $5000 at even circles rather than earned $3000. Before they made this rules, Carol almost won their Monopoly games, but, finally, Carol lost at the game because she have no money, properties, and buildings.

According to Julie’s situation, she knew the notion of Parrondo’s paradox. If her money was even number, she could earn $3000 at odd circles (turns). It was true that Julie lost $1000 at even circles (turns), but she could earn $3000 at the next turn if her money was even number. However, in Carol’s situation, she did not know the notion of Parrondo’s paradox, so she usually lost $6000 in two circles. Therefore, Parrondo’s paradox can make a winning strategy by two losing games, but the paradox does not apply all situations or people.

Game Theory 15 – Types of Games (4)

Part 15. Types of Games (5) – Perfect information and Imperfect information

 

A perfect information game and an imperfect information game have opposite meanings. In a perfect information game, all players can recognize other players’ moves and actions. However, many people confuse the difference with perfect information games and imperfect information games because these games look like abstract notions. What is the standard of comparison between perfect and imperfect information? Do they really have different meanings or make vastly distinct results? To explain these two games easily, I answer the second question first. The answer of the second question is “Yes.” As I mentioned above, all players who play a perfect information game can notice the progress of their game and other players’ purposes and results. However, in a imperfect information game, participants cannot recognize other people’s actions or results. They can suppose other people’s next actions and results, but it does not mean they know all the information of a game.

Chess games are the great examples to easily explain a perfect information game. In a chess game, two players readily read the other player’s actions. If player A moved his or her bishop, then player B saw through player A’s design, which was attacking player B’s chess piece, located the diagonal position of player A’s bishop. This chess game is a perfect information game. Most of the people can notice that players who play a perfect information game can detect other players’ actions and designs exactly without assumptions.

Poker games are the great examples to simply explain an imperfect information game. In a poker game, it is impossible to read other players’ cards. If a player tries to sneak other people’s cards, this act is a cheating. A participant of a poker game can assume other players’ cards by their acts or tones, but it cannot bring exactly same images of other participants’ cards.

Eventually, the standard of comparison between perfect and imperfect information is that players can or cannot notice other players’ actions or results without assumptions. If a player of a game know other participants acts, then the game is a perfect information game. However, a player of a game do not know other participants’ acts, then the game is an imperfect information game.

Game Theory 14 – Types of Games (3)

Part 14. Types of Games (3) – Chicken Game (A Part of Symmetric Games)

 

In symmetric games, the payoff (result) is based on other people’s strategies, not their behaviors. However, in asymmetric games, participants do not have same strategies. The good example to explain is “Chicken Game.”

The meaning of “chicken” in chicken games is a coward, not a hen or rooster. The origin of this game is the car racing game in 1950s. Two people started to step on accelerators of their car from both ends of the road. Their two cars would be crashed if a guy had not turned the steering wheel of his car. However, the guy who turned his steering wheel would lose in this chicken game. Nowadays, the meaning of a chicken game is the participants in the game keep competing each other without concessions.

In twentieth century, the United States and Soviet Union (USSR) did chicken games to hold a dominant position on the hegemony of the world. It is a famous example of chicken games, but the collapse of the oil price in nowadays is a kind of the chicken game. The Russian Federation started to expand its dominance to eastern Europe by Crimean Peninsula. However, the United States failed to stop the extension of Russian power to eastern Europe because the residents of Crimean peninsula already agreed to get in the Russian Federation. Therefore, the United States started to increase the oil supply through the supply of shale oils. The Energy Information Administration of the United States said that the oil outputs of Bakken in Northern Carolina state, Eagle Ford and Permian in Texas state, which are the big three shale oil fields, increased 100 thousand barrels than the outputs of December. The low oil price is a big burden to the Russian Federation because oil exportation is a big part of to maintain Russian finances. This situation is a chicken game. American government wants to stop the expansion of Russian power to eastern Europe, but Russian government do not want to follow America’s request. The United States tries to change the political decisions of Russia (Eastern Europe policy) through the low-oil-price chicken game, but it can be harmful to the United States because the low price decreases the profits of American oil productions.

Game Theory 13 – Types of Games (2)

Part 13. Types of Games (2) – Zero-sum and Non-zero-sum Games

 

If the result of profits and losses is zero, that game is a kind of zero-sum game. The profit and loss in a zero-sum game is limited, so if someone gains profits in the game, the other person has to lose his or her benefits in this game. In other words, if I lose my benefits in a game or a market, my competitors take my benefits. Therefore, participants in zero-sum games have to compete keenly to keep their profits. However, in non-zero-sum games, most of the participants in the games will take advantages because keen competitions are not required in non-zero-sum games. Even though a participant takes profits in an non-zero-sum game, it does not mean that other participants in this game lose their profits. Many markets were started non-zero-sum games, but they changed to zero-sum styles. One of the best examples is a mobile communication market.

A lot of people used telephones when mobile services were started. Mobile telecom companies (such as Verizon Wireless, AT&T, Sprint and T-Mobile) did not have to compete keenly because they have many latent customers. When these companies advertised their services at the first time, it was not difficult to attract people to their customers. In this time, the mobile telecom market was a non-zero-sum game. Nowadays, however, it has been changed. In developed countries, the penetration rate of cellphones was exceeded 100 percent. It means that almost 100 percent of people in the countries use cellphones, so the companies do not have latent customers anymore. The enterprises have to compete each other to take other telecom companies’ consumers to improve their profits. Therefore, if a company increases its profits because it has attracted a lot of new customers through the Christmas promotion, other companies are failed to improve their benefits because the market is limited.

Game Theory 12 – Types of Games (1)

Part 12. Types of Games (1) – Cooperative and Non-cooperative Games

 

Most of the readers have already realized that the game theory is not a simple progress to explain. I explained Nash Equilibrium during four posts, but Nash Equilibrium has been existed because of the basic types of the game.

Before introducing the notion of cooperative and non-cooperative type of the game, what is the meaning of “cooperative”? A dictionary meaning of cooperative is “acting in conjunction with others.” It means that people are willing to share their profits or other positive things to achieve their goals. Of course, “non-cooperative” means that people do not want to help each other.

---

Cooperative/Non-cooperative

The players of cooperative games are willing to help each other. In the cooperative games, the players (whole of them or some parts of them) should agree the binding agreements, which mean powerful rules (the players have to follow these agreements, but the agreements are not their duties), making coalitions. If they are not agree these agreements or deny to help each other, the type of the game will be change to an non-cooperative type. Also, if players break rules or agreements, they are punished. One of the best examples of the cooperative type of games is plea bargaining. Plea bargaining is a policy to treat judicial problems promptly. Most judicial problems need to spend a lot of times because attorneys and prosecutors appeal against a court decision. However, if prosecutors use plea bargaining to criminals, all of the people in the court can save a lot of times, skipping unnecessary judicial proceedings. Also, prosecutors can get other information of the crimes, so they can easily focus on other important problems. In this situation, all of the players of the plea bargaining (suspects, attorneys and prosecutors) agreed to do plea bargaining and followed the rules of plea bargaining, so it is a kind of cooperative type of the game. Nevertheless, it is illegal in some countries (in South Korea), but, in the United States, many prosecutors are using plea bargaining, which is the most famous cooperative type of the game theory, to save their times.

Non-cooperative games are totally different with cooperative games. All (or some) of the players did not agree binding agreements, or not want to follow the rules of the games. Therefore, in non-cooperative types of the games, the players are not allowed to cooperate each other or make coalitions. They may be allowed to make agreements, which follows the rules of the games, even though some players break the rule, the players have no responsibilities about that. A prisoner’s dilemma, a hostile bid and pure competition are good examples to explain non-cooperative games. In the non-cooperative game, the players will focus on their own profits rather than cooperation, so this behavior is called self-enforcing behaviors.

 

Game Theory 10 – Nash Equilibrium (3)

Part 10. Nash Equilibrium (3) – Correlation between Nash Equilibrium and Guaranteed The Lowest Price

“Guranteed The Lowest Price”, “The Cheapest Store in the Whole Country (or City, Town and so on)” are very familiar catchphrases. When we arrived at major supermarkets (such as Walmart, CVS, Target), there are lots of these familiar sentences in the markets. Many major retail companies say that they compensate their customers for differences. However, most of the products whose prices was guaranteed have same prices in a lot of retail chains. Therefore, there are a lot of “guranteed” catchphrases, but only few people were compensated though this marketing strategy. For this reason, Most of people have just ignored this guaranteed marketing strategy, but the basic principle of this strategy are made up by Nash Equilibrium.

I suppose that there are Supermarket Alpha and Echo Retail Store in Wood Mall. Supermarket Alpha and Echo Retail Store have exactly same area, selling similar stuff (such as groceries and industrial products). However, one day, Supermarket Alpha started “Guranteed The Lowest Price in the City.” This supermarket compensate its customers for the differences, if the products’ prices are higher than those of supermarkets in the city. Also, Supermarket Alpha pays the difference by twice. After this marketing strategy is started, most of the products’ prices in Supermarket Alpha have the lowest prices in the city because the supermarket do not want to compensate for differences. However, a few people receive the differences by cash because some products’ prices are higher than those of Echo Retail Store.

In this case, if Echo Retail Store sells its products costly, most of people does not want to buy products or groceries in Echo Retail Store because the next store, Supermarket Alpha, sells same products and groceries cheaply. Even if Echo Retail Store sells its products cheaply, people will report the difference between the price of a product in Echo Retail Store and this of Supermarket Alpha. Customers just look the prices of products in Echo Retail Store because they want to get rewards of the differences. Therefore, there is only one solution. Echo Retail Store start to sell its products by same prices with those of Supermarket Alpha. After the decision of Echo Retail Store, nobody can report the differences and two supermarkets can earn more profits.

Therefore, these two supermarkets will have same prices, so it is Nash Equilibrium. Because of their profits, they start to sell their products at same price rather than compete in prices. It can cause oligopoly, making negative results to customers. “Guranteed the Lowest Price” catchphrases are one of the most common advertisements in our lives, but the basic principle of this strategy is composed of Nash Equilibrium.

Game Theory 9 – Nash Equilibrium (2)

Part 9. Nash Equilibrium (2) – The History of Nash Equilibrium

It is definitely true that Nash Equilibrium was named after John Forbes Nash, but the idea of Nash Equilibrium was based on Antonie Augustin Cornet, who was a French mathematician and philosopher. His oligopoly theory did an important role to make the basic concept of Nash Equilibrium. Nash referred Cornet’s oligopoly theory, but Nash Equilibrium was covered larger academic areas. Cornet’s oligopoly theory was focused the result when each companies’ benefit was maximized. His oligopoly thinking was only limited to economics; however, Nash Equilibrium covers not only economics, but also other academic parts. The other famous figure in the game theory, John Neumann, and Oskar Morgenstern mentioned mixed strategy Nash Equilibrium, but they limited to zero-sum games. In other words, they only introduced the concept of Nash Equilibrium at zero-sum game situations. The most important part of Nash’s role is that he proved his own definition (extended definition) of Nash Equilibrium. He used Brouwer fixed point theorem to identify mixed strategies that existed outside of zero-sum games, which means he thought that Nash Equilibrium could apply other situations.

Other game theorist found that Nash Equilibrium could make wrong predictions in some situations (specific situations). Therefore, they introduced refinements of Nash Equilibrium, which is the improved version of Nash Equilibrium, to solve perceived flaw points of Nash’s theory. In 1965, Reinhard Selten introduced subgame perfect equilibrium to solve the uncertain possibilities, which was that Nash Equilibrium based on incredible threats. Also, other theorist focused the repetition of a game and absence of perfect information. However, subsequent refinements and extensions of the Nash equilibrium concept share the main insight on which Nash’s concept rests.

Nash Equlibrium cannot be a perfect theory to explain non-cooperative situations of the game theory. However, it took the important role to identify what is non-cooperative games and how to prove them. Therefore, if the game theory will exist in the world, the basic concept of Nash Equilibrium is not able to be changed.