Abstract
This paper investigates the exploration-exploitation trade-off in dynamic matching markets with finite lifetimes. Moving beyond traditional continuum models, the study explores a discrete, stochastic setting where randomness creates localized imbalances. We establish that the unavoidable utility loss for any strategy is tightly bounded at $\Theta(T\sqrt{T})$, where $T$ is the agent's lifetime. We further introduce a "Modified Reasonable Strategy" that achieves this asymptotic optimality through geometric partitioning of the state space.
Introduction
In matching markets like job searches or dating, agents face a fundamental "ticking clock" dilemma. Accepting a match too early risks missing a superior partner, while waiting too long reduces the time available to enjoy the match's benefits. Most existing economic literature utilizes "continuum" models that assume an infinite, smooth flow of agents. While mathematically elegant, these models fail to capture the "noise" and localized imbalances inherent in real-world discrete interactions—moments where specific demographics or "charm" levels are over- or under-represented. This paper addresses this gap by analyzing the discrete matching problem and the resulting "chaotic oscillations" that complicate the search for an ideal match.
Methodology
The market is modeled as a $T \times T$ grid, where axes represent an agent's cardinal "charm" value and their remaining lifetime. Agents enter the pool at age 0 and must match before reaching age $T$. To analyze this system, the authors introduce two key theoretical pillars:
- A Reasonable Notion of Loss: Rather than focusing solely on total utility, the paper defines "loss" as the discrepancy between an agent's actual utility and a baseline where they match with an equal-value partner for their entire lifetime.
- The Modified Reasonable Strategy: To establish an upper bound on loss, the authors propose a strategy that partitions the $T \times T$ state space into geometric "strips." Agents are restricted to matching with partners within their assigned strip. This approach leverages concentration inequalities (such as Chernoff bounds) to ensure that gender and population imbalances within these strips remain manageable over time.
The theoretical framework was validated using synthetic numerical simulations with $n=500$ agents per step and lifetimes $T$ ranging from 100 to 500. Each scenario was run for 2,000 iterations to observe long-term stability and variance.
Key Insights and Results
The transition from continuum to discrete models reveals significant costs. In discrete settings, the system does not converge to a simple steady state but instead suffers from "chaotic oscillations" due to random arrival patterns. Even with a large number of agents, the random arrival of specific types of people creates constant, localized friction.
The $\sqrt{T}$ Factor
The central finding is that the average loss scales with $T\sqrt{T}$. The $\sqrt{T}$ term represents the "tax" imposed by the uncertainty and variance of the discrete process. As agents age, they naturally become less demanding—a "desperation" that is proven to be rational given the diminishing remaining utility. The paper formalizes this "ticking clock" effect.
Theoretical Bounds
- Lower Bound (Theorem 3.1): The authors prove that no matter what strategy agents use, they will suffer an average loss of at least $\Omega(T\sqrt{T})$ with high probability.
- Upper Bound (Theorem 3.2): They demonstrate that the "Modified Reasonable Strategy" achieves an average loss of at most $O(T\sqrt{T})$, making it asymptotically optimal.
In simulations, the strategy performed even better than the theoretical worst-case bounds. For $n=500$ and $T=100$, the observed average loss was approximately $2.21 T\sqrt{T}$, indicating that the system is remarkably robust despite the oscillations observed in the discrete setting.
Conclusion and Future Work
This research provides a rigorous foundation for understanding discrete matching markets. However, several avenues for extension remain. The current model assumes "charm" is a common value; incorporating idiosyncratic private preferences would increase realism. Additionally, while uniform proposals are currently used, future work could explore recommendation algorithms to further reduce search costs. Finally, while simulations indicate stability, a formal proof that the system consistently returns to its typical range after rare, large deviations remains an open mathematical challenge.
Summary updated