# Tag Info

## Hot answers tagged game-theory

61

Nash's major contributions, as far as I know, are the following: His work on game theory. EDIT: This is viewed by many mathematicians as being more important to economics than mathematics. However, see the answer by Gil Kalai (someone else whose views should be taken much more seriously than mine). His famous work on the existence of smooth isometric ...

48

Nash's lesser known papers also contain some clever constructions. Here's an example: A path space and the Stiefel-Whitney classes. Proc. Nat. Acad. Sci. U.S.A. 41, 320–321 (1955) [MR71081] There, he provides a rather simple proof of the fact that Stiefel-Whitney classes of the tangent bundle $TM \to M$ of a smooth manifold $M$ do not depend on the ...

37

I think von Neumann dealt with the case $n=2$, and it was by no means obvious how to extend the concept of equilibrium for the general case and prove that it always exists. More precisely, $n$ players before Nash were reduced to the $n=2$ case by partioning the players into two groups in all possible ways. Once you regard several players as a single player, ...

37

A few years ago several classic Nintendo games (including Mario, Donkey Kong, and Legend of Zelda) were examined from a computational complexity point of view. They proved that generalized versions of these games are NP-hard, and in some cases PSPACE-hard. Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta, "Classic Nintendo games are (...

32

Concerning Deane Yang's 4th point, permit me to cite the earlier MathOverflow question, "$C^1$ isometric embedding of flat torus into $\mathbb{R}^3$," which displays (and links to1) some amazing images from the Hévéa2 project's illustration of the Nash-Kuiper $C^1$ embedding theorem applied to the flat torus:     1 Courtesy of Benoît ...

31

The board game Monopoly is often used to explain Markov Chains to laypeople. Ian Stewart has a couple of Mathematical Recreations articles about it in Scientific American. The first (in the April 1996 issue) has the title "How Fair is Monopoly?" (A copy it can be found here.) The second (in the October 1996 issue) has the title "Monopoly Revisited" (A ...

27

Why focus only on geometry? Nash investigated a lot of fields, in only thirteen (?) published papers. That on the isometric embedding contains a fixed point theorem that is now called the Nash-Moser iteration, which turns out to be extremely fruitful in many parts of analysis, especially in PDEs, when ordinary methods fail. More precisely, it is used when ...

27

Hex (https://en.wikipedia.org/wiki/Hex_(board_game)) is a board game that was developed by John Nash (and independently and earlier, Piet Hein). It is interesting mathematically in a number of ways. For example, unlike something like chess, it is easy to see that under optimal play the first player will win a game of Hex. But though it is known that the ...

24

My wife and I have a standing agreement where I pick up our son Horatio from school and she picks up our daughter Hypatia. One day, because I knew I would be near Hypatia's school, it was convenient to swap duties. I emailed her a message, "I'll pick up Hypatia today, and you get Horatio. Please confirm; otherwise it is as usual." She texted me back, "Let'...

23

This answer overlaps with other answers but I think another restatement may be helpful because the situation is slightly confusing. After the two-person zero-sum result, it is natural to ask about extending the results to $n>2$ and to non-zero-sum games. Sometimes it is stated that Nash was the first to carry out this extension, but this is slightly ...

23

Let me mention Nash's two famous contributions to game theory: The notion of equilibrium of non cooperative games and a proof that every game has an equilibrium. Nash's bargaining model, his proposed axioms that a solution should satisfy, and his solution. Links: (Nash's paper; a good wiki page (Hebrew)) Addition: Nash also independently invented in 1947 ...

22

The Essential John Nash (ed. Kuhn and Nasar) contains the full text of nine of Nash's papers along with some editorial introductions and an autobiographical essay by Nash.

22

I discussed this with Arvind Singh a while ago and I think we can show the non trivial inequality $p_{opt}\leqslant\frac{3}{8}$ with simple arguments. The proof relies on the symmetry of the problem and the intuition is that one can not find a strategy wich is good simultaneously for a configuration and its inverse. It will be simpler to work with the sets ...

20

This game can be described as an impartial edge colouring game on $K_n$ where creating a monochrome $K_k$ is not allowed, and the last player to make a move wins (normal play). Hence, it is equivalent to a nimber. I use the terms $P$-position and $N$-position sporadically to mean "a game state where the previous (resp. next) player has a winning strategy". I ...

20

This rewrites as $4f(a^2 +b^2)\le f(a^2) +f(b^2 )+2f(0)$ for a decreasing function $f(x)=\sqrt{x+1}-\sqrt{x}=1/(\sqrt{x+1}+\sqrt{x})$.

20

I like this question a lot. It provides an interesting way of talking about some of the ideas connected with the maximality principle and the modal logic of forcing. Let me make several observations. First, Alice can clearly win, in one move, with any forceably necessary statement $\sigma$, which is a statement for which $\newcommand\possible{\Diamond}\... 19 This is not an answer but is too long for a comment. The point is that the distance between any two zombies is non-increasing with time no matter what your strategy. Change the coordinate system so that you're at the origin at all times and assume that zombies move at speed$1$(the stupid, non-colluding kind of zombie). If your speed is zero then the ... 18 Here is a partial answer. I'll assume$m$and$n$are the number of intersections rather than the number of squares. If both values are even, then the second player can always win by rotating the first player's previous move by 180 degrees. If precisely one value is odd, then the first player can win by removing one row or column, making it even by even. ... 18 IMO one of the most important recent work related to the computational complexity of (puzzle) games is the Nondeterministic Constraint Logic model of computation developed by Robert A. Hearn and Erik D. Demaine: Robert A. Hearn and Erik D. Demaine, "Games, Puzzles, and Computation", 2009 The framework can be used to easily prove the complexity of the ... 17 Rubik's Cube puzzle https://www.youcandothecube.com/blog/puzzling-science-using-the-rubiks-cube-to-teach-problem-solving gives an excellent possibility for some musings in mathematics and physics. See, for example, https://www.sciencedirect.com/science/article/pii/0378437182903624 https://arxiv.org/abs/1106.5736 https://arxiv.org/abs/1706.06708 https://... 17 Winning Ways for your Mathematical Plays (Wikipedia link) by Berlekamp, Conway and Guy, 1982. This is a book discussing two-player full-information games. It is very good. While most of the games in the book are not in any way popular, some of them are. The Wikipedia article gives a partial list. The book builds on an earlier book On Numbers and Games (... 16 For even$n$, I claim that nobody has a winning strategy, and therefore both players have drawing strategies. To see this, observe first that by the fundamental theorem of finite games, we know that either one of the players has a winning strategy, or both players have drawing strategies. Next, I claim that Bob has a drawing strategy, which is simply to ... 16 Allow me to mention that since the players in effect adopt the roles of the quantifiers$\forall$and$\exists$, as Bob has a winning strategy just in case for every move for Alice, there is a reply by Bob, and so on, some logicians have preferred to use alternative names that would better highlight this connection. When I was a graduate student attending ... 15 Let$n$be odd. Inductively assume that$n-2$is a first player win. Suppose eating$3$is not a winning play for the first player. Then we should eat$1$first, of course. If the second player responds by eating$1$, we use the winning strategy for$n-2$. If the second player responds by eating$3$, then we use the second player's winning or drawing ... 14 Although this is not directly about Riemannian geometry, his paper Arc structure of Singularities (1995) certainly classifies as sufficiently geometrical. By all accounts, this paper was actually conceived some 30 years or more earlier. Ex post facto, the contents of that paper were way ahead of their time. In some twenty years, much has been written (and ... 14 There are numerous proofs of what I call the fundamental theorem of finite games. Theorem. (Fundamental theorem of finite games) In any finite two-player game of perfect information, one of the players has a winning strategy. Proof 1. Back-propagation through the game tree. Label the nodes with the player who has a winning strategy from that position. ... 14 Demaine et al. proved in this paper that Tetris is NP-hard. More of a gimmick but: Based on that paper, Szita & Lörincz tried to teach a number of algorithms to play Tetris in this paper. 14 First, Alice chooses minimal$n_a$divisible by 3 such that her bits at positions$n_a, n_a + 1, n_a + 2$are not all the same, and Bob similarly chooses$n_b$. Looking at triplet$A_{n_a}, A_{n_a + 1}, A_{n_a + 2}$. Alice chooses$m_a$according to following rule: {010: 2, 011: 2, 001: 1, 110: 0, 100: 0, 101: 1}. Bob chooses$m_b$in the same way. Now ... 13 Nash's paper "Real algebraic manifolds", Ann. of Math 56(1952), 405-421, started off quite a bit of work in real algebraic geometry, where Nash functions is a well-established term for$\mathcal{C}^\infty\$-semialgebraic functions.

Only top voted, non community-wiki answers of a minimum length are eligible