Many platforms repeatedly pair two groups of people: drivers with riders, residents with hospitals, users with users on dating apps. The standard tool is the Gale-Shapley "deferred acceptance" algorithm, in which one side proposes and the other accepts or rejects. Its output is stable, meaning no two people would both rather leave their partners for each other. It is also lopsided. Every proposer gets their best partner among all stable matchings, and every receiver gets their worst. This is called proposer-optimal bias. A substantial literature now computes fairer stable matchings, but it assumes everyone's preferences are fixed and fully known. In real platforms, preferences drift: riders move, interest fades, new options change what people want. The only algorithm in the file that maintains stability under drift, Stable Matching with Evolving Preferences, keeps the matching nearly stable by re-running deferred acceptance. As a result, it reproduces the full proposer bias at every step.
This proposal argues that drift does more than bring back the classical bias. It creates two new sources of one-sided advantage that a fair static algorithm, re-run on each period's estimates, cannot remove. The first is repair initiative: when drift creates a blocking pair, someone must act to fix it. The second is measurement asymmetry: when preferences can only be learned through costly queries, a proposal-driven tracker learns proposers' lists far better than receivers' lists. We propose to build and test a matching tracker that balances both. We will measure fairness on the true, drifting preferences rather than on the system's estimates.
Core Claim
In a repeated matching market where preferences drift and must be queried, a tracker can look fair on its estimated preferences and still be unfair on the true ones. The gap favors whichever side initiates repairs and is queried more. Our claim is that the gap can be closed by two changes:
- Repairs alternate between the sides according to a running ledger of accumulated dissatisfaction.
- The query budget is split between the sides according to where estimation error most affects the fairness gap.
The combined tracker should approach the fairness of a full-information exact solver re-run every period, while using far fewer queries and causing far less turnover of partners.
The quantity we care about is the time-averaged signed gap measured on true ranks:
$$G_T = \frac{1}{T}\sum_{t=1}^{T}\left[\frac{1}{n}\sum_{m\in M}r^t_m(\mu_t(m)) - \frac{1}{n}\sum_{w\in W}r^t_w(\mu_t(w))\right].$$
Here $M$ and $W$ are the two sides, each of size $n$. The term $\mu_t$ is the matching held at period $t$, and $r^t_a(b)$ is the rank agent $a$ truly assigns partner $b$ at time $t$. The absolute value of the summand is the per-period sex-equality cost studied by Fair Procedures for Fair Stable Marriage Outcomes. The sign tells us which side is being favored.
The novelty lies in three choices. We define fairness over time rather than per snapshot. We evaluate on the truth rather than on estimates. We attribute any bias to specific mechanisms, namely who initiates repairs and how queries are allocated, rather than only to who proposes.
Relation to Prior Work
The fairness side supplies our methods.
- Equitable Stable Matchings in Quadratic Time introduced PowerBalance, which alternates proposals toward whichever side is currently worse off, followed by rotation-based local search (Deferred Local Search, DLS). We reuse its alternation idea but carry the "who is worse off" state across time.
- Balancing Bias in Two-sided Markets for Fair Stable Matchings gives ISORROPIA, an exact solver that prunes the rotation graph. A rotation is a cyclic exchange of partners that moves the matching toward the receivers' preferred end. ISORROPIA is our full-information oracle. Both methods assume static, complete preference lists. The research file notes that a single preference swap can create or dissolve rotations, so neither method can be updated incrementally.
The drift side supplies the regime.
- Kanade et al. model drift as random adjacent swaps that the algorithm does not observe. They show that periodically re-sorting and re-running deferred acceptance leaves $O(n\log n)$ blocking pairs. Their "window" strategy, which queries only the top $O(\log n)$ of each estimated list, achieves $O((\log n)^2)$. We adopt their query model and drift process. We depart from them by targeting the interior of the set of stable matchings instead of its proposer-optimal endpoint. Note that their window is designed around proposers' needs, which is exactly the measurement asymmetry we hypothesize.
- Competing Bandits in Non-Stationary Matching Markets handles drift under serial dictatorship, where agents pick in a fixed priority order. Its finding of "forced exploration" for low-priority agents is evidence that priority structures compound harm under drift. This motivates our claim, but its one-sided setting does not apply to our two-sided stability question.
- Active Learning for Fair and Stable Online Allocations chooses which agent to query using paired optimistic and pessimistic bounds. We borrow the idea of side-aware query selection, but its theory assumes static utilities and an exact fair-matching oracle, which is NP-hard here.
Two further lines motivate rather than constrain the work. Interactive-systems work shows that drift is often caused by exposure rather than being random. AcCoRD finds that agents handle preferences that appear only after an option is shown at rates as low as 0.09. Modeling needs user modeling argues that users refine their goals in response to the system. Both suggest that random adjacent swaps understate the drift a deployed matcher will face, so we add structured drift to our tests.
Research Program
We will build a tracker called Balanced Evolving Matching. It keeps a current matching and updates it each period in three steps.
Detection. The tracker spends a query budget on both sides' estimated top windows to find blocking pairs.
Repair. It starts from the current matching rather than rebuilding from scratch. Blocking pairs are resolved by a proposal process in which the right to propose goes to the side with the larger cumulative true-rank deficit on the dissatisfaction ledger. The ledger is estimated from queried ranks. A turnover penalty discourages re-matching agents unless doing so removes instability or reduces the ledger gap.
Query allocation. The budget is split between sides in proportion to an estimate of how much each side's rank uncertainty contributes to the uncertainty in $G_T$. This means the tracker deliberately queries receivers' comparisons among proposers, which a deferred-acceptance tracker rarely does.
Alongside the algorithm we will run an attribution analysis. Starting from Kanade et al.'s deferred-acceptance tracker, we switch on balanced repair alone, balanced querying alone, and both. This splits the signed gap $G_T$ into a part caused by repair initiative and a part caused by measurement asymmetry.
We will also attempt a modest theory result. Under Kanade et al.'s swap model, a tracker whose repairs come from one side and whose queries are proposal-driven should have a nonzero expected signed gap, even when its post-processing is fair on its estimates. The intuition is that receivers' rank errors do not average out, because the tracker only learns receivers' ranks near the proposers it happens to compare. We regard this as a target result, not a promise.
Baselines
Naive reference: periodic deferred acceptance. The do-nothing reference re-runs proposer-side deferred acceptance from scratch each period on fully queried lists. A variant alternates the proposing side each period. This shows the raw size of the bias and the turnover cost of swinging between the two extreme ends of the stable set. Every method gets the same drift sequences and the same total number of preference queries. For full re-sorting this baseline usually needs more queries than the budget allows, so we report it both at its natural cost and truncated to budget.
Strongest stability-under-drift method: Kanade et al.'s windowed tracker. We implement it as described, interleaving robust sorting and windowed queries with deferred acceptance. The cited guarantees are $O(n\log n)$ blocking pairs for the naive re-sort versus $O((\log n)^2)$ for the windowed method, as asymptotic bounds. No reported empirical fairness or sex-equality result under drift was found on Lacuna for this method. Beating it means matching its blocking-pair count within a small constant factor while cutting the absolute value of $G_T$ substantially.
Strongest fairness method: estimate-then-balance. This is the most dangerous competitor. We run Kanade et al.'s tracker to obtain estimated lists, then apply PowerBalance plus DLS (Tziavelis et al.), or ISORROPIA, to those estimates each period. It receives an identical query budget. Its tuning parameters, including PowerBalance's proposal budget and the local-search depth, get the same search budget as ours. On static instances, Wu et al. report that heuristics like PowerBalance and BiLS can leave dissatisfaction gaps up to 9 times the exact optimum. They also report that ISORROPIA finds the exact balanced matching in seconds on NYC Taxi instances with more than $10^6$ stable matchings, up to 1,000 times faster than enumeration. We therefore use ISORROPIA, not the heuristics, as the strongest fair post-processor. Beating it means a lower true $|G_T|$ and lower turnover at equal queries and equal blocking pairs.
Upper reference: full-information oracle. This is ISORROPIA re-run each period on the true lists. It bounds achievable per-period fairness and exposes its turnover cost.
Ablations. Two ablations isolate the key ingredients: balanced repair with deferred-acceptance-style querying, and balanced querying with one-sided repair.
Why not just…?
Why not just alternate which side proposes each period? Deferred acceptance always lands on one of the two extreme ends of the stable set. Alternating therefore flips every agent between their best and worst stable partners. This may produce a small time-averaged gap, but turnover will be maximal. Our turnover metric will show this directly. If alternation turns out to achieve low $|G_T|$ with turnover our users would tolerate, we will report that it suffices for fairness and that the remaining contribution concerns stability of assignments.
Why not just re-run an exact fair solver on estimated preferences each period? This is the estimate-then-balance baseline, and it is a real threat. If the measurement-asymmetry hypothesis is false, it will match our tracker on true $|G_T|$. In that case our contribution narrows to the turnover gained from warm-started repair. The attribution ablation settles this: if balanced querying adds nothing beyond balanced repair on true-rank fairness, we drop that claim.
Why not just query everyone fully and run the oracle? When queries are cheap, the oracle wins on per-period fairness by construction. We will sweep the query budget to locate where the oracle's cost becomes prohibitive. Kanade et al.'s analysis suggests full re-sorting is costly. We will also measure how far the oracle's sex-equal matching jumps between periods after small drifts. The exact optimum of an NP-hard objective can move discontinuously, which would make it a poor policy even when it is affordable.
Why not just drop stability and use Nash-welfare reciprocal recommendation? Tomita and Fu balance exposure in dating markets by maximizing the product of user utilities. On their Japanese dating data this cut envious male users from 434 to 31, at an 18% loss in expected matches. Their method allocates recommendation slots, not final pairs, so it gives no blocking-pair guarantee. Zhao et al. tie blocking pairs to driver defection in dispatch. We treat this approach as answering a different question rather than as a baseline.
Proposed Experiments
Synthetic markets. We use the synthetic families from Tziavelis et al. (uniform, Gaussian, and their discrete and correlated variants, at 2,000 to 4,000 agents) and Mallows-model markets. These are driven by two kinds of drift: Kanade et al.'s random adjacent swaps, and structured drift in which the Mallows central ranking moves steadily or a hidden attribute is "triggered" after exposure, following AcCoRD's taxonomy.
Real-data initializations. LibimSeTi supplies 17 million dating ratings to initialize two-sided preferences, with synthetic drift applied on top. The file does not indicate timestamps, so we do not claim natural drift there. NYC Taxi and Didi Chengdu GAIA give natural drift: preferences come from pickup distance and fare, and they change as vehicles and requests move over time.
Metrics. Every method is run at matched query budgets. We report:
- true time-averaged signed gap $G_T$ and its absolute value;
- per-period sex-equality and balance cost on true lists;
- blocking pairs per period;
- fraction of agents re-matched per period;
- queries per period.
Decisive checks. The first test is the measurement-asymmetry hypothesis itself. Under estimate-then-balance with deferred-acceptance-style querying, does the true gap $G_T$ show a consistent sign favoring proposers, while the gap computed on estimates is near zero? If not, the paper's central mechanism is wrong.
The second test asks whether our tracker beats estimate-then-balance on true $|G_T|$ and on turnover, without exceeding Kanade et al.'s blocking-pair counts by more than a constant factor across budgets.
The third test asks whether the advantage grows under structured drift relative to random swaps. Exposure-driven drift is systematic, so one-sided query errors should accumulate rather than average out.
References
- Stable Matching with Evolving Preferences
- Fair Procedures for Fair Stable Marriage Outcomes
- Equitable Stable Matchings in Quadratic Time
- Balancing Bias in Two-sided Markets for Fair Stable Matchings
- Competing Bandits in Non-Stationary Matching Markets
- Active Learning for Fair and Stable Online Allocations
- AcCoRD: Evaluating User-Agent Collaboration Under Realistic User Preference Dynamics
- Modeling needs user modeling
- Balancing Fairness and High Match Rates in Reciprocal Recommender Systems: A Nash Social Welfare Approach
- Preference-Aware Task Assignment in On-Demand Taxi Dispatching: An Online Stable Matching Approach