Skip to main content

Questions tagged [nash-equilibrium]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
39 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. ...
0 votes
1 answer
90 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 ...
1 vote
1 answer
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 ...
21 votes
2 answers
1k views

PPAD and Quantum

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 ...
3 votes
1 answer
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 ...
2 votes
0 answers
200 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 ...
-4 votes
1 answer
158 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)...
0 votes
1 answer
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 ...
3 votes
1 answer
855 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 ...