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,791
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-...
- 6,051
8
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 ...
- 9,018
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,791
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 $\...
- 451
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 ...
- 51.2k
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.
...
- 14.2k
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 ...
- 14.2k
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 ...
- 25k
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 ...
- 25k
4
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,788
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
Given a 2-player zero-sum game in EFG, find a pure Nash equilibrium (given that one exists)
It is NP-Hard to find a pure Nash equilibrium in a 2P0S game given in extensive form, even if one is promised to exist.
It is NP-Hard to decide if a pure Nash equilibrium exists in a 2P0S game given ...
- 256
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
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
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,788
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
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 ...
- 10.9k
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 ...
- 256
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,816
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 ...
- 342
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,616
1
vote
Applications of Game theory in computer science?
Since the title is about CS and not TCS, maybe an answer about applications of game theory to networking can be of some interest.
Questions about game theory and equilibria arise naturally in ...
- 1,158
Only top scored, non community-wiki answers of a minimum length are eligible