# Questions tagged [nash-equilibrium]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
1k views

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
• 6,063
71 views

### Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game?

It is well-known that in a $2$-player zero sum game if one player plays a regret minimizing mixed strategy, and the other player best-responds at each round to that mixed strategy, we are guaranteed ...
• 59
861 views

### Is there a tool for finding Nash equilibria in parametric games?

There are a few tools, either online or offline, that could solve (find equilibrium) in a game explicitly given as a real-valued matrix. Such tools are Game Theory Explorer and Gambit. However, as ...
• 9,458
201 views

### Two-player zero-sum games in extensive form represented as directed acyclic graphs

The following is a way to represent two-player zero-sum games in extensive form. Consider a directed acyclic graph $G$ where each non-terminal vertex is one of 3 types: player 1 vertex, player 2 ...
• 2,151
1 vote
66 views

### How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

Consider a bimatrix game problem with matrix $A$ and $B$. The definition of the value $v = [v_1, v_2]$ of the Nash equilibrium $(x, y)$ are as follows, $$v_1 = x^TAy,$$ $$v_2 = x^TBy.$$ The situation ...
• 141
1 vote
41 views

### Encoding of continuous functions in PPAD

I'm studying the complexity class PPAD (from the seminal 1994 work by Papadimitriou) which contains complete problems such as computing Nash equilibria or finding the fixed point of a Brouwer map. ...
• 111
92 views

### Is there a fundamental link between Nash's equilibrium and Turing's halting problem?

Since Nash equilibrium exists, is there a computational analogue of this equilibrium point? I am trying to approach Nash equilibrium from computational point of view to see if the equilibrium point ...
• 109
80 views

### Seeking for a game for modelling a problem using game thoery [closed]

I have a problem which I want to formulate it as a game, using game theory. In this problem there is several agents, we can consider the agents as the employees of different offices, these agents have ...
• 1