Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning

Traditional matching market algorithms often assume agents maximize expected rewards. However, human decision-making frequently exhibits behavioral biases, such as loss aversion and non-linear probability weighting, which are better captured by Cumulative Prospect Theory (CPT). This paper investigates how agents can learn to reach a player-optimal stable matching in competitive markets when their preferences are governed by CPT-distorted rewards rather than simple averages.

The authors adapt the Explore-Then-Gale-Shapley (ETGS) framework to incorporate CPT-based utility estimation. They utilize a quantile-based estimator that processes empirical reward distributions to compute distorted utilities. To address the sub-optimality of standard exploration, they propose an 'Improved CPT-ETGS' algorithm that adaptively selects an active set of arms, effectively reducing unnecessary exploration. Furthermore, the authors address adversarial market conditions by modifying confidence intervals to account for potential reward corruption, providing robust guarantees for both known and unknown corruption budgets.

The study establishes that the CPT-ETGS algorithm achieves a player-optimal regret of O(K log T / Δ^(2/α)), where K is the number of arms, T is the time horizon, Δ is the minimum preference gap, and α is the Hölder continuity coefficient of the weighting function. By refining the exploration strategy, the Improved CPT-ETGS algorithm achieves optimal regret bounds that match theoretical lower bounds in large markets (where K ≫ N). Additionally, the authors demonstrate that even under adversarial corruption, logarithmic regret is achievable by widening confidence intervals to account for the distortion and corruption simultaneously.

This work bridges the gap between behavioral economics and multi-agent reinforcement learning. By moving beyond risk-neutral reward models, the proposed algorithms provide a more realistic framework for real-world matching platforms—such as labor markets or ride-sharing apps—where human participants may prioritize avoiding catastrophic outcomes over maximizing average gains. The inclusion of robustness to corruption further enhances the applicability of these models to practical, potentially adversarial digital environments.