Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
13 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 ...
Lutfar Rahman Milu's 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 ...
Lance Fortnow's 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-...
Daniel Apon's user avatar
  • 6,001
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. ...
Lance Fortnow's 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 ...
Denis's user avatar
  • 8,883
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 $\...
Yuval Peres's user avatar
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 ...
David Eppstein's user avatar
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. ...
domotorp's user avatar
  • 14k
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 ...
domotorp's user avatar
  • 14k
4 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 ...
Peter Shor 's user avatar
4 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 ...
Peter Shor 's user avatar
3 votes

Trying to understand the intuition behind Yao's Minimax Principle

It seems worth it to write up the "game" answer. You are playing a game where you choose an algorithm $A$ and your opponent chooses an input $I$. You want to minimize $C(I,A)$. First suppose ...
usul's user avatar
  • 7,615
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 ...
Yonatan N's user avatar
  • 1,642
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 ...
Klaus Draeger's user avatar
2 votes

Implementation of surreal numbers for games

Here is an implementation of Surreal Numbers in a relatively new language, Julia. https://github.com/mroughan/SurrealNumbers.jl Described at https://www.sciencedirect.com/science/article/pii/...
Matt's user avatar
  • 21
2 votes
Accepted

Maximum stable matching/allocation

Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists). You can find the current best approximation algorithm for MAX SMTI in the following paper: Z. Kiraly, Linear ...
Hiroki Yanagisawa's user avatar
2 votes

The logic in derivation of virtual welfare

I think I've gotten part of the answer. The above statement actually says that for any truthful mechanism, the expected profit is equal to its expected virtual surplus. If we are searching for ...
xyguo's user avatar
  • 191
2 votes

On bandwidth of graphs

As you mentioned that "My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too", you can have a look at the thesis by Morgan Chopin -- "Optimization ...
jayesh's user avatar
  • 21
2 votes

Applications of Game theory in computer science?

In Formal Verification game theory is a recurring theme. I think that one of the most important applications is to define the Simulation Preorder as a game between two players: Spoiler (he) and ...
greps's user avatar
  • 157
2 votes

White elephant gift exchanges: mechanisms for fair division

What we did this year was restrict the people you could steal from so that the later players didn't have as large an advantage. So the $n$ players sat in a circle and they could only steal along edges ...
Chris Jones's user avatar
2 votes

Evidence that PPAD is hard?

While this has been bumped anyway, maybe I can have the hubris to mention a heuristic that comes to mind. An NP-complete problem is, given a circuit, is there an input that evaluates to True? This ...
usul's user avatar
  • 7,615
2 votes
Accepted

A game on several graphs

Since Steven Stadnicki's answer doesn't appear to have been accepted by the asker, I figured it may still be helpful to provide an update: I have a reduction from 3SAT to MULTI-GAME. I haven't looked ...
gdmclellan's user avatar
2 votes

Algorithm to find $n$ player nash equilibrium

The problem of computing Nash equilibria in general games is PPAD complete (which is believed to be hard), even for 2-player games. This was proven for 3-player games by Daskalakis et al. for 3-player ...
smalldog's user avatar
  • 121
1 vote
Accepted

Sequential Two-player Game related to "Bandit Detection"

This answer doesn't answer whether or not this is a special case of some kind of game that is studied in TCS. But hopefully the answer helps understand the nature of the game. The value of the game ...
Neal Young's user avatar
  • 10.8k
1 vote
Accepted

Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

From the comments, the desiderata are: Preferably, a game that is/was in play by some human population (as opposed to one whose rules were written to have it fall in the complexity class that I am ...
Kevin Wang's user avatar
1 vote
Accepted

What Complexity Class is this? Is this already known?

The game that you describe (let's call it "MineFreePath") is (very) similar to the "MineSweeper" game, a ...
J..y B..y's user avatar
  • 2,776
1 vote
Accepted

Algorithm for finding traffic equilibrium

The problem you are interested in is called the Traffic equilibrium problem. The paper "Traffic Equilibrium and Variational Inequalities" by Stella Dafermos formalizes it, shows that there ...
Jozef Mikušinec's user avatar
1 vote

How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

It depends on what your usecase is. If you are interested in getting close to an actual Nash equilibrium, then the quality measure you want will be the distance to the nearest Nash equilibrium (which ...
Arno's user avatar
  • 111
1 vote

Application of Yao's Minmax Principle for Adaptive Randomized Algorithms

You may find this video useful: https://www.youtube.com/watch?v=0vrqCDcxbxs&t=22s Also, this video here (time 00:43) states some books that can help: https://www.youtube.com/watch?v=mQQ36cDnmR8&...
Avi Tal's user avatar
  • 1,606

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