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 ...
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,616
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,961
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 ...
- 8,598
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,616
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.9k
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.9k
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 $\...
- 441
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.9k
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 ...
- 24.3k
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 ...
- 24.3k
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 ...
- 7,595
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,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 ...
- 2,500
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,329
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 ...
- 243
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 ...
- 7,595
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 ...
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 ...
- 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 ...
- 21
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/...
- 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 ...
- 157
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 ...
- 406
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 ...
- 121
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 ...
- 156
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 ...
- 2,733
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 ...
- 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&...
- 1,596
1
vote
Accepted
Understanding Prisoner's dilemma
If you look at the definition for Nash equilibrium, you can see that if both $A$ and $B$ are in $\texttt{State 4}$, then if $A$ changes their mind that would mean that they would be defecting from a ...
- 26
Only top scored, non community-wiki answers of a minimum length are eligible