1
$\begingroup$

The setting is the following: There are n players that want to compete in a specific game over the course of an event. A game is played between 2 teams of 2 players each (so a 2v2). Each player as a general rating value based on the ELO-System and it is assumed that the combined rating of a team is the mean of the members ratings. Over the course of one event the ratings of the players are not changed, that is done after all games are finished.

The task is the following: For those n players and an input number k, calculate a schedule of k matches to be played such that:

  1. Every player should play equally many times, if possible, and if not, no player a should play two games more than another player b.
  2. One team can only play in one match. (So if player a and player b are matched in one game playing against some enemy team, they will not be matched for a team again)
  3. The matches should be as fair as possible, fair meaning that the ratings of the opposing teams are roughly equal. I am not sure what the best metric for that might be, but I suppose using something like a mean squared error over the differences in rating of all the matches generated should do.

I think solving this perfectly is probably a very hard problem, so I guess I am looking for some kind of estimation. Condition (1) is the most important and must always be satisfied.

Until now I only have a solution for generating good teams instead of games based on a weighted maximum matching problem (approach coming from here), but I would love to implement the problem described above.

Edit:

It does not matter in which order the generated games take place and all games are played out sequentially, not in parallel (which means there is no need to optimize for games happening at the same time).

$\endgroup$
1
  • $\begingroup$ Do you want to have multiple matches played at the same time? Does the schedule just describe the set of matches to be played, or also the times at which they should be played? $\endgroup$
    – D.W.
    Commented Mar 1, 2023 at 18:21

1 Answer 1

0
$\begingroup$

There are many plausible approaches, but one that would be easy to implement would be to formulate this as an instance of integer linear programming (a classic technique in operations research, which your problem could be considered an example of).

Introduce zero-or-one variables $x_{a,i,t}$, with the intended meaning that $x_{a,i,t}=1$ means that player $a$ plays on team $t$ ($t=0$ or $t=1$) in the $i$th match. Also introduce variables $m$, the minimum number of matches per player, and $d_i$, the difference in rating between two teams who are playing each other in round $i$. (I am using the sum of differences in ratings in each round rather than mean squared difference as my metric of "roughly equal", to make this expressible as integer linear programming.) Also introduce variables $y_{a,b,i,t}$, with the intended meaning that $y_{a,b,i,t}=\min(x_{a,i,t},x_{b,i,t})$, i.e., $y_{a,b,i,t}=1$ iff both $a$ and $b$ are paired together on team $t$ in the $i$th round.

Then we can introduce linear inequalities to enforce that these variables are set consistently and comply with your requirements, e.g.,

  • $m \le \sum_{i,t} x_{a,i,t} \le m+2$ for all $a$
  • $\sum_{i,t} y_{a,b,i,t} \le 1$ for all $a,b$ with $a \ne b$
  • $\sum_a \text{rating}(a) \cdot x_{a,i,0} \le \sum_a \text{rating}(a) \cdot x_{a,i,1} + d_i$, $\sum_a \text{rating}(a) \cdot x_{a,i,0} \ge \sum_a \text{rating}(a) \cdot x_{a,i,1} - d_i$ for all $i$
  • $y_{a,b,i,t} \le x_{a,i,t}$, $y_{a,b,i,t} \le x_{b,i,t}$, $y_{a,b,i,t} \ge x_{a,i,t} + x_{b,i,t}-1$
  • $\sum_a x_{a,i,t} = 2$ for all $i,t$
  • $x_{a,i,0} + x_{a,i,1} \le 1$ for all $a,i$

Then your goal is to minimize $\sum_i d_i$.

$\endgroup$
4
  • $\begingroup$ This definitely looks good, thank you! My only concern right now is that metric to decide if a set of games is roughly fair, I feel like if the d you propose is at best still pretty high, every game might still be too unfair to be acceptable. Is there a way to improve on that? $\endgroup$
    – libra
    Commented Mar 1, 2023 at 21:34
  • $\begingroup$ @libra, another approach is to use the $L_1$ metric instead of $L_\infty$ as in my answer or $L_2$ as in your question. In particular, use a separate $d_i$ for each $i$, and then minimize $\sum_i d_i$. Is that better? $\endgroup$
    – D.W.
    Commented Mar 2, 2023 at 3:19
  • $\begingroup$ I probably need to experiment with it. However, with the set of conditions right now it’s possible for a player a to be on two opposing teams at once right? $\endgroup$
    – libra
    Commented Mar 2, 2023 at 10:18
  • $\begingroup$ @libra, OK, I updated my answer accordingly. I changed to use $L_1$ instead of $L_\infty$. Also, good point about one player being on opposing teams. I've edited my answer to fix this, by adding the last linear inequality. $\endgroup$
    – D.W.
    Commented Mar 2, 2023 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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