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

arXiv: https://arxiv.org/abs/2606.19883 · HTML: https://mlsanity.com/paper/2606.19883/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 18 Jun 2026.

## Builds on (most cited first, 10 of 10)

- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Cumulative Prospect Theory Meets Reinforcement Learning: Prediction and Control](https://mlsanity.com/paper/1506.02632/) (2015)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [A Survey of Risk-Aware Multi-Armed Bandits](https://mlsanity.com/paper/2205.05843/) (2022)
- [Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets](https://mlsanity.com/paper/2408.08690/) (2024)
- [Risk-sensitive Bandits: Arm Mixture Optimality and Regret-efficient Algorithms](https://mlsanity.com/paper/2503.08896/) (2025)
- [Bandit algorithms to emulate human decision making using probabilistic distortions](https://mlsanity.com/paper/1611.10283/) (2016)

## Abstract (arXiv)

We study a multi-agent multi-armed bandit problem in the competitive setup with two-sided matching markets under a human centric decision making model. To capture human preferences, we use cumulative prospect theory (CPT) that weighs the actions of the agent in a nonlinear fashion using a (α-H"older continuous) weight function. CPT has been widely used in behavioral economics and risk sensitive machine learning to emulate human preferences. We analyze the state-of-the-art learning algorithm with CPT weight distorted rewards and obtain a player optimal regret of O(Klog T left(frac1Deltaright)2/α), where K denotes the number of arms, T is the learning horizon, and Delta represents (suitably defined) players' minimum preference gap. Noticing the dependence on Delta to be sub-optimal, we further improve this regret by judiciously selecting the active set of arms during exploration, which removes the dependence on K in the dominant term and achieves an improved (optimal) regret guarantees in the setting where the number of arms K is significantly larger than the number of players N. In addition, we consider adversarial markets where the observed rewards of the agents may be corrupted. We propose and analyze algorithms for robust markets with CPT as risk sensitive measure in both settings where the total corruption budget is known and where it is unknown, and establish logarithmic player-optimal regret guarantees in both cases.