Game Theory to the Rescue When Hard Decisions Are to Be Made
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Part Number | 47 | |
| Number of Parts | 169 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/21088 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
EuroPython 201647 / 169
1
5
6
7
10
11
12
13
18
20
24
26
29
30
31
32
33
36
39
41
44
48
51
52
53
59
60
62
68
69
71
79
82
83
84
85
90
91
98
99
101
102
106
110
113
114
115
118
122
123
124
125
132
133
135
136
137
140
143
144
145
147
148
149
151
153
154
155
156
158
162
163
166
167
169
00:00
Decision support systemNP-hardGame theoryGame theoryDecision support systemSelf-organizationMultilaterationSurfaceComputer programmingMultiplication signTwitterStudent's t-testAreaProcess (computing)Social classReading (process)QuicksortTheoryLecture/Conference
01:12
Game theoryWitt algebraGame theorySurfaceDecision support systemComputing platformVideoconferencingDatabaseBitCombinational logicPhysical systemResultantVideo gameSystem callWordMultiplication signCodeExpert systemStress (mechanics)Solid geometryArithmetic meanPrice indexAxiom of choiceComputer configurationCellular automatonPosition operatorMatching (graph theory)Scheduling (computing)Line (geometry)Computer animationLecture/Conference
06:00
Game theoryComputer chessNetwork topologyTheory of everythingDeterminismInteractive televisionLevel (video gaming)Revision controlLecture/Conference
06:46
Multiplication signTable (information)PlastikkarteResultantStrategy gameComputer chessGraph coloringGame theoryNeuroinformatikBitAverageLevel (video gaming)CASE <Informatik>Volume (thermodynamics)TheoryQuicksortInformationLecture/Conference
08:43
Prisoner's dilemmaTheoryNeumann boundary conditionLevel (video gaming)Tablet computerTheoryGame theoryData Encryption StandardComputer chessDirection (geometry)Computer animation
09:28
TheoryBargaining problemThermodynamic equilibriumTheoryForm (programming)Computer chessGame theoryRandomizationWhiteboardData Encryption StandardMultilaterationLecture/ConferenceComputer animation
10:13
Thermodynamic equilibriumTheoryVideo gameResultantPrisoner's dilemmaDecision support systemComputer programmingMathematical modelCalculationGroup actionLecture/Conference
11:02
TheoryGame theoryThermodynamic equilibriumBargaining problemMultitier architectureResultantGame theoryRepresentation (politics)Different (Kate Ryan album)Decision support systemOptical disc driveNeuroinformatikGroup actionNormal-form gameNumberVideo gameComputer scienceAxiom of choiceMultiplication signRight angleComputer simulationLogicSimulationMathematicsComputer animationLecture/Conference
14:31
Parity (mathematics)Game theoryNormal-form gamePlotterMatrix (mathematics)Basis <Mathematik>Computer animation
14:53
Basis <Mathematik>SummierbarkeitForm (programming)Matrix (mathematics)Game theorySymmetry (physics)Prisoner's dilemmaPresentation of a groupBitWeightDifferent (Kate Ryan album)Position operatorLecture/Conference
15:39
Game theoryEquals signGame theoryPoint (geometry)Perfect groupInteractive televisionMatrix (mathematics)InformationComputer animationLecture/Conference
16:14
Video gameGame theoryInformationPerfect groupComputer chessGame theoryComplete informationComputer configurationPrisoner's dilemmaClassical physicsSoftware developerComputer animationLecture/Conference
16:49
Normal-form gamePrisoner's dilemmaReduction of orderTime seriesEndliche ModelltheorieOperator (mathematics)Computer animationMeeting/InterviewLecture/Conference
18:30
Prisoner's dilemmaNormal-form gameMultiplication signGroup actionComputer animationLecture/Conference
19:05
Axiom of choiceThermodynamic equilibriumPrisoner's dilemmaGame theoryStrategy gameGroup actionRoundness (object)Lecture/Conference
20:10
Prisoner's dilemmaRoundness (object)Game theoryMereologyMultiplication signComputer animationLecture/Conference
20:50
Pattern languageResultantAlgebraBayesian networkComputer simulationLecture/Conference
21:21
Tournament (medieval)Prisoner's dilemmaGame theoryTheoryStrategy gameMultiplication signTournament (medieval)BlogBitPrisoner's dilemmaGame theoryDifferent (Kate Ryan album)CausalityTerm (mathematics)TheoryComputer animation
22:06
Extension (kinesiology)Maxima and minimaBitSound effectMultiplication signLibrary (computing)Mathematical optimizationMatrix (mathematics)Slide ruleBargaining problemThermodynamic equilibriumLecture/Conference
23:05
Prisoner's dilemmaStrategy gameMaxima and minimaKey (cryptography)MereologyLibrary (computing)Decision support systemParticle systemPhysical systemInformationCycle (graph theory)Multiplication signIterationData miningView (database)BitGame theoryResultantProgrammer (hardware)Video gameInsertion lossPrisoner's dilemmaInteractive televisionDisk read-and-write headStandard deviationThresholding (image processing)MultiplicationComputer programmingTournament (medieval)Computer animationLecture/Conference
Transcript: English(auto-generated)
00:00
Next thought would be game theory to the rescue when hard decisions are to be made. So, ladies and gentlemen, please welcome our next speaker, Alexander Handoff. Probably wait until the talks finish, but thank you anyway.
00:22
Okay, I'm going to talk about game theory, obviously, today. So, let me introduce yourself and myself. So, in my day job, I develop and I consult. So, I'm moving vertically through things. And I review technical solutions and will work on bringing high-tech startups together with bigger companies
00:43
if they have something that helps both companies. So, that's what I'm doing today time. If you have a challenging high-tech startup, talk to me. Maybe we can help you. And also, I'm one of the organizers of the conference here. I'm program chairing. I'm also active in the MongoDB community.
01:02
I like to talk. And if you have any comments, questions, feel free to ping me on Twitter later. Game theory. We will only be able to stretch the surface of game theory today. So, there won't be no coding if you last chance to leave now.
01:22
And I hope I can give you an idea about game theory because it's a little bit alive beyond if, else, else if. It's a glance into a different life a little bit. I stumbled across using it just like by coincidence at the beginning of the year
01:42
while actually the call for proposals were running. And yeah, people seem to like the idea, unfortunately. So, I mean, game theory is a very human concept. It's not tech.
02:00
It has a background in economics and philosophy. And I think you can imagine yourself. Like, our world is getting much more hectic, complicated. So many options, decisions, and we are required to make decisions all the time. And sometimes this can be really difficult or stressful.
02:22
And we very often worry, did we make the right choice? Did I pick the right Pokemon to win the next challenge? So, a little knowledge of game theory can become really handy. Not only coding and life, solving some problems.
02:44
And yeah, it's about making the best decisions you can. But probably not only best decisions for yourself, also the best decisions for you and the people who surround you. We'll step into that later. So, just think about how do you make decisions?
03:03
How do you make judgments? Do you really note down the pros and cons and wake them up? Some people do. Some people don't. They very much rely on their stomach, as we say in Germany.
03:21
So, think about, do your decisions affect others? And do you care about it? And this is where game theory is going. You have to anticipate the decisions that others do while you're interacting with them.
03:41
And how they impact you and how your decisions impact the others. And yeah, this is basically like the basic idea of game theory. And actually, I stumbled across it. For one client, we were getting messy accounting data from some very popular online platform for videos.
04:06
And we can check what's in there. Sometimes they just match by some word stuff we don't really know. And we try to account to the people who gave the video material or audio licenses.
04:21
And so, we could do it manually, but it's really a lot of data. It would be like many people and not effective because it's really a penny accounting business. And so, we also use systems like, for example, Elasticsearch.
04:41
And really, Elasticsearch, who knows Elasticsearch? Yeah, most of you. So, you know you can also get a probability back on the quality or the results you get. So, how you get some indicator, how Elasticsearch thinks, how accurate the result is. And so, we have something to work with. So, but we have also customized systems.
05:03
We can look directly at the database. We have some funny search stuff. I don't want to go too deep in this, but just like I was really stuck in a combination of, okay, I have all these expert systems I can ask. And probably one expert system will improve my input. And if I put it into the other expert system, I can even get better input.
05:24
And so, I was getting really confused. And so, I thought, what about game theory? Because I can't really use if, else, else, if, then, will, will, will, to really solve it. And so, I remembered game theory and gave it a try.
05:42
And so, let me introduce you a little bit more into game theory. And I hope it will help you to make decisions in your coding or whatever problems you're facing. Or like basically maybe just in your life or maybe even better in your life. So, game theory.
06:00
Very often if you see a picture about game theory, you will see chess. And yes, but it's actually a very bad example because is game theory about playing games? No. Again, you can leave if you thought this was a game talk. It's not about playing games. It's about interactions between humans, which we can also like prevent.
06:24
We can basically imagine it's also like a game. Like a simplified version of interactions. We can regard this as a game. And we know games like chess or Go or Tic Tac Toe. But they're deterministic.
06:41
Every player knows at every stage of the game everything. You see, you can see, if I'm white, I see everything. Basically, it would be like playing poker with all cards on the table all the time.
07:01
And basically, it's just like you can calculate all possible results. Of course, we don't because our brains are not capable and even computers are not capable of calculating all the results imaginable for each and every move in time.
07:22
So, it's imagining like game theory having all the cards on the table. If the information is not having all the cards on the table, some information might be hidden.
07:41
And is there a way to determine how you still can evaluate chances, build up a strategy? And basically, this is what I was doing. As an 8-year-old, I believed I will win chess against the partner of my mother if I just chose the right color in the beginning.
08:06
After I lost many, many games, I came to the conclusion that's not the case. It's very unlikely. But I think the average chess player is also trying to find a strategy and anticipating what the next moves of your opponent might be,
08:23
although you can basically calculate each and every possible result. You're anticipating what your player will do. You're anticipating his strategy and this is getting us a little bit closer to game theory. And game theory was not just like invented overnight.
08:43
Let's have a little glance into game theory history. It was like first mentioned, this goes back to the 1700s, war grave letters, guys from Britain. There's a French guy who wrote a paper leading in the direction.
09:05
And then in the beginning of the 20th century, things start to pick up with Ernst Zermulo. No, I can't read with you, I'm sorry. Ernst Zermulo, über die Anwendung der Mengelehre und die Theorie des Schachspieres,
09:21
which actually can translate about how applying set theory in chess games. Then in the late 1920s, the thing starts to really pick up with a paper from a Hungarian scientist, Jean von Neumann.
09:42
I think he moved to the U.S. later. And he wrote another paper, Zur Theorie des Gesellsarfspiele, which is about theory in board games. And this paper got noticed a lot. And in 1944, he published a book co-authored with Oskar Morgenstern, Theory of Games and Economic Behavior.
10:08
And so we see already the game theory thing is very close to economics. And usually we think economics and people caring about economics are just a soft business.
10:21
It's not like programming is much better. So we don't probably look into theories there. And the challenge is, can we build up a mathematical model? Can we basically analyze and calculate results of people's actions, the decisions the players might do?
10:41
And basically, that's probably the most famous thing in the 1950s. It's like the prisoner's dilemma, and John Nash came up with the Nash equilibrium. And yeah, it's very famous because John Nash's life was a beautiful mind movie, so he's very popular.
11:01
And by the way, this is a picture of John von Neumann, the Hungarian scientist. So, background, game theory is in economics, political science, and psychology. It's used as well in logic, computer science, biology, and poker.
11:21
It's a mathematical approach to real life simulations. There are situations that involve two or more decision makers. And each decision maker, you for example, has a number of different actions they might take. And the ultimate outcome does not just depend on your actions, it also depends on what the other people do.
11:47
So, you're forced to think and come up with a strategy. And this is, basically. So, let's start with a really simple game.
12:01
It's something easy and practical. It's called a zero-sum game, and the zero-sum game is the winner takes it all. And the other's game is the other's loss. And I'm really happy, so many people, and it's so crowded because I would like to play two finger mora. So, please partner with the one on your right.
12:23
Everybody picks the right partner. It doesn't work. Yeah, it doesn't work. Yeah, sorry, sorry, sorry, I thought you can go from lunch and have a nap. I'm sorry now, back to action. So, two finger mora is a very simple game. Pick a partner and you basically, you have two choices.
12:47
Show one finger or two finger. And you have to decide who is the even player and who's the odd player. And then, just like as rock and scissors, you play with your partner and you show your fingers at the same time.
13:04
And if the result is even, even player wins and the result is odd, odd player wins. So, you basically have 50-50 chance. So, and you have five minutes and I will be back once you have the results.
13:26
I did a simulation. Oh, you did a simulation. Okay. All right, guys.
13:45
Five minutes was a joke. We're enjoying this.
14:07
Okay, we continue now. It's good to hear you all have fun with... I didn't imagine this simple game would make you so lucky. Okay, but basically, what would be like a mathematical representation of what we were just like doing?
14:26
We call this like the strategic form and basically...
14:48
Yeah, that's like what we call the strategic form. And so, and this is also like the basis one can calculate on with like these matrices. So, zero-sum games, one winner, one loser.
15:04
It's very competitive. There's another nice way. It's called one-zero-sum games. It's more about synergy and everyone games. And for example, like doing the same game in a little bit different form. So, let's do a non-zero, same game, but please don't get as excited as...
15:26
I've only 15 minutes left and I have to get you to prisoner's dilemma. It's my goal. So, let's play a positive way of this thing. Let's do the same game, but a similar game.
15:42
So, if you show the same count of fingers, each of you gets two points. And if it differs, you only get one point. And this is basically about cooperation. You want to give it a try? No, I think everybody can imagine. So, you have the idea.
16:03
So, you can like interactions and this is like very simple interactions put into a matrix and we can work with that. There are games with perfect information. As I mentioned chess, goal, tic-tac-toe. So, everybody knows about everything and all the options and outcomes for the other players.
16:21
And there are games with incomplete information, basically life. So, yeah, that's like the two. And as next, just like the classic game theory thing is the prisoner's dilemma. So, what is the prisoner's dilemma?
16:41
The prisoner's dilemma, imagine they're like two criminals. They're already with the police. The police has caught them. And imagine having them in two rooms in the police headquarters and they're being interrogated.
17:03
And the dilemma is each of the two criminals does not know how the other criminal will decide. So, if you cooperate, I mean if you ever have seen one of the U.S. series,
17:24
they say if you cooperate we can make a deal with the DA and you will get free. So, the thing is if you cooperate, you might get free. You don't get any sentence. But what if your colleague, your criminal colleague, your co-operator, your conspirator, also is cooperating?
17:50
Because then both are cooperating and it's not all the criminals cooperating. They're just like saying, yes, we did it. We're so sorry. And everybody will get free.
18:00
Of course, they will both get a sentence, a reduced sentence on that. And the other outcome, of course, is just stay quiet. And probably the police won't be able to prove anything or probably only like a minor crime and then you might only end up with like a one-year sentence.
18:24
And this is the prisoner's dilemma. We have a nice couple. And now let's get it into our strategic form.
18:43
So, confess. They get minus five of your sentence each. Keep quiet. So, if the other one confesses, you're really screwed.
19:00
You go to jail for 20 years and you don't want that. And if you both keep quiet, we assume, yeah, okay, you will get some sentence but not to the full crime. You probably might only end up in prison for one year. And how can you actually decide?
19:20
Because there's a dominant strategy, what we call in game theory, it's a dominance. So, what's always the best outcome you should choose? Actually, confessing is because you either go to jail for one year or five years but never for 20 years. So, this is the best choice.
19:44
And also confessing is the only strong Nash equilibrium in the game. And the equilibrium is basically when there are no more games for no one in being in the games.
20:01
So, basically, nobody wants to take any action because he can no longer gain from it. And this is, of course, in this simple game, this is just like one round. But just like imagine there's more criminals involved, like a gang of five. And you have to think about, oh, what do the other four people decide on?
20:23
And it's a completely different game because probably there are a couple, they're very close and they never will give each other up. But if it's just like some random guys you met on the street and you form the gang to break in, you might tend to decide, oh, let's better confess because I don't trust those guys and also I don't want to be a part.
20:46
I can be a part from them but you don't want to be a part from your boyfriend for a time. So, this is where things can get complicated. And how can we calculate stuff like that?
21:01
We can use algebra, there's many approaches. Bayesian Nash equilibriums, we can do just like Monte Carlo simulations to get some results. And there's some material you can look into. There's a Python tool called Gambit.
21:23
You can just play around with and think. There's a really nice blog post from a biologist, Martin Jones. It's evolving strategies for an iterated prisoner's dilemma tournament. I think it's very descriptive with outcomes and everything. So, I had really a lot of fun reading it while doing research for this talk.
21:44
And there's also from Stanford on Coursera a game theory course from Matthew Jackson, which I think is really good. Very well taught stuff. And I hope I was able to give you a glance into game theory, a little bit different approach on thinking.
22:05
And yeah, I hope you had a good time. And if there's time left, we can play some more Two Finger Morale. Yeah, okay, yeah, thank you.
22:28
Questions? Yes. Hi. So, first, thank you very much for the talk. Can I ask you to go back to the slide where you have the matrix?
22:44
This? Yeah. So, here it's very clear. Can you speak up a little bit? I hardly can hear you. Okay, yeah. So, here I think it's very clear that the optimum for both, if the goal is that they both serve minimum sentences, is that they both keep quiet.
23:04
But you said that the Nash equilibrium is basically that if they both would confess. Yeah, basically that's the best strategy is to confess. Why? Because there's no better strategy not confessing. Well, the thing is you can calculate, like, probabilities.
23:23
I mean, I don't understand why you would prefer being in prison for five years instead of one. Sorry? I don't understand why you would prefer being in prison for five years instead of one. I mean, I know they have good food, but…
23:41
No, the thing is you don't know what the other one does. That's the problem. You don't know what your partner decides on. That's the whole trick of game. Thank you for the question. That's the key. You don't know what the other party does. And so you need to make a decision on basically what's the best move, but you don't know.
24:03
That's why. That's why this is the dominant strategy. It minimizes your loss. You will never go to prison for 20 years if you confess. So, like, the minimum or the maximum you can…
24:21
So, basically, if you would keep quiet, you would basically risk a very higher penalty. Yeah, basically, if you keep quiet, it's a higher bet. I mean, if you know, it's… So, first of all, side note, I think it's interesting how people standing up and being very loud kind of is the tragedy of the comments, so another game theory concept.
24:43
But my question really is, were you able to solve your data problems using game theory? I was. Yeah, I was able to improve it. Because, like, the thing is, when do I end? Like, putting, like, the information into the next system to improve it. So, basically, I didn't mention it in the talk because it was a little bit deeper.
25:04
You can also define a threshold. And if you know, like, the gain will be minimum. And I think, if I remember, it was, like, 5% or so. So, if you say, we think the information is 95% accurate. And after, like, also, like, a threshold of iterations, so it won't go on forever.
25:24
I mean, if you just have one letter, we might never… We will never get a real result. That's the two things. Yeah, you can do a threshold. Usually, you say, like, okay, percentage on probability or, like, iterations and then just, like, take the result as is.
25:42
It was very good for improving and interaction on multiple systems. We have a few more questions. We don't have much time, so try to be short. Okay, this is done. We have one question here. Have you used the Python axle rod?
26:02
No, no, I haven't used it. But I've seen it online during your research. Have you used it? It was developed by a friend of mine at Cardiff University. So, it's been very interesting in kind of raising interest in Python programmers in the… I just wondered if you had a strategy in the tournament.
26:21
No, actually, like, actually, I was quite surprised because I thought when I did research on… When I was trying to solve the problem, I was doing… I just thought, okay, Python game theory, I expected, like, at least 10 libraries and the result, there were hardly any. So, I was quite surprised because usually there's a Python library for everything in life.
26:44
So, yes, it'd be great if we could pick up on the, like, helping and building stuff like that and also, like, just, like, add game theory to our toolset of thinking when we're trying to solve problems. Because I know from, like, at least I feel being, like, programming a lot, you tend to think very deterministic.
27:08
Yeah, this is the truth, this is the end. Game theory opens up your mind to be a little bit more flexible, finding a practical solution. Yeah, so that's, yeah. Very well, we are out of time.
27:20
So, let's thank our speaker. Thank you.