On a graph $G(V,E)$ with possibly parallel edges, Alice and Bob play the following game.
- Alice picks a subset $U\subseteq V$ with an even number of vertices.
- Bob picks a subset $T\subseteq U$ with $|T| = |U|/2$.
- Alice's score is the fraction of edges in $E$ that are covered by $T$, that is, adjacent to at least one vertex of $T$.
What is the largest score that Alice can get?
Some examples of graphs:
- If $G$ is a cycle on $n = 2 k$ vertices, then Alice's best strategy is to pick all vertices, and Bob's best strategy is then to pick $k$ adjacent vertices. In this case, exactly $k+1$ out of $2 k$ edges are covered, so Alice's score is $1/2 + 1/k$.
- If $G$ is a union of $k$ disconnected edges, then regardless of what Alice does, Bob can pick the endpoints of half the edges adjacent to two vertices in $U$, and half the edges adjacent to one vertex in $U$, and then Alice's score is exactly $1/2$.
- If $G$ is a clique on $2 k$ vertices, then again Alice's best strategy is to pick all vertices. Regardless of what Bob picks, the number of covered edges is $k^2 + {k\choose 2} \approx 3k^2/2$, while the total number of edges is ${2k \choose 2} \approx 2k^2$, so Alice's score is approximately $3/4$.
- If $G$ is a disjoint union of cycle on $2 k$ vertices and clique on $2 k$ vertices, then picking all vertices is not an optimal strategy for Alice, since then Bob can pick only the vertices of the cycle, and then Alice's score is $\approx k / (2k^2)$ which can be very near 0 when $k$ is large. A better strategy for Alice here is to pick only the vertices of the clique.
- If $G$ is any graph with 3 vertices (even with parallel edges), then there are always two vertices each of which is adjacent to at least 1/2 of the edges. By picking these two vertices, Alice scores at least $1/2$.
- If $G$ is any graph with 4 vertices, then again Alice can score at least $1/2$, either by picking all four vertices, or (if that fails when Bob picks e.g. $v_3,v_4$), then this means that at least half the edges are adjacent to $v_1,v_2$, so Alice can score $1/2$ by picking them.
- If $G$ is a star with a center and 4 leaves, where there are $k$ parallel edges from the center to leaves 1, 2, 3, and $2k$ parallel edges from the center to leaf 4, then Alice can score at most $2/5$: if she picks two vertices, then Bob might not choose the center; if she pick four vertices, then Bob might not choose the center and leaf #4. In both cases at most $2k$ edges are covered, so Alice's score is $2k/5k = 2/5$.