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, ...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
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 $\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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)...
user avatar
  • 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
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible