CODEWITHSUNDEEP
pythonalgorithmmatching
JaGu
JaGu

Reputation: 11

Is there any matching algorithm to create groups of 4 players according to their level of play?

In a sport known as padel tennis people organize games in groups of 4. Each player has a "level of play" assigned: from 1 (for beginners) to 7 (for professional players). It can have 1 decimal.

Problem objective: maximize the number of Groups of 4 players created.

Data. 2 datasets: one for players that publish games and other one for players that look for games. Each dataset with columns for player's ID and Level of play.

Constraint. Publisher's Level of play fixes the gap for the players that can join: +-0.5. Note: if publisher's Level of play is 7, the gap for the players who join is from 6 to 7. If it is 1, then the gap is from 1 to 2.

Assumption: when publishing a game, the player does it alone, so he/she expects 3 more people to join, individually (from the other dataset). There are more players in the second dataset.

Variations of the problem: study the different outcomes when varying % of pairs in the second dataset (which initially is zero). Extra combinations, transforming the first dataset into pairs. Remark: when creating pairs for analyzing a variation of the problem, create them with the Level of play gap criteria of +-1. Bigger goal would be to know which combination creates more games.

Additional problem (?): computational capacity to run all the possible matchings.

Friend has recommended me python or VBA Excel to run the different matching simulations but I am open to suggestions. Thank you for reading and hopefully answering with some hints of where to start :) PS: I have very little experience in python.

Upvotes: 1

Views: 217

Answers (1)

kcsquared
kcsquared

Reputation: 5409

The main problem is solvable by sorting, and greedily matching 'publisher' players to groups of 3 'searching' players.

Each publisher corresponds to an interval of length 1, which are the acceptable skill levels of players in their game. Sort these intervals by their right endpoint. Also sort the 'searching' players by their level.

Now, walk through both lists simultaneously. While there are at least 3 searching players and at least 1 interval to be considered, look at the smallest 3 players, p1, p2, and p3, and the smallest interval, I = [left, right]. There are three cases:

  1. If right < p3, then we can't ever match this interval, so discard it.
  2. Else if p3 <= right but left > p1, then discard p1 from consideration.
  3. Otherwise, this is a valid match, so record 'Interval I matched players (p1,p2,p3)' and remove I, p1, p2, and p3 from consideration.

Repeating these steps will give the maximum possible number of groupings. This can be proven by similar methods as the proof for greedy interval scheduling.

As an example of the algorithm running:

Publishing Players [1.0, 2.5, 3.2, 3.5]
Corresponding intervals: ([1.0-2.0], [2.0-3.0], [2.7-3.7], [3.0-4.0])

Searching Players [1.0, 2.2, 2.5, 2.9, 3.0, 3.4, 3.8]

Loop iterations:
Iteration 1:
I =          [1.0, 2.0]
p1, p2, p3 = [1.0,      2.2, 2.5]
I's right end too small, discard I

Iteration 2:
I =               [2.0,          3.0]
p1, p2, p3 = [1.0,      2.2, 2.5]
p1 too small, discard p1

Iteration 3:
I =         [2.0,              3.0]
p1, p2, p3 =    [2.2, 2.5, 2.9]
Match found: discard I, p1, p2, p3

Iteration 4:
I =         [2.7,          3.7]
p1, p2, p3 =    [3.0, 3.4,     3.8]
I's right end too small, discard I

Iteration 5:
I =          [3.0,          4.0]
p1, p2, p3 = [3.0, 3.4, 3.8]
Match found: discard I, p1, p2, p3

Out of players or intervals: done.

If you generalize the problem, for example so that 'gap intervals' do not all have the same length or they have different values/weights, the greedy method no longer works, and a dynamic programming approach is needed.

Upvotes: 1

Related Questions