Improved Bandits in Many-to-one Matching Markets with Incentive
  Compatibility
Fang Kong Shuai Li
Two-sided matching markets have been widely studied in the literature due to
their rich applications. Since participants are usually uncertain about their
preferences, online algorithms have recently been adopted to learn them through
iterative interactions. \citet{wang2022bandit} initiate the study of this
problem in a many-to-one setting with \textit{responsiveness}. However, their
results are far from optimal and lack guarantees of incentive compatibility. An
extension of \citet{kong2023player} to this more general setting achieves a
near-optimal bound for player-optimal regret. Nevertheless, due to the
substantial requirement for collaboration, a single player's deviation could
lead to a huge increase in its own cumulative rewards and an $O(T)$ regret for
others. In this paper, we aim to enhance the regret bound in many-to-one
markets while ensuring incentive compatibility. We first propose the adaptively
explore-then-deferred-acceptance (AETDA) algorithm for responsiveness setting
and derive an $O(N\min\left\{N,K\right\}C\log T/\Delta^2)$ upper bound for
player-optimal stable regret while demonstrating its guarantee of incentive
compatibility, where $N$ represents the number of players, $K$ is the number of
arms, $T$ denotes the time horizon, $C$ is arms' total capacities and $\Delta$
signifies the minimum preference gap among players. This result is a
significant improvement over \citet{wang2022bandit}. And to the best of our
knowledge, it constitutes the first player-optimal guarantee in matching
markets that offers such robust assurances. We also consider broader
\textit{substitutable} preferences, one of the most general conditions to
ensure the existence of a stable matching and cover responsiveness. We devise
an online DA (ODA) algorithm and establish an $O(NK\log T/\Delta^2)$
player-pessimal stable regret bound for this setting.