

\section{APCK Model and CA-UCB} \label{section:problem}

In a recent paper, \citet{centralized} studied Scenario 0. Subsequently, \citet{caucb} proposed a solution approach that is decentralized, the CA-UCB algorithm. CA-UCB finds a stable match in Scenario 0 by avoiding conflicts using the notion of a ``plausible set.'' The plausible set for a player $p_i$ at time-step $t$ is defined as $S^{(i)}(t) := \{a_j : p_i \succ_{a_j} p_k, \text{ where } \bar{A}^k(t-1) = a_j\}$ i.e. the set of all arms $a_j$ such that at time-step $(t-1)$ another player $p_k \neq p_i$ successfully pulled the arm, but $p_i$ knows that $a_j$ prefers $p_i$ over $p_k$. This set also includes the arms the player successfully pulled (if any) and all the arms that were unmatched at the previous time-step. This makes it so that $p_i$ only attempts arms where there is a possibility of it successfully pulling the arm, avoiding conflicts. Then, $p_i$ attempts to pull the arm with the highest UCB value among $S^{(i)}(t)$  
\section{APKP Model and OCA-UCB} \label{sec_APKP_model}

Notice that the CA-UCB approach to the solution only works if both the players and the arms have full knowledge of the arms' preferences, which is used by players when constructing $S^{(i)}(t)$. When players do not know arms' preferences, they must be able to learn, their own position in the arms' preference orderings and recreate something similar to plausible sets. In some models, this learning is made possible by allowing explicit communication. For example, \citet{communicative} develop a protocol for agent coordination via explicit planning of, and communication about, collisions. 
Communication may be plausible in cooperative models, but the standard model of two-sided matching, as applied to, for example labor markets, is fundamentally competitive, and thus we focus on situations where explicit communication is not permitted between agents.
We propose an algorithm, OCA-UCB \emph{(Optimistic CA-UCB)}, which exploits the fact that the arms still have full knowledge of their own preferences in order to achieve stability without the need for agents to communicate.


Following the general structure of the CA-UCB algorithm, all players initially set their UCB estimates for the arms to $\infty$. However, now in addition to the UCB estimates, each player will also keep track of their position in the arms' preference orderings. This can be done simply by having each player maintain two sets: $O_{k_h}^{(i)}$ the set of all players that $p_i$ believes are ranked higher than itself in $a_k$'s preference ordering, and $O_{k_l}^{(i)}$ which is the set of all players that $p_i$ believes are ranked lower than itself. Initially, for each player $p_i$, these sets are initialized to $O_{k_h}^{(i)} = \phi$ and $O_{k_l}^{(i)} = P \setminus p_i$. Thus, each player starts with the optimistic belief that it is the most preferred by each of the arms. 

Notice, when updating plausible sets, the only information that $p_i$ requires is its' relative positioning in $a_k$'s preference with respect to $p_j$ if $\bar{A}_j (t-1) = a_k$. This can be accomplished using the two sets described above. Since each player starts out with an optimistic view of itself in the arms' preference orderings, conflicts are almost inevitable. This is because according to each player, all the arms are in the plausible set, even when they ought not to be. Suppose conflict occurs between two players, say $p_i$ and $p_j$, for an arm $a_k$ at time-step $t$, and player $p_j$ wins the conflict, then $p_i$'s belief with respect to $p_j$ and $a_k$ gets updated. More precisely, 
$O_{k_h}^{(i)} = O_{k_h}^{(i)} \cup \{p_j\}$ and 
$O_{k_l}^{(i)} = O_{k_l}^{(i)} \setminus \{p_j\}$. 
At future time steps, $p_i$ can use this information when considering $a_k$ in its plausible set. Functionally the rest of the algorithm is the same as CA-UCB. The only difference is that, at the end of each time-step, the players make use of the matching information and update $O_{k_h}^{(i)}$ and $O_{k_l}^{(i)}$ accordingly. 




Eventually, each of the players will have complete sets that represent the arms' true preferences with respect to the other players. In fact, we show theoretically that this approach to the solution does not affect the convergence guarantee of the CA-UCB algorithm in the APCK Model in Theorem \ref{th:simple_theorem}.

\begin{theorem}
Under the belief update scheme described above, OCA-UCB shares CA-UCB's guarantee of convergence to stability. 
\label{th:simple_theorem}
\end{theorem}

We include the proof to this theorem in the appendix and present empirical evidence on the performance of OCA-UCB in Section \ref{subsec:APKP_model_results}. 








\section{APU Model and PCA-DAA} \label{sec:APU_Model}

The previous section looked at the APKP model where the agents did not have access to arms' preferences. Instead, the players relied on the fact that the arms had perfect knowledge about their own preferences and used deterministic feedback obtained to recreate something similar to the plausible set from the CA-UCB algorithm. However, in the APU model, even arms lack knowledge of their preferences, making feedback received from them noisy, invalidating the approach from the previous section.


Given this dilemma of unreliable feedback associated with conflict results, we must formulate an approach in which agents can pick the best possible arms while avoiding conflicts. To accomplish this, we introduce a notion of \textbf{highest expected reward}. The players keep track of estimated conflict win probabilities and attempt arms that maximize the product of reward estimates and win probability. We detail the algorithmic approach to using this heuristic in Algorithm \ref{alg:new_algorithm} (PCA-DAA). 

\begin{algorithm}[H]
\caption{\textbf{Probabilistic Conflict Avoiding-Deferred Acceptance Algorithm (PCA-DAA)}}
\label{alg:new_algorithm}
\begin{algorithmic}[1]
\begin{small}
    \Procedure{PCA-DAA}{$\lambda \in [0, 1)$}
        \For{$t \in \{1, \cdots, T\}$}
            \For{$i \in \{1, \cdots, n\}$}
                \If{$t = 1$}
                    \State Set reward to $\infty$ for all arms \label{setinf}
                    \State Set $\mathcal{Z}_{win} = 1 $ for all arms \label{setone}
                    \State Sample $j \in [1, K]$ uniformly at random
                    \State Set $A_i(t) \gets a_j$
                \Else
                    \State $D_i(t) \sim Ber(\lambda)$ \label{bern}
                    \If{$D_i(t) = 0$} 
                        \State $A_i(t) \gets $ \Call{Get-Best-Arm}{$p_i$, $t$} \label{getbest}
                    \Else 
                        \State $A_i(t) \gets A_i(t-1)$ \label{pulllast}
                    \EndIf
                \EndIf 
            \EndFor
            \For{$a_j \in \{a_1, \cdots, a_k\}$}
                \State $p_{win} \gets $ \Call{Resolve-Conflict}{$a_j$, $t$}
                \State $r_{player},  r_{arm}  \sim $ \Call{Sample-Reward }{$p_{win}$ , $a_j$} \label{samplereward}
                \State \Call{Update-Arm-Rewards}{$a_j$, $r_{player}$} \label{updateplyr}
                \State \Call{Update-Player-Rewards}{$p_{win}$, $r_{arm}$} \label{updatearm}
                \For{$p_i \in \{p_1, \cdots, p_n\}$} \label{prob1}
                    \State \Call{Update-Probability }{$p_i$, $a_j$, $p_{win}$} \label{prob2}
                \EndFor
            \EndFor
        \EndFor
    \EndProcedure
\end{small}
\end{algorithmic}
    
\begin{algorithmic}[1] 
\begin{small}
    \Procedure{Get-Best-Arm }{Player $p_i$, Time $t$}
    \For{$a_j \in \{a_1, \cdots, a_k\}$}
        \State $p_{prev} \gets$ Player that pulled $a_j$ at $(t-1)$
        \State REWARDS$[j] \gets p_i$ tracked $\mathcal{R}$ for $a_j$ 
        \State Z$[j] \gets $ probability of winning: $p_i$ against $p_{prev}$ for $a_j$
    \EndFor
    \State  $j \gets \arg \max \left( \text{REWARDS} \circ \text{Z} \right)$ \label{circ}
    \State \Return $a_j$
    \EndProcedure
\end{small}
\end{algorithmic}
    
\begin{algorithmic}[1]
\begin{small}
    \Procedure{Resolve-Conflict }{Arm $a_i$, Time $t$}
        \State players $\gets$ Requesting players at time $t$
        \State values $\gets$ Arm tracked rewards of players 
        \State player $\gets \arg \max_{\{p_i \in \text{players}\}} \left( \text{values} \right)$  
        \State \Return player
    \EndProcedure
\end{small}
\end{algorithmic}
\end{algorithm}


The algorithm is parameterized by $\lambda  \in [0, 1) $, used to introduce a random delay mechanism to reduce the likelihood of conflicts \cite{caucb,Kong_Yin_Li_2022}. This is controlled in line \ref{bern} where each player draws a Bernoulli Random Variable $D_i(t)$ with expectation $\lambda$. If $D_i(t) = 0$, the player attempts the arm with the highest expected reward, else it will attempt the arm that it did in the previous time step. 

Initially, like CA-UCB, each player sets the reward estimate for the arms to $\infty$. Unlike CA-UCB however, the players also keep track of some probability estimates. Each probability estimate $\mathcal{Z}^{(i)}_j(a_k)$ represents player $p_i$'s belief about how likely it is that it will win a conflict against player $p_j$ for arm $a_k$. Each of these entries are initially set to 1. (line \ref{setinf} and \ref{setone} in Algorithm \ref{alg:new_algorithm}). With these initial beliefs, at each subsequent time step, the players will attempt to pull the arm that maximizes the product of the reward estimate and the probability of winning (line \ref{circ} of procedure \textproc{Get-Best-Arm}). Another important distinction is how the arms pick the players. The arms no longer know their preferences and need to learn them. So, each arm will also keep track of beliefs about the payoffs associated with the players. Then, at the end of each time step, the arms will pick the player that it believes will give the highest reward (similar to how arms behave in the simultaneous choice mechanism of \citet{two_sided_matching}). A player and arm both receive a reward and update their beliefs when an arm is pulled successfully. No reward is given if an arm is not pulled or if a pull request is not received. Players update their beliefs about winning after all matches are made.

One thing to note is that the arms might not have fully accurate estimates for \emph{all} the players in the given horizon. However, the arms only need accurate  estimates for the players who have the arm in their `achievable set' i.e. the set of players that an arm can form a stable match with given their respective preference orderings. The `deferred acceptance’ structure is such that the arms are only picking from the set of available proposals. As long as the players get an accurate enough estimation of their preferences in the APU model, the arms will get the information necessary about the subset of players required to make the match stable. 


Finally, the structure of the algorithm allows us to use different methods to keep track of beliefs about expected rewards and the probability of conflict wins. In this paper we use two: first, UCB, as used by \citet{caucb}, and second, a Thompson Sampling variant, as used by \citet{Kong_Yin_Li_2022}.




\subsection{Using UCB} \label{subsec:APU_UCB}
We use the Upper Confidence Bound (UCB) approach to keep track of reward estimates, as used in multi-armed bandit literature by \citet{original_ucb}. We use UCB in the PCA-DAA algorithm and refer to it as PCA-UCB. Players must keep track of beliefs about payoffs and the probability of winning conflicts. The UCB heuristic can be used to estimate both, while the arms only needing to estimate rewards. Equation \ref{eq:ucb_reward} describes how beliefs about reward payoffs are estimated.


\begin{equation}
    \text{UCB}_j^{(i)}(t) = 
        \begin{cases}
            \infty & \qquad \text{ if } N_j^{(i)} = 0\\
            \hat{\mu}_j^{(i)} + \sqrt{\frac{3 \log t}{2 N_j^{(i)} (t-1)}} & \qquad \text{ otherwise}
        \end{cases}
        \label{eq:ucb_reward}
\end{equation}
\noindent where $N_j^{(i)}$ is the number of times player $p_i$ has pulled arm $a_j$ at time-step $t$, and $\hat{\mu}_j^{(i)}$ is the empirical mean tracked by player $p_i$ for arm $a_j$. Next, to estimate the probabilities of conflict wins, we use a similar quantity that shares the optimism property of UCB.
\begin{equation}
    \label{equ:probability_entry}
    \mathcal{Z}_{j}^{(i)}(a_k) =
        \begin{cases}
                1 & \qquad \text{ if } n_j^{(i)} = 0\\
                \frac{w_j^{(i)}}{n_j^{(i)}} + \sqrt{\frac{3  \log(t)}{2 \cdot n_j^{(i)}}} & \qquad \text{ otherwise}
        \end{cases}
\end{equation}
\noindent where $\mathcal{Z}_{j}^{(i)}(a_k)$ represents player $p_i$'s belief about the probability of winning a conflict against player $p_j$ for arm $a_k$. $w_j^{(i)}$ is the number of times player $p_i$ has won this conflict and $n_j^{(i)}$ is the total number of times this conflict has happened thus far. We upper-censor $\mathcal{Z}_{j}^{(i)}(a_k)$ at 1. At the end of each time step, belief estimates are updated once rewards are sampled and matching information made public. If a player wins a conflict, the corresponding probability estimate increases, otherwise, it decreases. This is handled by the \textproc{Update-Probability} function in Algorithm \ref{alg:new_algorithm}.




\begin{figure*}[ht]
    \begin{center}  
        \includegraphics[width=0.9\textwidth]{figs/APCK_vs_APKP.pdf}
    \end{center}
    \caption{\begin{small}The left sub-figures show the APCK models using CA-UCB and the right sub-figures show the APKP model using OCA-UCB. Results are averaged over 1000 runs. The first row varies market size with uniformly random preferences, the second row varies player preference heterogeneity while keeping market size constant at $N=K=10$. OCA-UCB converges to stability even with uncertainty on both sides, though it takes longer (expected because of increased complexity)\end{small}}
    \vspace{-1.3em}
    \label{fig:APKP_results}
\end{figure*}



\subsection{Using Thompson Sampling} \label{subsec:APU_Thompson} 

Thompson Sampling \cite{original_thompson} (TS) is another approach to solving the MAB problem which has seen a recent resurgence in the literature \cite{agrawal2012analysis,chapelle2011empirical,Kong_Yin_Li_2022}. In the PCA-DAA algorithm, TS can be used to keep track of both the beliefs about rewards as well as probability estimates for winning a conflict. The arms also use TS to keep track of reward estimates. Henceforth, we will refer to this approach as the PCA-TS algorithm. The players and arms keep track of the same information as in UCB, i.e. the total reward obtained for an arm/player, the total number of pulls of an arm, and the total number of conflict wins against each player. The distinction is in how this information is used to update beliefs. 

First, we estimate the rewards. We assume  the variance ($\sigma^2 = 1$) in rewards of the arms and the players are known. Then, we update the mean and precision ($\tau = \frac{1}{\sigma^2}$) as:

\begin{equation}
    \mu_{\text{new}}, \tau_{\text{new}} =\frac{\tau_0 \mu_0 + \tau \sum_{i=1}^n x_i}{\tau_0 + n \tau} , \tau_0 + n \tau 
    \label{eq:thupdate}
\end{equation}

\noindent where $\{\mu_{\text{new}}, \tau_{\text{new}}\}$ are the new mean and precision, $\{\mu_0, \tau_0\}$ are the old mean and precision, $\tau=1$ is the known true precision, and $\sum x_i$ is the sum of rewards for the agent in question. This reward estimate is analogous for both the players and the arms. 
When an agent needs an estimate for a reward for a particular player or an arm, it samples from $\mathcal{N}(\mu_0, \frac{1}{\tau_0})$ where $\mu_0$ and $\tau_0$ is the corresponding mean and precision tracked by the agent for the specific player/arm. 
A Bernoulli distribution is used to keep track of the probability of a player $p_i$ winning a conflict against player $p_j$ for arm $a_k$. 
\begin{equation}
    \mathcal{Z}_{j}^{(i)}(a_k) = \frac{\alpha_j^{(i)}(a_k)}{\alpha_j^{(i)}(a_k) + \beta_j^{(i)}(a_k)}
    \label{equ:thprob}
\end{equation}
\noindent where $\alpha_j^{(i)}(a_k)$ is the number of times $p_i$ has won the conflict and $\beta_j^{(i)}(a_k)$ is the number of times $p_i$ has lost the conflict against player $p_j$ for arm $a_k$. 


\section{Conclusion and Future Work} \label{sec_conclusion} 










In this paper, we describe algorithms that allow agents to learn their preferences in repeated two-sided matching. Our algorithms are the first to provably converge without explicit communication between agents (the proposers) when arm preferences are not common knowledge (the APKP model). When arms themselves do not know their own preferences, we propose a similar algorithmic structure that relies on optimism and converges successfully across a range of simulated settings, and demonstrate that a Thompson Sampling approach converges to stability more quickly and smoothly than a UCB approach. An important direction for future work will be to prove theoretical guarantees on convergence in this setting. 

\section{Introduction} \label{sec_introduction}

The classic literature on two-sided matching ~\cite[e.g.]{GS, Roth_Xing_1997, Haeringer_Wooders_2011}, encompassing applications including long- and short-term labor markets, dating and marriage, school choice, and more, has typically focused on situations where agents are aware of their own preferences. The problem of learning preferences while participating in a repeated matching market first started receiving attention in the AI literature in the work of \citet{two_sided_matching}, and the general idea of two-sided matching under unknown preferences has since been studied in economics and operations research as well ~\cite{Lee_Schwarz_2009, johari2022experimental}. This area of research has received renewed attention in the last few years, along with novel theoretical insights into convergence properties of upper-confidence-bound style algorithms \cite{caucb, Kong_Yin_Li_2022, communicative}. 



The two-sided matching problem involves agents on two sides of a market who have preferences for each other but cannot communicate explicitly. The goal is to create a matching process that ensures \emph{stability}, where no pairs of agents would rather be matched with each other over their current match. \citet{GS} famously demonstrated, constructively, the existence of such matchings. The Gale-Shapley algorithm is structured around one side of the market \emph{proposing} and the other side choosing whether to accept proposals. This theory has been applied to various markets, like matching medical students to residencies \cite{roth1999redesign} and students to schools \cite{abdulkadirouglu2005boston}, with the assumption that agents know their own preferences. There has also been considerable interest in the AI community on two-sided matching in the presence of various constraints, e.g. diversity constraints \cite{aziz2022matching,benabbou2018diversity}. ~\citet{two_sided_matching} introduced a version of the problem (called \emph{two-sided bandits}) where agents engage in repeated matching without prior knowledge of preferences and studied the impact of the specifics of the matching mechanism on \emph{convergence} to stability. There has also been recent work on computing the probability that a matching is stable or finding the matching with the highest probability of being stable under different models of preference uncertainty \cite{Aziz_and_co}.


The exploration-exploitation dilemma that characterizes bandit problems is further complicated in two-sided bandits by uncertainty on not just the values of the ``arms'' of the bandit, but also uncertainty on whether the arms will accept or reject your attempt to pull them (your proposal). This additional uncertainty arises from the multi-agent nature of the problem; instead of there being just one player, there are multiple players competing for the arms, and the arms also have preferences associated with the players. 
Recently, \citet{caucb} studied one specific matching mechanism, namely the simultaneous choice mechanism \cite{two_sided_matching}, where at each round all the agents on the receiving side (henceforth \emph{arms}) get to view all their proposals before deciding which one to accept, and introduced an algorithm that provably converges to stability under the stringent assumptions that (1) all arms have complete knowledge of their preferences, and (2) these preferences are common knowledge, so the proposers (henceforth \emph{agents}) also know them. The algorithm is a variation of the well-known family of UCB algorithms.


\paragraph{Contributions}
In this paper, we are interested in the more general case, where neither the agents nor the arms start off with knowledge of their own preferences. This problem is significantly more complex because it adds a layer of uncertainty that could potentially lead to agents converging to an unstable equilibrium much more easily than in the case with one-sided uncertainty and common knowledge of the other side's preferences. We tackle this in two steps. First, we relax the common knowledge assumption and assume only that arms are aware of their own preferences. In recent work, \citet{communicative} used a framework where agents are allowed to explicitly communicate with each other to find a matching in this setting. We resolve the question of convergence in the more traditional non-cooperative setting of stable matching when arm preferences are not common knowledge. Our algorithm uses the concept of ``plausible sets'' (arms that an agent might be able to ``win'' in the next time step) from the CA-UCB algorithm \cite{caucb}. We show how to define and update these sets in order to develop a provably convergent algorithm (which we call Optimistic CA-UCB or OCA-UCB). The case with two-sided uncertainty is more challenging. We introduce a framework (the Probabilistic Conflict Avoiding Deferred Acceptance Algorithm) that maintains and uses an additional optimistic estimate on the probability of winning each possible contentious situation. We show how to instantiate the algorithm with both UCB and Thompson Sampling style estimates, and empirically demonstrate convergence to stability. Finally, we experimentally evaluate the speed of convergence as a function of the number of agents in the market and the level of preference heterogeneity. 



\section{Setting} \label{sec_problem}


There are $N$ agents (henceforth referred to as players) and $K$ stochastic arms. To ensure that each player can be matched, we assume that $N \leq K$ \cite{centralized,caucb,basu21,sankararaman21}. The set of players is denoted by $P = \{p_1, p_2, \cdots, p_n\}$ and the set of arms by $A = \{a_1, a_2, \cdots a_k\}$. For each $p_i \in P$, there is a distinct (unknown) mean reward $\mu_j^{(i)}$ associated with each arm $a_j$ with unit variance. If $\mu_j^{(i)} > \mu_k^{(i)}$, we say that $p_i$ prefers $a_j$ over $a_{k}$ denoted by $a_j \succ_{p_i} a_k$. Similarly, the arms also have distinct mean rewards associated with each player. The arms may or may not have this information available to them a priori depending on the setting in consideration. 


At each time-step $t \in \{1, \cdots, T\}$, player $p_i \in P$ attempts to pull an arm $a_j \in A$. Let $A^i(t)$ and $\bar{A}^i(t)$ denote, respectively, the arm that player $p_i$ attempted to pull, and the arm that player $p_i$ successfully pulled at time $t$. If multiple players attempt to pull the same arm, a conflict will arise. If the arms are aware of their preferences, the player that is the most preferred by the arm will be picked in the event of a conflict (if the arms are not fully aware of their preferences, then the chosen player will depend on the arm's decision-making algorithm). At the end of each time-step, if a player $p_i$ is successfully matched with an arm i.e. $\bar{A}^i(t) =  m_i(t)$, it will receive a random reward $X_{i, m_i(t)} \sim \mathcal{N}(\mu_{m_i(t)}^{(i)}, 1)$.  Players that fail to successfully pull an arm will receive a reward of 0 and $\bar{A}^i(t) =  \phi$. The final matching is made public to all the agents at the end of each time step. 

We use the classic notion of a stable matching: a bipartite matching from the group of players to the group of arms such that no player and arm prefer each other over their current matching i.e $\nexists (p_i, m_i(t))$ such that $p_i$ prefers an arm $a_j \neq m_i(t)$ and $a_j$ also prefers $p_i$ over its current match. There may be more than one stable match. Our primary focus in this work is on convergence to stability. Another quantity we study is maximum Player Pessimal Regret. We use the Gale-Shapley algorithm with arms as proposers in order to calculate the player-pessimal stable match \cite{GS}. Denote the reward received by player $p_i$ in a player pessimal match by $X_i$. Then, we define maximum player-regret at each time-step as $R(t) = \max_{i\in \{1, \cdots, n\}} \left(X_i - X_{i, m(t)} \right)$ which is the maximum difference (over players) between the reward a player received in its current match and the reward it would have received in a stable matching that player-pessimal.

In this work we consider matching markets with varying levels of information availability. As is standard in models of learning in two-sided matching, we assume no explicit communication between agents on the proposing side. Throughout the rest of the paper we assume that the players do not have access to their own preferences and need to learn them over time. As mentioned above, we consider several scenarios in terms of arm's preferences. For convenience, we name those as follows: 

\begin{itemize}
    \item Scenario 0: Players have access to arm preferences. Arms have access to arm preferences. We call this the \textbf{Arm Preferences Common Knowledge (APCK)} model.
    \item Scenario 1: Players do not have access to arm preferences. Arms have access to arm preferences. We call this the \textbf{Arm Preferences Known but Private (APKP)} model.
    \item Scenario 2:  Players do not have access to arm preferences. Arms do not have access to arm preferences. We call this the \textbf{Arm Preferences Unknown (APU)} model.
\end{itemize}

\noindent The APCK model is studied by \citet{caucb} and a decentralized solution approach is described in the Conflict Avoiding Upper Confidence Bound (CA-UCB) algorithm. Our main contribution is to detail decentralized approaches to solutions for Scenarios 1 and 2. We begin with a quick recap of CA-UCB in the APCK model.
\section{Simulation Results} \label{sec:results}

We run simulation experiments where (1) preferences are uniformly random on both sides of the market with varying market sizes $N=K \in \{5, 10, 15, 20\}$; (2) player preference heterogeneity is varied with market size $N = K = 10$. The maximum reward an agent can get is $(K +1)$, when matched with its most preferred arm, and the minimum is 1, when matched with the least preferred. The reward gaps (of the means) between consecutively ranked agents are kept constant at $\Delta = 1$.
To control the level of heterogeneity in player preferences, we use a method due to \citet{Ashlagi_Kanoria_Leshno_2017}, as also used by \citet{caucb}.
The level of heterogeneity is controlled by a parameter $\beta \in [0, 10, 100, 1000]$. Heterogeneity in preferences decreases with $\beta$, and as $\beta \to \infty$ all players have the same preferences with probability 1. To translate $\beta$ to preference orderings we sample the mean reward $\mu^{(i)}_j$ of arm $a_j$ for player $p_i$ using the following process:
\vspace{-1em}

\begin{equation} 
    \begin{split}
        x_j & \stackrel{i.i.d}{\sim} \text{Uniform([0,1])} \\
        \epsilon_{j,i} & \stackrel{i.i.d}{\sim} \text{Logistic(0, 1)}\\
        \overline{\mu}_j^{(i)} &= \beta \cdot x_j + \epsilon_{j,i}\\
        \mu^{(i)}_j &= \#\{k: \overline{\mu}^{(i)}_k \leq \overline{\mu}_j^{(i)}\}
    \end{split}
    \label{equ:varied_het}
\end{equation}

\noindent These random utilities $\mu_j^{(i)}$ are mapped so that the gap in rewards between consecutively ranked arms is kept constant at $\Delta = 1$. The hyper-parameter $\lambda$ is set to $0.9$.\footnote{%
There are alternative methods for controlling heterogeneity in player preferences, for example notions like uncoordinated/coordinated markets \cite{roglin_and_colleagues}. The method we use corresponds to uncoordinated markets when $\beta$ is low. However, 
coordinated markets are different, with correlation defined on the edges of the matching graph rather than the vertices. We find that the convergence time in these edge-correlated cases is actually comparable to when preferences are uniformly random, compared with node-correlation, where convergence time increases (see Supplement).
}

To objectively quantify the quality and rate of convergence, we introduce a notion of a ``convergence proxy": It measures, in sliding windows of size $\mathcal{X}$, the percentage of time-steps where market stability was greater than $\theta$. It effectively measures the tendency of a market to converge within the next $\mathcal{X}$ time-steps. We calculate the \emph{convergence proxy} line for PCA-UCB vs PCA-TS for when agents' preferences are uniformly random and market sizes are varied. This allows us to objectively visualize the convergence behavior of the two approaches, and draw concrete conclusions about their behaviors.  



We run 1000 simulations in each scenario, monitoring the market state. We take a snap-shot of the maximum player regret and market stability every 10 time-steps and average the results. We use Loess smoothing to evaluate the trend in the data and present the results in the following sections.


\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\columnwidth]{figs/UCB_APU_l01.pdf}
    \vspace{-1em}
    \caption{\begin{small}Results of experiments run in the APU model using UCB to keep track of beliefs: first row has preferences uniformly random, second row has varied player preference heterogeneity with $N=K=10$. Key Takeaways: the markets converge to stability in expectation. Using UCB, there is a dependence on player preference heterogeneity and the time taken to convergence. If you compare this figure against Figure \ref{fig:APU_th}, Thompson Sampling converges to stability slightly faster than UCB and smoother, showing no dependence on player preference heterogeneity.\end{small}}
    \label{fig:APU_UCB}
    \vspace{-1.4em}
\end{figure}

\subsection{OCA-UCB in the APKP model} \label{subsec:APKP_model_results}

Recall that, in this scenario the players must learn their own position in the arms' preference order and their own preferences. We compare the performance of this model with the APCK model using CA-UCB. Both models were run with their respective algorithms, with 6000 time-steps for random preferences and 3000 time-steps for varied preference homogeneity. The results are shown in Figure \ref{fig:APKP_results}.


\begin{figure}[h]
    \centering
    \vspace{-1.2em}
    \includegraphics[clip,width=0.4\columnwidth]{figs/ucb/varied/beta_conflict.pdf}
    \caption{\begin{small}The number of conflicts as a function of time for different values of $\beta$ when using PCA-UCB in the APU model. As time progresses, the number of conflicts decreases and after a certain point they converge to 0 (converge to stability). Higher values of $\beta$ result in an overall higher number of conflicts when using UCB. This explains the trend seen in Figure \ref{fig:APU_UCB} where we can see that the probability of market stability depends on the value of $\beta$ when player preference heterogeneity is varied.\end{small}}
    \label{fig:varied_conflicts}
    \vspace{-1.4em}
\end{figure}

The figures in the first row of Figure \ref{fig:APKP_results} show results from the experiments where agents' preferences are uniformly random. We can see that OCA-UCB converges to stability in the APKP model, with increasing market sizes corresponding to slower convergence. This trend in similar to the APCK model running CA-UCB, albeit OCA-UCB convergence is the APKP model is slightly slower. 

The second row in Figure \ref{fig:APKP_results} details experimental results for varying player preference heterogeneity. As can be seen from the APCK Model running CA-UCB, decrease in player preference heterogeneity in the APCK model does not have any effect on the convergence of CA-UCB. This trend carries over to OCA-UCB in the APKP model, with convergence slightly slower. This shows that in the setting with varying levels of player preference homogeneity, OCA-UCB does not show any noticeable difference in the rate at which the markets converge to stability. 




\subsection{PCA-UCB and PCA-TS in the APU Model} \label{subsec:APU_Model_results}
Recall that, in this scenario, both the players and the arms do not have access to any preference information. Our proposed approach is to make use of a deferred acceptance algorithm, where at each time-step the players attempt the arm with the  \emph{highest expected reward}. As the arms become more confident about their reward estimates for players, the probability estimates that the players keep track of will be more representative of true probabilities. Given the structure of Algorithm \ref{alg:new_algorithm} (PCA-DAA), we propose two methods in Section \ref{sec:APU_Model} to keep track of agents' beliefs: UCB (PCA-UCB), and Thompson Sampling (PCA-TS). In this section, we detail the results of our experiments when using these approaches. 

\subsubsection{Using PCA-UCB}

Figure \ref{fig:APU_UCB} summarizes the results of PCA-UCB in the APU model. 20,000 time steps were run for random preferences and 10,000 for varied player preferences. The first row shows results for random preferences, while the second row shows results for varied player preferences.







Firstly, notice that the APU model using PCA-UCB takes longer to stabilize compared to the APKP model using OCA-UCB, as seen in Figures \ref{fig:APKP_results} and \ref{fig:APU_UCB}. This is due to the fact that both players and arms need to learn their beliefs from scratch. Regardless, when market preferences are random, the trends in both figures are similar, with market stabilization probabilities approaching 1 and player regret tending to 0. This shows that PCA-UCB can find stable matches in a decentralized fashion with unknown preferences on both sides of the market when preferences are random. 

\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\columnwidth]{figs/TH_APU_l01.pdf}
    \caption{\begin{small} Results of experiments run in the APU model using Thompson Sampling to keep track of beliefs. The first row shows market stability and average player regret when preferences are uniformly random on both sides of the market whereas the second row is for when player preference heterogeneity is varied. All the markets stabilize and player regret tends to 0. Performance was better than UCB in terms of convergence rate and smoothness. \end{small}}
    \label{fig:APU_th}
   
\end{figure}

A little more interesting however, is the second row of sub-figures in Figure \ref{fig:APU_UCB} which shows what happens when the players' preference heterogeneity is varied. It shows that higher values of $\beta$ (more homogeneity) leads to slower convergence. We hypothesize that with higher homogeneity in preferences, it takes a while for the players to learn to avoid conflicts because the arms' own uncertainty allows optimism to prevail for longer among more players. This is further corroborated by Figure  \ref{fig:varied_conflicts} which shows more conflicts in the early stages of the algorithm with higher $\beta$ values. Despite this, markets still converge to stability for all $\beta$ values in all 1000 runs. This shows that PCA-UCB can find stable matches with varying levels of preference heterogeneity.









\subsubsection{Using PCA-TS} 

Results for when PCA-TS was used in the APU model are shown in Figure \ref{fig:APU_th}. Like Figure \ref{fig:APU_UCB} (the UCB results), the first row in Figure \ref{fig:APU_th} is when the agent preferences are sampled uniformly at random, and the second row is where the players' preference heterogeneity is varied. 

Results from PCA-UCB (Figure \ref{fig:APU_UCB})  and PCA-TS (Figure \ref{fig:APU_th}) show similarities in market stability and player regret for all market sizes with uniformly random preferences, with larger markets stabilizing slower. However, PCA-TS does not show dependency on $\beta$ when player preference heterogeneity is varied, likely due to quicker convergence of Thompson beliefs. We can also see that PCA-TS converges faster and more smoothly than PCA-UCB. We will discuss this particular property in further detail in the next subsection. The results demonstrate that Algorithm \ref{alg:new_algorithm} can find a stable match in the APU model using both UCB and Thompson Sampling.








 

\subsubsection{Convergence Comparison: UCB vs. Thompson Sampling} 

When looking at Figures \ref{fig:APU_UCB} and \ref{fig:APU_th}, we can see that the Thompson Sampling approach of keeping track of beliefs appears better than UCB in terms of both speed and smoothness of convergence. To quantify this behavior, we turn to the \emph{convergence proxy} we defined earlier, this time comparing the stability graphs of PCA-UCB and PCA-TS. 

\begin{figure}[h]
    \centering
    \vspace{-1.5em}
    \includegraphics[clip,width=.4\columnwidth]{figs/convenrgence.pdf}
    \caption{\begin{small}Convergence Comparison of UCB and Thompson Sampling in the APU model with varying market sizes and uniformly random preferences on both sides of the market. The Thompson Sampling approach (dotted) converges slightly faster and stays that way compared to the UCB (solid) which tends to dip time and again before ultimately reaching convergence. \end{small}}
    \label{fig:convergence_proxy}
\end{figure}


We set $\mathcal{X} = 1000, \theta = 90$ and generate these lines, the results of which are summarized in Figure \ref{fig:convergence_proxy}. Each color on the graph corresponds to the market size with the solid line representing PCA-UCB and the dotted line representing PCA-TS. We can see that the lines associated with Thompson Sampling reach 1.0 (i.e. 100\% of the time-steps in question have stability $> 90\%$) quicker and tend to stay that way. In comparison, the convergence proxy for UCB reaches 1.0 slower for each of the market sizes, and often the proxy value dips before going back up again. By nature of the way beliefs are kept track of, whenever a player chooses to explore, it causes a disturbance in the believed preference ordering of the player. When the internal belief state for a player changes, the player’s set of arms in consideration changes, leading to a different matching. This behavior causes the match to be unstable at some time-steps. This is more frequent in the early stages of the algorithm and becomes less frequent as confidence increases about player preferences. PCA-TS does not exhibit this dipping effect and reaches 1.0 in an overall much smoother manner. The combination of these two reasons suggests that Thompson Sampling might be a better approach for keeping track of agent beliefs in the APU model. 


