Learning in Matching Games with Bandit Feedback

Technical Summary: Learning in Matching Games with Bandit Feedback

Problem Formulation
This paper introduces a novel learning problem situated at the intersection of two-sided matching markets and game theory. The setting involves a generalized market with two distinct sets of agents, $P$ and $A$, who are matched by a central platform over a time horizon $T$. Unlike traditional matching problems where agents possess static, known preferences, or standard Multi-Armed Bandit (MAB) settings where agents receive direct stochastic payoffs, this framework posits that once matched, agents engage in a two-player zero-sum game (ZSG) with an initially unknown payoff matrix.

In this scenario, agents must simultaneously learn the underlying game dynamics and derive their preferences from the outcomes of these interactions. At each time step $t$:

1. A central platform generates a matching $m_t$ based on estimated agent preferences.
2. Matched agents select strategies (mixed actions) and sample specific actions.
3. Agents receive stochastic bandit feedback (rewards) and observe the actions of their matched partner.
4. Agents update their estimates of the payoff matrices and their preferences for the next round.

The core challenge is to learn a Matching Equilibrium, a solution concept defined by [10] where the matching is stable (no blocking pairs) and the agents play a Nash Equilibrium (NE) with their assigned partners. The difficulty arises because agents do not know the game matrices a priori and must explore to form preferences, while the matching mechanism (typically Gale-Shapley) relies on those preferences to ensure stability.

Methodology and Algorithm
To address this, the authors propose UCB-MG, an algorithm based on the principle of "optimism in the face of uncertainty." The methodology operates as follows:

• Optimistic Estimates: Agents maintain upper confidence bounds (UCB) for the payoff matrices of potential matches. Specifically, for a pair $(p, a)$, the estimated payoff matrix $\bar{A}_{p,a}$ is constructed by adding a confidence bonus to the empirical mean of observed rewards.
• Preference Formation: Based on these optimistic payoff matrices, agents compute the optimistic value of the game ($\bar{V}^*$) assuming optimal play (minimax strategies) against each potential partner. Agents then rank their preferences according to these optimistic game values.
• Matching: The central platform collects these reported preferences and executes the Gale-Shapley (GS) algorithm to generate a stable matching for the current round.
• Strategy Execution: Once matched, agents select actions based on the minimax strategies derived from their optimistic payoff matrices, sample actions, and receive feedback to update their estimates.

Regret Formulation: Matching Instability
A critical contribution of the paper is the definition of an appropriate regret metric, termed Matching Instability (MI). Standard regret definitions from MAB or game theory are insufficient because the goal is to converge to a joint equilibrium of matching and strategy.

The authors define MI as the minimum total subsidy required to stabilize the market given a current matching $m$ and strategy profile $X$. Mathematically, it is the solution to a linear program minimizing subsidies $s_a$ subject to:

1. No Blocking Pairs: Ensuring no pair $(p, a)$ can improve their utility by deviating, given the current strategies.
2. Individual Rationality: Ensuring agents prefer their match over being unmatched.
3. Value Guarantee: Ensuring agents receive a utility at least equal to the minimax value of their game (a relaxation of the strict Nash condition to facilitate tractable analysis).

The cumulative regret $R_T$ is defined as the sum of Matching Instability over the horizon $T$.

Key Contributions

1. Learning Problem Definition: The paper formalizes the first learning setting where agents in a two-sided market must learn unknown zero-sum games to form preferences for matching.
2. Regret Metric: It introduces Matching Instability, extending the concept of Subset Instability [8, 17] to settings where matched agents play games. This metric quantifies the distance from a Matching Equilibrium.
3. Algorithm Design: The authors propose a UCB-based algorithm (UCB-MG) that integrates optimistic game value estimation with the Gale-Shapley mechanism.
4. Theoretical Guarantees: The paper proves that the proposed algorithm achieves a sublinear, instance-independent regret bound of $\tilde{O}(\sqrt{Tmkpa})$, where $T$ is the horizon, $m$ and $k$ are the number of actions per agent, and $p$ and $a$ are the number of agents on each side.
5. Generalization: The theoretical bound unifies existing results. When $m=k=1$, it recovers the bound for classical two-sided matching ($\tilde{O}(\sqrt{Tpa})$). When $p=a=1$, it recovers the bound for self-play in zero-sum games ($\tilde{O}(\sqrt{Tmk})$).

Results and Empirical Evidence
The authors provide empirical validation using synthetic instances where payoff matrices are sampled from a normal distribution. They compare three scenarios:

• Self-Play: Both sides follow the UCB-MG algorithm.
• Nash-Response: One side knows the true game matrices and plays the Nash Equilibrium strategy, while the other learns.
• Best-Response: One side knows the true matrices and the opponent's strategies, playing the best response.

Results indicate that the system learns a stable outcome in all scenarios, exhibiting sublinear regret growth. As expected, the Nash-Response scenario yields the lowest regret. Interestingly, while the Best-Response scenario initially outperforms Self-Play, its performance degrades as the market size (number of agents and actions) increases, likely due to the complexity introduced by one side exploiting the other.

Significance and Future Directions
The paper claims significance as an initial step toward understanding learning in environments where agents receive payoffs only after interacting through actions in a game, rather than receiving direct preference signals. It demonstrates that stable outcomes can be learned efficiently in such complex, coupled settings.

The authors modestly frame this work as a foundation for future research. They identify several open directions:

• Extending the model from zero-sum to general-sum games.
• Integrating no-regret learning algorithms (like Exp3) into the matching framework to handle non-zero-sum dynamics.
• Relaxing the assumption that agents observe their partner's actions.
• Exploring alternative game models (Markov games, Stackelberg games) and matching structures (many-to-one markets).
• Investigating decentralized settings where agents select both matches and strategies without a central coordinator.