# Questions tagged [nash-equilibrium]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
77 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
1 vote
61 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
973 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 ...
• 5,983
68 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
194 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,131
143 views

### Understanding Prisoner's dilemma [closed]

Imagine two prisoners held in separate cells, interrogated simultaneously, and offered deals (lighter jail sentences) for betraying their fellow criminal. They can "cooperate" (with the other prisoner)...
• 95
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