Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning
For researchers in online learning and behavioral economics, this work extends matching market bandits to human-centric CPT preferences and adversarial robustness, though the novelty is incremental as it adapts existing algorithms to a new preference model.
This paper studies multi-agent multi-armed bandit problems in two-sided matching markets under cumulative prospect theory (CPT) preferences, achieving player-optimal regret of O(K log T (1/Δ)^{2/α}) and improved regret independent of K when K >> N. It also provides robust algorithms for adversarial reward corruption with logarithmic regret guarantees.
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ölder 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 $\mathcal{O}(K\log T \left(\frac{1}Δ\right)^{2/α})$, where $K$ denotes the number of arms, $T$ is the learning horizon, and $Δ$ represents (suitably defined) players' minimum preference gap. Noticing the dependence on $Δ$ 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.