Hacker News new | past | comments | ask | show | jobs | submit login
Game Theory: Open Access textbook (arxiv.org)
271 points by hocaoglv on Dec 13, 2017 | hide | past | favorite | 54 comments



There are many sources to develop an understanding of game theory. To build mastery in game theory, check out Osborne and Rubinstein's text. The authors offer it as a free download (http://arielrubinstein.tau.ac.il/books.html).

This is the text used by advanced graduate students, the material is explained precisely.


It's a pretty intro level book, but a great one.

I'd say its suitable for maybe junior level undergraduates.


It's a shame that he released it under a no-deriv's CC license. The actual cost of textbooks is small compared to the penalty we all pay from not having our textbooks iteratively refined. http://blog.jessriedel.com/all-posts/2015/04/16/beyond-paper...


Has anyone here applied Game Theory to a real-world productionized problem? I'm curious.

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.


Most corporate strategy/competitive strategy problems use game theory on a daily basis. Market entry, retaliation, oligopoly, monopoly, etc. are good examples.

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.


Any chance of elaborating? I'm curious if GT is a 'real tool' (compared to, for example, SWOT analysis), or a high-level mindset?


The standard in antitrust law when evaluating a merger or acquisition is to write down a game theoretic model of competition, estimate the parameters of the model (consumers' tastes, degree of substitutability between products, etc.), and make projections of prices based on those parameters.


Interesting. Thanks and a fistbump for the username. :-)


More of a high-level mindset, since GT is more of an academic topic.

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.


It sounds like in your examples, ideas and conclusions from GT were used to inform practice (sort of like mental models), but GT models themselves were not explicitly deployed.

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.


> 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.


The signaling example is quite interesting. Thank you


In The Black Swan, Nassim Nicholas Taleb argues that applying game theory to real life situations is one instance of the ludic fallacy. https://en.wikipedia.org/wiki/Ludic_fallacy


Fair warning: N. Taleb is more or less an anti-intellectual. He hates on most formal models he didn't write himself and most of his books are musings on heuristics.


From what I understand, Game Theory is used in "mechanism design", or basically the design of auctions for things like the FCC spectrum auctions, or how facebook / google auction off ad slots.

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...


Just to add: A bit more about the type of auction design facebook was using at the time the article was written.

https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%9...


I don't think people actually use Vickrey auctions in practice (although it's likely to use some of the same ideas). Even though it has some really cool properties (you're theoretically perfectly incentivized to bid your real price), it has some weaknesses in real life "imperfect" auctions (as an example, weak to collaboration from what I remember).

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.


Yes algorithmic game theory is what I'm getting at. I wonder if you know of any talks about tech companies implementing game theory algorithms in production systems? You mentioned Facebook but they don't seem to have any talks at conferences on the topic. What other companies do you know that implement game theory algorithms?


The "novelty" behind "Generative Adversarial Networks" (GANs), a very popular deep learning network, is based on Game Theory. It's a "game" between a Generator and a Discriminator networks where one try to fool the other. The Generator tries to fool the Discriminator by producing output the Discriminator can't distinguish between fake or real.

You can find real-word applications for GANs (specially the Pix2Pix variety) in a lot of domains.


Not myself (well one of the below applied to me at a brief point in my career), but here are cases I know of.

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.


Thanks, this is a good list. It sounds like there aren't a whole of cases where game theory is explicitly implemented in code, but there are some.

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".


I know it's being used to decide where to place random controls in LA airport, day to day. If the controls were in the same locations, the bad guys would just avoid them, but you don't want the completely random either because some areas have higher throughput, or something like that. Lookup Milind Tambe for more details. They also augmented the technology with psychology considerations. Check if there is a video of a presentation from Tambe on the subject: it's fascinating!


I’m an applied mathematician that eventually became a macroeconomist by way of game theory.

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...


I wasn't too clear in my verbiage, but I guess by "applied" I mean actual game-theoretic computations (what is known as algorithmic game theory) being implemented in code, as opposed to a broad allusions to canonical problems like the Prisoner's Dilemma.

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?


Yes, it is really used explicitly by algorithms employed by HFT funds, any system that explicitly or implicitly works with or through auctions, and by cellphone tower management systems. One could also argue that the Byzantine Generals Problem’s solution (the much vaunted blockchain of cryptocurrency lore) is game-theoretic in nature so the whole bitcoin & cetera crowd/craze (spending on your perspectives on the matter) could be considered to be founded upon the application of Game Theory of the algorithmic (computable) variety.


It's more useful to those designing the game than to those playing it. Auction sites, financial regulators, traffic planners...


Here's one that I found interesting - the Dutch school placement lottery: https://medium.com/social-choice/why-a-dutch-court-stopped-h...


Perhaps there are real world scenarios not totally unlike those from game theory. You can imagine situations like the prisoners' dilemma, where maximizing each individual's expected benefit from taking some action is suboptimal due to no means to cooperate.


Define "applied." Researchers in economics and political science use it to understand all kinds of things, does that account? The Rand Corporation probably had an influence on real-world military policy during the cold war with it...


>> but I've never seen an application of it in real life.

Here is one: you and a friend get arrested and are questioned separately, with police trying to turn you.

</sarcasm>


When big corps buy small startup just to kill it off because it might eat into their cake or because their competitor might buy them, that's game theory.


You've described a situation. A situation itself is not a game theory. A situation might lend itself to being modelled using techniques from game theory, but you've not pointed at why.

Someone could equally say the situation you described is 'strategy' or 'design' or 'product management' and it would be equally enlightening.


I'm looking to learn Game Theory. Anyone with knowledge in this space have good additional recommendations?


Thinking Strategically by Avinash Dixit and Barry Nalebuff is a fantastic way to start. You can pick it up without any prior knowledge of game theory.

I'd also recommend Ken Binmore's Game Theory: A Very Short Introduction.


This youtube channel has proven invaluable to me: https://www.youtube.com/user/JimBobJenkins

His book is also great (http://gametheory101.com/textbooks/), but mostly a reiteration of the videos.


The last two lectures in the The Georgia Tech Machine Learning course on Udacity cover some basics of Game Theory. Just skip ahead, the game theory part is mostly self-contained. https://www.udacity.com/course/machine-learning--ud262 The Reinforcement Learning course includes some of the same (exactly the same) game theory content and then adds an additional lecture on further topics in game theory https://www.udacity.com/course/reinforcement-learning--ud600 Again, skip to the last couple lectures.


Kreps, Game Theory and Economic Modeling has a nice overview and contextualization as I recall. I also really like Brian Skyrm's little books (Evolution of the Social Contract and Stag Hunt) for an introduction to the evolutionary side.

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.


I'm currently a TA in a basic game theory for MSc students at a technical university. For the basic theoretical concepts we use as a course book Leyton-Brown & Shoham (2008) Essentials of Game Theory: A Concise, Multidisciplinary Introduction. This book is great because it is short and to the point, precise without diving deep into everything. Introduces most important concepts in less than 100 pages.


The original: Theory of Games and Economic Behavior, published in 1944 by Princeton University Press, by John von Neumann and Oskar Morgenstern the text that created the interdisciplinary research field of game theory, is still worth reading.


I really enjoyed Gintis's 'Game Theory Evolving', which focuses on evolutionary game theory. Mind you, I was a biologist when I was working with it, so that was much more relevant to what I was thinking about.


I learned Game Theory from this Open Yale course:

https://www.youtube.com/playlist?list=PL6EF60E1027E1A10B

24 excellent lectures by Ben Polak.


MIRI recommends Game Theory: An Introduction by Steven Tadelis

https://intelligence.org/research-guide/


I'm building some games for this topic for my startup [1]. But we won't have them ready until the spring.

[1] http://www.simcase.io


I hope you'll post something here when you launch. I like the ideas presented on the site but they are a bit vague right now.


I had a professor once classify GT as a sub set of statistical decision theory. Might be worth picking up a SDT text.

Does anyone ever read Theory of Games by von Neumann?


This is backwards. Decision theory, which is the foundation of inference in statistics today (Bayesian, minimax, etc. are all special cases of it) is formulated as a one player game. Certain things mesh nicely when you realize this. For example, we know that there is a Nash equilibrium for large classes of games if we allow random strategies. Likewise, for decision theory with nonconvex loss functions, optimal procedures are almost always random.

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.


"Decision theory is 1-player game theory" -- I think I saw this on LessWrong, once, but I can't find it now.


Theory of games is VERY old, predating most other groundbreaking work (Nash, Shapley, Myerson, etc.)


Look up game theory lectures on coursera


Looks like there are more format options here: https://archive.org/details/1512.06808v1


Aside: I misinterpreted the title as saying "applying game theory to OER textbooks" and imagined a paper discussing the incentives/payouts for creators of educational content like textbooks.

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)
I'm fascinated by the interplay between the for-money publishing business and the idea of open source content, and would really love to see a paper studying this subject. Some concrete questions: 1. If an author is interested in maximizing total payout, should she write for a mainstream publisher or self-publish? 2. If an author is interested in most educational impact (maximize the number of readers), should she pursue a one of the commercial routes (publish or self-publish) or release the book as public domain?

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?


I use Game Theory in pretty much everything (academic) Here are some thoughts on the literature.

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


Explanation of Part V in the introduction is interesting and might be a property which sets this book apart from the fold.


Anyone know of any sources for game theory applications to ethics?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: