Follow us on Twitter!
One mans freedom fighter, another's terrorist.
Monday, April 21, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 29
Guests Online: 29
Members Online: 0

Registered Members: 82852
Newest Member: sockpuppets
Latest Articles

An Intoduction to Game Theory

Arrow Image it's only math, science, and a lot of logic



When I started searching through the articles, I was immensely surprised that no article had been written on game theory. After all, what do people like us enjoy? Math, science, logic, winning, and (quite possibly) manipulating people. Game theory is my secret crush. No, it's not about monopoly or sports (although it can be used for these things). In the words of wikipedia, “Game theory attempts to mathematically capture behavior in strategic situations, or 'games', in which an individual's success in making choices depends on the choices of others." This article won't bring you the full fledged joy of game theory; that only comes with further understanding. However, I have no doubt that you, like me, will be addicted very quickly.

Oddly enough, modern game theory has it's roots in Von Neumann, a man who you computer hardware hackers should recognize. Regardless, let me start you with the basics. In this article, you will just be analyzing games, not solving them. Nevertheless, this is a necessary step to advanced game theory. My hope is to work you up to a simple yet puzzling situation which will keep you thinking about game theory insanely too much.

If you've followed me thus far you'll have realized what a game is. Simply put, it's any situation in which game theory is used in analysis. There are a few assumptions that are made about these games (although some can be worked around if not present). They involve decisions, they have more than one player, all the players have common knowledge (they know all the information and they know everyone else knows it), and that the players act in their own interest. The latter point is called a rational decision. Conversely a decision that does not make oneself most happy is considered irrational. That is not to say one cannot care about others, only that if it is what the player cares about, he will make himself happy by making others happy. Get it?

Alright, now for a simple example. You and your friend are sitting on your computers getting ready to play some multi-player game. Assuming you were foolish and made no arrangements beforehand, neither of you are sure which of two games you're going to play. Game X or Game Y. Given that you and your friend both would rather play game X, and your least favorite option is to choose different games and not be able to play, the matrix would look as follows.

<TABLE WIDTH=100% CELLPADDING=4 CELLSPACING=0>
<COL WIDTH=85*>
<COL WIDTH=85*>
<COL WIDTH=85*>
<TR VALIGN=TOP>
<TD>
<P><BR>
</P>
</TD>
<TD>
<P>you pick X</P>
</TD>
<TD>
<P>you pick Y</P>
</TD>
</TR>
<TR VALIGN=TOP>
<TD>
<P>friend picks X</P>
</TD>
<TD>
<P>2,2</P>
</TD>
<TD >
<P>0,0</P>
</TD>
</TR>
<TR VALIGN=TOP>
<TD >
<P>friend picks Y</P>
</TD>
<TD >
<P>0,0</P>
</TD>
<TD>
<P>1,1</P>
</TD>
</TR>
</TABLE>

So the columns represent you and the rows represent your friend. In each cell, the first number corresponds to your happiness with the situation and the second to your friends. Larger values are assigned to the more preferable options, but what numbers you choose or how much larger they are doesn't really matter. Since you both have the exact same preferences here, the numbers are the same. Since you and your friend both have common knowledge of your preferences, if you both choose game X, you are both as happy as possible. That is since you both like game X the most, and you both know the other likes game X the most, it is reasonable that you both choose game X. If you had been irrational and chosen the game you didn't like it would no longer be a game as stated above. If you had called your friend to pick one, then this situation would be a different type of game, one that I'm afraid is not covered in this article.

Anyway, that was simple. If you both like the same game the most, you'd both play it. It makes sense without a table or even without game theory. Yet this is just an extremely simple example that will be a building block for everything else in game theory. Look at the cell that we arrived upon. There is a very definitive answer there. If either you or your friend choose a different option (without the other switching), you could not do any better. This is called a Nash equilibrium.

Before I present a slightly different and more puzzling situation I want to give you hope that not all game theory is this trivial. Game theory has been used by the U.S. to earn billions of dollars. It was used by a Harvard professor to sell a $100 bill for over $400. Law enforcement, poker sharks, businesses, and stock brokers all use it to get the best out of a situation. I have no doubt that us hackers can't too.

And with that, I present a very famous puzzle, the Prisoner's Dilemma. Two criminals known to work together are caught and taken for interrogation to separate rooms. With the evidence the police have, the situation lays as such: If neither confess, they'll both get only 1 year in prison. If one confesses and the other doesn't, then the confessor will get 5 years, while the other gets nothing. If both confess, they'll both get 3 years in prison. The criminals are told such and their matrix looks like this. Remember, the higher numbers represent the more preferable option.

<TABLE WIDTH=100% CELLPADDING=4 CELLSPACING=0>
<COL WIDTH=85*>
<COL WIDTH=85*>
<COL WIDTH=85*>
<TR VALIGN=TOP>
<TD>
<P><BR>
</P>
</TD>
<TD>
<P>#1 Confess</P>
</TD>
<TD>
<P>#1 Keep Silent</P>
</TD>
</TR>
<TR VALIGN=TOP>
<TD>
<P>#2 Confess</P>
</TD>
<TD>
<P>1,1</P>
</TD>
<TD >
<P>0,3</P>
</TD>
</TR>
<TR VALIGN=TOP>
<TD >
<P>#2 Keep Silent</P>
</TD>
<TD >
<P>3,0</P>
</TD>
<TD>
<P>2,2</P>
</TD>
</TR>
</TABLE>

What would you do? Well it turns out both prisoners always confess and the little desired option, not the least though, is received by both prisoners. Why? Look at the 1st column first. Regardless of what prisoner 2 does, it is always better for prisoner 1 to confess. The same holds true for prisoner 2. Study the table until you can verify this. Again, the first number in a cell always corresponds to the column header, in this case prisoner #1's preferences. Isn't that crazy though? Why don't they just both stay silent? Because the moment one thinks the other prisoner will confess it is better for them to do so as well. And so they always both end up confessing.

That's one of my favorite games. I hear you wondering, does it have any real life application? Yeah. If you think about it, you can find an infinite number. Here's one: two enemy countries are deciding whether to build up an army. The most desirable option would be for them both to save their money and not, but the moment one thinks the other will, they both end up doing it.

So that's game theory for you. The very tip of the iceberg admittedly, but still, it's quite a glimpse. I really do hope you're hooked like myself. If you search the Internet you can find lots more about it, and if this article goes over well, I'd be happy to indulge you with some more intermediate material. Thanks so much for reading, and in my custom I'll finish with a quote,

"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
-John von Neumann

Comments

rootDaemonon March 29 2011 - 21:50:27
Could an admin edit this so the html shows up?
rootDaemonon March 29 2011 - 21:50:44
Could an admin edit this so the html shows up?
Pwnzallon April 05 2011 - 16:28:14
Try BBcode or if not, just copy and paste in this website and it will render HTML for you: http://w3schools.. . .html_intro
cyber-guardon April 13 2011 - 12:58:15
Very interesting topic, however this article I believe is way too brief covering only the very basics
dgourdon May 01 2011 - 21:37:18
I had already gone over this information about game theory before, but I found it enjoyable reading it over again. I think it serves its purpose as an introduction well. I would very much enjoy another, more in depth article.
Xunxenon August 23 2011 - 07:20:21
Yale has an open course on intro to game theory, for those interested. http://oyc.yale.e. . .me-theory/
kierronon January 30 2012 - 05:17:14
Interesting post, I've always been kinda curious about game theory
Post Comment

Sorry.

You must have completed the challenge Basic 1 and have 100 points or more, to be able to post.