35
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 ...
27
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.
22
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.) ...
14
This isn't a complete answer, but it's an incomplete one.
Some background and related lit for those who aren't familiar --
A nice property would be envy-freeness, in which no player would like to trade with another after the mechanism is complete. Unfortunately, for indivisible goods and no money we can see that this is impossible (there might be one good ...
12
Here's a reference that you will want to look at: http://www.jstor.org/stable/10.2307/25442651
Mafia: A theoretical study of players and coalitions in a partial information environment
Braverman, M. and Etesami, O. and Mossel, E.
The Annals of Applied Probability
2008
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 ...
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
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 ...
11
The answer is that the mechanism must be truthful for every set of possible types: the mechanism does not know which are the true types ahead of time. So for a pair of types $v_i$ and $v_i'$, the mechanism must be truthful if an agent's true type is $v_i$: i.e. his utility must be greater if he bids $v_i$ than if he bids $v_i'$. But the mechanism must also ...
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
Imagine having to predict 0 or 1 on every round, and we are counting the number of correct predictions. Every deterministic strategy has an adversarial sequence that makes it always predict incorrectly. Hence, no competitive ratio is possible.
However, the randomized strategy of flipping a coin on every round will be $2$-competitive with the best constant ...
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 ...
10
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 ...
10
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 ...
9
Mechanism design is basically just algorithm design, where you don't control the inputs: instead, you assume that the inputs are controlled by different agents, who each have their own set of feasible actions, and their own utility function over outcomes, and are acting to maximize their own utility (and not yours, as the mechanism designer). So you are ...
9
See Tic-Tac-Toe by Randall Munroe.
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
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
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
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 ...
7
Much of the white elephant gift exchange experience is also controlled by random selection. A popular variation includes the rule that the first picks last, but that is not always included in the rule. This takes the unfair advantage of being randomly selected first out of the equation.
Another rule requires that there are no direct "steal-backs" in the ...
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
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; ...
Only top voted, non community-wiki answers of a minimum length are eligible
