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.

在这篇论文中，我们介绍了适应性的探索 - 延迟接受算法（AETDA）用于回应性设置，并得到了一个玩家最优稳定遗憾的 O (Nmin {N,K} ClogT/Δ²) 上界，同时证明了它的激励兼容性保证。我们还考虑了更广泛的可替代偏好，在此设置中设计了一种在线 DA（ODA）算法，并为其建立了一个 O (NKlogT/Δ²) 的玩家最差稳定遗憾界限。

通过激励兼容性在多对一匹配市场中改进的赌博算法

Improved Bandits in Many-to-one Matching Markets with Incentive  Compatibility

We study the problem of online learning in competitive settings in the
context of two-sided matching markets. In particular, one side of the market,
the agents, must learn about their preferences over the other side, the firms,
through repeated interaction while competing with other agents for successful
matches. We propose a class of decentralized, communication- and
coordination-free algorithms that agents can use to reach to their stable match
in structured matching markets. In contrast to prior works, the proposed
algorithms make decisions based solely on an agent's own history of play and
requires no foreknowledge of the firms' preferences. Our algorithms are
constructed by splitting up the statistical problem of learning one's
preferences, from noisy observations, from the problem of competing for firms.
We show that under realistic structural assumptions on the underlying
preferences of the agents and firms, the proposed algorithms incur a regret
which grows at most logarithmically in the time horizon. Our results show that,
in the case of matching markets, competition need not drastically affect the
performance of decentralized, communication and coordination free online
learning algorithms.

在双边撮合市场中，我们研究了竞争环境下在线学习的问题，如一方的代理人必须通过重复互动了解对另一方的企业的偏好，并与其他代理人竞争成功匹配。我们提出了一类分散、不需要协调的算法，代理人可以使用该算法在结构化匹配市场中达到稳定匹配，其决策仅基于代理人自己的游戏历史，不需要预先了解企业的偏好。研究表明，在代理人和企业的底层偏好具有现实结构假设的情况下，所提出的算法在时间范围内具有最多对数增加的后悔成本。在匹配市场的情况下，我们的结果表明，竞争不会极大地影响分散、不需要通信和协调的在线学习算法的性能。

基于结构匹配市场的去中心化、无需通信和协调的学习

Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets

The problem of two-sided matching markets has a wide range of real-world
applications and has been extensively studied in the literature. A line of
recent works have focused on the problem setting where the preferences of
one-side market participants are unknown \emph{a priori} and are learned by
iteratively interacting with the other side of participants. All these works
are based on explore-then-commit (ETC) and upper confidence bound (UCB)
algorithms, two common strategies in multi-armed bandits (MAB). Thompson
sampling (TS) is another popular approach, which attracts lots of attention due
to its easier implementation and better empirical performances. In many
problems, even when UCB and ETC-type algorithms have already been analyzed,
researchers are still trying to study TS for its benefits. However, the
convergence analysis of TS is much more challenging and remains open in many
problem settings. In this paper, we provide the first regret analysis for TS in
the new setting of iterative matching markets. Extensive experiments
demonstrate the practical advantages of the TS-type algorithm over the ETC and
UCB-type baselines.

本文针对未知偏好的两侧市场匹配问题，提出了首个 Thompson Sampling 算法的回报分析，证明 TS 算法在实践中优于 ETC 和 UCB 算法。

匹配市场中的赌博学习的汤普森抽样

Thompson Sampling for Bandit Learning in Matching Markets

We study two-sided matching markets in which one side of the market (the
players) does not have a priori knowledge about its preferences for the other
side (the arms) and is required to learn its preferences from experience. Also,
we assume the players have no direct means of communication. This model extends
the standard stochastic multi-armed bandit framework to a decentralized
multiple player setting with competition. We introduce a new algorithm for this
setting that, over a time horizon $T$, attains $\mathcal{O}(\log(T))$ stable
regret when preferences of the arms over players are shared, and
$\mathcal{O}(\log(T)^2)$ regret when there are no assumptions on the
preferences on either side. Moreover, in the setting where a single player may
deviate, we show that the algorithm is incentive compatible whenever the arms'
preferences are shared, but not necessarily so when preferences are fully
general.

该研究针对两侧市场匹配问题，通过引入一种新算法，提高了在分散式多人选手竞争、无优先认知偏好和与偏好相关猜测等场景下博弈的结果鲁棒性。