20.23 Building a Matchmaking System

Design a matchmaking system that pairs users, players, tasks, or entities according to compatibility rules.

algorithmscase-studiessystems

20.23 Building a Matchmaking System

Problem

Design a matchmaking system that pairs users, players, tasks, or entities according to compatibility rules.

Matchmaking appears in multiplayer games, marketplaces, job platforms, tutoring systems, dating apps, mentoring programs, ride-sharing systems, reviewer assignment tools, and distributed work schedulers. The input is a set of participants and preferences. The output is a set of matches.

Example:

players:
A rating=1200 region=asia
B rating=1230 region=asia
C rating=1700 region=europe
D rating=1710 region=europe

A reasonable match set is:

A vs B
C vs D

The core algorithmic problem is matching under constraints. The engineering problem is balancing fairness, speed, quality, and business rules.

Solution

Start with a greedy matcher over a compatibility score. For each unmatched participant, find the best currently available partner that satisfies hard constraints.

A participant model:

from dataclasses import dataclass
import math

@dataclass(frozen=True)
class Player:
    id: str
    rating: int
    region: str
    wait_seconds: int = 0

Hard constraints:

def compatible(left, right, max_rating_gap=200):
    if left.id == right.id:
        return False

    if left.region != right.region:
        return False

    if abs(left.rating - right.rating) > max_rating_gap:
        return False

    return True

Scoring:

def match_score(left, right):
    rating_penalty = abs(left.rating - right.rating)
    wait_bonus = left.wait_seconds + right.wait_seconds

    return -rating_penalty + 0.1 * wait_bonus

Higher score means better match.

Greedy Pairing

A simple greedy matcher scans possible pairs and repeatedly takes the best available pair.

def greedy_match(players):
    candidates = []

    for i, left in enumerate(players):
        for right in players[i + 1:]:
            if compatible(left, right):
                candidates.append((
                    match_score(left, right),
                    left.id,
                    right.id,
                ))

    candidates.sort(reverse=True)

    matched = set()
    matches = []

    for score, left_id, right_id in candidates:
        if left_id in matched or right_id in matched:
            continue

        matched.add(left_id)
        matched.add(right_id)

        matches.append({
            "left": left_id,
            "right": right_id,
            "score": score,
        })

    return matches

Example:

players = [
    Player("A", 1200, "asia"),
    Player("B", 1230, "asia"),
    Player("C", 1700, "europe"),
    Player("D", 1710, "europe"),
]

print(greedy_match(players))

Possible output:

[
  {'left': 'C', 'right': 'D', 'score': -10.0},
  {'left': 'A', 'right': 'B', 'score': -30.0}
]

This works well as a first version. It is easy to explain and test.

Hard Constraints vs Soft Preferences

Separate hard constraints from soft preferences.

Hard constraints reject a match entirely:

different game mode
blocked users
incompatible language
invalid region
rating gap too large

Soft preferences affect ranking:

closer rating is better
shorter latency is better
longer wait time deserves priority
same language is better
previously matched pair is worse

This separation prevents accidental policy confusion. A soft preference should not silently become a hard rejection.

Relaxing Constraints Over Time

Matchmaking often relaxes rules as users wait.

A new player may initially require:

rating gap <= 100
same region
latency <= 50 ms

After waiting 60 seconds:

rating gap <= 250
same region
latency <= 100 ms

After waiting 180 seconds:

rating gap <= 500
nearby region allowed
latency <= 150 ms

Implement dynamic thresholds:

def allowed_rating_gap(wait_seconds):
    if wait_seconds >= 180:
        return 500

    if wait_seconds >= 60:
        return 250

    return 100

Use the more patient player's wait time:

def compatible_dynamic(left, right):
    effective_wait = max(left.wait_seconds, right.wait_seconds)
    max_gap = allowed_rating_gap(effective_wait)

    if left.region != right.region:
        return False

    return abs(left.rating - right.rating) <= max_gap

This improves match rate while preserving quality for users who have not waited long.

Stable Matching

Some domains need stability rather than only high scores.

In stable matching, participants rank possible partners. A matching is stable if there is no unmatched pair that would both prefer each other over their current assignments.

This is useful for:

students and schools
residents and hospitals
mentors and mentees
reviewers and papers

A simplified Gale-Shapley implementation:

from collections import deque

def stable_matching(proposer_preferences, receiver_preferences):
    free = deque(proposer_preferences.keys())
    next_choice = {
        proposer: 0
        for proposer in proposer_preferences
    }

    current_match = {}
    receiver_rank = {
        receiver: {
            proposer: rank
            for rank, proposer in enumerate(preferences)
        }
        for receiver, preferences in receiver_preferences.items()
    }

    while free:
        proposer = free.popleft()
        preferences = proposer_preferences[proposer]

        if next_choice[proposer] >= len(preferences):
            continue

        receiver = preferences[next_choice[proposer]]
        next_choice[proposer] += 1

        if receiver not in current_match:
            current_match[receiver] = proposer
            continue

        incumbent = current_match[receiver]

        if receiver_rank[receiver][proposer] < receiver_rank[receiver][incumbent]:
            current_match[receiver] = proposer
            free.append(incumbent)
        else:
            free.append(proposer)

    return {
        proposer: receiver
        for receiver, proposer in current_match.items()
    }

Stable matching optimizes for stability, not necessarily total score. Choose it when participants have ordered preferences and blocking pairs matter.

Bipartite Assignment

Some matchmaking problems are bipartite:

workers -> tasks
drivers -> riders
reviewers -> papers
students -> projects

Each match has a cost or score. The goal is to maximize total score or minimize total cost.

For small cases, brute force is acceptable.

import itertools

def best_assignment(left_items, right_items, score):
    best = None
    best_score = -math.inf

    for permutation in itertools.permutations(right_items, len(left_items)):
        total = 0
        pairs = []

        for left, right in zip(left_items, permutation):
            value = score(left, right)
            total += value
            pairs.append((left, right))

        if total > best_score:
            best_score = total
            best = pairs

    return best, best_score

This is factorial time and only suitable for tiny examples. Production systems use algorithms such as the Hungarian algorithm, min-cost max-flow, or specialized optimization solvers.

Min-Cost Flow Model

Many real matchmaking systems fit a flow model.

source -> participants -> opportunities -> sink

Edges encode eligibility and costs.

Examples:

Constraint Flow encoding
Each user gets at most one match Capacity 1
Task needs three workers Capacity 3
Reviewer can review five papers Capacity 5
Match quality Edge cost
Hard incompatibility No edge

This is more complex than greedy matching, but it supports capacity constraints and global optimality.

Use greedy matching when simplicity and latency matter. Use flow or assignment when global quality and fairness matter.

Queue-Based Matchmaking

Online matchmaking works over a waiting pool.

class MatchmakingQueue:
    def __init__(self):
        self.players = {}

    def join(self, player):
        self.players[player.id] = player

    def leave(self, player_id):
        self.players.pop(player_id, None)

    def match_once(self):
        matches = greedy_match(list(self.players.values()))

        for match in matches:
            self.players.pop(match["left"], None)
            self.players.pop(match["right"], None)

        return matches

In a real service, wait time should update continuously. Store join timestamps instead of static wait seconds.

@dataclass(frozen=True)
class QueuedPlayer:
    id: str
    rating: int
    region: str
    joined_at: float

Compute wait time at match time.

Fairness

A pure score maximizer may repeatedly favor easy-to-match users and leave hard-to-match users waiting.

Fairness techniques include:

Technique Effect
Wait-time bonus Prioritizes patient users
Maximum wait target Forces relaxation
Diversity constraints Avoids homogeneous matches
Quotas Ensures allocation across groups
Round-robin queues Prevents starvation
Randomization Reduces deterministic bias

Fairness must be defined for the product. In games, it may mean balanced skill and low latency. In review assignment, it may mean equal workload. In hiring, it may involve legal and policy constraints that require careful review.

Avoiding Repeat Matches

Some systems should avoid pairing the same participants repeatedly.

Store recent pair history.

def pair_key(left_id, right_id):
    return tuple(sorted((left_id, right_id)))

Apply a penalty:

def match_score_with_history(left, right, recent_pairs):
    score = match_score(left, right)

    if pair_key(left.id, right.id) in recent_pairs:
        score -= 1000

    return score

For a hard ban, reject the pair instead.

def compatible_with_history(left, right, recent_pairs):
    if pair_key(left.id, right.id) in recent_pairs:
        return False

    return compatible(left, right)

Whether repetition is acceptable depends on the domain.

Group Matchmaking

Some systems need groups rather than pairs.

Example:

5 players per team
2 teams per match

A simple approach:

  1. Sort players by rating.
  2. Form a candidate group.
  3. Split into balanced teams.
def form_group(players, group_size):
    players = sorted(
        players,
        key=lambda player: player.wait_seconds,
        reverse=True,
    )

    return players[:group_size]

Split balanced teams greedily:

def split_balanced_teams(players):
    ordered = sorted(
        players,
        key=lambda player: player.rating,
        reverse=True,
    )

    team_a = []
    team_b = []
    sum_a = 0
    sum_b = 0

    for player in ordered:
        if sum_a <= sum_b:
            team_a.append(player)
            sum_a += player.rating
        else:
            team_b.append(player)
            sum_b += player.rating

    return team_a, team_b

This heuristic is simple and often reasonable. Exact balanced partitioning is a combinatorial optimization problem.

Metrics

A matchmaking system needs operational and quality metrics.

Track:

Metric Meaning
queue_size Waiting participants
match_rate Matches per minute
average_wait_time User wait experience
p95_wait_time Tail latency
average_rating_gap Match quality
region_mismatch_rate Relaxation pressure
cancellation_rate Users leaving before match
rematch_rate Repeated pair frequency
unmatched_count Starvation signal

Quality metrics should be segmented by region, rating band, mode, and time of day. Aggregate averages can hide bad experiences for small groups.

Testing

Test basic pairing.

def test_greedy_match_pairs_compatible_players():
    players = [
        Player("A", 1000, "asia"),
        Player("B", 1050, "asia"),
    ]

    matches = greedy_match(players)

    assert len(matches) == 1
    assert {matches[0]["left"], matches[0]["right"]} == {"A", "B"}

Test incompatible regions.

def test_different_regions_do_not_match():
    players = [
        Player("A", 1000, "asia"),
        Player("B", 1000, "europe"),
    ]

    assert greedy_match(players) == []

Test rating gap.

def test_rating_gap_blocks_match():
    players = [
        Player("A", 1000, "asia"),
        Player("B", 1500, "asia"),
    ]

    assert greedy_match(players) == []

Test wait-based relaxation.

def test_wait_time_relaxes_rating_gap():
    left = Player("A", 1000, "asia", wait_seconds=180)
    right = Player("B", 1400, "asia", wait_seconds=10)

    assert compatible_dynamic(left, right) is True

These tests check the policy before optimizing the matcher.

Common Bugs

The most common matchmaking bug is mixing hard constraints and soft preferences. A penalty is not the same as a rejection.

Another common bug is greedy local matching that produces poor global results. This matters when match quality is coupled across many participants.

Users can starve if wait time is not part of the score or relaxation policy.

Distributed queues can match the same user twice unless joins, leaves, and matches are atomic.

Pair history can grow without bound. Keep a time-bounded or count-bounded history.

Group matchmaking can look balanced by average rating while still producing unfair role or latency distribution.

Metrics can hide bad tail behavior. Always inspect p95 or p99 wait time, not only averages.

Recipe

Build the system in layers.

Start with a clear participant model. Separate hard compatibility checks from soft scoring. Implement greedy pair matching as a baseline. Add wait-time relaxation to avoid starvation. Add recent-pair penalties when repetition is undesirable. Use stable matching when participant preferences matter. Use assignment or flow algorithms when global optimality and capacity constraints matter. For groups, form candidate pools and then balance teams. Track queue size, wait time, match rate, quality, cancellations, and tail behavior.

The main lesson is that matchmaking is constrained optimization under time pressure. Greedy algorithms give fast useful matches, but fairness, stability, global quality, and operational safety determine whether the system behaves well in production.