Fatigue-Aware Degree Budgets for Reciprocal Recommendation

On two-sided platforms such as dating apps and job boards, a match needs both people to say yes. The users everyone wants receive far more inbound contact than they can answer. Their reply rates fall over time, and today's systems read that decline as "preference drift": the person's tastes changed, so old data should be discounted. This proposal tests a different explanation. Much of that apparent drift is fatigue caused by the recommender itself, because it keeps routing people to the same few users. If so, drift and capacity are the same phenomenon seen from two sides. The right fix is then a degree budget that regenerates over time: each user can absorb only so much recent inbound attention, and that capacity recovers as their load decays. Discounting old data does not fix the problem, and neither does a fixed cap.

The idea, in two sentences: model each user's willingness to respond as decreasing in their recent, exponentially decayed inbound load, and allocate recommendations under that moving capacity instead of a static cap or a static preference matrix. This single model has two known settings as its endpoints. When load is forgotten instantly, it reduces to per-round capacity matching. When load is never forgotten, it reduces to the hard degree-bounded matching studied in online algorithms. It therefore offers a principled answer to a real conflict between the two literatures.

Core Claim

The degree-constraint literature and the drift literature give opposite advice about history. Degree-bounded Online Bipartite Matching: OCS vs. Ranking shows that when offline nodes can be matched at most $d$ times, an online algorithm should condition on each node's accumulated degree. Its degree-aware correlated selection beats the classical random-rank Ranking algorithm, with a competitive ratio of at least 0.875 versus Ranking's 0.8264 upper bound at $d=2$. The drift literature warns that leaning on accumulated history causes preference inertia. Right Now, Wrong Then responds by exponentially down-weighting old preference data, and Continual Low-Rank Adapters for LLM-based Generative Recommender Systems responds by letting a single adapter move toward new preferences under a proximal anchor.

Our claim is that in reciprocal markets the conflict dissolves once the state variable is right. That variable is decayed inbound load, $L_j(t)=\sum_{s<t}\delta^{\,t-s}x_j(s)$. Here $x_j(s)$ is the number of inbound recommendations or contacts user $j$ received in period $s$, and $\delta\in[0,1]$ is a per-population memory parameter. We model the probability that $j$ accepts $i$ at time $t$ as

$$p_{ij}(t)=\sigma\big(u_{ij}-\lambda_j L_j(t)\big),$$

where $u_{ij}$ is a slowly varying affinity score, $\lambda_j\ge 0$ is $j$'s sensitivity to load, and $\sigma$ is the logistic function. The functional form borrows the exponentially decaying annoyance memory that Ads that Stick used for single-user ad exposure. We apply it to inbound load on the receiving side of a two-sided market, which that paper does not consider.

The claim makes a testable prediction. If fatigue explains a meaningful share of declining reply rates, then:

  • $L_j(t)$ predicts $j$'s replies beyond what calendar time and user fixed effects predict;
  • policies that keep $L_j$ below a threshold should produce more mutual matches than policies that only re-weight data by recency.

Research Program

The work has three parts.

Measurement. On interaction logs with timestamps, we fit the acceptance model above against two competitors. The first is a recency-discounted static-affinity model, the reciprocal analogue of the time-varying reward in Non-Stationary DPO. The second is a model with free per-period user drift terms. We then ask how much out-of-sample reply prediction comes from load rather than from time.

The main identification risk is that popular users are both heavily loaded and inherently choosy. We therefore rely on within-user variation: the same user's load rises and falls with platform-wide traffic fluctuations. The test is whether their reply rate moves with that fluctuation.

Allocation. We build two policies under the regenerating budget.

The offline/batch version keeps the doubly stochastic Sinkhorn machinery of Balancing Fairness and High Match Rates in Reciprocal Recommender Systems, which maximizes a Nash-welfare (product-of-utilities) objective over recommendation lists. We change two things:

  • each round's column capacities are set from $L_j(t)$ rather than held fixed;
  • expected utilities are the load-adjusted $p_{ij}(t)$.

That paper names time-evolving preferences as its open problem. Our contribution is to treat part of that evolution as a consequence of the allocation itself.

The online version replaces the accumulated degree that correlated selection conditions on with decayed load. We will try to prove a competitive ratio that interpolates in $\delta$. At $\delta=1$ it must recover the hard-bound guarantees of Feng et al. as a sanity check. For $\delta<1$ we compare against an offline optimum that knows the fatigue dynamics. We treat the proof as a stretch goal; the empirical program does not depend on it.

Evaluation. Because allocation changes future load, logged data cannot evaluate policies directly. We use semi-synthetic simulators fitted to the logs, and we report results under simulators with and without fatigue, so that the method is not graded only by a world built to favor it.

Baselines

The naive reference point is independent unilateral ranking. Each side gets a BPR-style collaborative filter (a standard pairwise ranking model trained on implicit feedback), and recommendations are top-$k$ with no capacity coordination or time weighting. It shows how much any coordination buys at all. Revisiting Reciprocal Recommender Systems shows this baseline wastes display slots on redundant pairs, although no reported number for the size of that loss was found on Lacuna.

The strongest existing competitor on the capacity side is Nash-welfare Sinkhorn allocation from Tomita and Fu. It spreads attention away from hubs, so it may capture most of the fatigue benefit without modeling fatigue. On their Japanese dating dataset it cut envious male users from 434 to 31, at the cost of an 18% reduction in total expected matches. The Japanese dataset is not available to us, so we cannot compare on it directly. What matters is the shape of that tradeoff. Beating this baseline means at least one of two outcomes:

  • more realized mutual matches at equal or lower Gini and envy;
  • the same match count with lower inequality.

The strongest competitor on the drift side is the same Sinkhorn allocator fed recency-discounted affinities, with exponential weighting in the style of Non-Stationary DPO. That paper reports length-controlled win rate rising from 7.29 to 8.93 on UltraFeedback-LM over static DPO, but that is a language-model alignment result. No reported result was found on Lacuna for time-discounted reciprocal recommendation, so this combination is our own construction.

We also include:

All methods share the same affinity backbone, the same train/test chronology, the same per-round slot budget, and the same hyperparameter search budget. For our method that search covers $\delta$ and the $\lambda$ prior. For the discounted baseline it covers the discount rate. For the capped baseline it covers the cap.

The key ablation sets $\lambda_j=0$ while keeping everything else. This isolates whether load-dependent acceptance, rather than time-varying capacity alone, drives any gain.

Why not just…?

Why not just discount old data by recency and re-run Nash-welfare allocation each period? This is the most serious alternative, and it may work well when drift is truly exogenous. It fails under fatigue for a mechanical reason: it learns that a hub stopped replying only after that hub's replies collapse, and it keeps routing traffic there until the evidence arrives. It also cannot predict that the hub recovers once load falls, so it under-recommends recovered users for as long as the discount window remembers their bad period. The measurement study settles this directly. If load adds nothing beyond time in held-out reply prediction, this baseline is the right answer, and we will report that.

Why not just impose a fixed daily cap on inbound recommendations? A cap is a regenerating budget with $\delta=0$ and a uniform threshold, so it sits inside our model family and is tuned with the same budget. Ads that Stick shows that, when annoyance memory persists ($\delta\approx0.98$), uniform spacing underperforms the optimized schedule by at least 10% in reward. That evidence is about one user's ad exposure, though, not about two-sided markets. If the fitted $\delta$ on real logs is near zero and $\lambda_j$ is nearly homogeneous, caps will tie our method. We treat that as a real outcome, not a failure of the comparison.

Why not just rely on Nash welfare, which already spreads attention away from popular users? Nash welfare spreads attention according to estimated utilities. It flattens hubs uniformly when it should flatten them in proportion to each user's load sensitivity. The difference should appear when $\lambda_j$ varies across users: some popular users tolerate heavy inbound volume and some do not. We test this explicitly by stratifying results by fitted $\lambda_j$ and by running simulators with homogeneous versus heterogeneous sensitivity. If the gap vanishes in both, the fatigue model is unnecessary.

Why not just continually retrain the affinity model, as PESO does? Continual adaptation tracks a moving target in representation space. It has no notion that the platform's own allocation moves that target. It is complementary rather than competing: we use it as the affinity backbone in all arms, so any gain we report is on top of it.

Proposed Experiments

Data. The primary real data is the BOSS Zhipin recruitment dataset and the Libimseti dating data used by Yang et al. and Gentile et al. We use inbound applications or messages as the load proxy and replies as acceptance. A known risk is that the released Libimseti extracts may lack usable timestamps. If so, the measurement study runs on BOSS Zhipin alone and Libimseti is used only for affinity fitting. The controlled settings are the Speed Dating dataset and synthetic two-sided markets of Gentile et al.'s 2,000-by-2,000 design, extended with a known fatigue mechanism and known exogenous drift.

Decisive check 1: is fatigue real? The first and most decisive check is the measurement study. Using a within-user analysis, we test whether a one-standard-deviation increase in decayed inbound load predicts a drop in reply probability. We compare held-out log-loss against the recency-discount model and the free-drift model.

  • If the load coefficient is indistinguishable from zero, the allocation program is abandoned, and the contribution becomes a negative result on fatigue as a source of drift.
  • If it is clearly nonzero, we report the fitted $\delta$ and the spread of $\lambda_j$, which determine whether caps or Nash welfare could suffice.

Decisive check 2: does allocation exploit it? In semi-synthetic simulators calibrated to these fits, we compare all baselines on:

  • realized mutual matches;
  • coverage-adjusted recall (CRecall);
  • Gini index of matches;
  • envious pairs;
  • hub reply rate over time.

We run three simulator variants: fatigue only, exogenous drift only, and both. The proposal succeeds if the load-aware policy wins clearly under fatigue and stays within noise of the recency-discount baseline under pure exogenous drift. Losing badly in the no-fatigue world would mean the method overfits its own assumption.

Decisive check 3: online regime. On synthetic adversarial and stochastic arrival sequences, we compare the decayed-load correlated-selection policy against Ranking and hard-degree correlated selection. At $\delta=1$ it must reproduce Feng et al.'s behavior. As $\delta$ decreases, we track where hard-degree conditioning starts to "favor the old" in a harmful way.