All Questions
Tagged with gt.game-theory cc.complexity-theory
22 questions
2
votes
0
answers
37
views
Complexity of deciding whether a given payoff vector can be achieved by some mixed strategy profile in a normal form game
Note that this mixed strategy profile does not need to be a Nash equilibrium. I'm mostly looking for references, as I assume the answer is known, but my searches have only found results about Nash ...
0
votes
0
answers
70
views
Undecidability of games with limited hidden state
Surprisingly, approximate win probability for one-player games with randomness and 3 bits of hidden state (in addition to non-hidden state; rational transition probabilities) is uncomputable.
Question:...
- 2,742
3
votes
1
answer
249
views
Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?
I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc.
For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games:
It is ...
- 33
0
votes
1
answer
233
views
What Complexity Class is this? Is this already known?
Let's call this the Path Game.
For this example, lets imagine a 16x16 grid:
Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We ...
- 21
11
votes
0
answers
206
views
Is 4-in-a-row PSPACE-complete?
This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this ...
- 682
13
votes
3
answers
1k
views
A game on several graphs
Consider the following game on a directed weighted graph $G$ with a chip at some node.
All nodes of $G$ are marked by A or B.
There are two players Alice and Bob. The goal of Alice (Bob) is to ...
- 2,023
10
votes
1
answer
516
views
What is the complexity of this game?
This is a generalization of my previous question.
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after ...
- 2,023
10
votes
1
answer
420
views
Is this game EXPSPACE-complete?
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after a game that will be described below. Let $x$ be ...
- 2,023
1
vote
0
answers
52
views
Circuit games in extensive form with imperfect information
Consider $l,m,n,N \in \mathbb{N}$ and circuits $C: \{0,1\}^{l+m} \rightarrow \{0,1\}^l$, $D: \{0,1\}^{l+n} \rightarrow \{0,1\}^l$. Consider the following zero-sum two-layer extensive-form game with ...
- 2,181
2
votes
0
answers
216
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,181
16
votes
0
answers
546
views
Quantum Hardness of Finding Nash Equilibria
This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen.
Their main result is that the existence of ...
- 6,051
32
votes
3
answers
2k
views
Is this variation of TQBF still PSPACE-complete?
Deciding if a quantified boolean formula such as
$\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$
always evaluates to true is a classical PSPACE-complete ...
- 752
7
votes
1
answer
1k
views
Why is computing pure Nash equilibria NP-complete?
In this paper, it is claimed that computing pure-strategy Nash equilibria of games in standard normal form is NP-complete.
This confuses me, because I do not understand why it is hard to guess the ...
user1338
3
votes
1
answer
493
views
How do you compute the fixed point of a best-response function efficiently?
I have a polynomial time best-response function that has the same properties as a game-theory game (convexity, compactness, set-valued). I don't know that much topology, but my understanding is that ...
user1338
4
votes
0
answers
108
views
Games where $\omega(G) < \omega^*(G) < \omega^{ns}(G) < 1$?
A two player game $G = (I,O,V,p)$ is such that, if two non-communicating players Alice and Bob are given questions $(x,y)\in I^2$ drawn from the probability distribution $p$, they are supposed to ...
- 3,888
12
votes
2
answers
488
views
How hard is it to count the number of local optima for a problem in PLS?
For a polynomial local search problem, we know that at least one solution (local optimum) must exist. However, many more solutions could exist, how hard is it to count the number of solutions for a ...
- 10.3k
12
votes
2
answers
475
views
Complexity of finite-state partial information games
Given a deterministic partial-information zero-sum game with only finitely many states,
whose possible outcomes are [lose,draw,win] with values [-1,0,+1] respectively,
what is the complexity ...
user6973
19
votes
2
answers
2k
views
How hard is Mafia?
Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29.
Basically, it works as follows:
At the beginning, ...
- 291
0
votes
2
answers
726
views
What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD
I have been thinking about Pspace in conjunction with searching for a Natural Notion of Stablilty for Complex Dynamical Systems.
A natural question in this direction is the Nash equilibrium. ...
- 1,598
9
votes
1
answer
463
views
What is the Complexity Classification of Portfolio Theory in Financial Economics?
As you will all know, there is ongoing fall out from the Financial Crisis of 2008. I was thinking about how complexity theory fitted into all this, when I realised I did not know the basic complexity ...
- 1,598
31
votes
1
answer
2k
views
Refereed games with uncorrelated semi-private coins
I was (and still am) really interested in the answer to this question, because this is an interesting variation on the complexity of games which hasn't been resolved, so I offered a bounty. I thought ...
34
votes
5
answers
3k
views
Evidence that PPAD is hard?
There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "...
- 9,910