<p>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.</p>
<hr />
<p>As a first step, we argue that the triplets game is harder (in the appropriate sense) than the <span class="math-container">$\textrm{Denser Induced Subgraph}$</span> game defined as follows.</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>Proof outline:</p>
<p>Given an instance of the <span class="math-container">$\textrm{Denser Induced Subgraph}$</span> game with graph <span class="math-container">$G = (V,E)$</span>, we construct a <span class="math-container">$\textrm{Triplets}$</span> instance as follows. Without loss of generality, assume <span class="math-container">$G$</span> has no isolated vertices. The set of elements in our instance will be <span class="math-container">$V \cup (E \times \{0,1\})$</span>. For each edge <span class="math-container">$e \in E$</span> between vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span>, we have two triplets of the form <span class="math-container">$(u, v, (e, 0))$</span> and <span class="math-container">$(u, v, (e, 1))$</span>. Additionally, for each vertex <span class="math-container">$v \in V$</span>, we throw in four additional triplets of the form <span class="math-container">$(v,v,v)$</span>. This completes the reduction.</p>
<p>Now imagine the proceedings of the <span class="math-container">$\mathrm{Triplets}$</span> game. As long as some vertex from <span class="math-container">$V$</span> has not been picked, the choice of such a vertex strictly dominates that of any element from <span class="math-container">$E$</span>. Indeed, picking an element from <span class="math-container">$E \times \{0,1\}$</span> only ever gives a potential score increase of <span class="math-container">$1$</span> (and also blocks the opponent from at most <span class="math-container">$1$</span> point), while picking an element from <span class="math-container">$V$</span> automatically gives a score increase of <span class="math-container">$4$</span>, with potential for more.</p>
<p>Therefore, under optimal play, the first <span class="math-container">$|V|$</span> rounds will correspond to both players picking elements from <span class="math-container">$V$</span>. 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.</p>
<p>Let <span class="math-container">$V_A$</span> be the vertices chosen by player A, and <span class="math-container">$V_B$</span> those chosen by B. The score for player A is the sum of (i) four points per vertex chosen from the <span class="math-container">$(v,v,v)$</span> triplets (ii) two points per induced edge created from these vertices, and (iii) one point for each split edge. Therefore, the score is <span class="math-container">$4|V|/2 + 2|E[V_A]| + (|E| - |E[V_A]| - |E[V_B]|)$</span>, where <span class="math-container">$E[S]$</span> is the set of edges induced by <span class="math-container">$S$</span>. Since the first and last terms are ultimately equal for both players, the player with the larger induced subgraph wins. <span class="math-container">$\square$</span></p>
<hr />
<p>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).</p>
<blockquote>
<p><strong>The Planted Dense Subgraph Problem</strong> (informal). Let <span class="math-container">$G = (V,E)$</span> be a random graph sampled from the Erdos-Renyi distribution <span class="math-container">$G(n, 1/\sqrt{n})$</span>. With probability <span class="math-container">$1/2$</span>, we return <span class="math-container">$G$</span> as is. Otherwise, we let <span class="math-container">$V'$</span> be a uniformly random subset of <span class="math-container">$V$</span> of size <span class="math-container">$\sqrt{n}$</span>. For each <span class="math-container">$u,v$</span> pair in <span class="math-container">$V'$</span>, we add an edge <span class="math-container">$(u,v)$</span> to <span class="math-container">$E$</span> independently with probability <span class="math-container">$n^{-1/4}$</span>. Only then do we return <span class="math-container">$G$</span>. The problem is to, given only the output of the above, correctly identify whether or not the Erdos-Renyi graph was augmented.</p>
<p><strong>The Planted Dense Subgraph Conjecture</strong> (informal). No polynomial-time algorithm can solve the Planted Dense Subgraph problem with probability at least <span class="math-container">$51\%$</span>.</p>
</blockquote>
<p>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 mattering<sup>1</sup>). 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 <span class="math-container">$r$</span> times before A catches on, then the first <span class="math-container">$r-1$</span> rounds can be seen as &quot;freebie&quot; rounds for B, while the <span class="math-container">$r$</span>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.</p>
<p>Once the dense component is exhausted, the two players resume fighting over the rest of the graph. While A has chosen <span class="math-container">$r$</span> more vertices here than B has, B's first <span class="math-container">$r$</span> vertices are worth <span class="math-container">$\Omega(n^{1/4})$</span> times as much, and thus B is ultimately the winner.</p>
<p><sup>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 <span class="math-container">$O(1)$</span> in the final score.</sup></p>
<hr />
<p>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.</p>
<p>An approach based on the hardness of the &quot;normal&quot; 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.</p>

CC BY-SA 4.0
2018-11-12T17:14:03.903Z
The reduction is very cool. Can you give a reference to this "The Planted Dense Subgraph" conjecture?
Erel Segal-Halevi
CC BY-SA 4.0
2018-11-12T17:40:03.260Z
The conjecture has appeared a number of times under slightly varying flavors, including https://www.cc.gatech.edu/~klai9/FinalThesis.pdf (Conjecture 2), https://users.cs.duke.edu/~rongge/derivatives_ics.pdf (Densest Subgraph Assumption), http://proceedings.mlr.press/v40/Hajek15.pdf (PC Hypothesis), http://www.math.ias.edu/files/ABW10_STOC.pdf (DUE Assumption), https://core.ac.uk/download/pdf/62922882.pdf (Planted Dense Subgraph Conjecture), among others. 

The end results are similar enough that the above construction needs almost no modification to be adapted to the chosen flavor.
Yonatan N
CC BY-SA 4.0
2018-11-12T17:50:04.640Z
Interesting, thanks! I have just added to the question, an explicit strategy by which the first player can win a score of at least $3|T|/8$. So $3|T|/8$ is computable but $|T|/2$ is not computable (assuming the conjecture is true). Do you have an idea, what is the largest computable score?
Erel Segal-Halevi
CC BY-SA 4.0
2018-11-14T17:44:33.387Z
Not off the top of my head, but I'll see if I can think about it some more over the weekend. Nice 3/8 argument!
Yonatan N
CC BY-SA 4.0
2018-11-10T20:44:27.803Z
2019-08-21T19:10:59.717Z
2020-06-17T09:38:08.363Z
Yonatan N
<p>The <em>game of triplets</em> is defined by a finite set of elements <span class="math-container">$X$</span>, and a finite multi-set <span class="math-container">$T$</span> containing triplets of elements. 
Two players take turns picking elements from <span class="math-container">$X$</span> until all elements are taken. Then, the score of each player is the number of triplets from <span class="math-container">$T$</span> in which he has at least 2 elements.</p>

<p>A standard <a href="https://en.wikipedia.org/wiki/Strategy-stealing_argument" rel="nofollow noreferrer">strategy-stealing argument</a> shows that the first player can always score at least <span class="math-container">$|T|/2$</span>. Suppose by contradiction that it is false. Then the second player can score more than <span class="math-container">$|T|/2$</span>. But then the first player, copying the second player's winning strategy, can score more than <span class="math-container">$|T|/2$</span> too. This is a contradiction since the sum of scores is <span class="math-container">$|T|$</span>.</p>

<blockquote>
  <p>QUESTION: what is an explicit strategy for the first player to get a score of at least <span class="math-container">$|T|/2$</span>?</p>
</blockquote>

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

<p><span class="math-container">\begin{matrix}
\bf a \downarrow b \rightarrow &amp; \bf 0 &amp; \bf 1 &amp; \bf 2 &amp; \bf 3 \\
\bf 0    &amp;3/8&amp;0&amp; 0 &amp; 0 \\
\bf 1    &amp;3/4&amp;1/2&amp; 0 &amp;   \\
\bf 2    &amp; 1 &amp; 1 &amp;   &amp;   \\
\bf 3    &amp; 1 &amp;   &amp;   &amp;   \\
\end{matrix}</span>
Initially, every triplet has potential <span class="math-container">$3/8$</span>, so the potential-sum is <span class="math-container">$3|T|/8$</span>.</p>

<p>Player 1's strategy is: pick an element that maximizes the potential-sum. 
Suppose that element is <span class="math-container">$x$</span> and the element picked next by player 2 is <span class="math-container">$y$</span>. I claim that the potential-sum after these two moves weakly increases:</p>

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

<p>All in all, the potential-sum increases by the sum of <span class="math-container">$P(a+1,b)-P(a,b)$</span> over all triplets that contain <span class="math-container">$x$</span>, and decreases by (at most) the sum of <span class="math-container">$P(a+1,b)-P(a,b)$</span> over all triplets that contain <span class="math-container">$y$</span>. By the choice of <span class="math-container">$x$</span>, the first sum is weakly larger. So the potential-sum weakly increases.</p>

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

CC BY-SA 4.0
2018-11-08T09:25:59.567Z
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
CC BY-SA 4.0
2018-11-08T17:04:27.283Z
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
CC BY-SA 4.0
2018-11-09T05:06:36.543Z
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
<gt.game-theory><combinatorial-game-theory>
Winning strategy in the game of triplets
Erel Segal-Halevi
# Winning strategy in the game of triplets

(Asked by: username_0 on 2018-11-06)

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](https://en.wikipedia.org/wiki/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.

**Tags:** gt.game-theory, combinatorial-game-theory
> **Comments:**
> **username_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.  
> **username_2**: 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.  
> **username_3**: 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).  

---

## 1 answers

### Answer by username_4 on 2018-11-10. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: The reduction is very cool. Can you give a reference to this "The Planted Dense Subgraph" conjecture?  
> **username_4**: The conjecture has appeared a number of times under slightly varying flavors, including https://www.cc.gatech.edu/~klai9/FinalThesis.pdf (Conjecture 2), https://users.cs.duke.edu/~rongge/derivatives_ics.pdf (Densest Subgraph Assumption), http://proceedings.mlr.press/v40/Hajek15.pdf (PC Hypothesis), http://www.math.ias.edu/files/ABW10_STOC.pdf (DUE Assumption), https://core.ac.uk/download/pdf/62922882.pdf (Planted Dense Subgraph Conjecture), among others.   The end results are similar enough that the above construction needs almost no modification to be adapted to the chosen flavor.  
> **username_0**: Interesting, thanks! I have just added to the question, an explicit strategy by which the first player can win a score of at least $3|T|/8$. So $3|T|/8$ is computable but $|T|/2$ is not computable (assuming the conjecture is true). Do you have an idea, what is the largest computable score?  
> **username_4**: Not off the top of my head, but I'll see if I can think about it some more over the weekend. Nice 3/8 argument!  

---

