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 taken. Then, the score of each player is the number of triplets from $T$ in which he has at least 2 elements.

A standard strategy-stealing argument shows that the first player can always score at least $|T|/2$. Suppose by contradiction that it is false. Then the second player can score more than $|T|/2$. But then the first player, copying the second player's winning strategy, can score more than $|T|/2$ too. This is a contradiction since the sum of scores is $|T|$.

QUESTION: what is an explicit strategy for the first player to get a score of at least $|T|/2$?

EDIT: Here is an explicit strategy for the first player to get at least $3|T|/8$. To each triplet in $T$, assign a potential $P(a,b)$ based on the number of its elements taken by the (first,second) player:

\begin{matrix} \bf a \downarrow b \rightarrow & \bf 0 & \bf 1 & \bf 2 & \bf 3 \\ \bf 0 &3/8&0& 0 & 0 \\ \bf 1 &3/4&1/2& 0 & \\ \bf 2 & 1 & 1 & & \\ \bf 3 & 1 & & & \\ \end{matrix} Initially, every triplet has potential $3/8$, so the potential-sum is $3|T|/8$.

Player 1's strategy is: pick an element that maximizes the potential-sum. Suppose that element is $x$ and the element picked next by player 2 is $y$. I claim that the potential-sum after these two moves weakly increases:

  • The potential of a triplet that contains neither $x$ nor $y$ does not change.
  • The potential of a triplet that contains both $x$ and $y$ changes from $P(a,b)$ to $P(a+1,b+1)$, which is always at least as large.
  • The potential of a triplet that contains $x$ and not $y$ increases by $P(a+1,b)-P(a,b)$;
  • The potential of a triplet that contains $y$ and not $x$ decreases by $P(a,b)-P(a,b+1)$; it is easy to check in the table that $P(a,b)-P(a,b+1)\leq P(a+1,b)-P(a,b)$ (the decrease when going right is at most the increase when going down).

All in all, the potential-sum increases by the sum of $P(a+1,b)-P(a,b)$ over all triplets that contain $x$, and decreases by (at most) the sum of $P(a+1,b)-P(a,b)$ over all triplets that contain $y$. By the choice of $x$, the first sum is weakly larger. So the potential-sum weakly increases.

So the final potential-sum is at least $3|T|/8$. At the end, a triplet has potential $1$ ($0$) iff it is won by player 1 (2), so the final potential-sum equals player 1's score.

  • 1
    It's quite unlikely that there's one simple strategy, as is the case with most games where strategy-stealing proves that the first player can always win. – domotorp Nov 8 at 9:25
  • I agree with domtorp. I suspect "take the element with the highest number of occurrences" is the right basic heuristic, though the number of occurrences isn't exactly the right thing to be counting. Strategy stealing arguments usually mean that if you follow a certain heuristic, you're always able to play defensively when challenged and end up winning. The issue is figuring out how and when to play defensively. – Stella Biderman Nov 8 at 17:04
  • To add to the previous commenters, it would be very interesting if a game of this type (with strategy-stealing in a natural framework other than "I cut you choose") were proven PSPACE complete (with for example, $T$ → a winning first move being PSPACE complete). – Dmytro Taranovsky Nov 9 at 5:06

This isn't a complete proof, but here's some justification for why known conjectures imply that the game may be computationally hard to solve. Namely, I'm going to argue that finding the correct first move is already probably tricky.


As a first step, we argue that the triplets game is harder (in the appropriate sense) than the $\textrm{Denser Induced Subgraph}$ game defined as follows.

Two players, A and B, alternate picking vertices on a common graph G. Vertices can only be picked once. When no more vertices remain to be picked, the subgraphs induced by each player's choices are compared. The player with the larger number of induced edges is declared the winner.

Proof outline:

Given an instance of the $\textrm{Denser Induced Subgraph}$ game with graph $G = (V,E)$, we construct a $\textrm{Triplets}$ instance as follows. Without loss of generality, assume $G$ has no isolated vertices. The set of elements in our instance will be $V \cup (E \times \{0,1\})$. For each edge $e \in E$ between vertices $u$ and $v$, we have two triplets of the form $(u, v, (e, 0))$ and $(u, v, (e, 1))$. Additionally, for each vertex $v \in V$, we throw in four additional triplets of the form $(v,v,v)$. This completes the reduction.

Now imagine the proceedings of the $\mathrm{Triplets}$ game. As long as some vertex from $V$ has not been picked, the choice of such a vertex strictly dominates that of any element from $E$. Indeed, picking an element from $E \times \{0,1\}$ only ever gives a potential score increase of $1$ (and also blocks the opponent from at most $1$ point), while picking an element from $V$ automatically gives a score increase of $4$, with potential for more.

Therefore, under optimal play, the first $|V|$ rounds will correspond to both players picking elements from $V$. After these rounds, the players alternate picking up the even-sized collection of triples that have not yet been claimed, which correspond to exactly the edges whose endpoints have been picked once by each player. Any reasonable strategy here, for either player, ends up picking up exactly half of those available triplets. The game ends with a sequence of NOOP moves on the already-picked-up triplets.

Let $V_A$ be the vertices chosen by player A, and $V_B$ those chosen by B. The score for player A is the sum of (i) four points per vertex chosen from the $(v,v,v)$ triplets (ii) two points per induced edge created from these vertices, and (iii) one point for each split edge. Therefore, the score is $4|V|/2 + 2|E[V_A]| + (|E| - |E[V_A]| - |E[V_B]|)$, where $E[S]$ is the set of edges induced by $S$. Since the first and last terms are ultimately equal for both players, the player with the larger induced subgraph wins. $\square$


With this in mind, we can appeal to some of the work in the literature of detecting dense subgraphs. There's a ton of relevant work out there on this that one can appeal to, but for simplicity of analysis I'll appeal to a particular conjecture on the difficulty of finding dense random graphs in sparse random graphs (I believe that this dependence can be removed with just a little more thought, but this is not meant to be a formal proof).

The Planted Dense Subgraph Problem (informal). Let $G = (V,E)$ be a random graph sampled from the Erdos-Renyi distribution $G(n, 1/\sqrt{n})$. With probability $1/2$, we return $G$ as is. Otherwise, we let $V'$ be a uniformly random subset of $V$ of size $\sqrt{n}$. For each $u,v$ pair in $V'$, we add an edge $(u,v)$ to $E$ independently with probability $n^{1/4}$. Only then do we return $G$. The problem is to, given only the output of the above, correctly identify whether or not the Erdos-Renyi graph was augmented.

The Planted Dense Subgraph Conjecture (informal). No polynomial-time algorithm can solve the Planted Dense Subgraph problem with probability at least $51\%$.

Suppose that the graph was augmented, and there is an unusually dense component. Since no poly-time algorithm can reliably detect this dense subgraph's presence, it also cannot reliably sample a vertex from this dense component (e.g. due to self-reducibility). Therefore, since (from Player A's perspective) it is selecting a random vertex from a pure Erdos-Renyi graph, it does not matter much which vertex A picks (up to a small change in its scoring that will end up not mattering1). However, if Player B is omniscient, it can reliably sample a vertex from the dense component on its first shot. This process repeats a superconstant number of times before B's choices begin unveiling the dense component to A (otherwise, a polynomial-time algorithm can traverse every path in this game tree to constant depth in order to solve the Planted Dense Subgraph problem). If the process repeated $r$ times before A catches on, then the first $r-1$ rounds can be seen as "freebie" rounds for B, while the $r$th round is the beginning of A and B fighting over the dense component, with B getting the first move and (by your strategy stealing argument) a winning subset.

Once the dense component is exhausted, the two players resume fighting over the rest of the graph. While A has chosen $r$ more vertices here than B has, B's first $r$ vertices are worth $\Omega(n^{1/4})$ times as much, and thus B is ultimately the winner.

1. By some type of concentration and pigeonhole argument, the difference between making the first choice and the second choice should not be more than $O(1)$ in the final score.


Therefore, despite the game being very weakly solved for player A, it's unlikely that it's computationally feasible for A to play out even the first move of the winning strategy.

An approach based on the hardness of the "normal" densest subgraph problem should not be difficult to attain here, either, and composing the reduction with a hardness of approximation result likely can be used to get some kind of hardness based on more mainstream conjectures (eg ETH). I'm not sure what the difficulty of moving up to NP-hardness (or beyond) may be.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.