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.
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
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$, ...
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
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 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
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
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
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; ...
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, ...
5
These are my two comments as an answer:
Of course you are right that if the strategic form (also called the normal form) is given explicitly then one can just check all pure strategy profiles. In that case, the problem of deciding if there is a pure equilibrium is clearly not likely to be NP-hard.
However, the paper shows in Theorem 3.1 hardness for ...
5
Unanimity and transitivity do no imply IIA.
For example, consider the Borda-count voting mechanism. There is an example of the violation of IIA here.
5
As others have said, there is less than you would expect. A couple of tangentially related papers:
"Multiplicative Weights in Coordination Games and the Theory of Evolution" by Chastain, Livnat, Papadimitriou, and Vazirani. This paper argues that evolutionary dynamics (in a simple model) is equivalent to a coordination game between genes being played with ...
5
The following paper at least formalizes the notion of approximate equilibria being close to exact equilibria, and proves some related structural results.
Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, and Santosh Vempala (2010). On Nash equilibria of approximation-stable games. In Proceedings of the Third international conference on ...
5
There is no algorithm that always beats all others in an IPD tournament. Proof: if your algorithm cooperates in round 1, then it gets last place in a tournament where all other bots always defect; if your algorithm defects in round 1, then it gets last place in a tournament where all other bots play unforgiving tit-for-tat (cooperate until the opponent ...
5
If p=q=s=t=−1, then it is easy to see that a pure NE can be reached by local search starting from (a3, a3). So in the rest of the proof, assume that at least one of p, q, s, and t is equal to 1.
If p=q=1, then (a1, a2) is a pure NE. Similarly, if s=t=1, then (a2, a1) is a pure NE.
In the remaining cases, at least one of the pairs (p, q), (q, p), (s, t), ...
5
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 finish.
Denote the words in the oracle after $t$ rounds by $A_t$, so initially $A_0=\emptyset$.
Denote the words queried by $M^{A_t}$ by $Q_t$.
The main ...
4
Is there a tool which solves parametric games?
Not that I am aware of (I am a co-author of GTE and help with Gambit).
The best suggestion I have if you don't find such a tool (and I doubt one exists) is to do a parameter sweep and solve a bunch of individual instantiations and see what the resulting sets of equilibria say about $EQ()$. Gambit is very ...
4
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, 2004, pp 457-467
There also are lots of follow-up works, as for instance
Sayan Bandyapadhyay, Aritra Banik, Sandip Das, Hirak Sarkar:
"Voronoi game on ...
3
By the Ky Fan minimax theorem, if you can identify the strategy spaces of the two players with convex compact subsets of a locally convex topological vector space, and the payoff function $M(x, y)$ is convex and continuous in $y$ for any $x$, and also concave and continuous in $x$ for any $y$, then the minimax theorem holds.
Only top voted, non community-wiki answers of a minimum length are eligible