As of May 31, 2023, we have updated our Code of Conduct.
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
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 ...
David Eppstein'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
  • 5,963
8 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 ...
gigabytes's user avatar
  • 1,446
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 ...
Shaull's user avatar
  • 5,511
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,473
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
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
  • 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 $\...
Yuval Peres's user avatar
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
  • 13.9k
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, ...
Gamow's user avatar
  • 5,742
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
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

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
Halbort's user avatar
  • 153
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
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 ...
hengxin's user avatar
  • 2,329
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 ...
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,175
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,175
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

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
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
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

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

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,566

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