Questions tagged [combinatorial-game-theory]

Combinatorial game theory

25 questions
75 views

Impartial Combinatorial Games as a core of the final undergraduate project

Solving several problems of Impartial Combinatorial Games in Game Theory has drawn my attention. So that, I'd like to ask if it's possible to use this topic (e.g. Sprague Grundy theorem) as a core or ...
81 views

Auction theory - Selling Multiple Items via Social Networks

I am trying to understand this paper. The one thing that I cannot wrap my head around is the payment policy for the Generalized Information Diffusion Mechanism. It is explained on page 72 with ...
187 views

Winning strategy in the game of triplets

The game of triplets is defined by a finite set of elements $X$, and a finite multi-set $T$ containing triplets of elements. Two players take turns picking elements from $X$ until all elements are ...
225 views

Games on Turing machines that are AH-hard

I'm interested in proving that finding optimal play in a particular two-player game is harder than the arithmetic hierarchy. I suspect this to be true, because even carrying out a deterministic end-...
254 views

Among an infinite variety of n x n board games, why are some interesting?

Suitably generalized to $n \times n$ boards, Checkers, Chess, and Go are each EXPTIME-Complete. (See the Wikipedia Game Complexity table.) Each of these two-person games of perfect information has a ...
73 views

Nim-game variant - weird ending condition

the game is structured like this: two players the players alternate moves 4 heaps $h_1,h_2,h_3,h_4$ with sizes $n_1,n_2,n_3,n_4$ at each move, the player can either remove one or two elements from ...
697 views

Can generalized twenty questions be solved by a greedy algorithm?

The game of twenty questions can be generalized in the following way. Let $\Omega$ be a finite set and $\mathcal Q$ a collection of subsets of $\Omega$, called the questions. A point $x\in\Omega$ ...
146 views

The logic in derivation of virtual welfare

I am learning algorithmic game theory with the lecture notes posted by Tim Roughgarden. In lecture 5 it is proved that the problem of revenue (or profit) maximization in single-parameter environment ...
848 views

What is the application of combinatorial game theory

I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are ...
250 views

Finding an equivalent NP-complete instance for this game-theory problem

I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't ...
154 views

Applications of Combinatorial Games in Computational Biology

I'm looking for general references in the literature about applications of games algorithmics in computational biology. Q1. What are the notable cases of computational-biology or bioinformatics ...
518 views

Properties expressible in 2-CNF or 2-SAT

How does one show that a certain property cannot be expressed in 2-CNF (2-SAT)? Are there any games, such as pebble games? It seems that the classical black pebble game and the black-white pebble ...
510 views

Implementation of surreal numbers for games

There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they ...
210 views

Is there a gadget that reduces generalized geography to undirected graphs?

The directed Generalized Geography game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in Hans L. Bodlaender, Complexity of path-forming ...
220 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
328 views

Sylver Coinage Game

A game in which the players alternately name positive integers that are not sums of previously named integers (with repetitions being allowed). The person who names 1 (so ending the game) is the loser....
255 views

Examples of Computer-Found Optimal Strategies in Games

I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.
221 views

Is the complexity of ARC KAYLES still open?

In the problem NODE KAYLES two opposing players take turns playing on an undirected graph. In each turn, a player selects a vertex $u$ and removes $u$ and all its neighbors from the graph. The first ...
423 views

Winning strategy of an “edge or isolated vertex” deletion game

Is this perfect information game played on graphs know/studied? Given a graph $G= (V,E)$, two players alternate picking an edge or an isolated node. If the player picks an edge $e = (u,v)$ the two ...
1k views

Is there a natural problem on the naturals that is NP-complete?

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
1k views

How hard is Mafia?

Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29. Basically, it works as follows: At the beginning, ...
175 views

What is the known complexity of this game? (similar to PushPush-1)

I've been looking at a few entries in http://library.msri.org/books/Book56/files/10demaine.pdf (on combinatorial algorithmic game theory). I didn't see the following game listed there, and I want to ...
2k views

Permutation game redux

This is a restatement of an earlier question. Consider the following impartial perfect information game between two players, Alice and Bob. The players are given a permutation of the integers 1 ...
451 views

Is there a method of solving the game of “war”

I was thinking of determining the game of war. I could write a fairly simple game that takes two "decks" of cards, and plays them against each other but I do not think this is optimal. Because in ...
607 views

The Dracula game

Background This question is motivated by a board game called 'Dracula'. In this game there is one vampire and four hunters, the purpose of the hunters is to catch the vampire. The game takes place in ...