Learning Equilibria in Matching Markets with Bandit Feedback

We can take the dual of the linear program (5) to obtain:

To interpret (\(\ddagger\)), observe that there exist optimal \(S^*\) and \(Z^*\) all of whose entries lie in \(\lbrace 0,1\rbrace\), because this linear program can be embedded into a maximum weight matching linear program. Take such a choice of optimal \(S^*\) and \(Z^*\). Then, \(S^*\) is an indicator vector corresponding to a (partial) matching on a subset of the agents such that all pairs in this matching are blocking with respect to \((X, \tau)\). Similarly, \(Z^*\) is an indicator vector of agents who would rather be unmatched than match according to \((X, \tau)\).

We first prove the claim that \(I(X, \tau ; u, \mathcal {A})\) is at least (\(\ddagger\)). Based on the above discussion, the optimal objective of (\(\ddagger\)) is obtained through \(S^*\) and \(Z^*\) that represent a matching and a subset of agents, respectively. Let S be the union of agents participating in \(S^*\) and \(Z^*\). We see that the objective of (\(\ddagger\)) is equal to the utility difference at S, i.e.: \(\begin{equation*} \left(\max _{X^{\prime }\in \mathscr{X}_{S}} \sum _{a\in S} u_a(\mu _{X^{\prime }}(a)) \right) - \left(\sum _{a \in S} u_a(\mu _{X}(a)) + \tau _a)\right). \end{equation*}\) This is no larger than Subset Instability by definition.

We next prove the claim that \(I(X, \tau ; u, \mathcal {A})\) is at most (\(\ddagger\)). Let us consider \(S^*\) that maximizes: \(\begin{equation*} \max _{S \subseteq \mathcal {A}} \left(\max _{X^{\prime }\in \mathscr{X}_{S}} \sum _{a\in S} u_a(\mu _{X^{\prime }}(a)) \right) - \left(\sum _{a \in S} u_a(\mu _{X}(a)) + \tau _a)\right). \end{equation*}\) Let us take the maximum weight matching of \(S^*\). Let S be given by the matched agents in this matching and let Z be given by the unmatched agents in this matching (using the interpretation of (\(\ddagger\)) described above). We see that the objective at (\(\ddagger\)) for \((S, Z)\) is equal to Subset Instability, which proves the desired statement.□

By Proposition 4.2, we know that Subset Instability is equal to (5). Moreover, by strong duality, we know that Subset Instability is equal to (\(\ddagger\)) (the dual linear program of (5)). Thus, it suffices to prove that the maximum unhappiness of any coalition is equal to (\(\ddagger\)).

We first prove the claim that (\(\ddagger\)) is at most the maximum unhappiness of any coalition with respect to \((X, \tau)\). To do this, it suffices to construct a coalition \(\mathcal {S}\subseteq \mathcal {A}\) such that (\(\ddagger\)) is at most the unhappiness of \(\mathcal {S}\). We construct \(\mathcal {S}\) as follows: Recall that there exist optimal solutions \(S^*\) and \(Z^*\) to (\(\ddagger\)) such that \(S^*\) corresponds to a (partial) matching on \(\mathcal {I}\times \mathcal {J}\) and \(Z^*\) corresponds to a subset of \(\mathcal {A}\). We may take \(\mathcal {S}\) to be the union of the agents involved in \(S^*\) and in \(Z^*\). Now, we upper bound the unhappiness of \(\mathcal {S}\) by constructing \(X^{\prime }\) and \(\tau ^{\prime }\) that are feasible for (7). We can take \(X^{\prime }\) to be the matching that corresponds to the indicator vector \(S^*\). Because \((S^*, Z^*)\) is optimal for (\(\ddagger\)), \(\begin{equation*} u_i(j) + u_j(i)\ge (u_i(\mu _{X}(i)) + \tau _i) + (u_j(\mu _{X}(j)) + \tau _j) \end{equation*}\) for all \((i, j)\in X^{\prime }\). Thus, we can find a vector \(\tau ^{\prime }\) of transfers that is feasible for (7). Then, since \(\sum _{a\in \mathcal {S}} \tau ^{\prime }_a= 0\), the objective of (7) at \((X^{\prime }, \tau ^{\prime })\) is \(\begin{equation*} \sum _{a\in \mathcal {S}} \bigl (u_a(\mu _{X^{\prime }}(a)) - u_a(\mu _{X}(a)) - \tau _a\bigr). \end{equation*}\) This equals to the objective of (\(\ddagger\)) at \((S^*, Z^*)\), which equals (\(\ddagger\)), as desired.

We now show the inequality in the other direction, that (\(\ddagger\)) is at least the maximum unhappiness of any coalition with respect to \((X, \tau)\). It suffices to construct a feasible solution \((S, Z)\) to (\(\ddagger\)) that achieves at least the maximum unhappiness of any coalition. Let \(\mathcal {S}\) be a coalition with maximum unhappiness, and let \((X^{\prime }, \tau ^{\prime })\) be an optimal solution for (7). Moreover, let S be the indicator vector corresponding to agents who are matched in \(X^{\prime }\) and Z be the indicator vector corresponding to agents in \(\mathcal {S}\) who are unmatched. The objective of (7) at \((X^{\prime }, \tau ^{\prime })\) is \(\begin{equation*} \sum _{a\in \mathcal {S}} \bigl (u_a(\mu _{X^{\prime }}(a)) - u_a(\mu _{X}(a)) - \tau _a\bigr), \end{equation*}\) which equals the objective of (\(\ddagger\)) at the \((S, Z)\) that we constructed.□

We first prove the third part of the Proposition statement, then the first part of the Proposition statement, and finally the second part.

Proof of part (c). Because \(\sum _{a\in \mathcal {A}} \tau _a= 0\), Subset Instability satisfies the following: \(\begin{align*} I(X, \tau ; u, \mathcal {A}) &\ge \left(\max _{X^{\prime }\in \mathscr{X}_\mathcal {A}} \sum _{a\in \mathcal {A}} u_a(\mu _{X^{\prime }}(a)) \right) - \left(\sum _{a\in \mathcal {A}} u_a(\mu _{X}(a)) + \tau _a\right)\\ &= \left(\max _{X^{\prime }\in \mathscr{X}_\mathcal {A}} \sum _{a\in \mathcal {A}} u_a(\mu _{X^{\prime }}(a)) \right) - \left(\sum _{a\in \mathcal {A}} u_a(\mu _{X}(a))\right). \end{align*}\) The second line is exactly the utility difference.

Proof of part (a). From above, we have that Subset Instability is lower bounded by the utility difference, which is always nonnegative. Hence, Subset Instability is also always nonnegative.

To see that Subset Instability is 0 if and only if \((X, \tau)\) is stable, first suppose \((X, \tau)\) is unstable. Then, there exists a blocking pair \((i, j)\), in which case \(\begin{equation*} I(X, \tau ; u, \mathcal {A}) \ge u_i(j) + u_j(i) - (u_{i}(\mu _{X}(i)) + u_{j}(\mu _{X}(j)) + \tau _i+ \tau _j) \gt 0 \end{equation*}\) by the definition of blocking. Now, suppose \(I(X, \tau ; u, \mathcal {A}) \gt 0\). Then, there exists a subset \(S\subseteq \mathcal {A}\) such that \(\begin{equation*} \left(\max _{X^{\prime }\in \mathscr{X}_S} \sum _{a\in S} u_a(\mu _{X^{\prime }}(a)) \right) - \left(\sum _{a\in S} u_a(\mu _{X}(a)) + \tau _a\right) \gt 0. \end{equation*}\) Let \(X^{\prime }\) be a maximum weight matching on S. We can rewrite the above as \(\begin{equation*} \sum _{(i,j)\in X^{\prime }} \bigl (u_i(j) + u_j(i) - (u_i(\mu _{X}(i)) + u_j(\mu _{X}(j)) + \tau _i+ \tau _j\bigr) \gt 0. \end{equation*}\) Some term in the sum on the left-hand side must be positive, so there exists a blocking pair \((i, j)\in X^{\prime }\). In particular, \((X, \tau)\) is not stable.

Proof of part (b). We prove that \(\begin{equation*} |I(X, \tau ; u, \mathcal {A}) - I(X, \tau ; \tilde{u}, \mathcal {A})| \le 2\sum _{a\in \mathcal {A}} {\Vert }u_a- \tilde{u}_a{\Vert }_\infty . \end{equation*}\) The supremum of L-Lipschitz functions is L-Lipschitz, so it suffices to show that \(\begin{equation*} \left(\max _{X^{\prime }\in \mathscr{X}_S} \sum _{a\in S} u_a(\mu _{X^{\prime }}(a)) \right) - \sum _{a\in S} (u_a(\mu _{X}(a)) + \tau _a) \end{equation*}\) satisfies the desired Lipschitz condition for any \(S \subseteq \mathcal {A}\). In particular, it suffices to show that (8) \(\begin{equation} \left| \sum _{a\in S} (u_a(\mu _{X}(a)) + \tau _a) - \sum _{a\in S}(\tilde{u}_a(\mu _{X}(a)) + \tau _a) \right| \le \sum _{a\in \mathcal {A}} {\Vert }u_a- \tilde{u}_a{\Vert }_\infty \end{equation}\) and (9) \(\begin{equation} \left| \left(\max _{X^{\prime }\in \mathscr{X}_S} \sum _{a\in S} u_a(\mu _{X^{\prime }}(a))\right) - \left(\max _{X^{\prime }\in \mathscr{X}_S} \sum _{a\in S} \tilde{u}_a(\mu _{X^{\prime }}(a))\right) \right| \le \sum _{a\in \mathcal {A}} {\Vert }u_a- \tilde{u}_a{\Vert }_\infty . \end{equation}\) For (8), we have \(\begin{equation*} \left| \sum _{a\in S} (u_a(\mu _{X}(a)) + \tau _a) - \sum _{a\in S} (\tilde{u}_a(\mu _{X}(a)) + \tau _a) \right| = \left| \sum _{a\in S} \bigl (u_a(\mu _{X}(a)) - \tilde{u}_a(\mu _{X}(a))\bigr) \right| \le \sum _{a\in \mathcal {A}} {\Vert }u_a- \tilde{u}_a{\Vert }_\infty . \end{equation*}\) For (9), this boils down to showing that the total utility of the maximum weight matching is Lipschitz. Using again the fact that the supremum of Lipschitz functions is Lipschitz, this follows from the total utility of any fixed matching being Lipschitz.□

The starting point for our proof of Theorem 5.1 is the typical approach in multi-armed bandits and combinatorial bandits [15, 22, 30] of bounding regret in terms of the sizes of the confidence interval of the chosen arms. However, rather than using the sizes of confidence intervals to bound the utility difference (as in the incentive-free maximum weight matching setting), we bound Subset Instability through Lemma 5.4. From here on, our approach composes cleanly with existing bandits analyses; in particular, we can follow the typical combinatorial bandits approach [15, 22] to get the desired upper bound.

For completeness, we present the full proof. We divide into two cases, based on the event E that all of the confidence sets contain their respective true utilities at every timestep \(t\le T\). That is, \(u_{i}(j)\in C_{i,j}\) and \(u_j(i)\in C_{j,i}\) for all \((i,j)\in \mathcal {I}\times \mathcal {J}\) at all t.

Case 1: E holds. By Lemma 5.4, we may bound

At each timestep t, let us consider the list consisting of \(w^t_{i_t, j_t}\) for all \((i_t, j_t) \in X^t\). Let us now consider the overall list consisting of the concatenation of all of these lists over all rounds. Let us order this list in decreasing order to obtain a list \(\tilde{w}_1, \ldots , \tilde{w}_L\) where \(L = \sum _{t=1}^{T} |X^t| \le n T\). In this notation, we observe that: \(\begin{equation*} \sum _{t=1}^{T} I(X^t, \tau ^t; u, \mathcal {A}) \le \sum _{t=1}^{T} \sum _{a\in \mathcal {A}^t} (\max (C_{a, \mu _{X^t}(a)}) - \min (C_{a, \mu _{X^t}(a)})) = \log (|\mathcal {A}| T) \sum _{l=1}^L \tilde{w}_l. \end{equation*}\) We claim that \(\tilde{w}_l \le O({\min (1, \frac{1}{\sqrt {(l / |\mathcal {A}|^2) -1}})})\). The number of rounds that a pair of agents can have their confidence set have size at least \(\tilde{w}_l\) is upper bounded by \(1 + \frac{1}{\tilde{w}_l^2}\). Thus, the total number of times that any confidence set can have size at least \(\tilde{w}_l\) is upper bounded by \((|\mathcal {A}|^2)(1 + \frac{1}{\tilde{w}_l^2})\).

Putting this together, we see that:

Case 2: E does not hold. Since each \(n_{ij}(\hat{u}_i(j) -u_i(j))\) is mean-zero and 1-subgaussian, and we have \(O(|\mathcal {I}||\mathcal {J}|T)\) such random variables over T rounds, the probability that any of them exceeds \(\begin{equation*} 2\sqrt {\log (|\mathcal {I}||\mathcal {J}|T/\delta)}\le 2\sqrt {\log (|\mathcal {A}|^2T/\delta)} \end{equation*}\) is at most \(\delta\) by a standard tail bound for the maximum of subgaussian random variables. It follows that E fails to hold with probability at most \(|\mathcal {A}|^{-2}T^{-2}\). In the case that E fails to hold, our regret in any given round would be at most \(4|\mathcal {A}|\) by the Lipschitz property in Proposition 4.4. (Recall that our upper confidence bound for any utility is wrong by at most 2 due to clipping each confidence interval to lie in \([-1, 1]\).) Thus, the expected regret from this scenario is at most \(\begin{equation*} |\mathcal {A}|^{-2}T^{-2}\cdot 4|\mathcal {A}|T\le 4|\mathcal {A}|^{-1}T^{-1}, \end{equation*}\) which is negligible compared to the regret bound from when E does occur.□

Like in the proof of Theorem 5.1, we divide into two cases, based on the event E that all of the confidence sets contain their respective true utilities at every timestep \(t\le T\). That is, \(u_{a}(a^{\prime })\in C_{a, a^{\prime }}\) for all pairs of agents at all t.

Case 1: E holds. By Lemma 5.4, we may bound

At each timestep t, let us consider the list consisting of \(w^t_{c_{i_t}, c_{j_t}}\) for all \((i_t, j_t) \in X^t\). Let us now consider the overall list consisting of the concatenation of all of these lists over all rounds. Let us order this list in decreasing order to obtain a list \(\tilde{w}_1, \ldots , \tilde{w}_L\) where \(L = \sum _{t=1}^{T} |X^t| \le n T\). In this notation, we observe that: \(\begin{equation*} \sum _{t=1}^{T} I(X^t, \tau ^t; u, \mathcal {A}^t) \le \sum _{t=1}^{T} \sum _{a\in \mathcal {A}^t} (\max (C_{c_a, c_{\mu _{X^t}(a)}}) - \min (C_{c_a, c_{\mu _{X^t}(a)}})) = \log (|\mathcal {A}| T) \sum _{l=1}^L \tilde{w}_l. \end{equation*}\) We claim that \(\tilde{w}_l \le O({\min (1, \frac{1}{\sqrt {(l / |\mathcal {C}|^2) -1}})})\). The number of instances that a pair of contexts can have their confidence set have size at least \(\tilde{w}_l\) is upper bounded by \(2n + \frac{1}{\tilde{w}_l^2}\). Thus, the total number of times that any confidence set can have size at least \(\tilde{w}_l\) is upper bounded by \((|\mathcal {C}|)(2n + \frac{1}{\tilde{w}_l^2})\).

Putting this together, we see that:

Case 2: E does not hold. Since each \(n_{ij}(\hat{u}_i(j) -u_i(j))\) is mean-zero and 1-subgaussian, and we have \(O(|\mathcal {I}||\mathcal {J}|T)\) such random variables over T rounds, the probability that any of them exceeds \(\begin{equation*} 2\sqrt {\log (|\mathcal {I}||\mathcal {J}|T/\delta)}\le 2\sqrt {\log (|\mathcal {A}|^2T/\delta)} \end{equation*}\) is at most \(\delta\) by a standard tail bound for the maximum of subgaussian random variables. It follows that E fails to hold with probability at most \(|\mathcal {A}|^{-2}T^{-2}\). In the case that E fails to hold, our regret in any given round would be at most \(4|\mathcal {A}|\) by the Lipschitz property in Proposition 4.4. (Recall that our upper confidence bound for any utility is wrong by at most two due to clipping each confidence interval to lie in \([-1, 1]\).) Thus, the expected regret from this scenario is at most \(\begin{equation*} |\mathcal {A}|^{-2}T^{-2}\cdot 4|\mathcal {A}|T\le 4|\mathcal {A}|^{-1}T^{-1}, \end{equation*}\) which is negligible compared to the regret bound from when E does occur.□

We follow the same argument as the proof of Proposition 3 in Russo and Van Roy [39].

We first recall the definition of \(\varepsilon\)-dependence and \(\varepsilon\)-eluder dimension: We say that an agent \(a^{\prime }\) is \(\varepsilon\)-dependenton \(a_1^{\prime },\ldots ,a_s^{\prime }\) if for all \(\phi (a), \tilde{\phi }(a)\in \mathcal {B}^d\) such that \(\begin{equation*} \sum _{k=1}^s \langle c_{a_k^{\prime }}, \tilde{\phi }(a) - \phi (a)\rangle ^2 \le \varepsilon ^2, \end{equation*}\) we also have \(\langle c_{a^{\prime }}, \tilde{\phi }(a) - \phi (a)\rangle ^2 \le \varepsilon ^2\). The \(\varepsilon\)-eluder dimension \(d_{{\varepsilon} \textrm{-eluder}}\) of \(\mathcal {B}^d\) is the maximum length of a sequence \(a_1^{\prime }, \ldots , a_s^{\prime }\) such that no element is \(\varepsilon\)-dependent on a prefix.

Consider the subset \(S_a\) of \(\lbrace t\mid a\in \mathcal {A}^t, \mu _{X^t}(a) \ne a\rbrace\) such that \(\begin{equation*} \mathbf {1}\left[\max \bigl (C_{a, \mu _{X^t} (a)}\bigr) - \min \bigl (C_{a, \mu _{X^t} (a)})\bigr) \gt \varepsilon \right]. \end{equation*}\) Suppose for the sake of contradiction that \(\begin{equation*} |S_a| \gt \left(\frac{4 \beta _T}{\varepsilon ^2} + 1\right) d_{{\varepsilon}\textrm {-eluder}}. \end{equation*}\) Then, there exists an element \(t^*\) that is \(\varepsilon\)-dependent on \(\frac{4 \beta _T}{\varepsilon ^2} + 1\) disjoint subsets of \(S_a\): One can repeatedly remove sequences \(a_{\mu _{X^{t_1}}(a)}^{\prime }, \ldots , a_{\mu _{X^{t_s}}(a)}^{\prime }\) of maximal length such that no element is \(\varepsilon\)-dependent on a prefix; note that \(s\le d_{{\varepsilon}\textrm {-eluder}}\) always. Let the subsets be \(S_a^{(q)}\) for \(q = 1,\ldots ,\frac{4 \beta _T}{\varepsilon ^2} + 1\), and let \(\phi (a), \tilde{\phi }(a)\) be such that \(\langle c_{\mu _{X^{t^*}}(a)}, \tilde{\phi }(a) - \phi (a)\rangle \gt \varepsilon\). The above implies that \(\begin{equation*} \sum _{q=1}^{\frac{4 \beta _T}{\varepsilon ^2} + 1}\sum _{t\in S_a^{(q)}} \langle c{\mu _{X^t}(a)}, \tilde{\phi }(a) - \phi (a)\rangle ^2 \gt 4\beta _T \end{equation*}\) by the definition of \(\varepsilon\)-dependence. But this is impossible, since the left-hand side is upper bounded by \(\begin{equation*} \sum _{t=1}^T\langle c{\mu _{X^t}(a)}, \tilde{\phi }(a) - \phi (a)\rangle ^2\le 4\beta _T \end{equation*}\) by the definition of the confidence sets. Hence, it must hold that \(\begin{equation*} |S_a| \le \left(\frac{4 \beta _T}{\varepsilon ^2} + 1\right) d_{{\varepsilon}\textrm {-eluder}}. \end{equation*}\) Now, it follows from the bound on the eluder dimension for linear bandits (Proposition 6 in Reference [39]) that the bound of \(\tilde{O} ((\frac{4 \beta _T}{\varepsilon ^2} + 1) d \log (1/\varepsilon).)\) holds.□

Let us consider the set of confidence set sizes \((\max (C_{a, \mu _{X^t} (a)}) - \min (C_{a, \mu _{X^t} (a)})))\) for t such that \(a\in \mathcal {A}^t, \mu _{X^t}\). Let us sort these confidence set sizes in decreasing order and label them \(w_1 \ge \cdots \ge w_{T_a}\). Restating C.2, we see that (10) \(\begin{equation} \sum _{t=1}^{T_a} w_t \mathbf {1}[w_t \gt \varepsilon ] \le O\left(\left(\frac{4 \beta _T}{\varepsilon ^2} + 1\right) d \log (1/\varepsilon) \right). \end{equation}\) for all \(\varepsilon \gt 0\).

We see that: \(\begin{align*} \sum _{t\mid a\in \mathcal {A}^t, \mu _{X^t}(a) \ne a}(\max (C_{a, \mu _{X^t} (a)}) - \min (C_{a, \mu _{X^t} (a)}))) &= \sum _{t=1}^{T_a} w_t \\ &\le \sum _{t=1}^{T_a} w_t \mathbf {1}[w_t \gt 1/T_a^2] + \sum _{t=1}^{T_a} w_t \mathbf {1}[w_t \le 1/T_a^2] \\ &\le \frac{1}{T_a} + \sum _{t=1}^{T_a} w_t \mathbf {1}[w_t \gt 1/T_a^2]. \end{align*}\)

We claim that \(w_i \le 2\) if \(i \ge d \log (T_a)\) and \(w_i \le \min (2, \frac{4 \beta _T (d \log T_a)}{i - d \log T_a})\) if \(i \gt d \log T_a\). The first part follows from the fact that we truncate the confidence sets to be within \([-1, 1]\). It thus suffices to show that \(w_i \le \frac{4 \beta _T (d \log T_a)}{i - d \log T_a}\) for \(t \le d \log T\). If \(w_i \ge \varepsilon \gt 1/T_a^2\), then we see that \(\sum _{t=1}^{T_a} \mathbf {1}[w_t \gt \varepsilon ] \ge i\), which means by (10) that \(i \le O((\frac{4 \beta _T}{\varepsilon ^2} + 1) d \log (1/\varepsilon)) \le O((\frac{4 \beta _T}{\varepsilon ^2} + 1) d \log (T_a))\), which means that \(\varepsilon \le \frac{4 \beta _T (d \log T_a)}{i - d \log T_a}\). This proves the desired statement.

Now, we can plug this into the above expression to obtain: \(\begin{align*} &{\sum _{t\mid a\in \mathcal {A}^t, \mu _{X^t}(a) \ne a}(\max (C_{a, \mu _{X^t} (a)}) - \min (C_{a, \mu _{X^t} (a)})))}\\ &\le \frac{1}{T_a} + \sum _{t=1}^{T_a} w_t \mathbf {1}[w_t \gt 1/T_a^2] \\ &\le \frac{1}{T_a} + 2 d \log (T_a) + \sum _{i \gt d \log T_a}^{T_a} \min \left(2, \frac{4 \beta _T (d \log T_a)}{i - d \log T_a}\right) \\ & \le \frac{1}{T_a} + 2 d \log (T_a) + 2 \sqrt {d \log T_a \beta _T} \int _{t=0}^{T_a} t^{-1/2} dt \\ & = \frac{1}{T_a} + 2 d \log (T_a) + 4 \sqrt {d T_a \log T_a \beta _T}. \end{align*}\) We now use the fact that: \(\begin{equation*} \beta _T = O\left(d \log T + \frac{1}{T} \sqrt {\log (T^2 |A|)}\right). \end{equation*}\) Plugging this into the above expression, we obtain the desired result.□

Like in the proof of Theorem 5.1, we divide into two cases, based on the event E that all of the confidence sets contain their respective true utilities at every timestep \(t\le T\). That is, \(u_{c_1}(c_2)\in C_{c_1, c_2}\) for all \(c_1, c_2 \in \mathcal {C}\) at all t.

Case 1: E holds. By Lemma 5.4, we know that the cumulative regret is upper bounded by \(\begin{align*} R_T &\le \sum _{t=1}^{T} \sum _{a\in \mathcal {A}^t} (\max (C_{a, \mu _{X^t}(a)}) - \min (C_{a, \mu _{X^t}(a)})) \\ &= \sum _{a\in \mathcal {A}} \sum _{t\mid a\in \mathcal {A}^t, \mu _{X^t}(a) \ne a}(\max (C_{a, \mu _{X^t} (a)}) - \min (C_{a, \mu _{X^t} (a)}))) \\ &\le \sum _{a\in \mathcal {A}} O(d \log (T |\mathcal {A}|) \sqrt {T_a}), \end{align*}\) where the last inequality applies C.3 to the inner summand. We see that \(\sum _{a\in \mathcal {A}} T_a= \sum _t |\mathcal {A}_t| \le n T\) by definition, since at most n agents show up at every round. Let us now observe that: \(\begin{equation*} \sum _{a\in \mathcal {A}} \sqrt {T_a} \le \sqrt {|\mathcal {A}|} \sqrt {\sum _{a\in \mathcal {A}} T_a} \le \sqrt {|\mathcal {A}| n T}, \end{equation*}\) as desired.

Case 2: E does not hold. From C.1, it follows that: \(\begin{equation*} \mathbb {P}[\phi (a) \in C_{\phi (a)} \quad \forall 1 \le t\le T] \ge 1 - 1/(|\mathcal {A}|^3 T^2). \end{equation*}\) Union bounding, we see that \(\begin{equation*} \mathbb {P}[\phi (a) \in C_{\phi (a)} \quad \forall 1 \le t\le T\forall a\in \mathcal {A}] \ge 1 - 1/(|\mathcal {A}|^2 T^2). \end{equation*}\) By the definition of the confidence sets for the utilities, we see that: (11) \(\begin{equation} \mathbb {P}[u(a, a^{\prime }) \in C_{a, a^{\prime }} \quad \forall 1 \le t\le T, \forall a, a^{\prime } \in \mathcal {A}] \ge 1/(|\mathcal {A}|^2 T^2). \end{equation}\) Thus, the probability that event E does not hold is at most \(|\mathcal {A}|^{-2} T^{-2}\). In the case that E fails to hold, our regret in any given round would be at most \(4 |\mathcal {A}|\) by the Lipschitz property in Proposition 4.4. Thus, the expected regret is at most \(4 |\mathcal {A}|^{-1} T^{-1}\), which is negligible compared to the regret bound from when E does occur.□

Recall that, by Proposition 4.4, the problem of learning a maximum weight matching with respect to utility difference is no harder than that of learning a stable matching with respect to Subset Instability. In the remainder of our proof, we reduce a standard “hard instance” for stochastic multi-armed bandits to our setting of learning a maximum weight matching.

Step 1: Constructing the hard instance for stochastic MAB. Consider the following family of stochastic multi-armed bandits instances: For a fixed K, let \(\mathcal {I}_\alpha\) for \(\alpha \in \lbrace 1,\ldots ,K\rbrace\) denote the stochastic multi-armed bandits problem where all arms have 0-1 rewards, and the k-th arm has mean reward \(\frac{1}{2} + \rho\) if \(k =\alpha\) and \(\frac{1}{2}\) otherwise, where \(\rho \gt 0\) will be set later. A classical lower bound for stochastic multi-armed bandits is the following:

Step 2: Constructing a (random) instance for the maximum weight matching problem. We will reduce solving the above distribution over stochastic multi-armed bandits problems to a distribution over instances of learning a maximum weight matching. Let us now construct this random instance of the maximum weight matching problem. Let \(|\mathcal {I}| = K\) and \(|\mathcal {J}| = 10 K\log (KT)\). Specifically, we sample inputs for learning a maximum weight matching as follows: For each man \(i\in \mathcal {I}\), select \(\alpha _i\in \lbrace 1,\ldots ,K\rbrace\) uniformly at random, and define \(u_i(j)\) to be \(\frac{1}{2} + \rho\) if \(\lfloor (j- 1) / \log K\rfloor = \alpha _i\) and \(\frac{1}{2}\) otherwise. Furthermore, let \(u_j(i) = 0\) for all \((i,j)\in \mathcal {I}\times \mathcal {J}\). Finally, suppose observations are always in \(\lbrace 0,1\rbrace\) (but are unbiased).

The key property of the above setup that we will exploit for our reduction is the fact that, due to the imbalance in the market, the maximum weight matching for these utilities has with high probability each i matched with some j whom they value at \(\frac{1}{2} + \rho\). Indeed, by a union bound, the probability that more than \(10\log (KT)\) different i have the same \(\alpha _i\) is at most

Step 3: Establishing the reduction. Now, suppose for the sake of contradiction that some algorithm could solve our random instance of learning a maximum weight matching problem with expected regret \(o(K^{3/2}\sqrt {T})\). We can obtain a stochastic multi-armed bandits that solves the instances in C.4 as follows: Choose a random \(i^*\in \mathcal {I}\) and set \(\alpha _{i^*} = \alpha\). Simulate the remaining i by choosing \(\alpha _{i}\) for all \(i\ne i^*\) uniformly at random. Run the algorithm on this instance of learning a maximum weight matching, “forwarding” arm pulls to the true instance when matching \(i^*\).

To analyze the regret of this algorithm when faced with the distribution from C.4, we first note that with high probability, all the agents \(i\in \mathcal {I}\) can simultaneously be matched to a set of \(j\in \mathcal {J}\) such that each i is matched to some j whom they value at \(\frac{1}{2} + \rho\). Then, the regret of any matching is \(\rho\) times the number of \(i\in \mathcal {I}\) who are not matched to a j whom they value at \(\frac{1}{2} + \rho\). Thus, we can define the cumulative regret for an agent \(i\in \mathcal {I}\) as \(\rho\) times the number of rounds they were not matched to someone whom they value at \(\frac{1}{2} + \rho\). For \(i^*\), this regret is just the regret for the distribution from C.4. Since \(i^*\) was chosen uniformly at random, their expected cumulative regret is at most \(\begin{equation*} \frac{1}{K}\cdot o(K^{3/2}\sqrt T) = o(\sqrt {KT}), \end{equation*}\) in violation of C.4.

Step 4: Concluding the lower bound. This contradiction implies that no algorithm can hope to obtain \(o(K^{3/2}\sqrt {T})\) expected regret on this distribution over instances of learning a maximum weight matching. Since there are \(O(K\log (KT)) = \widetilde{O}(K)\) agents in the market total, the desired lower bound follows.

Consider any matching \(X\ne X^*\). Since \(\begin{equation*} \sum _{a\in \mathcal {A}}u^{\mathrm{UCB}}_a(\mu _{X}(a))\le -\Delta ^{\mathrm{UCB}} + \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X^*}(a)) \end{equation*}\) by the definition of \(\Delta ^\mathrm{UCB}\), we have

The proof proceeds in five steps, which we now outline. We first show the matching returned by ComputeMatch\(^{\prime }\) is the maximum weight matching \(X^{\text{opt}}\) with respect to u. We next show that \(X^*\) as defined in ComputeMatch\(^{\prime }\) also equals \(X^{\text{opt}}\). These facts let us conclude that ComputeMatch\(^{\prime }\) returns \((X^*, \tau ^*)\). We then show \(\Delta ^\mathrm{UCB}\) is at least \(0.1\Delta\). We then show that \((X^*, \tau ^*)\) is stable with respect to \(u^{\prime }\). We finish by showing that this implies \((X^*, \tau ^*)\) is stable with respect to u.

Throughout the proof, we will use the following observation about the expanded confidence sets: (12) \(\begin{equation} \max (C^{\prime }_{i,j}) - \min (C^{\prime }_{i,j}) \le 0.1{} \frac{\Delta }{|\mathcal {A}|} \quad \text{and}\quad \max (C^{\prime }_{j, i}) - \min (C^{\prime }_{j, i}) \le 0.1{} \frac{\Delta }{|\mathcal {A}|} \end{equation}\) for all \((i, j)\) in the matching returned by ComputeMatching\(^{\prime }\). This follows from the assumptions in the lemma statement.

Proving ComputeMatch\(^{\prime }\) returns \(X^{\mathrm{opt}}\) as the matching. ComputeMatch\(^{\prime }\) by definition returns \(X^{*,2}\) always, so it suffices to show that \(X^{*,2} = X^{\text{opt}}\). Note that \(X^{*,2}\) is a maximum weight matching with respect to \(u^{\text{UCB}, 2}\). This means that \(\begin{align*} \sum _{a\in \mathcal {A}} u_a(\mu _{X^{*, 2}}(a)) &\ge -\sum _{a\in \mathcal {A}} (\max (C^{\prime }_{a, \mu _{X^{*,2}}(a) }) - \min (C^{\prime }_{a, \mu _{X^{*,2}}(a) })) + \sum _{a\in \mathcal {A}} u^{\text{UCB}, 2}_a(\mu _{X^{*, 2}}(a)) \\ &\ge - 0.1{}\Delta + \sum _{a\in \mathcal {A}} u^{\text{UCB}, 2}_a(\mu _{X^{*, 2}}(a)) \\ &\ge -0.1{}\Delta + \sum _{a\in \mathcal {A}} u^{\text{UCB}, 2}_a(\mu _{X^{\text{opt}}}(a)) \\ &\ge -0.1{}\Delta + \sum _{a\in \mathcal {A}} u_a(\mu _{X^{\text{opt}}}(a)). \end{align*}\) By the definition of the gap \(\Delta\), we conclude that \(X^{*,2}= X^{\text{opt}}\).

Proving \(X^*= X^{\mathrm{opt}}\). Suppose for sake of contradiction that \(X^* \ne X^{\text{opt}}\). Then, \(\begin{equation*} \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X^{*}}(a)) \ge \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X^{\text{opt}}}(a)) \ge \sum _{a\in \mathcal {A}} u_a(\mu _{X^{\text{opt}}}(a)), \end{equation*}\) since \(X^*\) is a maximum weight matching with respect to \(u^{\mathrm{UCB}}\). Moreover, by the definition of the gap, we know that \(\sum _{a\in \mathcal {A}} u_a(\mu _{X^{*}}(a)) \le \sum _{a\in \mathcal {A}} u_a(\mu _{X^{\text{opt}}}(a)) - \Delta\). Putting this all together, we see that \(\begin{align*} \sum _{a\in \mathcal {A}} (\max (C_{a, \mu _{X^{*}}(a) }) - \min (C_{a, \mu _{X^{*}}(a) })) &\ge \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X^{*}}(a)) - \sum _{a\in \mathcal {A}} u_a(\mu _{X^{*}}(a))\\ &\ge \Delta . \end{align*}\) We now use this to lower bound the utility of \(X^*\) on \(u^{\text{UCB}, 2}\). By the definition of the confidence sets, we see that \(\begin{align*} \sum _{a\in \mathcal {A}} u^{\text{UCB}, 2}_a(\mu _{X^{*}}(a)) &\ge \sum _{a\in \mathcal {A}} u^{\text{UCB}}_a(\mu _{X^{*}}(a)) + \frac{1}{2} \sum _{a\in \mathcal {A}} (\max (C_{a, \mu _{X^{*}}(a) }) - \min (C_{a, \mu _{X^{*}}(a) })) \\ &\ge \sum _{a\in \mathcal {A}} u^{\text{UCB}}_a(\mu _{X^{*}}(a)) + 0.5 \Delta . \end{align*}\) However, \(X^{\text{opt}}\) only achieves a utility of \(\begin{align*} \sum _{a\in \mathcal {A}} u^{\text{UCB}, 2}_a(\mu _{X^{\text{opt}}}(a)) &\le \sum _{a\in \mathcal {A}} u_a(\mu _{X^{\text{opt}}}(a)) + \sum _{a\in \mathcal {A}} (\max (C^{\prime }_{a, \mu _{X^{\text{opt}}}(a) }) - \min (C^{\prime }_{a, \mu _{X^{\text{opt}}}(a) })) \\ &\le \sum _{a\in \mathcal {A}} u_a(\mu _{X^{\text{opt}}}(a)) + 0.1{}\Delta . \end{align*}\) But this contradicts the fact (from above) that \(X^{\text{opt}} = X^{*,2}\) is a maximum weight matching with respect to \(u^{\mathrm{UCB}, 2}\). Therefore, it must be that \(X^*= X^{\text{opt}}\).

Putting the above two arguments together, we conclude ComputeMatch\(^{\prime }\) returns \((X^*, \tau ^*)\) in this case.

Bounding the gap \(\Delta ^{\mathrm{UCB}}\). We next show that \(\Delta ^{\text{UCB}} \ge 0.1{} \Delta\). We proceed by assuming (13) \(\begin{equation} \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X}(a))\ge -0.1{}\Delta + \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X^*}(a)) \end{equation}\) for some \(X\ne X^*\) and deriving a contradiction.

We first show that (13) implies a lower bound on \(\begin{equation*} S = \sum _{a\in \mathcal {A}} (\max (C_{a, \mu _{X}(a)}) - \min (C_{a, \mu _{X}(a)})) \end{equation*}\) in terms of \(\Delta\). Because the confidence sets contain the true utilities and \(u^{\mathrm{UCB}}_a\) upper bounds \(u_a\) pointwise, (13) implies \(\begin{equation*} S + \sum _{a\in \mathcal {A}}u_a(\mu _{X}(a)) \ge \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X}(a))\ge -0.1{}\Delta + \sum _{a\in \mathcal {A}} u_a(\mu _{X^*}(a)). \end{equation*}\) Applying the definition of \(\Delta\), we obtain the lower bound \(\begin{equation*} S\ge - 0.1{}\Delta + \sum _{a\in \mathcal {A}} u_a(\mu _{X^*}(a)) - \sum _{a\in \mathcal {A}} u_a(\mu _{X}(a))\ge (1 - 0.1{})\Delta . \end{equation*}\)

Now, we apply the fact that \(X^{*} = X^{*,2} = X^{\text{opt}}\). We establish the following contradiction: \(\begin{align*} 0.1{}\Delta + \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X^*}(a)) &\ge 0.1{}\Delta + \sum _{a\in \mathcal {A}} u_a(\mu _{X^*}(a)) \\ &=\sum _{a\in \mathcal {A}} (u_a(\mu _{X^*}(a)) + 0.1{}\Delta /|\mathcal {A}|) \\ &\stackrel{\text{(i)}}{\ge } \sum _{a\in \mathcal {A}} u^{\mathrm{UCB},2}_a(\mu _{X^*}(a)) \\ &\stackrel{\text{(ii)}}{\ge } \sum _{a\in \mathcal {A}} u^{\mathrm{UCB},2}_a(\mu _{X}(a)) \\ &\stackrel{\text{(iii)}}{\ge } \frac{S}{2} + \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X}(a)) \\ &\stackrel{\text{(iv)}}{\ge } \left(\frac{1}{2}(1 - 0.1{})\right)\Delta + \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X}(a)) \\ &\stackrel{\text{(v)}}{\ge } \left(\frac{1}{2}(1 - 0.1{}) - 0.1{}\right)\Delta + \sum _{a\in \mathcal {A}} u^{\mathrm{UCB}}_a(\mu _{X^*}(a)). \end{align*}\) Here, (i) comes from (12) in the lemma statement; (ii) holds because \(X^*= X^{*,2}\) is a maximum weight matching with respect to \(u^{\mathrm{UCB},2}\); (iii) is by the definition of \(u^{\mathrm{UCB},2}\); (iv) follows from our lower bound on S; and (v) follows from (13).

Proving that \((X^*, \tau ^*)\) is stable with respect to \(u^{\prime }\). By D.1, \((X^*, p^{\prime })\) is an optimal primal-dual pair with respect to \(u^{\prime }\). Now, it suffices to show that the primal-dual solution corresponds to the market outcome \((X^*, \tau ^*)\) for \(u^{\prime }\). To see this, notice that \(p^{\prime }_a= 0\) for unmatched agents and \(\begin{equation*} p^{\prime }_a= p^*_a- \frac{\Delta ^{\text{UCB}}}{2 |\mathcal {A}|} = \tau ^*_a+ u^{\prime }_a(\mu _{X^*}(a)) \end{equation*}\) for matched agents.

Proving that \((X^*, \tau ^*)\) is stable with respect to u. We show the stability \((X^*, \tau ^*)\) with respect to u by checking that individual rationality holds and that there are no blocking pairs.

The main fact that we will use is that \(\begin{equation*} u_a(\mu _{X^*}(a)) \ge u^{\prime }_a(\mu _{X^*}(a)). \end{equation*}\) To prove this, we split into two cases: (i) agent a is matched in \(X^*\) (i.e., \(\mu _{X^*}(a)\ne a\)), and (ii) agent a is not matched by \(X^*\). For (i), if a is matched by \(X^*\), then \(\begin{equation*} u_a(\mu _{X^*}(a)) \ge u^{\mathrm{UCB}}_a(\mu _{X^*}(a)) - 0.1{} \frac{\Delta }{|\mathcal {A}|} \ge u^{\mathrm{UCB}}_a(\mu _{X^*}(a)) - \frac{\Delta ^{\mathrm{UCB}}}{|\mathcal {A}|} = u^{\prime }_a(\mu _{X^*}(a)). \end{equation*}\) For (ii), if a is not matched by \(X^*\), then \(u_a(\mu _{X^*}(a))\ge u^{\prime }_a(\mu _{X^*}(a)),\) because both sides are 0.

For individual rationality, we thus have \(\begin{align*} u_a(\mu _{X^*}(a)) + \tau ^*_a&\ge u^{\prime }_a(\mu _{X^*}(a)) + \tau ^*_a\ge 0, \end{align*}\) where the second inequality comes from the individual rationality of \((X^*, \tau ^*)\) with respect to \(u^{\prime }\).

Let us next show that there are no blocking pairs. If \((i, j)\in X^*\), then we see that: \(\begin{equation*} u_i(\mu _{X^*}(i)) + \tau ^*_i+ u_{j}(\mu _{X^*}(j)) + \tau ^*_{j} = u_i(\mu _{X^*}(i)) +u_{j}(\mu _{X^*}(j)), \end{equation*}\) as desired. Next, consider any pair \((i, j)\not\in X^*\). Then, \(\begin{equation*} u_i(j) + u_j(i) \le u^{\mathrm{UCB}}_i(j) + u^{\mathrm{UCB}}_j(i) = u^{\prime }_i(j) + u^{\prime }_j(i). \end{equation*}\) It follows that \(\begin{align*} u_i(\mu _{X^*}(i)) + \tau ^*_i+ u_{j}(\mu _{X^*}(j)) + \tau ^*_{j} &\ge u^{\prime }_i(\mu _{X^*}(i)) + \tau ^*_i+ u_{j}(\mu _{X^*}(j)) + \tau ^*_{j} \\ &\ge u^{\prime }_i(j) + u^{\prime }_j(i) \\ &\ge u_i(j) + u_j(i), \end{align*}\) where the second inequality comes from the fact that \((X^*, \tau ^*)\) has no blocking pairs with respect to \(u^{\prime }\).

This completes our proof that \((X^*, \tau ^*)\) is stable with respect to u.□

As in the proof of Theorem 5.1, the starting point for our proof is the typical approach in multi-armed bandits and combinatorial bandits [15, 22, 30] of bounding regret in terms of the sizes of the confidence interval of the chosen arms. Our approach does not quite compose cleanly with these proofs, since we need to handle the transfers in addition to the matching.

We divide in two cases, based on the event E that all of the confidence sets contain their respective true utilities at every timestep \(t\le T\). That is, \(u_{i}(j)\in C_{i,j}\) and \(u_j(i)\in C_{j,i}\) for all \((i,j)\in \mathcal {I}\times \mathcal {J}\) at all t.

Case 1: E holds. Let \(n_{ij}^{t}\) be the number of times that the pair \((i,j)\) has been matched by round t. For each pair \((i, j)\), we maintain a “blame” counter \(b^t_{ij}\). We will ultimately bound the total number of timesteps where the algorithm chooses a matching that is not stable by \(\sum _{(i,j)} b_{i,j}^T\).

We increment the blame counters as follows. First, suppose that \(\begin{equation*} \max (C_{a, \mu _{X^t}(a)}) - \min (C_{a, \mu _{X^t}(a)}) \le 0.1{}\frac{\Delta }{|\mathcal {A}|} \end{equation*}\) for every matched agent \(a\in \mathcal {A}\). By Lemma 6.2 and since the event E holds, we know the chosen matching is stable and thus incurs 0 regret. We do not increment any of the blame counters in this case. Now, suppose that \(\begin{equation*} \max (C_{a, \mu _{X^t}(a)}) - \min (C_{a, \mu _{X^t}(a)}) \gt 0.1{}\frac{\Delta }{ |\mathcal {A}|} \end{equation*}\) for some matched agent a. We increment the counter of the least-blamed pair \((i, j) \in X^t\).

We now bound the blame counter \(b^T_{ij}\). We use the fact that the blame counter is only incremented when the corresponding confidence set is sufficiently large, and that a new sample of the utilities is received whenever the blame counter is incremented. This means that: \(\begin{equation*} b^T_{ij} = O\left(\frac{|\mathcal {A}|^2 \log (|\mathcal {A}| T))}{\Delta ^2} \right). \end{equation*}\) The maximum regret incurred by any matching is at most \(12 |\mathcal {A}|\), which means that the regret incurred by this case is at most: \(\begin{equation*} 12 |\mathcal {A}| \sum _{(i, j)} b^T_{ij} \le 12 |\mathcal {A}| \sum _{(i, j)} O\left(\frac{|\mathcal {A}|^2 \log (|\mathcal {A}| T))}{\Delta ^2}\right) = O \left(\frac{|\mathcal {A}|^5 \log (|\mathcal {A}| T))}{\Delta ^2} \right). \end{equation*}\)

Case 2: E does not hold. Since each \(n_{ij}(\hat{u}_i(j) -u_i(j))\) is mean-zero and 1-subgaussian and we have \(O(|\mathcal {I}||\mathcal {J}|T)\) such random variables over T rounds, the probability that any of them exceeds \(\begin{equation*} 2\sqrt {\log (|\mathcal {I}||\mathcal {J}|T/\delta)}\le 2\sqrt {\log (|\mathcal {A}|^2T/\delta)} \end{equation*}\) is at most \(\delta\) by a standard tail bound for the maximum of subgaussian random variables. It follows that E fails to hold with probability at most \(|\mathcal {A}|^{-2}T^{-2}\). In the case that E fails to hold, our regret in any given round would be at most \(12|\mathcal {A}|\) by the Lipschitz property in Proposition 4.4. (Recall that our upper confidence bound is off by at most 6 due to clipping the confidence interval to lie in \([-1, 1]\), so the expanded confidence sets also necessarily lie in \([-3, 3]\).) Thus, the expected regret from this scenario is at most \(\begin{equation*} |\mathcal {A}|^{-2}T^{-2}\cdot 12|\mathcal {A}|T\le 12|\mathcal {A}|^{-1}T^{-1}, \end{equation*}\) which is negligible compared to the regret bound from when E does occur.□

It suffices to verify feasibility and, by weak duality, check that \(X^*\) and \(p^*\) achieve the same objective value. It is clear that \(X^*\) is primal feasible. For dual feasibility, if \((i, j)\not\in X^*\), then \(\begin{equation*} p^*_i+ p^*_j\ge p^{\prime }_i+ p^{\prime }_j\ge u^{\prime }_i(j) + u^{\prime }_j(i) = u^{\mathrm{UCB}}_i(j) + u^{\mathrm{UCB}}_j(i); \end{equation*}\) and if \((i, j)\in X^*\), then \(\begin{equation*} p^*_i+ p^*_j= p^{\prime }_i+ p^{\prime }_j+ 2\frac{\Delta ^{\text{UCB}}}{|\mathcal {A}|}\ge u^{\prime }_i(j) + u^{\prime }_j(i) + 2\frac{\Delta ^{\text{UCB}}}{|\mathcal {A}|} = u^{\mathrm{UCB}}_i(j) + u^{\mathrm{UCB}}_j(i). \end{equation*}\) Finally, we check that they achieve the same objective value with respect to \(u^{\mathrm{UCB}}\). By D.1 and strong duality, \(X^*\) achieves the same objective value as \(p^{\prime }\) with respect to \(u^{\prime }\). Hence,

We first prove the first part of the statement, and then the second part of the statement.

Proof of part (a). We note that it follows immediately from Definition 6.4 that NTU Subset Instability is nonnegative. Let us now show that \(I(X; u, \mathcal {A})\) is zero if and only if \((X, \tau)\) is stable. It is not difficult to see that the infimum of (\(\dagger\)) is attained at some \(s^*\).

If \(I(X; u, \mathcal {A}) = 0\), then we know that \(s^*_a= 0\) for all \(a\in \mathcal {A}\). The constraints in the optimization problem imply that X has no blocking pairs and individual rationality is satisfied, as desired.

If X is stable, then we see that \(s= \vec{0}\) is a feasible solution to (\(\dagger\)), which means that the optimum of (\(\dagger\)) is at most zero. This, coupled with the fact that \(I(X; u, \mathcal {A})\) is always nonnegative, means that \(I(X; u, \mathcal {A}) = 0,\) as desired.

Proof of part (b). Consider two utility functions u and \(\tilde{u}\). To show Lipchitz continuity, it suffices to show that for any matching X: \(\begin{equation*} |I(X; u, \mathcal {A}) - I(X; \tilde{u}, \mathcal {A})| \le 2\sum _{a\in \mathcal {A}} {\Vert }u_a- \tilde{u}_a{\Vert }_\infty . \end{equation*}\) We show that: \(\begin{equation*} I(X; \tilde{u}, \mathcal {A}) \le I(X; u, \mathcal {A}) + 2\sum _{a\in \mathcal {A}} {\Vert }u_a- \tilde{u}_a{\Vert }_\infty , \end{equation*}\) noting that the other direction follows from an analogous argument. Let \(s^*\) be an optimal solution to (\(\dagger\)) for the utilities u. Consider the solution \(s_a= s^*_a+ 2 {\Vert }u_a- u_a{\Vert }_{\infty }\). We first verify that s is a feasible solution to (\(\dagger\)) for \(\tilde{u}\). We see that: \(\begin{align*} & \min \bigl (\tilde{u}_i(j) - \tilde{u}_i(\mu _{X}(i)) - s_i, \tilde{u}_j(i) - \tilde{u}_j(\mu _{X}(j)) - s_j\bigr) \\ &= \min \bigl (\tilde{u}_i(j) - \tilde{u}_i(\mu _{X}(i)) - s^*_i- 2 {\Vert }u_i- \tilde{u}_i{\Vert }_{\infty }, \tilde{u}_j(i) - \tilde{u}_j(\mu _{X}(j)) - s^*_j- 2 {\Vert }u_j- \tilde{u}_j{\Vert }_{\infty }\bigr) \\ &\le \min \bigl (u_i(j) - u_i(\mu _{X}(i)) - s^*_i, u_j(i) - u_j(\mu _{X}(j)) - s^*_j\bigr) \\ &\le 0, \end{align*}\) as desired. Moreover, we see that \(\begin{equation*} \tilde{u}_a(\mu _{X}(a)) + s_a= \tilde{u}_a(\mu _{X}(a)) + s^*_a+ 2 {\Vert }u_a- u_a{\Vert }_{\infty } \le u_a(\mu _{X}(a)) + s^*_a\ge 0. \end{equation*}\) Thus, we have demonstrated that s is feasible. This means that: \(\begin{equation*} I(X; \tilde{u}, \mathcal {A}) \le \sum _{a\in \mathcal {A}} s_a= \sum _{a\in \mathcal {A}} s^*_a+ 2\sum _{a\in \mathcal {A}} {\Vert }u_a- \tilde{u}_a{\Vert }_\infty = [I(X; u, \mathcal {A}) + 2\sum _{a\in \mathcal {A}} {\Vert }u_a- \tilde{u}_a{\Vert }_\infty , \end{equation*}\) as desired.□

We construct subsidies for this setting to be: \(\begin{equation*} s_a= \max (C_{a, \mu _{X}(a)}) - u_a(\mu _{X}(a))\le \max (C_{a, \mu _{X}(a)}) - \min (C_{a, \mu _{X}(a)}). \end{equation*}\)

Step 1: Verifying feasibility. We first show that s is a feasible solution to (\(\dagger\)). \(\begin{align*} & \min \bigl (u_i(j) - u_i(\mu _{X^\mathrm{UCB}}(i))- s_i, \tilde{u}_j(i) - u_j(\mu _{X^\mathrm{UCB}}(j)) - s_j\bigr) \\ &= \min \bigl (u_i(j) - u^{\mathrm{UCB}}_i(\mu _{X^\mathrm{UCB}}(i)), \tilde{u}_j(i) - u^{\mathrm{UCB}}_j(\mu _{X^\mathrm{UCB}}(j))\bigr) \\ &\le \min \bigl (u^{\mathrm{UCB}}_i(j) - u^{\mathrm{UCB}}_i(\mu _{X^\mathrm{UCB}}(i)), u^{\mathrm{UCB}}_j(i) - u^{\mathrm{UCB}}_j(\mu _{X^\mathrm{UCB}}(j))\bigr) \\ &\le 0, \end{align*}\) where the last step uses the fact that \(\mu _{X^\mathrm{UCB}}\) is stable with respect to \(u^{\mathrm{UCB}}\) by definition. Moreover, we see that \(\begin{equation*} u_a(\mu _{X^\mathrm{UCB}}(a)) + s_a= u^{\mathrm{UCB}}_a(\mu _{X^\mathrm{UCB}}(a)) \ge 0, \end{equation*}\) where the last inequality uses that \(\mu _{X^\mathrm{UCB}}\) is stable with respect to \(u^{\mathrm{UCB}}\) by definition. This implies that s is feasible.

Step 2: Computing the objective. We next compute the objective of (\(\dagger\)) at s and use this to bound \(I(X^*; u, \mathcal {A})\). A simple calculation shows that: \(\begin{equation*} I(X^*; u, \mathcal {A}) \le \sum _as_a= \sum _{a\in \mathcal {A}} (\max (C_{a, \mu _{X^\mathrm{UCB}}(a)}) - \min (C_{a, \mu _{X^\mathrm{UCB}}(a)})), \end{equation*}\) as desired.□