Problems

This page is a bit outdated now, and the best source of open problems on this site right now are the manuscripts on the publications page. I'm leaving the problem below because it doesn't seem to appear anywhere else.

Combinatorial Games

In an ‘achievement‘ game played on a hypergraph, players take turns selecting previously unchosen vertices of the hypergraph, with the goal controlling all the vertices of some edge with just their own points. (Example: Tic-Tac-Toe is an achievement game where the hypergraph game has 9 vertices and 8 edges.)

The cooperative bias...

We can define the biased versions of games, where, for example, Player 1 might get to choose 2 points on each turn of an achievement game, while Player 2 can only choose 1 point on each turn. There are many interesting questions and results about these biased games.

We can also define the cooperative bias of an achievement game, where Player 1 gets to select (for example) 2 points on each turn, but they are of different ‘classes’: for example, maybe he gets to color one point blue and one point red on each turn, but to win, he must occupy some edge either only with blue or only with red. In this case, it is as if there are three players of the game, and two of them are ganging up on the third.

We want to consider the behavior of the cooperative bias on some extremely simple k-regular hypergraphs. One which is certainly very simple is the hypergraph where the m edges are all disjoint. Of course in the regular achievement game Player 1 cannot win, and it is easy to see that in the regular 2:1 biased game, Player 1 can win in exactly 2k-1 turns. What about in the 2:1 cooperative bias game? Player 1 can certainly still win, but I cannot tell you exactly how long it takes. Is it exponential in k? Or more like (k!)? I can’t rule out either of these possibilities.