I have the responsibility of creating a schedule for a card game league. While creating the schedule, the following problem has arisen...
Let $n,g,s \in \mathbb{N+}$ where $s \leq n$.
Let $P = \{1, 2, 3, ... n\}$
We'll say $A \in \Theta(n, g, s)$ iff $A = a_1,a_2, ... a_g$ such that $a_i \subset P$ and $|a_i| = s$.
If $A \in \Theta(n, g, s)$, $A_{i,j} = |\{a_k : a_k \in A \wedge i,j \in a_i \}|$, and $L(A) = min\{A_{i,j} : 1 \leq i,j \leq n\}$.
Provide a method for finding the set $O \subset \Theta(n,g,s)$ such that $A \in O \implies \forall_{A' \in \Theta(n,g,s)} L(A) \geq A'$.
This problem corresponds to the following problem in english...
Assume there is a card game in which exactly $s$ players must participate. Now assume there is a card game league of $n$ players with a season of $g$ games. Create a schedule of games which maximizes the number of times each player plays each other player.
In the math above, $P$ corresponds to the set of all players.
$\Theta(n,g,s)$ is the set of all possible schedules where a schedule $A$ is a sequence of subsets of the players.
If $A$ is a valid schedule $A_{i,j}$ denotes the number games which include player $i$ and $j$ in $A$.
$O$ denotes the set of optimal schedules. i.e. the set of schedules for which the minimum encounters between any two players is maximized.
Is there a well known solution to this problem or a similar one? Many of the solutions I have seen deal with 1 on 1 matchups.
You can solve the problem via integer programming as follows. Let binary decision variable $x_{i,k}$ indicate whether player $i\in P$ plays in game $k\in\{1,\dots,g\}$. Let $z$ represent $\min_{1\le i<j \le n} \sum_k x_{i,k} x_{j,k}$, which is the minimum number of encounters across all pairs of players. The problem is to maximize $z$ subject to \begin{align} \sum_i x_{i,k} &= s &&\text{for all $k$} \tag1 \\ z &\le \sum_k x_{i,k} x_{j,k} &&\text{for all $1\le i<j\le n$} \tag2 \end{align} Constraint $(1)$ selects exactly $s$ players per game. Constraint $(2)$ enforces the maximin objective. You can linearize $(2)$ by introducing binary (or continuous) decision variable $y_{i,j,k}$ to represent $x_{i,k} x_{j,k}$ and replacing $(2)$ with linear constraints \begin{align} z &\le \sum_k y_{i,j,k} &&\text{for all $1\le i<j\le n$} \tag3 \\ y_{i,j,k} &\le x_{i,k} &&\text{for all $1\le i<j\le n$ and $k$} \tag4 \\ y_{i,j,k} &\le x_{j,k} &&\text{for all $1\le i<j\le n$ and $k$} \tag5 \end{align}
Note that the problem is highly symmetric with respect to player and game. If your solver does not automatically exploit such symmetry, you might want to explicitly impose symmetry-breaking constraints to improve the solve time.