37
It is an Unordered Constraint Satisfaction game and it is PSPACE-complete and it has been proved to be PSPACE-complete only recently;
a proof can be found in:
Lauri Ahlroth and Pekka Orponen, Unordered Constraint Satisfaction Games.
Lecture Notes in Computer Science Volume 7464, 2012, pp 64-75.
Abstract: We consider two-player constraint satisfaction ...
30
It may also be worthwhile to note that this problem was also solved in the 70's by Thomas Schaefer in Complexity of decision problems based on finite two-person perfect-information games. In fact, he proves a slightly stronger result in that the language remains PSPACE-complete even when restricted to positive CNF formulas.
23
One of the most famous examples of game theory in computer science is Yao's minimax principle. Let $X$ be a set of inputs for some problem, and let $A$ be a set of (deterministic) algorithms for that problem. Yao's principle states that
$$
\max_{x\in X} \operatorname{E}\limits_{a\in A} \left[T(a,x)\right]
\ge
\min_{a\in A} \operatorname{E}\limits_{x\in X} \...
15
This answer has two parts, together showing that the correct bound is $\Theta(\log N)$:
A lower bound of $\Omega(\log N)$ (times the radius of the first circle).
A matching upper bound of $O(\log N)$.
Lower bound of $\Omega(\log N)$
Consider two unit circles that touch at a point $p$. (See below; $p$ is on the right, the bug starts on the left.) ...
12
There are a number of game-theoretic characterizations of complexity classes. The most famous may be
AP=PSPACE (figuring out who wins a deterministic game which lasts for a polynomial number of moves is a PSPACE-complete question),
IP=PSPACE (in a polynomial-length deterministic game played against a player who makes random moves, distinguishing between ...
12
The best known example is probably checkers (also known as draughts), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on solved games; notable among them are connect four and nine men's morris. Additionally, several chess endgames have been solved.
This perhaps doesn't seem like an answer to your ...
12
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 2018.
**Update: Nov, 16, 2019
We proved that the game is tractable for 3-CNFs under some restrictions on 3-CNFs. We also radically conjectured that this game is ...
11
No, no-regret dynamics do not converge to Nash equilibrium in general games, and its not hard to think of examples.
On the other hand, no regret dynamics do always converge to coarse correlated equilibrium in any game, and no-internal regret dynamics always converge to the set of correlated equilibria.
They are also known to converge to Nash equilibrium ...
11
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 codes. See Conway and Sloane, "Lexicographic codes: Error-correcting codes from game theory", IEEE Trans. Inf. Th. 1986.
More simply, if you are willing to ...
11
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 one or you could use it to solve the halting problem. But you can achieve any value less than one by the strategy that for some fixed sufficiently large $t$, ...
10
Game theory played a significant role in solutions to the "full abstraction problem" in programming language semantics. In particular, the first fully-abstract semantics for Plotkin's PCF were given using games as models.
The relevant citations are:
Full Abstraction for PCF, by Samson Abramsky, Radha Jagadeesan, and Pasquale Malacaria
and
On Full ...
9
See Tic-Tac-Toe by Randall Munroe.
8
See Wolfe and Berlekamp -- Mathematical Go. Using Conway's theory of games, they show how to analyze certain kinds of Go endgames. Their solutions turn out to be measurably better than the solutions given by top Go players. (Not quite an answer to your problem, as those latter solutions were probably never claimed to be optimal.)
8
(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-way functions, there are Nash equilibria that are hard to find (and thus, $\mathsf{PPAD}$ is hard): On the Cryptographic Hardness of Finding a Nash Equilibrium
...
8
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 automatically generate a system (i.e. a finite-state transducer), that guarantees that for every input sequence of the environment, the computation induced by the ...
8
Generalized Geography (GG) is PSPACE-complete even on planar directed bipartite graphs,
but, as reported in:
Hans L. Bodlaender, Complexity of path-forming games, Theoretical Computer Science, Volume 110, Issue 1, 15 March 1993, Pages 215-245
GG (and some other PSPACE-complete variants) are linear-time-solvable in graphs of bounded treewidth.
SIDE NOTE: ...
8
For company $A$/the firm/giant corporation/"big pharma"/"THE MAN", the strategy does not change from the symmetric version:
Consider a round where the probability of seeing only lesser candidates thereafter is $> .5$. If company $A$ keeps the candidate, then it has a chance of winning $> .5$. If $A$ does not keep the candidate, then company $B$ can ...
8
I don't have an answer to your question of whether the theory of Conway games has been used in building game-playing programs, but still you might be interested in the Combinatorial Game Suite, "an open-source program to aid research in combinatorial game theory" (which I first learned about here). It includes an implementation of various standard ...
7
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 first player chooses an element from one of the two structures, and the second has to chose an element from the other, trying to maintain a local isomorphisms ...
7
Consider the maximum matching problem in bipartite graphs. The family of feasible solutions consists of all matchings, and local search is performed via finding augmenting paths. The problem belongs to PLS since an augmenting path can be found in polynomial time if a current matching is not maximum, and maximality can be checked in polynomial time. Any local ...
7
I can partially answer your question: counting the local optima of a PLS-complete search problem can indeed be #P-hard.
First, as Yoshio points out, there is a search problem $P_1$ in PLS whose associated counting problem is #P-complete. (We don't know if $P_1$ is PLS-complete, however.) Let $P_2$ be some PLS-complete problem. Then define $P'$ which, ...
7
The linear program for computing a correlated equilibrium in a game has size that is polynomial in the size of the game matrix: i.e. exponential in the number of players. The scheduling game that you describe is an $n$ player game, so the linear program will not be polynomially sized. However, it is a compactly represented game, so you can in principle use ...
7
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. If I understand the game right, Alice can win by playing every string in $S$. The only way to prevent this is if $m_A$ is polynomially-bounded but that would ...
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 ...
6
NOTE: my purported algorithm was incorrect; I deleted it.
One thing to realize is that it doesn't matter whether the game is deterministic or not. To randomize, the referee can ask each of the players to contribute a random number mod $p$, and then add them. It's easy to show that if the players use their optimal strategy, the sum is a random number mod $p$...
6
We have developed a user-friendly browser-based system to input and solve 2-player strategic-form and extensive-form games:
http://www.gametheoryexplorer.org/ (GTE)
Currently, we support:
finding all equilibria via polyhedral vertex enumeration (which works on the strategic-form representation, which is converted to in the case of extensive-form games; ...
6
It is easier for me to think of applications of computer science (techniques) to game theory, than the other way around. There is a very active field of algorithmic game theory which focuses on the development of efficient algorithms (or complexity results) for, e.g., Nash equilibria, Shapley values, and other such standard game theoretic concepts. Often, ...
6
A fixed point of a best response function is a Nash equilibrium -- the fact that you do not have the payoff matrix cannot make the problem easier (since if you know the payoff matrix, you also know the best response function, but not vice versa). Unfortunately, there are not in general good algorithms for computing approximate Nash equilibria in multi-player ...
6
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.
Suppose that you want to find an edge of a graph, and you can ask whether a given vertex is incident to the hidden edge, or not.
Now take the following bipartite ...
6
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 it's easy to adapt bad instances to set cover to show that the greedy algorithm can ask more questions than optimal by a logarithmic factor.
To see this, ...
Only top voted, non community-wiki answers of a minimum length are eligible
