Jump to content

Photo

Game Theory


  • Please log in to reply
3 replies to this topic

#1 Fatal Dawn

Fatal Dawn

    Byte

  • Members
  • 9 posts
  • LocationPennsylvania, USA

Posted 05 July 2012 - 12:17 PM

Hello fellow nerds, this is a recent short tutorial I had written about Game Theory.


Here I attempt to pick apart the different aspects of that complex theory and explain them by putting things into better perspective for those who are interested. Some of these examples are adopted from textbooks I have read on finite mathematics. I had to change some of the formatting, so I apologize for that. :)



----

Introduction to Game Theory

In many games, players require certain attributes or skills to excel in the game. Games of chance are heavily luck-based. With a simple roll of the die or a favorable spin of a roulette wheel, the volatile flow of the game is drastically altered. Other games require the player to use logic and strategy, requiring the player to plan their actions as well as the actions of opposing parties. Game theory attempts to observe and analyze these nuances as well translate them into mathematical terms.


A Strictly Determined Game

I’ll commence with the design of a strictly determined game. In a strictly determined game there can be a determined way for one player to win the game. Because of this reason, strictly determined games are not traditionally fair. Strictly determined games have at least one saddle point (as discussed below in minimax strategies) which provides opportunities for a player to win the game.

Minimax Strategies

As previously noted, you can tell whether a game is strictly determined because it will usually have at least one saddle point. Let’s take and analyze a simple, two-person game matrix (this is all one set).


| 1 2 |
| 4 3 |
| 9 8 |


Row minimum: 1, 3, 8,

Max of row min: 8


Column maximum: 9, 8
Min of column max: 8


8 is the saddle point, or the location of a value that is simultaneously a row minimum and a column maximum. The lesser of the highest (column) is equal to the greatest of the lowest (row). Or, the minimum number of the set of the column maximum is inversely proportional to the maximum number in the row of the minimum.

In some grid-based logic puzzles, the saddle point can indicate the fairness of a game. Games with zeroes as saddle points tend to be fair games (explained below).

Saddle points also share the same reward value. Because of this, saddle points are often associated with minimax strategies, or one that minimizes the maximum offensive effort that the opponent can have.

Here is a great resource if you are interested in learning more.


‘Fair Game’ Principle

In mathematical terms (and most likely by colloquial knowledge too), a fair game describes when the conditions of a game are equal for each player; meaning no player is more likely to win than another. However in game theory, the principle is taken a step further to describe a condition where the long term average of a player’s gain is zero (see zero-sum theory). Under these conditions a player’s losses tend to equal a player’s gains, so the net gain (or overall gain) is exactly zero – no less or no larger than any other player in the game. An iconic example of a fair game is a two-person coin flip. One player has the same probability of landing heads as the other player landing tails.


Logic and Ratio

Logic-based puzzle games, such as nonograms for example, use mathematical strategies and – moreover – deductive reasoning. Games such as these are highly peripheral; requiring players to use deductive reasoning as well as mathematical ratios to arrive at the most plausible solution by ruling out implausible combinations.

For example, in a 5x5 grid, players can rule out combinations that add up to five. If a player is given a 3/2 or 2/3 ratio combination, he or she can assume that even if two or three spaces are eliminated, the remaining spaces can only contain 1s. Similarly with a 4/1 or 1/4 ratio combination, the uneliminated spaces are always a meager point value of 1.

Here’s an example of a 3/2 ratio combination:

[ ] [ ] [ ] [ ] [ ] --> (eliminating any 2 from the set) [ ] [x] [ ] [ ] [x] --> (the rest must be 1 point values) [1 ] [x] [1 ] [ 1] [x]

Keep in mind that 1s are always irrelevant to the game. If the most you can get in a row is a 1, the row can and should be eliminated. You have nothing to gain and a lot to lose.

Most games that are strategy games involve the use of logic and ratios in relation to the strategy the player chooses to adopt.



Strategies in Relation to Probability and Reward

Some games require players to weigh their potential rewards with the probability of attaining those reward. Let’s use this matrix to represent a fair game between two players: Ashley and Ben.

Ben - b1 b2

Ashley - a1 a2


| x11 x12 |
| x21 x22 |

Strategies: a1b1, a1b2, a2b1, a2b2
Probability: p1x1, p1x2, p2x1, p2x2
Reward: x11, x12, x21, x22


Please note that p1 is representative of the probability of Ashley choosing strategy a1, while p2 represents her choosing a2. Conversely, x1 is representative of the probability of Ben choosing strategy b1, while x2 is representative of him choosing b2.

An ideal strategy is one which minimizes risk and maximizes chance. In other words, an ideal strategy is based on these conditions:

Low chance of negative (risk) + high chance of positive (reward).


Weighing Risk/Reward Options in a Game Matrix

Above, I explained the optimal strategy each player must take to minimize a negative event and maximize a positive event. However most games are uncertain from start to finish, thus it is not easy for a player a player to make sure he or she is taking the optimal strategy.

In the game matrix below a player is weighing his or her risk/reward options in a game matrix.

In the real world this could translate to natural circumstances. When a patient is deciding whether to make a life-altering decision such as a surgery or not to have surgery, that patient is weighing the risk and rewards of the necessity of the operation against nature (nature encompassing factors such as how long the patient will live depending on whether the surgery is performed or not).

Back to the virtual environment, suppose we were given the following matrix. Remember this is one set and that this is a strictly determined game.


Game Matrix -- Player


R -- NR
O -- NO

| 15 25|

| 3 30|

O – Player chooses the Option
NO – Player choose No option
R – Reward
Nr – No reward


In this scenario, let’s assume the game matrix assumes a [1 0] strategy and the player decides to also assume the same natural strategy.

In the game, the probability of reward is a low 10% (90% no reward), leaving us with the following combination
[.10 .90]

Using the game matrix’s strategy [1 0], the player makes a gamble and choose to opt (represented by set [15 25]). Here is what we get when we use matrix multiplication on the specified set:

[1 0] | 15 25 | |.10| --> [15 25] |.10| --> 24.5
| 3 30 | |.90| |.90|

If the player chooses the option, on average he or she would yield a 24.5 reward chance.


Using the natural strategy of the game matrix [0 1] and choosing no option [3 30],

[0 1] | 15 25| |.10| --> [3 30] |.10 | --> 27.3
| 3 30| |.90| |.90|


If the player chooses no option, on average he or she would yield a 27.3 reward chance.

From this standpoint choosing no option would be a slightly better strategy than choosing the option.
Suppose, though, that we were asked to figure out under what circumstances are choosing this choosing the option better than choosing no option. Here the computer’s matrix is using [ai 1 – ai].

Choosing the option

[1 0] | 15 25 | | ai | --> 15ai + 25 (1 – a1) -->25 – 10ai
| 3 30 | |1 – ai|

Choosing no option

[1 0] | 15 25 | | ai | --> 3ai + 30 (1 – a1) --> 30 – 27ai
| 3 30 | |1 – ai|

Since we have the two sets of equations, we are able to find out what the reward chance needs to be in order to consider whether choosing the option would be better than choosing no option. This is represented under the following inequality:

25 – 10ai > 30 – 27ai

This equality says that choosing the option is greater than choosing no option. If and only if…

17 ai > 5
(ai) > 5/17 or .294

Balancing the equation using simple algebra, we see that choosing the option would be better than choosing no option if the reward chance is greater than .294.


Conclusion

It is very important to note that game theory has far-reaching implications beyond the virtual quandary. I’ve only touched the tip of the iceberg, so to speak. Generally, game theory falters in its assumption that most people pathologically tend to observe patterns and form decisions based thereof. Although, natural game matrices tend to operate and behave in this sort of manner, players do not. Under certain conditions, nature is presupposed to act indefinitely with a definite number of probabilities. As such, logic is the basis for any undertaking. Game theory implies examining the current or natural patterning conditions in order to adjust one’s actions accordingly.

Thanks for reading!


Posted Image

#2 Coconut Man

Coconut Man

    Gigabyte

  • Members
  • 798 posts
  • LocationThe latest Smash Major

Posted 13 January 2013 - 02:29 AM

Intriguing... I like it! :D

fl9Uov4.gif


#3 SushiKitten

SushiKitten

    Coffee Cat

  • Members
  • 1,916 posts
  • LocationCanada

Posted 13 January 2013 - 06:39 AM

Very interesting stuff.

Whenever I think of Game Theory, I think of the Monty Hall Problem that used to perplex me so much when I was in middle school. I thought it was so weird.

#4 Calvary

Calvary

    Conceptual

  • Members
  • 6,624 posts
  • Locationwww.

Posted 13 January 2013 - 08:31 AM

Unfortunately, whenever I see game theory I think of economics study. It's the most misleading topic because economics =/= fun.

tumblr_om7nwjm5Wm1rsea1wo1_500.gif
Ask for my discord/Insta/Tumblr if you want.