All Questions
2 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 ...
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