Positional s-of-k games

This paper introduces a general framework for "s-of-k" positional games where players score points by claiming at least $s$ elements of a winning set, and comprehensively analyzes the resulting scores under both optimal play and pairing-restricted strategies across various regular grid structures.

The Gist

Imagine you and a friend are playing a game on a giant, complex board made of dots and lines. This isn't just Tic-Tac-Toe; it's a high-stakes battle for territory.

In the classic version of this game (called "Maker-Breaker"), the goal is simple: Maker tries to grab every single dot in a specific shape (like a triangle or a square) to win that shape. Breaker tries to stop Maker by grabbing just one dot in every shape, effectively "poisoning" it so Maker can never complete it. It's an all-or-nothing game.

This paper introduces a new, more flexible way to play: The "s-of-k" Game.

The New Rules: It's Not All or Nothing

Imagine the winning shapes on the board are like pizza slices (the "k" in the name).

• In the old game, you had to eat the whole slice to get a point.
• In this new game, you get a point if you eat at least "s" pieces of that slice.

If a slice has 6 pieces (k=6), and the rule is "3-of-6" (s=3), you get a point just by grabbing half the slice. If the rule is "1-of-6," you get a point for grabbing just a tiny crumb.

The paper asks: How many points can Maker guarantee to score, and how many can Breaker force Maker to lose?

The Two Strategies: The Chess Master vs. The Robot

The researchers looked at this game in two different ways, like comparing a grandmaster chess player to a robot following a strict script.

1. The Optimal Score (SC): This is the "Grandmaster" score. Maker plays perfectly, thinking ahead, adapting to Breaker's moves, and finding the best possible path to grab the most slices.
2. The Pairing Score (SC2): This is the "Robot" score. Here, Maker is forced to use a Pairing Strategy. Before the game starts, Maker pairs up all the dots on the board (like matching socks).
   • The Rule: Whenever Breaker grabs a dot, Maker must immediately grab its partner.
   • Why study this? Pairing strategies are simple and easy to calculate, but they aren't always the best. The paper wanted to see: How much does Maker lose by being forced to play like a robot instead of a genius?

The Playing Fields: The Grids

To test these ideas, the authors played the game on four different types of "neighborhoods" (grids):

• Triangular Grid: A honeycomb of triangles.
• Square Grid: A standard checkerboard.
• Rhombus Grid: A diamond-shaped pattern.
• Hexagonal Grid: A classic honeycomb.

They calculated the "best possible score" (SC) and the "robot score" (SC2) for different rules (like needing 1 piece, 2 pieces, or 3 pieces of a shape to score).

The Big Discoveries (The "Aha!" Moments)

1. The Robot is Sometimes Good Enough
In some cases, the robot strategy works just as well as the grandmaster strategy.

• Example: On a square grid, if the rule is "grab 1 corner to score," the robot strategy guarantees Maker gets every single square. The robot and the genius get the same score.

2. The Robot Sometimes Stumbles
In other cases, the robot leaves points on the table.

• Example: On a triangular grid, if the rule is "grab 2 corners to score," the Grandmaster can get 50% of the triangles. But if Maker is forced to use the pairing strategy, she might only get 37.5%. The robot missed out on a quarter of the potential points!

3. The "Tie-Breaker" Mystery
The paper found a fascinating mathematical symmetry. If the rule is "grab half the slice," the game becomes a perfect tug-of-war. Maker and Breaker end up with almost exactly the same number of points (50/50), regardless of who goes first. It's like a perfectly balanced scale.

4. The "Gap" Problem
The authors found that for many complex rules, we don't know the exact answer yet. We have a "best guess" (a lower bound) and a "worst-case scenario" (an upper bound), but there is a gap between them.

• Analogy: It's like knowing a runner can finish a race in at least 10 minutes and at most 12 minutes, but we don't know if they actually run it in 10.5 or 11.5. The paper narrows this gap but doesn't always close it completely.

Why Does This Matter?

You might ask, "Who cares about counting pizza slices on a grid?"

This research is actually about resource management and strategy.

• Real Life: Imagine you are a manager trying to secure contracts. You don't need to win every contract to be successful; you just need to win enough of them (the "s" part).
• Computer Science: These games help us understand how algorithms perform when they are forced to make simple, pre-planned decisions (like the pairing strategy) versus when they can think dynamically.
• Game Design: It helps game designers create fairer board games where the "first player advantage" or "simple strategies" don't break the game.

The Bottom Line

This paper built a new "rulebook" for scoring games. It showed us that while simple, rigid strategies (like pairing socks) are often very strong, they sometimes leave points on the table compared to a flexible, thinking opponent. The authors mapped out exactly how much "points" Maker can guarantee on different shapes, turning abstract math into a clear map of victory and defeat.

Technical Summary

Here is a detailed technical summary of the paper "Positional s-of-k games" by Duchêne, Gledel, and Stojaković.

1. Problem Definition

The paper introduces and analyzes a general framework for scoring positional games, extending the classic Maker-Breaker paradigm.

• Context: In standard Maker-Breaker games, Maker wins by fully claiming a winning set (hyperedge), while Breaker wins by claiming at least one element in every winning set. In scoring variants, Maker aims to maximize the number of winning sets fully claimed, and Breaker aims to minimize this number.
• The s-of-k Generalization: The authors generalize this to $s$-of-$k$ games.
  • The game is played on a $k$-uniform hypergraph $(V, \mathcal{F})$ where every winning set has size $k$.
  • An integer threshold $s \in \{1, 2, \dots, k\}$ is fixed.
  • Scoring Rule: Maker scores a point for a winning set if she claims at least $s$ elements of that set.
  • Objective: Maker maximizes the total score; Breaker minimizes it.
• Metrics:
  • $SC(G, s)$: The score under optimal play by both players.
  • $SC_2(G, s)$: The score when Maker is restricted to a pairing strategy (a non-adaptive strategy where vertices are pre-paired, and Maker responds to Breaker's move by claiming the paired vertex).
• Motivation: This framework unifies various existing games (e.g., "Incidence" is a 2-of-2 game; "Majority" games are a specific case) and models real-life board games where partial control yields points.

2. Methodology

The authors employ a combination of combinatorial arguments, probabilistic methods, and constructive strategies to derive bounds for $SC$ and $SC_2$.

A. General Theoretical Tools

1. Erdős-Selfridge Theorem Adaptation: They adapt the classic theorem to provide bounds for the extreme cases $s=1$ and $s=k$.
   • $SC(G, k) \le n 2^{-k}$ (Upper bound for Maker).
   • $SC(G, 1) \ge n(1 - 2^{-k})$ (Lower bound for Maker).
2. Probabilistic Upper Bound for Pairing Strategies ($SC_2$):
   • They develop a novel linear programming approach (Theorem 4) to bound $SC_2$.
   • Logic: They model Breaker's response to a fixed pairing strategy as a random process (flipping a coin for each pair). By calculating the expected number of winning sets Maker scores under this random Breaker strategy, they prove the existence of a deterministic Breaker strategy that limits Maker's score to this expectation.
   • This yields tight upper bounds for $SC_2$ on regular grids.
3. Strategy Stealing & Symmetry:
   • They utilize Observation 1: $SC(G, s) \approx |\mathcal{F}| - SC(G, k-s+1)$. This highlights the duality between Maker's goal in an $s$-of-$k$ game and Breaker's goal in a $(k-s+1)$-of-$k$ game.
   • For odd $k$ and $s = (k+1)/2$, they use strategy stealing arguments to show $SC(G, s) = n/2 + o(n)$.

B. Case Studies on Regular Grids

The paper applies these tools to four specific grid types, analyzing winning sets defined by geometric shapes:

1. Triangular Grid ($G_\triangle$): Winning sets are triangles ($k=3$).
2. Square Grid ($G_\square$): Winning sets are squares ($k=4$).
3. Rhombus Grid ($G_\diamond$): Winning sets are rhombi on a triangular grid ($k=4$).
4. Hexagonal Grid ($G_\hex$): Winning sets are hexagons ($k=6$).

For each case, they construct specific pairing strategies for Maker to establish lower bounds for $SC_2$ and use the probabilistic method (Theorem 4) or specific tiling arguments to establish upper bounds.

3. Key Contributions and Results

A. Theoretical Framework

• Formalized the $s$-of-$k$ game class, providing a flexible parameter $s$ to model diverse scoring objectives.
• Proved that pairing strategies are not always optimal. Specifically, for a cycle $C_{14}$ in a 2-of-2 game, $SC_2(C_{14}, 2) = 2$ while $SC(C_{14}, 2) = 3$, demonstrating a gap between restricted and optimal play.

B. Bounds on Grids

The authors provide comprehensive lower and upper bounds for $SC$ and $SC_2$ across the four grid types. Key findings include:

Grid Type	Winning Set ($k$)	Threshold ($s$)	Key Results (asymptotic bounds)
Triangular	3	1	$SC_2 \in [0.75n, 0.9375n]$; $SC \in [0.875n, 0.964n]$
		2	$SC = n/2$; $SC_2 \ge 0.375n$
		3	$SC_2 \ge 0.035n$; $SC \le 0.125n$
Square	4	1	$SC = SC_2 = n$ (Maker wins all)
		2	$SC_2 \in [0.66n, 0.75n]$; $SC \in [0.66n, 0.86n]$
		3	$SC_2 \ge 0.125n$; $SC \ge 0.133n$
		4	$SC = SC_2 = 0$ (Breaker wins all)
Rhombus	4	1	$SC_2 \ge 0.916n$; $SC \ge 0.937n$
		2	$SC_2 \ge 0.527n$; $SC \le 0.927n$
		4	$SC_2 \ge 0.012n$; $SC \le 0.062n$
Hexagonal	6	1, 2	$SC = SC_2 = n$
		3	$SC_2 \ge 0.75n$; $SC \le 0.833n$
		4	$SC_2 \ge 0.1n$; $SC \ge 0.166n$
		5, 6	$SC = SC_2 = 0$

Note: $n$ represents the number of winning sets.

C. Specific Strategy Innovations

• Recursive Pairing (Square Grid, $s=3$): A multi-level pairing strategy where the grid is subdivided into $3\times3$blocks, and unpaired vertices are passed to higher levels, ensuring a score of$n/8$.
• Tiling with Subgrids: For the Square grid ($s=3$), they proved a lower bound of $2n/15$by tiling the board with$3\times5$ subgrids and solving the game on these small tiles, which outperforms the pairing strategy bound.
• Flower Pairing (Hexagonal Grid, $s=3$): A specialized pairing for hexagons that guarantees Maker $3n/4$points, significantly improving upon the$n/2$ bound from standard horizontal pairings.

4. Significance and Open Problems

• Bridging Theory and Practice: The $s$-of-$k$ framework successfully models games like Conquete and Hedron, where partial control of a region yields points, moving beyond the binary "win/loss" of traditional positional games.
• Quantifying Strategy Loss: The paper rigorously quantifies the "price of simplicity" by comparing $SC$ (optimal) vs. $SC_2$ (pairing). The results show that while pairing strategies are often strong, they can be suboptimal, especially in complex grid geometries.
• Open Problems:
  • The gap between lower and upper bounds remains significant for many cases (e.g., Square grid $s=2$, Rhombus grid $s=2$).
  • Conjecture: For the Rhombus grid with $s=4$, the authors conjecture that $SC_2(G_\diamond, 4) = 0$ (Maker cannot score any points with a pairing strategy), despite the existence of a general optimal strategy yielding $n/78$. Determining if a pairing strategy can yield a positive score here remains a difficult open question.

In conclusion, this paper establishes a robust mathematical foundation for a new class of scoring games, providing the first systematic analysis of $s$-of-$k$ games on regular grids and highlighting the limitations of pairing strategies in achieving optimal scores.