Game Theory: Open Access textbook(arxiv.org) |
Game Theory: Open Access textbook(arxiv.org) |
This is the text used by advanced graduate students, the material is explained precisely.
I'd say its suitable for maybe junior level undergraduates.
There are many hypothetical situations where game theory is said to be useful, but I've never seen an application of it in real life.
Game theory-heavy industries are the ones in a competitive balance. Think Coke/Pepsi, telecom, etc.
Another way game theory helps is in building the right mindset: you assume that your opponent is just as rational and smart as you, and will be trying to predict how you will react just as you're doing with him/her.
This helps to avoid the failures that result from underestimating your competitors ("we're smarter than them" or "we're better than them").
Disclaimer: I work in strategy.
Not a mathematician so I don't have any great references, but a couple bits in the press about it:
http://blogs.cornell.edu/info2040/2015/10/20/application-of-...
https://www.wired.com/2015/09/facebook-doesnt-make-much-mone...
https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%9...
You can find real-word applications for GANs (specially the Pix2Pix variety) in a lot of domains.
Google, Facebook, and many others use mechanism design (which roughly counts as game theory) to design ad auctions which automatically run as users run searches and load pages. That must be the biggest application of game theory in running code. Auctions are popular applications of game theory in other places, particularly the FCC spectrum auction which involves running code.
Game theory, of a kind, underlies "match" code that assigns medical residents to hospitals, and students to highschools in some school districts in the USA.
Game theory has actually been used to design security schedules for 'national security' in places like airports and the Coast Guard -- this research was led by an effort at USC.
Game theory is used in the design of prediction markets, which are often deployed within companies (though probably they don't need to do additional theory to deploy the markets to their application).
There is a lot of crowdsourcing at scale going on in semi-automated systems, and a lot of research on game theory in crowdsourcing, but I don't know how much that research gets implemented.
If Uber and Lyft aren't using a bit of game theory to set prices, and hopefully also think about incentives when assigning routes, then they're crazy. But perhaps they're using more "economics" than game theory.
Game theory has been used to study social voting sites and "contests" like reddit, hackernews, stackoverflow, quora. However, I don't know if any of the designers of these sites are explicitly using game theory.
The reason I'm interested in explicit implementations in code as opposed to theoretical narratives is because actual implementations have to deal with the not-so-nice cases in the real world, i.e. unaccounted-for interactions, stochasticity, flat-out incorrect conclusions, etc. (there are however some deterministic problem domains where the above aren't issues, and I'm curious to learn what these are). Every model is a simplification, but game theory models usually have less correspondence to reality than most hence my curiosity. Game Theory is often thought of to have broader applicability than it really has (due to hype). My interest is identifying those domains where game theory actually "works".
The answer to your question depends very sensibly on what you mean by the terms you use. Certainly various kind of game theoretic solutions to problems are used daily everywhere, from auctions on eBay, to what kind of policies to adopt in government, to how HFT hedge funds choose their positions, to what captains of industry choose to do in their boardrooms.
Since this is a technical environment, I’ll suggest you take a look at Game Theory for Wireless Engineers which applies Game Theory to the environment of self-interested nodes competing to get the best signal they can on a network that is a commons.
http://www.morganclaypool.com/doi/abs/10.2200/S00014ED1V01Y2...
Game Theory for Wireless Engineers is interesting, and I wonder if this is actually being applied in industry, or if it is in the realm of potential application?
Here is one: you and a friend get arrested and are questioned separately, with police trying to turn you.
</sarcasm>
Someone could equally say the situation you described is 'strategy' or 'design' or 'product management' and it would be equally enlightening.
Some possible moves:
- Write for a mainstream publisher (payout: ~5% royalties, reach: medium)
- Self publish commercially (payout: 45%+ royalties from createspace/lulu, reach: small)
- Release for free as OER under public domain / CC0 (no payout, reach: broad)
The answer to 2. is not obvious: some of the best textbooks I know are free (GFDL, CC *, or public domain because old), but somehow they don't get the respect they deserve because people have the perception of "free" as being somehow inferior quality. People think, if the book really was any good, surely you'd have to pay for it?
Even more interesting is to consider the game theoretic aspects of multiple authors/contributors. Why are software projects on githun with hundreds of collaborators the norm, but textbooks project limited to one or few main authors?
There are several different strands and evolutions of Game Theory.
1. Game Theory (non-cooperative):
The basis was Neumann/Morgenstern Theory of Games. It has been suggested in this thread, however its focus is a bit obscure today. Still useful for repeated games, for example. Both authors are also important for Decision Theory, see below. Afterwards came Nash, defining the what the basic solution concept would be up until maybe 1990. Simple Nash equilibria are used primarily where rational agents choose in mathematically nice spaces where uncertainty is not a major factor.
Following Nash, the Game Theory literature developed to produce equilibrium refinements. These, usually subsets of Nash equilibria, were created because Nash often predicts very little - the space of equilibria is often so large that nothing can be learned, or uncertainty requires the incorporation of different information sets of agents. The first developments came while incorporating uncertainty and multi-stage games (where people move in sequence). Harsanyi was able to show that most configurations of uncertainty situations can be represented as a Bayesian Game (the issue was the recursion of "he knows, that I know, that he knows that I know..."). The problem became, that these often produced unintuitive and large sets of equilibria. So we have refinements. Some target robustness, like Selten's Trembling Hand. Others target "natural behavior", empty threats and so on. Almost all of those refinements are a subset of a Nash concept. The development of refinements was en vogue prior to the 90's, when it stopped for reasons I will detail below. Basic Nash has survived, however, and is still the go-to tool to understand multi-agent decision problems (at least initially).
1.a Cooperative Game Theory:
Largely in parallel, mathematicians like Shapely and later economists like Roth also tried to think about cooperative games. Here, we don't look directly at what individual people do in isolation, but rather what groups are stable and plausible and what they can achieve. If for example a smaller group can "break" a coalition, then such a large coalition can not be considered a plausible solution. Matching theory comes from here, for example, so you will find it in most problems of assignment (say, students). Much as non-cooperative Game Theory, it is applied widely.
2. Decision Theory:
Decision theory developed in parallel and is a wide field. It is, however, critically important to Game Theory because it sets the stage for information, constraints and decisions that agents take. Expected utility, by Neumann and Morgenstern, was and is the basic instrument to understand how agents incorporate their knowledge. This was based on objective probabilities, so in parallel the Bayesian stream also developed. With a monumental and beautiful proof, Savage then developed Bayesian Decision Theory (based on works by de Finetti and others). This is critical to many, many fields in maths, statistics and science in general, and was then the basis for Game Theory. Aumann is associated with latter refinements of decision theory. Later on, the idea of uncertainty (Knightean uncertainy) became important. This is when you can not assign a probability to an outcome. Paradoxes by Elsberg and Allais have shown that this is actually an important decision problem in real life. Multiple approaches exist to generalize Decision Theory, such as Prospect Theory, MinMax Preferences, integration by capacities as opposed to measures. Schmeidler, Gilboa and Wakker are some names. Game Theory exists in this space as well.
3. Evolutionary Game Theory:
The idea came from Biology and is important because it is a way to justify Game Theoretic outcomes without even requiring purposeful action by agents. It had a huge impact on many problems, especially dynamic ones and "top down" models, but did not surplant traditional Nash in general. Some scientists believe it should. Other's think it's just one more tool. There are those who believe the whole of social sciences should be based on it... Let's say it did not achieve that yet.
4. Economic applications:
Economics was historically the discipline to apply Game Theory most. Initial concepts like Nash justified many early models of Markets. Earlier concepts of non-perfect competition were formalized with Game Theory. Things really started to take off when asymmetric information were introduced. Think Moral Hazard, Signaling Games, Contract Theory and so forth. What we know about economics, organizations, business, competition and many social phenomena today has largely been developed by applying Game Theory. There are too many great names to mention: Akerlof, Tirole, Spence, Hart, Homström, Myerson, Stiglitz.
5. Mechanism Design and Auction Theory
In the 70's and 80's, from the above applications, economists like Hurwitz, Myerson and Maskin developed mechanism design. The idea is simple and genius: If agents play games, what if we can choose the game they play? Which game do we choose without them walking away, but with us getting the desireable outcome? What is, in other words, the optimal mechanism inducing the agents to play a game? Initial examples and todays shining example of econ in action is Auction design. Which sort of auction mechanism is best to sell ads, be ebay or assign broadband licences? Mechanism design leads to very complex problems, which is why until the early 90's many simplified assumptions were used. While mechanism design has been very useful, this also lead to two developments. In econ, papers started to get more and more complex to accomodate real life issues like non-monetary transfers, dynamics, complex type sets and so forth. Computer scientists trying to implement mechanisms quickly discovered that many were simply to complex, so they started Algorithmic MD.
6. Experimental and behavioral games:
So earlier, I said that a whole cataloque of equilibrium refinement basically died out. Why is that? Well, with behavioral econ we were introduced to more realistic approaches to decisionmaking. Then questions arose, such as "what if I can not count on rationality of my competitor". As it turns out, this may actually break the inference of Nash equilibria pretty handily.
At the same time, economists and psychologists put people in experiments to play games. In some situations, Nash worked well. In other situations, one could accomodate much by using more complex Decision Theory. But in many instances, people would just not play Nash. In other words, they couldn't even figure out the most basic solution concept. Indeed one can do all sorts of experiments in a Game Theory 101 class showing that people often choose much too heuristically. Equilibrium refinements make Nash more complex, it was clear they had to be abandoned. Currently, research joint in decision theory and game theory works on finding better ways to model behavior when Nash is not reached.
Books:
Osborne/Rubinstein has been mentioned. Contrary to what was said, this is an undergrad book and a solid intro. There are two classic works. The major one is by Tirole and Fudenberg, the other is by Myerson. The former is more standard, the latter is better. Now there is a new book by Maschler, Solan and Zamir with like 900 pages. It's really good, and I would definitly get it as a second book after an intro.
For Mechanism Design, the best book is by Tilman Boergers. It's also free to download. Auction Theory specifically has a standard volume by Krishna. Both of those are math heavy. This is true in general, but Game Theory concepts can often be explained by intuition. For Mechanism Design, I fear that a solid math background would be required, because the space of "choosing a game" is mathematically not so nice. However solid means you should have a good grounding in analysis and optimization, perhaps dynamic systems. Basically, a math heavy undergrad education will be fine.
hope this helps
I'd also recommend Ken Binmore's Game Theory: A Very Short Introduction.
His book is also great (http://gametheory101.com/textbooks/), but mostly a reiteration of the videos.
Note, those aren't textbooks. They're applied/context works with introductions, and I think they're better for developing intuition before getting into a textbook.
For a really accessible textbook that (as I recall) isn't as math-heavy as some others, Morrow, Game Theory for Political Scientists.
https://www.youtube.com/playlist?list=PL6EF60E1027E1A10B
24 excellent lectures by Ben Polak.
Does anyone ever read Theory of Games by von Neumann?
But: game theory of two or more players is qualitatively different. For a one player game, we speak of optimal strategies. For multiplayer, noncooperative games, Nash equilibria take what would seem to be the obvious generalization of that and twist it in a whole new direction.
But seriously, auctions in general (ad auctions yes, but also many other "kinds" of marketplaces, like zillow for ex) are a super huge application of algorithmic game theory. I took a course in Algorithmic Game Theory with Eva Tardos, and she was constantly being asked by companies like Facebook for consulting on their auctions. Google also has a whole team of algorithmic game theory type people for their ads too.
Facebook actually has a meeting room named after her.
A lot of the effects described in GT can be learned by practice and observation of human competitive behavior, but studying it gives you a much better understanding of why certain situations happen, or how competitors will react.
The market entry game (retaliate/accommodate) is usually the best example:
https://books.google.com/books?id=xhAACwAAQBAJ&pg=PA77&lpg=P...
Another example is signaling: when you publicly declare that you will match prices aggressively and will never be undercut, that's not actually a threat to your competitors, but a signal that if they keep prices high, you will as well, avoiding a price war.
Game Theory is first and foremost a quantitative, mathematical theory, and I was wondering in what situations one would actually use the mathematics in production systems or in a mathematical analysis. There are a few replies on this thread that alluded to some applications.
I never worked directly with this, but auctions, resource allocation, etc. all use the mathematical tools from Game Theory.
Corporate strategy is too complex and nuanced to build hard mathematical models, so you need higher-level abstractions.