7

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 past position is forbidden. This is the rule used for instance in China and western countries. It is simple to state, but could bring some difficulties to ...


2

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 Duplicator (she). Given a Transition System (in other words, one set $S$ equipped with a labelled transition relation $S \rightarrow S$) Spoiler, starting from a ...


2

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 of a graph $G$. Picking $G$ to be reasonably expansive is enough to "mix" the gifts; the simple expander graph we used is to assign players 1 through $n$, and ...


2

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 at Steven's answer carefully or followed through the link he provided, but based on the following reduction I won't be surprised if MULTI-GAME is indeed PSPACE-...


1

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 networking, since the networks that make Internet are economic competitors and belong to different companies, but they need to collaborate in order to ensure ...


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