37
votes
Accepted
Is this variation of TQBF still PSPACE-complete?
It is an Unordered Constraint Satisfaction game and it is PSPACE-complete and it has been proved to be PSPACE-complete only recently;
a proof can be found in:
Lauri Ahlroth and Pekka Orponen, ...
- 22.3k
30
votes
Is this variation of TQBF still PSPACE-complete?
It may also be worthwhile to note that this problem was also solved in the 70's by Thomas Schaefer in Complexity of decision problems based on finite two-person perfect-information games. In fact, ...
- 541
12
votes
Is this variation of TQBF still PSPACE-complete?
We proved that this game is PSPACE-complete for 5-CNFs but has Linear Time algorithm for 2-CNFs. The previous best result was Ahlroth and Orponen's 6-CNFs.
You can find the conference paper at ISAAC ...
11
votes
Accepted
What is the application of combinatorial game theory
I think Kaveh's comment is the correct answer: applications? We don't need no applications.
But despite all that, combinatorial game theory does appear to have some applications in error correcting ...
- 50.2k
11
votes
Accepted
Equilibrium in a Halting Game
Even if you have a one-player game there is no computable equilibrium. Consider nature putting probability $1/2^i$ on program $i$. Any computable strategy will achieve some value strictly less than ...
- 8,546
8
votes
Accepted
Secretary hiring game
For company $A$/the firm/giant corporation/"big pharma"/"THE MAN", the strategy does not change from the symmetric version:
Consider a round where the probability of seeing only lesser candidates ...
- 1,099
8
votes
Implementation of surreal numbers for games
I don't have an answer to your question of whether the theory of Conway games has been used in building game-playing programs, but still you might be interested in the Combinatorial Game Suite, "an ...
- 4,309
8
votes
Evidence that PPAD is hard?
(I guess no one ever answered this older question with the newer results; here you go:)
Assuming the existence of quasipolynomially-hard indistinguishability obfuscation and subexponentially-hard one-...
- 5,963
8
votes
Applications of Game theory in computer science?
Another famous example of using game theory is in CS is synthesis: in synthesis we get a specification over inputs I and outputs O (e.g. in temporal logic, or as an automaton), and we want to ...
- 5,261
8
votes
Accepted
For which families of graphs is Generalized Geography in $P$?
Generalized Geography (GG) is PSPACE-complete even on planar directed bipartite graphs,
but, as reported in:
Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume ...
- 22.3k
7
votes
Applications of Game theory in computer science?
Combinatorial game theory plays a role in logic and computer science as in, for example, the Ehrenfeucht-fraïssé game, which is a logic game played on model-theoretic structures. At each turn, the ...
- 1,122
7
votes
Accepted
Is this game EXPSPACE-complete?
I don't have an exact characterization but it's unlikely this problem is EXPSPACE-complete. Suppose $M^{\Sigma^*}(x)$ accepts and let $S$ be the polynomial-size set of strings queries by this machine. ...
- 8,546
7
votes
Accepted
The theoretical complexity of Go - The state of the art
The state of the art for the theoretical complexity of go is well summed up on Wikipedia, with relevant references.
The main remaining open problem is for rules using a superko, i.e. repeating any ...
- 7,653
6
votes
Accepted
Can generalized twenty questions be solved by a greedy algorithm?
No. There's a huge literature on the topic, called combinatorial search theory, you can read more about these types of questions there.
The simplest example that I could think of is the following.
...
- 13.5k
6
votes
Can generalized twenty questions be solved by a greedy algorithm?
Your question is not very different from set cover (it would be exactly set cover if you stopped as soon as you found a set containing $x$ rather than keeping going until you have determined $x$) and ...
- 50.2k
6
votes
Accepted
Trying to understand the intuition behind Yao's Minimax Principle
$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$Let $ {\mathcal I } $ be the collection of possible inputs, endowed with a $\...
- 421
5
votes
Accepted
Why is computing pure Nash equilibria NP-complete?
These are my two comments as an answer:
Of course you are right that if the strategic form (also called the normal form) is given explicitly then one can just check all pure strategy profiles. In ...
- 1,713
5
votes
Accepted
How to prove the existence of a pure Nash equilibrium?
If p=q=s=t=−1, then it is easy to see that a pure NE can be reached by local search starting from (a3, a3). So in the rest of the proof, assume that at least one of p, q, s, and t is equal to 1.
If ...
- 16.2k
5
votes
Accepted
Iterated Prisoner's Dilemma Algorithms
There is no algorithm that always beats all others in an IPD tournament. Proof: if your algorithm cooperates in round 1, then it gets last place in a tournament where all other bots always defect; if ...
- 2,293
5
votes
Accepted
What is the complexity of this game?
This should be EXPSPACE-complete. I'll sketch how to achieve an exponential number of alternations, without reducing any EXPSPACE-complete problem to this one, but from here it should be simple to ...
- 13.5k
4
votes
Accepted
Stackelberg solution to $n$-player Hotelling's game on a segment
This game has been studied in
Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, René van Oostrum:
"Competitive facility location: the Voronoi game"
Theoretical Computer Science 310, ...
- 5,712
4
votes
Accepted
Is there a tool for finding Nash equilibria in parametric games?
Is there a tool which solves parametric games?
Not that I am aware of (I am a co-author of GTE and help with Gambit).
The best suggestion I have if you don't find such a tool (and I doubt one exists)...
- 1,713
3
votes
What is the application of combinatorial game theory
I was able to find an application of combinatorial game theory in cryptography. See the link here
- 163
3
votes
Implementation of surreal numbers for games
on some search there do not seem to be much published general implementations of surreal numbers. heres an implementation of surreal numbers in coq.
Surreal numbers in coq / Mamane, TYPES'04 ...
- 10.8k
3
votes
Accepted
From CHSH inequality to CHSH game
I think your history is entirely right. Computer scientists are used to thinking about protocols as games, while physicists are not, and this is probably why these results weren't formulated as games ...
- 23.5k
3
votes
Applications of Game theory in computer science?
The article in Distributed Computing Column 42 attempts to bring a game-theoretic perspective to distributed computing problems.
Distributed Computing Meets Game Theory: Combining Insights From Two ...
- 2,319
3
votes
For which families of graphs is Generalized Geography in $P$?
The problem is PSPACE-complete even on digraphs of directed tree width $1$. Just consider a PSPACE-Hardness construction provided in wiki. If we delete a vertex $c$ from a graph, remaining graph is ...
- 3,420
3
votes
Accepted
Minmax vs Maxmin
First of all, there is a lot of information in this related question: Max Min of function less than Min max of function.
That said, the source of your problem is a confusion about which choices are ...
- 2,470
3
votes
Accepted
Winning strategy in the game of triplets
This isn't a complete proof, but here's some justification for why known conjectures imply that the game may be computationally hard to solve. Namely, I'm going to argue that finding the correct first ...
- 1,624
3
votes
Can theoretical computer science be combined with mechanism and information design and applications in financial markets
This depends on whether the CS department you are studying at has somebody working in this field. Some of them (at least three of the top ten in the U.S.) do, and some of them don't, and some of them ...
- 23.5k
Only top scored, non community-wiki answers of a minimum length are eligible