Live data from Hacker News

Game Theory: Open Access textbook

arxiv.org

51–57 of 57 posts

Re: Game Theory: Open Access textbook

#51

Earlier quoted context omitted.

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

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…

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.

Re: Game Theory: Open Access textbook

#52
post #35

Earlier quoted context omitted.

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 o…

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?

Re: Game Theory: Open Access textbook

#53
post #45
post #13

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.

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…

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

Re: Game Theory: Open Access textbook

#54
post #50
post #49

Earlier quoted context omitted.

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 c…

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.

Re: Game Theory: Open Access textbook

#55
post #51

Earlier quoted context omitted.

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…

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 th…

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

Re: Game Theory: Open Access textbook

#56
post #13

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.

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

Re: Game Theory: Open Access textbook

#57
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

Post reply on HN