Optimization in game theory - Revision history

Dts87 at 16:02, 15 December 2021

2021-12-15T16:02:34Z

← Older revision		Revision as of 12:02, 15 December 2021
Line 13:		Line 13:
	=== Theory ===		=== Theory ===
	[[File:Prisoner's Dilemma.png\|thumb\|Payoffs for two players in Prisoner's Dilemma game. <ref name=":1" />\|283x283px]]		[[File:Prisoner's Dilemma.png\|thumb\|Payoffs for two players in Prisoner's Dilemma game. <ref name=":1" />\|283x283px]]
	~~==== Nash Equilibrium ====~~
	The Nash equilibrium is a fundamental concept in game theory. It is most widely used in predicting the outcome of a strategic interaction in the social sciences. A game consists of: a set of players, a set of actions available to each player, and a payoff function for each player. The payoff function is a player’s preference of the action profiles. A “pure-strategy Nash equilibrium” is an action profile with the property that no single player can obtain a higher payoff by deviating from this profile. <ref>R. A. McCain, ''Game theory and public policy''. Cheltenham: Edward Elgar, 2010.</ref>		The Nash equilibrium is a fundamental concept in game theory. It is most widely used in predicting the outcome of a strategic interaction in the social sciences. A game consists of: a set of players, a set of actions available to each player, and a payoff function for each player. The payoff function is a player’s preference of the action profiles. A “pure-strategy Nash equilibrium” is an action profile with the property that no single player can obtain a higher payoff by deviating from this profile. <ref>R. A. McCain, ''Game theory and public policy''. Cheltenham: Edward Elgar, 2010.</ref>

Line 23:		Line 22:

	=== Algorithm ===		=== Algorithm ===
	The common algorithm associated with computing a Nash Equilibrium is the Lemke-Howson algorithm. This algorithm utilizes iterated pivoting much like ~~the simplex algorithm used in~~ the simplex algorithm used in linear programming. A notable difference between the two algorithms is that unlike the simplex algorithm, the Lemke-Howson algorithm cannot be run in polynomial time. The Lemke-Howson algorithm can be considered a brute force algorithm in which we utilize a possible solution as a guess and continue to adjust it through each iteration until we have arrived at the Nash equilibrium. <ref name=":2" />		[[File:Lemke Howson Pivot Walk.png\|thumb\|Lemke Howson Pivot Walk]]
			The common algorithm associated with computing a Nash Equilibrium is the Lemke-Howson algorithm. This algorithm utilizes iterated pivoting much like the simplex algorithm used in linear programming. A notable difference between the two algorithms is that unlike the simplex algorithm, the Lemke-Howson algorithm cannot be run in polynomial time. The Lemke-Howson algorithm can be considered a brute force algorithm in which we utilize a possible solution as a guess and continue to adjust it through each iteration until we have arrived at the Nash equilibrium. <ref name=":2" />

	The tableau method is a pivoting process that can be used to find the Nash equilibrium using the Lemke-Howson algorithm. The first step is preprocessing, the goal here is to limit the options of the game by iterating to maintain the dominating strategies. This reduces the problem complexity and thus the work required to solve it. The initialization of the tableau is the next step. One tableau is needed for each player in the game. Now with a constructed tableau we can begin pivoting. The primary aspect here are the entry and exit variables. The exit variable is the entry variable to the next pivot until the complementarity conditions are met. <ref name=":2" />		The tableau method is a pivoting process that can be used to find the Nash equilibrium using the Lemke-Howson algorithm. The first step is preprocessing, the goal here is to limit the options of the game by iterating to maintain the dominating strategies. This reduces the problem complexity and thus the work required to solve it. The initialization of the tableau is the next step. One tableau is needed for each player in the game. Now with a constructed tableau we can begin pivoting. The primary aspect here are the entry and exit variables. The exit variable is the entry variable to the next pivot until the complementarity conditions are met. <ref name=":2" />

			The algorithm flow consists of four primary steps. Preprocessing is the first step, which consists of reducing the solution space by ruling out strictly dominated strategies. Tableaux Initilizations involve creating a tableaux for all involved parties in the game. With all tableauxs created the next step is pivoting. By chosing the basis variable to enter and exit on, multiple iterations of pivoting can be performed to fund the output which is the final step of the process.

	== Numerical Example ==		== Numerical Example ==

Lkr34 at 05:25, 15 December 2021

2021-12-15T05:25:35Z

← Older revision		Revision as of 01:25, 15 December 2021
Line 112:		Line 112:
	== Applications ==		== Applications ==
	The application of GT can be found across a multitude of disciplines, but the general framework of GT allows players to compare the outcomes of different decisions. A list of popular applications for GT will be discussed, and these game examples can be altered and applied to a wide range of scenarios.		The application of GT can be found across a multitude of disciplines, but the general framework of GT allows players to compare the outcomes of different decisions. A list of popular applications for GT will be discussed, and these game examples can be altered and applied to a wide range of scenarios.
	== Game Examples ==		=== Game Examples ===
	=== Stag Hunt ===		==== Stag Hunt ====
	This game balances safety and social cooperation. Two hunters go for a hunt, and each must choose to hunt a stag or a hare, without knowing which the other chooses. In order for the hunters to take down a stag, both must hunt the stag. Each may hunt a hare individually, but the payoff from the hare is less than that of the stag. The goal is to maximize payoff. <ref name=":0" />		This game balances safety and social cooperation. Two hunters go for a hunt, and each must choose to hunt a stag or a hare, without knowing which the other chooses. In order for the hunters to take down a stag, both must hunt the stag. Each may hunt a hare individually, but the payoff from the hare is less than that of the stag. The goal is to maximize payoff. <ref name=":0" />
	=== The Battle of Sexes ===		==== The Battle of Sexes ====
	This game falls into the category of coordination games and is based around the decisions for what two individuals will do on a given night. For instance, a girlfriend and boyfriend prefer to go to the opera and a football game, respectively. They do not decide on where they are going before leaving for the day and do not communicate with each other throughout the day. They prefer the place that they chose, but they would prefer to go to the same place. The goal is to maximize happiness. <ref name=":0" />		This game falls into the category of coordination games and is based around the decisions for what two individuals will do on a given night. For instance, a girlfriend and boyfriend prefer to go to the opera and a football game, respectively. They do not decide on where they are going before leaving for the day and do not communicate with each other throughout the day. They prefer the place that they chose, but they would prefer to go to the same place. The goal is to maximize happiness. <ref name=":0" />
	=== The Prisoner’s Dilemma ===		==== The Prisoner’s Dilemma ====
	Two criminals are arrested, imprisoned, and isolated from each other. Without enough evidence to accuse either criminal of a crime, there are three possible outcomes: both reveal evidence and both stay in prison for 4 years, one reveals evidence and one stays silent so the one that reveals is set free while the one that stays silent serves 5 years, and if both prisoners stay silent then both will only remain in prison for 2 years. The goal is to minimize prison time. <ref name=":0" />		Two criminals are arrested, imprisoned, and isolated from each other. Without enough evidence to accuse either criminal of a crime, there are three possible outcomes: both reveal evidence and both stay in prison for 4 years, one reveals evidence and one stays silent so the one that reveals is set free while the one that stays silent serves 5 years, and if both prisoners stay silent then both will only remain in prison for 2 years. The goal is to minimize prison time. <ref name=":0" />
	== Extensions of GT ==		=== Extensions of GT ===
	=== Evolutionary Game Theory ===		==== Evolutionary Game Theory ====
	GT was developed on human interaction, but the theory was applied in biology to model how animals behave when competing for a resource. Rather than using logic, the players, or animals, instead are motivated by reproductive success. In Evolutionary Game Theory, the success is based on the frequency of success against competing strategies. In the end, successful strategies will be used more frequently and be the final victor. <ref name=":0" />		GT was developed on human interaction, but the theory was applied in biology to model how animals behave when competing for a resource. Rather than using logic, the players, or animals, instead are motivated by reproductive success. In Evolutionary Game Theory, the success is based on the frequency of success against competing strategies. In the end, successful strategies will be used more frequently and be the final victor. <ref name=":0" />
	=== Behavioral Game Theory ===		==== Behavioral Game Theory ====
	While computers may try to optimize utility and use perfect logic, humans have been found to not always use logic or maximize utility. Instead, Behavioral Game Theory attempts to model and predict human choices in games, rather than advise the optimal solution. Experimental data is leveraged to show trends and account for external factors, such as emotions, bounded rationality, cultural influences, and reputation among others on the decisions that humans make in games. <ref name=":0" />		While computers may try to optimize utility and use perfect logic, humans have been found to not always use logic or maximize utility. Instead, Behavioral Game Theory attempts to model and predict human choices in games, rather than advise the optimal solution. Experimental data is leveraged to show trends and account for external factors, such as emotions, bounded rationality, cultural influences, and reputation among others on the decisions that humans make in games. <ref name=":0" />
	=== Mechanism Design ===		==== Mechanism Design ====
	Mechanism design introduces a reverse approach to GT in that the objective is known while the rules and mechanisms are unknown. The game must be designed such that players are incentivized to behave as the designer intended. As an example, a Vickrey auction style is an example of auctioning where the good goes to the highest bidder at the price of the second-highest bid. This form of game incentivizes players to be honest in their evaluation of the good. <ref name=":0" />		Mechanism design introduces a reverse approach to GT in that the objective is known while the rules and mechanisms are unknown. The game must be designed such that players are incentivized to behave as the designer intended. As an example, a Vickrey auction style is an example of auctioning where the good goes to the highest bidder at the price of the second-highest bid. This form of game incentivizes players to be honest in their evaluation of the good. <ref name=":0" />
	== Conclusion ==		== Conclusion ==

Lkr34 at 05:23, 15 December 2021

2021-12-15T05:23:52Z

← Older revision		Revision as of 01:23, 15 December 2021
Line 35:		Line 35:
	=== Problem Statement ===		=== Problem Statement ===
	Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both long and short distance rides:		Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both long and short distance rides:
	{\|		{\| class="wikitable"
	\|+Long Distance Price Matrix		\|+Long Distance Price Matrix
	! colspan="2" rowspan="2" \|		! colspan="2" rowspan="2" \|
Line 43:		Line 43:
	\|Long distance, low ($)		\|Long distance, low ($)
	\|-		\|-
	\| rowspan="2" \|Fylt		\| rowspan="2" \|'''Fylt'''
	\|Long distance, high ($)		\|Long distance, high ($)
	\|F: 90, B: 160		\|F: 90, B: 160
Line 52:		Line 52:
	\|F: 100, B: 150		\|F: 100, B: 150
	\|}		\|}
	{\|		{\| class="wikitable"
	\|+Short Distance Price Matrix		\|+Short Distance Price Matrix
	! colspan="2" rowspan="2" \|		! colspan="2" rowspan="2" \|
Line 60:		Line 60:
	\|Short distance, low ($)		\|Short distance, low ($)
	\|-		\|-
	\| rowspan="2" \|Fylt		\| rowspan="2" \|'''Fylt'''
	\|Short distance, high ($)		\|Short distance, high ($)
	\|F: 50, B: 60		\|F: 50, B: 60

Lkr34: Refined the solution and formatting for the numerical example

2021-12-15T05:12:18Z

Refined the solution and formatting for the numerical example

Show changes

Jsf244: Moved the Prisoner's Dilemma diagram to the section that references it.

2021-12-11T19:45:32Z

Moved the Prisoner's Dilemma diagram to the section that references it.

← Older revision		Revision as of 15:45, 11 December 2021
Line 12:		Line 12:
	== Theory, methodology, and/or algorithmic discussions ==		== Theory, methodology, and/or algorithmic discussions ==
	=== Theory ===		=== Theory ===
			[[File:Prisoner's Dilemma.png\|thumb\|Payoffs for two players in Prisoner's Dilemma game. <ref name=":1" />\|283x283px]]
	==== Nash Equilibrium ====		==== Nash Equilibrium ====
	The Nash Equilibrium is a fundamental concept in game theory. It is most widely used in predicting the outcome of a strategic interaction in the social sciences. A game consists of: a set of players, a set of actions available to each player, and a payoff function for each player. The payoff function is a player’s preference of the action profiles. A “pure-strategy Nash equilibrium” is an action profile with the property that no single player can obtain a higher payoff by deviating from this profile. <ref>R. A. McCain, ''Game theory and public policy''. Cheltenham: Edward Elgar, 2010.</ref>		The Nash Equilibrium is a fundamental concept in game theory. It is most widely used in predicting the outcome of a strategic interaction in the social sciences. A game consists of: a set of players, a set of actions available to each player, and a payoff function for each player. The payoff function is a player’s preference of the action profiles. A “pure-strategy Nash equilibrium” is an action profile with the property that no single player can obtain a higher payoff by deviating from this profile. <ref>R. A. McCain, ''Game theory and public policy''. Cheltenham: Edward Elgar, 2010.</ref>

	The classic game Prisoners’ Dilemma is widely used to demonstrate the Nash equilibrium. In this decision game, if one player stays silent while the other talks, that player will get 10 years in prison. If they both talk, they both get 8 years. If neither talk, they both will get 2 years. The Nash equilibrium for this game is each player talking and getting 8 years. While both players staying silent is the optimal solution, neither of the players have incentive from deviating to this profile because the player who remains silent is worse off. <ref name=":1">S. Woodcock, “The legacy of John Nash and his equilibrium theory,” ''The Conversation'', 21-Oct-2019. [Online]. Available: <nowiki>https://theconversation.com/the-legacy-of-john-nash-and-his-equilibrium-theory-42343</nowiki>. [Accessed: 10-Dec-2021].</ref>		The classic game Prisoners’ Dilemma is widely used to demonstrate the Nash equilibrium. In this decision game, if one player stays silent while the other talks, that player will get 10 years in prison. If they both talk, they both get 8 years. If neither talk, they both will get 2 years. The Nash equilibrium for this game is each player talking and getting 8 years. While both players staying silent is the optimal solution, neither of the players have incentive from deviating to this profile because the player who remains silent is worse off. <ref name=":1">S. Woodcock, “The legacy of John Nash and his equilibrium theory,” ''The Conversation'', 21-Oct-2019. [Online]. Available: <nowiki>https://theconversation.com/the-legacy-of-john-nash-and-his-equilibrium-theory-42343</nowiki>. [Accessed: 10-Dec-2021].</ref>
	~~[[File:Prisoner's Dilemma.png\|thumb\|Payoffs for two players in Prisoner's Dilemma game. <ref name=":1" />]]~~
	=== Methodology ===		=== Methodology ===
	Nash Equilibrium is commonly used as an example to describe a non-cooperative game involving two or more people. Mixed Integer Linear Programming (MILP) is an optimization method that aims to either maximize or minimize a linear objective function given at least one constraint. In addition, some of the variables in a MILP problem are discrete while others are continuous. Nash equilibrium can be found through mixed-integer linear programming optimization. It can also be found using other optimization methodologies, such as the one created by Tsaknakis and Spirakis. Their method takes the maximum deviation of a player’s payoff from the best payoff that could be achieved by the other players based on their strategy of choice. <ref name=":2">D. Pritchard, “Game Theory F07,” pp. 1–7.</ref>		Nash Equilibrium is commonly used as an example to describe a non-cooperative game involving two or more people. Mixed Integer Linear Programming (MILP) is an optimization method that aims to either maximize or minimize a linear objective function given at least one constraint. In addition, some of the variables in a MILP problem are discrete while others are continuous. Nash equilibrium can be found through mixed-integer linear programming optimization. It can also be found using other optimization methodologies, such as the one created by Tsaknakis and Spirakis. Their method takes the maximum deviation of a player’s payoff from the best payoff that could be achieved by the other players based on their strategy of choice. <ref name=":2">D. Pritchard, “Game Theory F07,” pp. 1–7.</ref>

Gh436: Conclusion

2021-12-10T19:35:20Z

Conclusion

← Older revision		Revision as of 15:35, 10 December 2021
Line 18:		Line 18:
	[[File:Prisoner's Dilemma.png\|thumb\|Payoffs for two players in Prisoner's Dilemma game. <ref name=":1" />]]		[[File:Prisoner's Dilemma.png\|thumb\|Payoffs for two players in Prisoner's Dilemma game. <ref name=":1" />]]
	=== Methodology ===		=== Methodology ===
	Nash Equilibrium is commonly used as an example to describe a non-cooperative game involving two or more people. Mixed Integer Linear Programming is an optimization method that aims to either maximize or minimize a linear objective function given at least one constraint. In addition, some of the variables in a MILP problem are discrete while others are continuous. Nash equilibrium can be found through mixed-integer linear programming optimization. It can also be found using other optimization methodologies, such as the one created by Tsaknakis and Spirakis. Their method takes the maximum deviation of a player’s payoff from the best payoff that could be achieved by the other players based on their strategy of choice. <ref name=":2">D. Pritchard, “Game Theory F07,” pp. 1–7.</ref>		Nash Equilibrium is commonly used as an example to describe a non-cooperative game involving two or more people. Mixed Integer Linear Programming (MILP) is an optimization method that aims to either maximize or minimize a linear objective function given at least one constraint. In addition, some of the variables in a MILP problem are discrete while others are continuous. Nash equilibrium can be found through mixed-integer linear programming optimization. It can also be found using other optimization methodologies, such as the one created by Tsaknakis and Spirakis. Their method takes the maximum deviation of a player’s payoff from the best payoff that could be achieved by the other players based on their strategy of choice. <ref name=":2">D. Pritchard, “Game Theory F07,” pp. 1–7.</ref>

	Linear programming (LP) is another method used in optimization to describe a problem that has an objective function, constraints, and variables that are both linear and continuous. It can be used to determine an optimal strategy for simple games like rock-paper-scissors or more complex ones like poker. <ref>N. Dotzenrod and M. Kweon, “Matrix game (LP for game theory),” ''Northwestern University Open Text Book on Process Optimization''. [Online]. Available: <nowiki>https://optimization.mccormick.northwestern.edu/index.php/Matrix_game_(LP_for_game_theory)</nowiki>. [Accessed: 10-Dec-2021].</ref> The goal is similar to an MILP problem in that it quantifies decision consequences in order to achieve a specific outcome. <ref>F. You, “6800-LP F21,” in ''SYSEN 5800 Lecture''.</ref> For the rock-paper-scissors game where there are two players involved, one player’s set of options are defined as a, where a = {1, 2, and 3} and the other as b, where b = {1, 2, and 3}. Each player can decide from one of three options, i.e. rock, represented by the number 1 and so forth. Their choice results in either a win, loss, or draw with the payoff represented by 1, -1, or 0, respectively. Depending on the established amount of times that the game is played, a matrix can be generated to model the outcome and size from the set of decisions made by both players.		Linear programming (LP) is another method used in optimization to describe a problem that has an objective function, constraints, and variables that are both linear and continuous. It can be used to determine an optimal strategy for simple games like rock-paper-scissors or more complex ones like poker. <ref>N. Dotzenrod and M. Kweon, “Matrix game (LP for game theory),” ''Northwestern University Open Text Book on Process Optimization''. [Online]. Available: <nowiki>https://optimization.mccormick.northwestern.edu/index.php/Matrix_game_(LP_for_game_theory)</nowiki>. [Accessed: 10-Dec-2021].</ref> The goal is similar to an MILP problem in that it quantifies decision consequences in order to achieve a specific outcome. <ref>F. You, “6800-LP F21,” in ''SYSEN 5800 Lecture''.</ref> For the rock-paper-scissors game where there are two players involved, one player’s set of options are defined as a, where a = {1, 2, and 3} and the other as b, where b = {1, 2, and 3}. Each player can decide from one of three options, i.e. rock, represented by the number 1 and so forth. Their choice results in either a win, loss, or draw with the payoff represented by 1, -1, or 0, respectively. Depending on the established amount of times that the game is played, a matrix can be generated to model the outcome and size from the set of decisions made by both players.
Line 74:		Line 74:
	Mechanism design introduces a reverse approach to GT in that the objective is known while the rules and mechanisms are unknown. The game must be designed such that players are incentivized to behave as the designer intended. As an example, a Vickrey auction style is an example of auctioning where the good goes to the highest bidder at the price of the second-highest bid. This form of game incentivizes players to be honest in their evaluation of the good. <ref name=":0" />		Mechanism design introduces a reverse approach to GT in that the objective is known while the rules and mechanisms are unknown. The game must be designed such that players are incentivized to behave as the designer intended. As an example, a Vickrey auction style is an example of auctioning where the good goes to the highest bidder at the price of the second-highest bid. This form of game incentivizes players to be honest in their evaluation of the good. <ref name=":0" />
	== Conclusion ==		== Conclusion ==
	This article summarized GT, a branch of mathematics that analyzes and predicts trends in a number of different game scenarios with a varying number of players. The ~~theory~~ and ~~methodology,~~ numerical ~~implementation,~~ and the ~~wide variety~~ of ~~applications~~ of GT were discussed. GT has existed since 1921, is still applied today, and will continue to be useful to individuals across all disciplines~~, such as the future development of Artificial Intelligence~~. ~~<ref name=":0" />~~		This article summarized GT, a branch of mathematics that analyzes and predicts trends in a number of different game scenarios with a varying number of players. The Nash Equilibrium is a fundamental concept in GT and is commonly used as an example to describe a non-cooperative game involving two or more people. Both MILP and LP are useful programming styles to solve various problems within GT. The common algorithm associated with computing a Nash Equilibrium is the Lemke-Howson algorithm. <ref name=":2" /> A numerical example based on taxi services was detailed and the steps for completing it were outlined. Finally, a few examples of common games that utilize GT and a few extensions of GT were discussed. GT has existed since 1921, is still applied today, and will continue to be useful to individuals across all disciplines.
	== References ==		== References ==
	<references />		<references />

Gh436: References

2021-12-10T19:24:30Z

References

Show changes

Jsf244: /* Numerical Example */

2021-11-29T03:07:08Z

Numerical Example

← Older revision		Revision as of 23:07, 28 November 2021
Line 32:		Line 32:

	Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both far and short distance rides:		Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both far and short distance rides:
	[[File:1.png\|center\|frameless\|~~576x576px~~\|Fylt and Beru 1]]		[[File:1.png\|center\|frameless\|632x632px\|Fylt and Beru 1]]

			[[File:2.png\|center\|Fylt and Beru 2]]


Line 38:		Line 40:

	Fylt draws up the following diagrams to determine the dominant strategies for both Beru and Fylt. Circled in green is the best choice given the two terminal options.		Fylt draws up the following diagrams to determine the dominant strategies for both Beru and Fylt. Circled in green is the best choice given the two terminal options.

			[[File:3.png\|center]]

	* Is there a dominant strategy for Beru and/or Fylt? If so, what is it?		* Is there a dominant strategy for Beru and/or Fylt? If so, what is it?

Jsf244: /* Numerical Example */

2021-11-29T03:05:11Z

Numerical Example

← Older revision		Revision as of 23:05, 28 November 2021
Line 32:		Line 32:

	Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both far and short distance rides:		Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both far and short distance rides:
			[[File:1.png\|center\|frameless\|576x576px\|Fylt and Beru 1]]

Jsf244: /* Numerical Example */

2021-11-29T02:59:38Z

Numerical Example

← Older revision		Revision as of 22:59, 28 November 2021
Line 32:		Line 32:

	Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both far and short distance rides:		Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both far and short distance rides:


			The Fylt finance department receives the cost matrices and performs calculations to inform the company’s future strategy.

			Fylt draws up the following diagrams to determine the dominant strategies for both Beru and Fylt. Circled in green is the best choice given the two terminal options.

			* Is there a dominant strategy for Beru and/or Fylt? If so, what is it?

			When the distance is far, the dominant strategies for both Beru and Fylt are to do low prices.

			When the distance is short, Beru does not have a dominant strategy because its optimal price depends on whether Fylt chooses to price low or high. If Fylt prices low, Beru should go low; but if Fylt prices high, Beru should go high. Fylt has a dominant strategy for short distances: low prices.

			* What is the Nash equilibrium, if it exists?

			Based on the data, the Nash equilibrium for short distances and long distances is for Beru and Fylt to do low prices. So for far trips, Beru will make 150, and Fylt 100. For short trips, Beru will make 30 and Fylt will make 50.

			* How should Fylt invest to outcompete Beru—in doing more short or long distance trips?

			Fylt should invest in scaling up its short distance trips.

	== Applications ==		== Applications ==