Technical Summary: Two-Sided Time-Independent Regret for Matching Markets with Limited Interviews

1. Problem Statement

The paper addresses the problem of two-sided bandit learning in matching markets where participants must learn their preferences through interaction while facing significant constraints. The setting involves $n$ agents and $m$ firms ($n \le m$) with strict, unknown preferences over each other. The core challenges identified are:

1. Limited Screening (Interviews): Participants can only evaluate a small fraction of potential partners before committing. The model formalizes this as a "pre-match" interview stage where agents select a subset of firms to interview. These interactions yield noisy, stochastic signals (hints) about match quality but do not guarantee a reward. Crucially, agents can only apply to firms they have interviewed.
2. Two-Sided Uncertainty: Unlike prior work that often assumes firms have known, fixed preferences, this model assumes firms are also uncertain and must learn their preferences over time.
3. Limited Feedback: In decentralized settings, agents receive only coarse, anonymous firm-side signals. Two feedback models are considered:
   • Vacancy-only ($V$): Agents observe which firms are currently vacant.
   • Hiring-change ($V^+$): Agents observe which firms have changed their hiring status (vacant or hired a different agent), without revealing identities.
4. Strategic Deferral: To handle firm uncertainty, the paper introduces a novel action space where firms can strategically defer (remain vacant) rather than hiring their current top applicant if they suspect their estimates are incorrect. This mechanism is designed to correct premature commitments and stabilize decentralized dynamics.

The objective is to minimize regret, defined as the gap between the expected reward of an agent's stable match (under ground-truth preferences) and the cumulative reward accrued over $T$ rounds. The paper specifically targets horizon-independent regret (i.e., $O(1)$ or $O(\text{poly}(n,m))$ independent of $T$), a significant improvement over the $O(\log T)$ bounds typical in bandit matching without interviews.

2. Methodology

The paper proposes algorithms for both centralized and decentralized market settings, leveraging the concept of interviews as "bandit hints."

Core Mechanisms

• Interviews as Hints: Agents interview $k$ firms per round (typically $k=2$). One firm is selected via a Round-Robin scheme ($f^{RR}_a(t)$) to ensure uniform exploration, and the other is the target application firm ($f^{apply}_a(t)$) determined by preference estimates.
• Strategic Rejection Policy (Algorithm 1): Uncertain firms maintain estimates of agent quality. If a firm's current top applicant is not estimated to dominate all previously rejected agents (who might now be preferred as estimates evolve), the firm strategically abstains from hiring. This creates a vacancy signal ($V$ or $V^+$) that alerts agents to re-evaluate, breaking potential deadlocks caused by early firm-side estimation errors.
• Empirical Means: Both agents and firms use empirical averages of observed rewards to update their preference lists.

Algorithmic Paradigms

1. Centralized Setting (Algorithm 6):

   • A Central Interview Allocator (CIA) coordinates interviews.
   • The CIA runs the Gale-Shapley (GS) algorithm on current estimated preferences to determine the target application firm for each agent.
   • Agents interview their target and a round-robin firm, then apply to the target.
   • This setting achieves time-independent regret by ensuring that once estimates are "valid" (correctly ordered relative to the stable match), the system converges immediately.

2. Decentralized Setting:

   • Coordinated (Algorithm 7, under $V$ feedback): Agents operate in alternating updating and committing phases.
     • Updating: Agents synchronously run a distributed GS execution based on a fixed snapshot of preferences.
     • Committing: Agents apply to their assigned matches.
     • Coordination: If an agent detects a preference inconsistency or a strategic rejection (via vacancy signals), it signals a switch back to the updating phase by abstaining from applying.
   • Coordination-Free (Algorithm 3 & 9, under $V^+$ feedback):
     • Agents act independently, reacting to hiring changes ($V^+$).
     • Agents maintain a candidate set of firms that have either never rejected them or have recently changed hires.
     • General Markets (Algorithm 9): To prevent infinite cycles in markets with multiple stable matchings, agents use $k=3$ interviews (current target, previous target, round-robin) and apply to a set of firms with probability $\lambda$. This randomization breaks blocking-pair cycles.

3. Key Contributions

1. Strategic Deferral for Uncertain Firms: The paper introduces deferral as a modular primitive for two-sided learning. It is the first work to extend the firm action space beyond "always hire," allowing firms to correct early mistakes and stabilize decentralized learning under limited feedback.
2. Horizon-Independent Regret with Constant Interviews: The authors prove that a constant number of interviews per round (specifically $k=2$) suffices to achieve time-independent regret. This improves upon the $O(\log T)$ guarantees of prior bandit-matching literature.
3. Resolution of Open Conjectures: In the single-agent case, the paper resolves an open conjecture by Bhaskara et al. [6], showing that two hints (interviews) suffice for time-independent regret using empirical means, whereas three were previously conjectured to be necessary.
4. Decentralized Learning under Anonymity: The work provides the first decentralized algorithms that achieve time-independent regret using only anonymous firm-side status signals (vacancy or hiring changes), even when firms are uncertain and strategic.

4. Results

The paper establishes the following regret bounds (where $\Delta$ represents the minimum reward gap):

• Centralized (Algorithm 6):

  • Regret: $O(nm^2 \Delta^{-2})$.
  • Optimality: Within a factor of $m$ of the information-theoretic lower bound $\Omega(nm)$. The authors conjecture $O(nm^2)$ is tight.

• Decentralized Coordinated (Algorithm 7, $V$ feedback):

  • $\alpha$-reducible markets: $O(n^3m^2 \Delta^{-2})$.
  • General markets: $O(n^4m^2 \Delta^{-2})$.
  • These bounds reflect the cost of distributed GS execution ($O(n^2)$) multiplied by the centralized learning cost.

• Decentralized Coordination-Free (Algorithm 3/9, $V^+$ feedback):

  • $\alpha$-reducible markets ($k=2$): $O(n^3m^2 \Delta^{-2})$ (market-dependent constants).
  • General markets ($k=3$): $O(\epsilon^{-1} n^5 m^4 \Delta^{-2})$, where $\epsilon$ depends on the randomization parameter $\lambda$ and decays exponentially with $n$ and $m$.
  • The exponential factor in general markets arises from the need to break cyclic blocking-pair dynamics without coordination.

5. Significance and Claims

The paper claims to provide a more general framework for decentralized double-sided learning by explicitly modeling firm uncertainty and introducing strategic deferral. Its significance lies in:

• Relaxing Strong Assumptions: It improves upon prior work (e.g., Liu et al. [19]) by removing the assumption that firms have known preferences and by operating under significantly weaker feedback (anonymous signals vs. full match identity revelation).
• Efficiency: It demonstrates that stable matchings can be learned with near-optimal, horizon-independent regret using only a constant number of low-cost pre-match interactions per round.
• Stabilization: The strategic deferral mechanism is shown to be essential for correcting instability in decentralized systems where firms learn, preventing the system from getting stuck in suboptimal states due to early estimation errors.

The authors note that while their bounds are near-optimal for centralized and structured decentralized settings, the exponential constants in general coordination-free markets highlight the inherent difficulty of resolving blocking pairs without coordination or richer feedback. They leave the derivation of tight lower bounds for coordination-free algorithms in unstructured markets as an open problem.