Stable Matching with Ties: Approximation Ratios and Learning
Authors: Shiyun Lin
Simon Mauras
Nadav Merlis
Vianney Perchet
Venue: NeurIPS 2025 poster ()
Keywords: Stable Matching
Bandit Learning
Approximation Ratio
Optimal Stable Regret
Primary area: theory

Abstract: We study matching markets with ties, where workers on one side of the market may have tied preferences over jobs, determined by their matching utilities. Unlike classical two-sided markets with strict preferences, no single stable matching exists that is utility-maximizing for all workers. To address this challenge, we introduce the \emph{Optimal Stable Share} (OSS)-ratio, which measures the ratio of a worker's maximum achievable utility in any stable matching to their utility in a given matching. We prove that distributions over only stable matchings can incur linear utility losses, i.e., an $\Omega (N)$ OSS-ratio, where $N$ is the number of workers. To overcome this, we design an algorithm that efficiently computes a distribution over (possibly non-stable) matchings, achieving an asymptotically tight $O (\log N)$ OSS-ratio.
    When exact utilities are unknown, our second algorithm guarantees workers a logarithmic approximation of their optimal utility under bounded instability.
    Finally, we extend our offline approximation results to a bandit learning setting where utilities are only observed for matched pairs. In this setting, we consider worker-optimal stable regret, design an adaptive algorithm that smoothly interpolates between markets with strict preferences and those with statistical ties, and establish a lower bound revealing the fundamental trade-off between strict and tied preference regimes.

Stable Matching with Ties: Approximation Ratios and Learning
Shiyun Lin'
Simon Mauras INRIA, FairPlay Joint Team simon maw.am@inra..aa...
Center for Statistical Science
School of Mathematical Sciences, Peking University shiyunlin@sta pku. edu. cn
Nadav Merlis
Vianney Perchet
Technion Israel Institute of Technology nmerlis@technion. ic
CREST, ENSAE, IP Paris
Criteo AI Lab, FairPlay Joint Team Vianney perchet@normall org
Abstract
We study matching markets with ties, where workers side of the market may have tied preferences over jobs, determined by their matching utilities. Unlike classical two-sided markets with strict preferences, exists that is uiliitymaxiiiiing for all workers. To address this challenge, we introduce the Optimal Stable Share (OSS)-ratio, which measures the ratio of worker's maximum achievable utility in any stable matching to their utility in given matching. We prove that distributions over only stable matchings incur linear utility losses, i... an (?N)) OSS-ratio, where N is the number of workers. To overcome this, design an algorithm that efficiently computes a distribution over (possibly non-stable) matchings, achieving an asymptotically tight Ollog N) OSS-ratio. When exact utilities are unknown, our second algorithm guarantees workers logarithmic approximation of their optimal utility under bounded instability. Finally, we extend our offline approximation results to a bandit learning setting where utilities are only observed for matched pairs. In this setting, we consider worker-optimal stable regret, design an adaptive algorithm that smoothly interpolates between markets with strict preferences and those with statistical ties, and establish a lower bound revealing the fundamental trade-off between strict and tied preference regimes.
single stable matching
Introduction
Two-sided matching markets are prevalent in various contexts, such as matching students to schools 2 31, doctors hospitals (50), or workers jobs (5). In this paper, we model the market company that assigns jobs to workers. Each participant has a preference ordering over the other side of the market. For example, jobs rank workers by ability, while workers rank jobs by personal preference. Stability ensures a fair equilibrium where workers receive sufficiently desirable jobs while respecting the preferences and priorities of all parties. When preferences are strict, the deferred acceptance algorithm (23) efficiently computes worker-optimal stable matching worker can get a better job without violating stability.
In online marketplaces, for example, the online crowd-sourcing platform Amazon Mechanical Turk, workers usually uncertain of their preferences over jobs at the beginning, since they do not have hands-on experience. However, there are numerous similar tasks to be delegated
"This work was performed when Shiyun Lin was visiting student CREST, ENSAF, IP Paris.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

on the platform and, fortunately, the uncertain preferences can thus be learnt during the iterative matchings. Recent research has explored this scenario within the framework of multi-player multi- armed bandits [42 43
8 37. Under the strict preferences assumption, these works combine bandit learning algorithms with the deferred acceptance procedure to guide the market toward the worker- optimal stable matching.
However, in real-life scenarios, workers could be indifferent between some jobs due to inherent uncertainty or coarse evaluations. For instance, conference management systems like the Toronto Paper Matching System (TPMS): while the system generates continuous scores to evaluate the suitability of each reviewer for paper, which theoretically avoids ties, the bidding process introduces unavoidable indifference through discrete categorical ratings (e.g.. "Eager", "Willing". "In a pinch". "Not willing"), creating natural ties in preferences. The challenge becomes even more pronounced in learning-base matching markets, where statistically indistinguishable utility estimates produce effective ties between options. This presents a fundamental limitation for bandit learning approaches, as standard algorithms typically fail to provide meaningful regret guarantees when facing such indifference structures in the preference landscape. In particular, when utility differences become small (statistically indistigguishable, existing regret bounds break down completely, and handling this regime was previously considered impossible [42].
With indifferent preferences, a stable matching can be obtained by arbitrarily breaking ties and apply- ing the deferred-aceess -aceetaaccceee algorithm. However, the resulting matching is no longer worker-optimal, as different tie-breaking rules may lead to different stable matchings preferred by different workers potentially creating dramatic utility disparities across outcomes. This challenge is particularly acute in bandit learning settings, where statistically indistinguishable utilities for one worker may lead to arbitrarily large regret for others due to the cascading effects of tie-breaking decisions. In fair resource allocation, fractional matching is a standard technique for balancing competing interests when single integral matching is infeasible 33 27 9 The Birkhoff-von Neumann (ByN) theorem [10 588 estab- lishes that such a fractional matching is equivalent to a probability distribution over integral matchings.
These observations motivate our core research question: For markets with tied preferences, can we approximate a stable solution by considering distributions over matchings, while guaranteeing all workers fair, minimum level of satisfaction?
To answer this question, we define a worker's optimal-stable-shaan (OSS) her maximum achievable utility across all stable matchings. We then introduce the OSS-ratio as a fairesss metric, which measures the fraction of the OSS that each worker is guaranteed to receive under any allocation.
We begin by analyzing the offline setting with known preferences, establishing tight OSS-ratio bounds across different matching classes. These results naturally extend to settings with preference uncer- tainty. Building on these offline results, we further formulate the problem within a multi-playe multi- armed bandit framework for online learning scenarios, and show how approximation guarantees provide the crucial foundation for achieving sublinear regret in matching markets with indifference.
1.1 Main Contributions
Offline Approximation Oracle and Matched Upper and Lower Bounds. We first demonstrate that restricting to stable matchings yields only trivial (and tight) lower bound on the OSS-ratio (Theorem [T, motivating our study for broader matching classes. We then establish a logarithmic lower bound for general matchings (Theorem 2) and construct an approximation oracle (Algorithm I achieving this bound while maintaining internal stability (Theorem 33.
Robustness to Approximated Preferences. We prove our positive results are robust to utility uncertainty: when exact utilitics are unknown but lie within a given uncertainty set, we maintain the same guarantees with only additive error bounded by the maximum uncertainty (Theorem 6). This holds especially for rectangular uncertainty sets, which model utility matrices estimated from data.
Bandit Learning in Matching Markets with Indifference. Building on our offline approximation results, we introduce a-approximation stable regret Reg, (T), using an a-fraction of the optimal- stable-share as tractable benchmark for markets with (statistical) ties. Our adaptive algorithm ETCO (Algorithm 3) seamlessly handles both striet and tied preferences. Theorem 7 establishes its regret bounds, which match the lower bound [52 in markets with large preference gaps. Theorem & further reveals a fundamental trade-off: no algorithm can simultaneously achieve optimal regret in both large-gap (standard regret) and small/no-gap (approximation regret) regimes.
2

---

1.2 Techniques Involved and Developed
The upper bound on the approximation ratio is the first key technical contribution of our paper. We establish this result via three main steps: 1) Introducing a novel component the duplication index into the algorithm design; 2) Constructing directed forest where edges encode conflicts between workers competing for the same job copies across different matchings; 3) Leveraging the tree structure and stability constraints to derive the upper bound inductively.
In the bandit learning setting, the primary technical challenge and key contribution lie in the lower bound proof. To establish this result, we carefully construct two instances with 4 workers and jobs, where the utility matrices differ in only one critical entry that determines whether meaningful ties exist. This construction reveals how ties in one worker's ' preferences propagate affect other workers' regret. Furthermore, we employ an inffommtiion-thorree algorithm must sample this critical entry sufficiently often to avoid incurring linear regret. To our knowledge, we are the first to provably show a tradeoff between standard regret and approximation regret in bandit settings.
argument to demonstrate that the
1.3 Related Work
Stable Matching with Ties. A natural extension of Gale and Shapley's ' work 23 considers settings with tied or incomplete preferences. Irving [29] introduced three stability notions weak, strong, and super-stability- with weak stability being the most studies [25] 26, 35| (4),, as it always guarantees existence, unlike strong or super-stability. However, weakly stable matchings may vary in size, and finding a maximum one is NP-hard [30], while verifying weak stability is NP-complete [46). Unlike prior work focused on maximizing matching size, instead study fair job allocations, ensuring each worker receives a utility within a guaranteed fraction of their optimal stable matching, and we characterize the approximation ratio of such allocations.
Fairness in Two-sided Matching. Recent work has increasingly addressed fairness in two-sided markets. In fair division, Freeman et al. [2D introduces double envy-freeness up to match (DEFI) and double maximin share guarantee (DMMS) for many-to-mane matching, while Igarashi et al. [28 studies many-to- mane-to-one matching, enforcing EF1 for one side while preserving stability. In machine learning, Karni et al. [32) incorporates preference-infone
individual fairness (PIIF) [4), requiring allocations to satisfy individual fairness 188 while respecting preferences. Our work diverges by focusing on one-to-one markets, where standard notions like RF1 and MMS are inapplicable. We propose novel share-based fairness concept (OSS-ratio) to measure workers' gains relative their aptimal-stable-share Our algorithm returns random matching that is ex-ante stable (no justified envy) and ex-post internally stable, achieving sostoo-boothwoolddd guarantee.
Bandit Learning in Matching Markets. Das and Kamenica [16 first formalized bandit problems in matching markets, with subsequent work 42 4 52 37 exploring this model. In this setting, players (with unknown utilities) and arms (with known preferences) form a two-sided market. Player- optimal stable regret (2 measures the utility difference between player's 's outcome and their optimal stable match. Yet, existing results are limited to markets with strict preferences, as stable regret becomes linear and ill-defined when ties exist. Kong et al. [8 recently studied indifference cases, but their
regret benchmark cannot recover optimal stable matches in tie-free settings. Our work bridges this gap by: (1) establishing tight logarithmic OSS-ratio for offline matching with ties, (2) introducing approximation regret as a tractable objective for tied markets, and (3) developing an adaptive algorithm that achieves optimal regret bounds in both tied and tie-free settings.
2 Preliminaries
We model the matching market as a company that assigns jobs to workers. There are N workers, W = {W1, W2, WN) } and K jobs, A = {a1, ag,. .ax}. J. The company assigns jobs to workers such that each job is assigned to at most one worker and each worker performs at most one job. The assignment is therefore matching μu. We shall use ((w) to represent the allocated job to worker w, the notation μ(w)= L or u(a)=
and (aaa) to denote the worker with job a. If a worker w or a job a remains unmatched, we will use
For every job, the company has strict rating over the workers based on their expertise and ability on this job. Specifically, if w > w', worker performs job strictly better than w'. On the other hand,
3

---

workers also have preferences over the jobs, and it is possible that a worker is indifferent among several jobs. The preferences of workers on jobs are represented through utility matrix U, where (ww,a) a), E [o. 1] denotes the preference of worker on job a. If U(w, a) > Uww, d'), worker w prefers job a over a', and (w, a) = U(w; a') implies that w is indifferent between jobs a and a'. For simplicity, we will assume that worker w will refuse to be matched with job if it has utility U Uww, a) = O; stated otherwise, either U U(w, 1) is positive but infinitely small or U (wc L) = 0 and ties are broken in favor of 1. As consequence, a problem instance (U, P.) is defined by utility matrix U and a preference profile Pa representing the preferences of jobs over workers.
Stability is a key concept in two-sided matching markets, which ensures there is no justified envy in the market, i.e., the only jobs a worker prefers over her own job are the ones that she is less suitable to face than the currently assigned worker. When preferences include ties, multiple stability notions arise, and we focus on weak stability 29]. A matching 1s is weakly stable if no worker-job pair exists where both strictly prefer each other over their allocated partners:
Definition (Weak Stability). A matching μ is weakly stable if there is no blocking pair (w, a) such that w >>a 1 (a) and U (w,aa) a) > U(w, ps (w)).
If a matching is weakly stable, there exists tie-breaking mechanism such that this matching is stable in the resulting instance with strict preferences. Conversely, any stable matching that is generated using a tie- tie-breaking mechanism is also weakly stable in the original instance. Without causing ambiguity, we will refer to weak stable as stable for brevity. Furthermore, internally stable matching [44] refers to matching where there are no blocking pairs when only considering the matched workers and jobs.
Definition 2 (Internal Stability). A matching j. is internally stable if there is no internally blocking pair (w, a) such that I) both w and a are matched in p. and 2) w > n²(a) and U (w, a) > U Uww, (()))
Given problem instance, we define the following classes of matchings: M := { : fo is a matching). μ is stable matching], and I := { : is an internally stable matching].
S == {ur
In matching market with ties, stable matchings nisms. A job a is a valid stable match of worker w if there exists a stable matching that matches w with a. We say a the optimal stable match of worker w if it the most preferred valid stable match, i.e. there exists a matching n² E S such that jc² (w) = a and U (w,, (ra(()(()) (w)) = max U Uww n(w)). We call U U(w, p² (w)) the optimal stable share (OSS) for worker w. denoted as (w)).
not unique, given different tie-breaking mecha-
The canonical results in two-sided matching markets are the Gale-Shapley theorem and algorithm (GS) [23]. which guarantee both the existence of stable matchings and an efficient O(n²) computation. The GS algorithm operates through an iterative proposal process. First, workers sequentially propose to their most preferred available jobs. Each job tentatively accepts its most preferred proposal and rejects others. After that, rejected workers continue proposing to their next preferences. The process terminates when no rejections occur, yielding a stable matching. In markets with strict preferences, GS produces a matching that is optimal for all proposers. However, when preferences contain ties, this optimality no longer holds uniformly.
Example 1 (Stable matching with indifference). Let W = (Wi, w2, wa be workers and A = {ai, .2) be jobs with w1 > W2 > W3 for all jobs. The utility matrix that encodes the preference of workers over jobs is given by:
I
1
0
1
There are 2 stable matchings in this instance: μ [ww,,, a1); (wz, a2) #2 = {(wi, o2), (w2, a1)}:
There are 4 extra non-empty internally stable matchings, where exactly one worker is assigned job of utility 1, and unmatched workers/jobs cannot be involved in blocking puirs.All workers have an OSS of 1. More precisely, W1 receives utility U'(w1) = U(w1, a1) = U (w 02) = 1 in both stable matchings, W2 receives utility U (w2)) = Uw22 a1) = 1 in μ2, and wy receives utility U (wa) = U U(w,, a2) = 1 in μr.
Example 1 demonstrates that different workers may achieve their optimal outcomes in different stable matchings. However, it is impossible to simultaneously guarantee all workers their OSS with single matching (even non-stable). Based on this impossibility result, a natural question arises as to whether an allocation exists such that every worker is at least satisfied at a certain level. Formally, given problem instance and a class of matchings C, we are interested in the following optimal stable share-ratio (OSS-ration
U'ww) Re = min max DEA(C) WEW Up(w)²
(1)

---

where A(C)) is the set of distributions over C and UD(W) is worker w's expected utility given distribution i... Un(w) = EE [(W)]] When we are constrained to the set of matchings, stable matchings and internally stable matchings, RM, Rs and Rz are defined accordingly.
The OSS-ratio adopts worst-case perspective by taking the maximum over workers, ensuring every worker receives fair share of their optimal stable utility. Formally, if maxy RM S a, then every worker wy is guaranteed at least [W:(w;) in expectation, regardless of the market's preference structure, The minimum over distributions reflects a central planner's 's optimization: the distribution represents a rotating schedule (e.g., matchings in the support correspond to daily assignments), and restricted support encodes practical constraints. For instance, limiting support to internally stable matchings ensures no justified envy arises between co-present workers in any schedule realization.
3 Approximation Ratios for Stable Matching with Ties
In this section, we aim to characterize the scale of the OSS-ratio Rc from the worker's perspective, which allows for ties, while additional findings related to the job side are provided in Appendix As a first observation, S C I C .M implies Rm S Rr S Rs. and Rs S N, since uniformly selecting worker and their favored stable matching achieves this bound.
3.1 Lower Bound
We first prove that the trivial upper bound on Rş is asymptotically tight. Theorem 1. There exists an instance, such that for any distribution over stable matchings, one worker only receives a 2/N fraction of their optimal stable share, i.e., Rs 2 = (NN).
To prove Theorem we construct an instance with N/2 highly-skilled workers and N/2 regular workers, such that every stable matching can satisfy at most one regular worker a time, proving that R& 2 N/2. The formal proof is deferred to Appendix B
However, closer look at our instance reveals that all regular workers can be satisfied in a single (non-stable) matching (See Remark 4 in Appendix BB. Thus, we turn our attention to distribution over (possibly non-stable) matchings, and the ratio RyM Theorem (isoommmsshwwsss shows that if we extend the support of D to include all matchings, i.c., D E (MM), the ratio RM is still lower bounded by log N.
Theorem 2. There exists instance s.t. for any distribution over (possibly non-stable) matchings, one worker only receives a 1/22(log N) fraction of their optimal stable share, i.e., RM = 2loo N).
To prove Theorem 2. we recursively construct instances with global ranking of jobs over workers, and each worker could be assigned to a job they like, but such that the number of workers grows logarithmically faster than the number of valuable jobs, proving that each worker can only receive a logarithmic fraction of their optimal stable share. The full proof could be found in Appendix B
3.2 Upper Bound
We show that the logarithmic ratio obtained in Theorem distributions over internally stable matchings.
2 is asymptotically tight, even if we consider
Theorem 3. For any problem instance, there exists a distribution D over internally stable matchings s.1. all workers only receive a 1/O(log N) fraction of their optimal stable share, iee, Ry = Olog N).
We prove Theorem 3 by constructing an offline approximation oracle (Algorithm I.. which generates uniform distribution over m internally stable matchings 7i....,, Mnn Each worker w is matched in exactly one matching P.. the key technical insight is that setting m > log, N + ensures UD(w) = U (w, (w)))) /m 2 U*(w) (w)/m. To prove this, construct directed forest where nodes represent workers who prefer a stable matching over the algorithm's 's output, and edges capture conflicts where workers compete for the same job copies under different matchings. By exploiting the tree structure and stability constraint, the proof shows that if any worker were worse off, the graph would imply an exponential growth in the number of workers. For more details, please refer to Appendix[C [
Remark 1. The distribution computed by Algorithm is not only "ex-post" internally stable, but also "ex-ante" (externally) stable, in the sense that no worker has justified envy towards any other worker's (randomized) allocation.
5

---

In Algorithm 7 each worker is assigned a job with probability o/ Under such an allocation, some matchings in the support only assign a subset of jobs. In practice, if some job is not allocated in matching P.. but is allocated to worker in ita we can give a to w in P. without breaking internal stability of Pz. This post-processing a Pareto improvement of our solution.
Remark 2.
Algorithm Internally Stable Matchings for Matching Market with Indifference
Input: N workers, K jobs, Utility matrix U that encodes the preference of workers over jobs, strict preference list Pa of jobs over workers, a positive number m..
1: For each job E A. duplicate it m times and denote the i-th copy as at))
2: Each replica (1) shares the same preference Pa as the original job a.
3: For each worker w, define ordering Pu. by sorting jobs dg by decreasing utility U U(w, a). breaking ties in favour of lower duplication index i, then in favour of lower index k. That is,
U Uww au) > Uww, ae)
(3) Pe of
U(w, ox) = (ww, ag) and i <
or
U(w,ax ux) = U(w, ac) and i = j and
4: Run Gale-Shaples algorithm on Pa and Pa to compute worker-optimal stable matching j..
5: For each E [m]) build a matching üis, which matches each job with (a)(a) A(a(t)). Output: The distribution D which selects each matching jú; with probability 1/m.
Finally, we show that Algorithm cannoot be manipulated by worker who mis-reports her preferences to obtain a distribution that gives them higher utility, whereas the proof is deferred to Appendix C.3
Theorem 4. Algorithm 1 is dominant strategy incentive compatible; for every utility matrices U and U" that differ only on the row of worker w. let D and D' be the distributions computed by Algorithm 7 then Up(w) 2 (w).
4 Robustness and e-Stability
In Section 3 we present an asymptotically tight algorithm for approximating the optimal stable share in markets with ties under stability. However, exact stability often proves too rigid for real-world applications where preferences may fluctuate slightly. We therefore introduce e-stability, which tolerates blocking pairs with utility gains below a threshold 6. This relaxation yields robust matching resilient to preference perturbations while maintaining theoretical guarantees.
Definition (e-Stability). Given e 2 0, a matching is e-stable if there is no e-blocking pair (w, a) such that w >a pla) and U (ww, a)= > (ww, +
The notion of e-stability is a relaxation of weak stability, where setting e = 0 makes it equivalent to weak stability (Definition []. In general, e-stable matching not unique. and there is not a single e-stable matching that simultancously maximizes the utilities for all workers. Therefore, similar to matching markets with ties, we define S. {u μ an e-stable matching]. and we call a valid c-stable match of worker w if there exists an c-stable matching matches w with o, and it is the optimal c-stable match of worker if it is the most preferred valid c-stable match, i.e., there exists a matching 'º²" E S, such that 1r." (w) = a and U (w, H., (w)) = max U(w, p(w)). And we say U (w, μ²t (w)
) is the optimal e-stable share for worker w, denoted as (w)).
Algorithm 2 (see Appendix D generalizes Algorithm | with a different workers' preference profiles generation. It outputs randomized matching that achieves expected utility within a log N factor of the optimal e-stable share, plus an e-additive error.
Theorem Given any utllity matrix U, parameter in = [log, N + 2], and the instability tolerance
2 0, Algorithm 2 computes distribution D E ((T), such that (n(w) (w) 6, Yu E W.
m
The proof of Theorem is deferred to Appendix D.2 over internally stable matchings, which do not depend on e.
Interestingly, the distribution D randomizes
In labor markets, worker preferences are typically estimated with uncertainty via i.i.d. observations, we construct utility uncertainty sets using concentration inequalities. Theorem 3 shows that for any utility matrix in such set U, Algorithm 2 produces random matching guaranteeing each

---

worker a logarithmic approximation to their optimal share within Ut where the proof is deferred to Appendix [D4] Theorem 6. Given uncertainry set U, the optimal stable share within U is
u' (w) == sup max (ww μ(w)), Vw E W.
(2)
UEM NESU
We define the center Ü of the set U as ((waa) inferete parameter as = 2- supu, Uxeu |U - U2llmax. Algorithm with input U, m and e oulputs a distribution D E (I) such that UD(w)
((w,a) and the uncertainty
[log2 N + 2],
-,, v, E W.
Example illustrates an application of Theorem to batch learning problems. Example 2 (Batch learning). Suppose that we have dataset of size T, where each data point U is noisy observation of the ground-truth truth utility matrix U, i.e., each (ii.j) is sampled from distribution with mean (i, Given a parameter set = 2/ / ((())/TT and define the uncertainty set for each entry (w. a.) as Uw {U(w,a) :U a) - (w, a) S $/2). and (w.o)EWxx aw where U the empirical mean utility matrix computed from the dataset. The OSS within the uncertainty set U" (w) could be defined as in Eq. 2 By Lemma 2 we know that with probability 1 8, the ground-truth utility matrix Ü E U, and hence (w)) S (w). Therefore, by running Algorithm 2 with the empirical mean utility matrix as input, and set =2 (o/n((3//// m = Llog, + 2]. we have w.p. 8 that the corresponding output distribution D over matchings (w)
satisfies (w)) [1gg2 N+2] 2 f for all w E W.
5 Bandit Learning in Matching Markets
Example 2 demonstrates the application of our offline oracle to learning problems. We now transition to an online learning setting, framing the matching market as a multi-pla multi-player bandit problem to show how the offline results naturally connect learning scenarios both with and without statistical ties.
In online marketplaces, companies can evaluate workers through interviews, but typically lack prior knowledge of worker preferences over jobs. Still, by leveraging repeated matching opportunities, these preferences be learned through ex-post evaluations. Recent work models this as multi-armed bandit (MAB) problem [4 43 377. where workers ("players") and jobs ("arms") interact over rounds. Each round, the company outputs a matching Hr assigning jobs to workers and observes 1-subgaussian rewards (t) for matched pairs (w,, (w.)) with mean (w,, pt (w:) ) E [0, 1]. Following bandit matching literature, we assume N S K (more jobs than workers) to ensure matching feasibility. If N > K, we can extend the problem by adding zero-utility jobs or randomly assigning unmatched workers.
The company seeks to learn the worker-optimal stable matching (w;)) through interactions. Specifi- cally, it aims to minimize the worker-optimal stable regret for each w; W, defined as the cumulative reward difference between being matched with n and that w; receives over T rounds:
T
(Tg.(T) = T U' -
Σ
xx)00)
The expectation is taken over the randomness of the received reward and the allocation strategy.
Prior work on minimizing worker-optimal stable regret focuses exclusively on tie-free markets 42 8,377, rendering their results inapplicable when preferences contain ties. Crucially, existing regret bounds scale as 1/A2, where is the minimum utility gap across all workers w and jobs a, i.e.,
A min, min [U(w, a) (w, a') [ i As shown in Example 2 in [42) this dependence is fundamental -chievvin sublinear regret requires A = w(IVTT).
When the benchmark is unachievable (computationally or statistically), prior work adopts a- approximation regret to ensure sublinear regret relative to an a-fraction of the benchmark [3 54 14)
While definitions of A vary slightly across works, this strongest version generalizes other formulations.
7

---

In our setting, since ties prevent all workers from simultaneously achieving their optimal stable share, we assume access to an offline oracle that, given utilityy matrix U, outputs randomized matching guaranteeing each worker at least an 1/a of U (w) in expectation, with additional enror Formally, Definition 4 ((a, O-Appooximation lar uncertainty set U with width Oracle), An (a, apaproxximation oracle takes a rectangu- input and returns a (randomized) matching jt satisfying: [U)[w)]] 2 (w)) (w) - e for every worker w, where a E [0, is a worker-specific approximation ratio vector (often simplified to ax) If (w) = a is uniform across workers and independent of we call it (a, capproxxiiiiino oracle,
For example, Algorithm guaranttess that for any input utility matrix U, a² 2 [log N + 2]. With ties, our regret metric should not compare against the OSS each time, but against an a-fraction of the optimal stable share, since the offline oracle can only guarantee this fraction expectation:
Reg (T) = aT U (w:: E
(1(1)
where a E (0, 1] is the approximation ratio given by the offlin oracle. When we want to emphasize that the observations (()) come from a distribution v, we write (eg:(T; v) and Reg. (T:v).
(T;
For markets without ties, (37) achieves a stable regret of O In T/A2), matching the D R(Nhr In / lower bound [52] in I and A. We seek best-of-both-worlde guarantee, i.e. an algorithm that attains (T) = (In A)) when A = wII/VT), and Reg, (T) o(T) when A (1/vTT).
5.1 Algorithm: Explore-thers thee-hhhoos--Oaaceee
We present our algorithm, Explore-then- Caaieen-Chose-OOO Choose-Oracle (ETCO, Algorithm in Appendix E and summarize it here. The algorithm consists of two phases. In each round of the exploration phase, the company allocates a job to every worker in a round-robin way to estimate their utilities accurately. In the second phase, the company checks for plausible ties in utilities. If none exists, it computes matching using GS algorithm; otherwise, it uses the approximation oracle. In subsequent rounds, jobs allocated based the chosen oracle's 's output.
In the exploration phase, the company allocates jobs to workers in round-robin way, according to the index of the workers. In this way, every K rounds, each worker is matched to every job exactly once. The maximal number of exploration rounds is bounded by a parameter To. After each allocation,
based on the observation, we update the estimated utility (i,) = (ti.e(()) (T Ti. (o(t)
and the observation count of worker uy and job (i) as (.)) T.) + 1. The company also builds a confidence set for each utility estimate, ensuring the true expected utility is included with
high probability. Particularly, the confidence interval (CI) for worker w; preference utility over job aj is [LCB,,, UCB.s), with the upper and lower confidence bounds defined as
6hnT UCB,; = Ú(i)) + max 1F
6 LCBI, = -i max (Tij.
(5)
When confidence sets for jobs 0j and ay disjoint (LCBi,, > UCB or vice versa), we can determine worker w; 's strict preference between them. all top-N job Cls for w, become disjoint, we recover the true preference with high probability. If this occurs for all workers before the exploration phase To ends, we switch to the Gale Shapl-S oracle for exploitation, as no top-N ties exist w.h.p. Otherwise, remaining CI overlaps indicate potential ties, triggering approximation oracle instead.
5.2 Theoretical Analysis
Before stating the regret guarantee for ETCO algorithm, we first give formal definition of the minimum preference gap, which measures the hardness of the learning problem.
Definition (Minimum Preference Gap). For each worker w; and job 0g + a,,, let Dia. = (i - (il be the preference gap for w; between aj and ag- Let ra be the preference ranking of worker w, and rik be the k-th preferred job in wa's ranking for k E [K]. Define Amin [Mn Arraaee the minimum preference gap among all workers and their first (N + 1)-ranked jobs.
8

---

Next, we present upper bounds for the worker-optimal stable regret for each worker when using ETCO. Theorem 7 (Upper Bound), Following the ETCO algorithm with exploration phase of length Tu and a. an
6k T
-approximation oracle, for wi E W, we have that
To
K In
96K In
K KITT
(Tg:(T) 0
if Amin
92
(6)
A
To
InT' To
96A In
K In
Regi (T) 2aTo + +
TV
if A min
O
(7)
To
See Appendix G for the proof. Our bound exhibits two regimes: (1) large-A regime: when Amin
is large, the exploration phase learns the top-(N++1) job preferences w.h.p. before To. enabling exact worker-optimal stability via Gale-Shapley in exploitation. This reduces to ETGS (37] under centraliza- tion; (2) small-A tied regime: for small Amin or exact ties, worker-optimal stability is unattainable; instead, implementing an approximation oracle guarantees an a-approximation regret sublinear in T.
When Amin is sufficiently large, our upper bound matches the Q In T/A min) lower bound [52
for serial dictatorship markets (where all jobs share identical preferences). This tightness, however, comes at fundamental trade-off: Theorem 8 shows that extending sublinear regret guarantees to wider ranges of Amin unavoidably worsens approximation regret in small- or no-gap regimes.
Prior to presenting our trade-off lower bound, we formally define two key concepts. The Pareto- optimal stable matching set St comprising stable matchings where no worker's utility can be strictly improved without harming another worker, and the relevant preference utility gap Aret representing the maximum utility perturbation that preserves SU
Definition 6 (Pareto-optimal Stable Matching Set). Given a utility matrix U, the worker-optimal Pareto-optimad stable matching set Styt is the set of all matchings μ such that: 1) is stable; 2) If there exists a stable matching pl and a worker w such that U(w, ('w)) > U(w, p(w)), then for some w/ * w, it holds that U(u U(w,, pp (((w") U U(w', ,(('))
Definition 7 (Relevant Utility Gap). Given utility matrix U, the relevant preference gap Aret is
Ard inf {e: ::: [N],j E (1,5) e (U(i,)) E, + s.t. Soy # soy 1 (8)
By definition, Art 2 O. When sy contains multiple matchings, A since any perturbation acts as a tie-breaker, eliminating at least one matching from Sy (by the uniqueness of worker-optimal stable matching in freefree markets). Furthermore, Are Amin because perturbations smaller than Ami cannot alter any worker's ' top-N preferences or the worker-optimal matching"
Theorem 8 (Trade-off between Regret and Approximation Reget). Let E (0, })) and fix N 44 Consider the class of instances with large relevant utility gap, denoted as Ee(T), i.e., for any instance v E (TT), we have A 2 1/24/ for some absolute guarantees sublinear regret for all workers, for all v E (T)) Then there exists an instance such that this algorithum suffers QQTT1-25 approximation regret for some worker when Arei w.r. the best approximation ratio ax for this instance, i.e.
0. Assume that an algorithm
SUPUEEEITY Reg; (T: =0,
IfV w. W, limsup T-000
T
- Wi E W, v' S.1. A 0, and Reg, a' a' (w)) =
(9) where a" (w;) = max (a(w:) ): a(w) 2 1/ V W). for any w, E W. and R is the OSS-ratio on matchings with a given utility matrix U.
The proof appears in Appendix H We construct two serial dictatorship instances with 4 workers and 4 jobs each, whose utility matrices differ in only one entry (for the highest-priority worker), yielding A = The first instance evaluates a -approximation regret, while the second analyzes standard stable regret. Crucially, this single entry difference completely alters the benchmark utilities for the other three workers. Thus, one the two cases happens: (1) under-sampling: without
AAttallyy if we assume an oracle that can determine whether there is a unique worker-optimal stable matching within the uncertainty we prove similar upper bound in Theorem 7 with Amin replaced by Ard.

---

enough samples of the differing entry, at least one worker incurs linear approximation regret; (2) over-sampling: After To samples of the differing entry, at least one of the remaining workers suffers (76) approximation regret.
Theorem X establishes an inherent trade-off between large-gap and small / no-gap regimes: as ď - O, sublinear regret in the former necessitates linear approximation regret in the latter. Consequentl,, the exploration length To of ETCO algorithm critically determines regime-specific performance. We provide two To choices and their corresponding regret bounds.
Corollary 1. Following ETCO algorithm with To = - (K In I' 1/3 forr wi E W, we have
Reg.(T) (T) = =0 K KI
if Amin = - (T)):: Reg = o ( T))3)) Af = (T
A2
min
Choosing To 1 TT/3 (K yields the optimal approximation regret upper bound in the small gap regime when implementing explore-then-commee type algorithms. However, this choice is not satisfiable when Amin E [52 (T-1/2). Ó (T-1/3)). since setting To as such cannot guarantee detection of instances when Amin falls in this intermediate regime. For these cases, we must resort to the approximation oracle during exploitation. Cruicially, since the oracle's solution differs by a constant factor from the Gale-Shapley optimal, each exploitation round incurs constant regret when measured against (3) resulting an overall linear regret.
Corollary 2. Following ETCO algorithm with To = 21n T. for we E W. we have
T
K In A min
if Amin á (T Reg. a a- (T) = (vKTInT) if Amii = Ō ÖT
(T): = 0
Choosing To (2 In 7) yields the optimal regret that matches the lower bound for any Amin á (T-1/2). However, for Amin = Ô 1/2), we can only guarantee sublinear approximation regret with approximation ratio of 1/1n T even when using an offline a-approximation oracle.
Remark 3. The approximation regret lower bound in Theorem is both non-trivial and potentially of independent interest for bandit theory. While combinatorial bandits typically use approximation regret to circumvent computational limits (with statistical lower bounds focusing on 1-regret [I5] 39 48)),
our result reveals fundamental distinction: in matching markets, this approximation factor persists even given unlimited computational resources.
6 Conclusion
In this paper, we study stable matching with one-sided indifference, modeled as a company assigning workers to jobs. Using utility matrix to encode workers' potentially tied preferences over jobs, we define the optimal stable share (OSS) for each worker as the maximum utility achievable in any stable matching. To address fairness, we introduce the OSS-ratio, quantifying the fraction of the OSS a worker obtains under random matchings. We first analyze distributions over stable matchings. showing that a linear approximation to the OSS is trivial and asymptotically tight. For general matchings, we prove that no better than logarithmic approximation is possible. To achieve this bound, we propose a polynomial-timg algorithm computing a distribution over internally stable matchings, which is asymptotically optimal in OSS ratio and dominant strategy incentive-coppatin Next, we extend our framework to settings where the utility matrix is uncertain but lies within a given uncertainty set. By incorporating c-stable matchings and relating them to perturbations of the utility matrix, we derive a logarithmic approximation with an additive c error, matching the deterministic case. Finally, we explore online learning, where existing stable regret frameworks fail to handle tied preferences. Leveraging the OSS-ratio, we define a-approximation stable regret and provide an algorithm whose upper bound matches the lower bound in the no-tied case. We further derive approximation regret bounds for small or no utility gaps and establish a fundamental trade-off between regret types, highlighting the need for careful exploration stopping time decisions.
Our work establishes the first iistence-independent worker-optimal stable regret bound in bandit learning for matching markets, achieved through centralized job allocation. However, real-world marketplaces typically operate decentralized settings where workers cannot directly coordinate. While the Gale-Shapley algorithm naturally decentralizes, extending our approximation guarantees to decentralized bandit learning remains an open challenge, which is an important direction for future research. Furthermore, exploring the application of our proposed algorithms to real-world datasets would be a valuable next step, as would help address the practical challenge of stable matching when ties exist in preference rankings.
10

---

Acknowledgements
This project has received funding from the European Union's 's Horizon 2020 research and innovation programme under the Marie Sklodowska- Curie grant agreement No 101034255. Shiyun Lin acknowl- edges the financial support from the China Scholarship Council (Grant No.202306010152) Vianney Perchet's research was supported in part by the French National Research Agency (ANR) in the framework PEPR IA FOUNDRY project ANR-23-CE23-0000 It was also funded by the European Union (ERC, Ocean, 101071601), Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
MAANR-3-PPIA-OOA
and through the grant DOOM
References
[1] Atila Abdulkadiroglu and Tayfun Sönmez. School choice: A mechanism design approach. American economic review, 93(3):729-747, 2003.
[2] Atila Abdulkadiroğlu, Parag A Pathak, and Alvin Roth. The new york city high school match. American Economic Review, 95(2):364-367, 2005.
[3] Atila Abdulkadiroglu, Parag A Pathak, Alvin E Roth, and Tayfun Sönmez. The boston public school match. American Economic Review, (5(2):368-371 2005.
[4] Elliot Anshelevich, Sanmay Das, and Yonatan Naamad. Anarchy, stability, and utopia: creating better matchings. Autonomous Agents and Multi Agent Systems, 26(1):120-140) 2013.
[5] Esteban Arcaute and Sergei Vassilvitskii. Social networks and stable matchings in the job market. In International Workshop on Internet and Network Economics, pages 220-231. Springer, 2009.
[6] Haris Aziz, Rupert Freeman, Nisarg Shah, and Rohit Vaish. Best of both worlds: Ex ante and ex post fairness in resource allocation. Operations Research, 2023.
[7] Moshe Babaioff, Tomer Ezra, and Uriel Feige. On besst-of-both-worldd fair-share allocations. In International Conference Web and Internet Economics, pages 237-255. Springer. 2022.
[8] Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log? (t) regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pages 705-715. PMLR, 2021.
[9] Gerdus Benade, Aleksandr M Kazachkov, Ariel D Procaccia, Alexandros Psomas, and David Zeng. Fair and efficient online allocations. Operations Research, 72(4):1438-144 2024.
[10] Garrett Birkhoff. Three observations on linear algebra. Univ. Nac. Tacuman, Rev. Ser. A, 5: 147-151, 1946.
[11] Eric Budish. The combinatorial assignment problem: compeinnttecomppitiiiiee from equal incomes. Jourmal of Political Economy, 11966):061-1103; 2011.
competitive equilibrium
[12] Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos, and Rohit Vaish. Sta- ble fractional matchings. In Proceedings of the 2019 ACM Conference Economics and Computation, pages 21-39, 2019.
[13] Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):1-32, 2019.
[14] Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. Journal of Machine Learning Research, 17 130):1-33, 2016.
[15] Richard Combes, Mohammad Sadegh Talebi Mazraeh Shahi, Alexandre Proutiere, et al. Com- binatorial bandits revisited. Advances in neural information processing systems, 28, 2015.

---

[16] Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In Proceedings of the 19th international joint conference on Artificial intelligence, pages 947-952, 2005.
[17] Lester Dubins and David A Freedman. Machiavelli and the gale-shapley algorithm. The American Mathematical Monthly, 88(7):485-49) 1981.
[18] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science conference, pages 214-226, 2012.
[19] Michal Feldman, Simon Mauras, Vishnu V Narayan, and Tomasz Ponitka. Breaking the envy cycle: fest-of-both-wordds guarantees for subadditive valuations. arXiv preprint arXiv:2304.03706, 2023.
[20] Duncan Karl Foley. Resource allocation and the public sector. Yale University, 1966.
[21] Rupert Freeman, Evi Micha, and Nisarg Shah. Two-sided matching meets fair division. In International Joint Conference on Artificial Intelligence, 2021.
[22] Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEF/ACM Transactions on Networking, 1666)1146611478, 2012.
[23] David Gale and Lloyd Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-11) 15, 1962.
[24] Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2)377--39, 2019.
[25] Magnús M Halldórsson, Robert W Irving, Kazuo Iwama, David F Manlove, Shuichi Miyazaki, Yasufumi Morita, and Sandy Scott. Approximability results for stable marriage problems with ties. Theoretical Computer Science, 306(1-3):431 447, 2003.
[26] Magnús M Halldórsson, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa. Randomized approximation of the stable marriage problem. Theoretical Computer Science, 325(3):439 2004.
[27] Daniel Halpern and Nisarg Shah. Fair and efficient resource allocation with partial information. arXiv preprini 2005 2021.
[28] Ayumi Igarashi, Yasushi Kawase, Warut Suksompong, and Hanna Sumita. Fair division with two-sided preferences. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 2756-2764, 2023.
[29] Robert W Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3): 261-272, 1994.
[30] Kazuo Iwama and Shuichi Miyazaki. Stable marriage with ties and incomplete lists. Encyclope- dia of algorithms, pages 883-885, 2008
[31] Sham M Kakade, Adam Tauman Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the thirty- annual ACM symposium on Theory of computing. pages 546-555, 2007.
[32] Gili Karni, Guy N Rothblum, and Gal Yona. On fairness and stability in two-sided matchings. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). schloss-Dagsturs Leibniz Zentrum für Informatik, 2022.
[33] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352-358, 1990.
[34] Michael P Kim, Aleksandra Korolova, Guy N Rothblum, and Gal Yona. Preference-infomee fairness. In / /thh Innovations in Theoretical Computer Science Conference, ITCS 2020, pages 16-1. Schloss Dagstuhl-Leibniz Zentrru fur Informatik GmbH, Dagstuhl Publishing, 2020.
12

---

[35] Zoltán Király. Better and simpler approximation algorithms for the stable marriage problem. Algorithmica, 60(1):3-20, 2011.
[36] Donald E Knuth. Mariages stables leurs relations avec d' d'autres problèmes combinatoires (stable marriage and its relation to other combinatorial problems). In CRM Proceedings and Lecture Notes, volume 10. Les Presses de l'Université de Montréal, 1976.
[37] Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching markets. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1512-1522. SIAM, 2023.
[38] Fang Kong, Jingqi Tang, Mingzhu Li, Pinyan Lu, John C.S. Lui, and Shuai Li, Bandit learning in matching markets with indifference. In The Thirteenth International Conference Learning Representations, 2025. URL Rtt.:tttt///ppeereevvee
net. formm? www.ooiddummuaeiie.ee 1d=7ENaks199]
[39] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pages 535-543. PMIR, 2015.
[40] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[41] Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125-131, 2004.
[42] Lydia Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In International Conference on Artificial Intelligence and Statistics, pages 1618-1628. PMLR, 2020.
[43] Lydia Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. The Journal of Machine Learning Research, ((():9912--9644 2021.
[44] Yicheng Liu, Pingzhong Tang, and Wenyi Fang. Internally stable matchings and exchanges. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
[45] David Manlove. The structure of stable marriage with indifference. Mathematics, 122(1-3):167-181, 2002.
Discrete Applied
[46] David F Manlove, Robert W Irving, Kazuo Iwama, Shuichi Miyazaki, and Yasufumi Morita. Hard variants of stable marriage. Theoretical Computer Science, 276(1-2):261-277) 2002.
[47] Nadav Merlis and Shie Mannor. Batch-size independent regret bounds for the combinatorial multi-armed bandit problem. In Conference on Learning Theory, pages 2465-2489. PMLR, 2019.
[48] Nadav Merlis and Shie Mannor. Tight lower bounds for combinatorial multi-an aalti-armed bandits, In Conference on Learning Theory, pages 2830-2857. PMLR, 2020.
[49] Pierre Perrault. When combinatorial thompson sampling meets approximation regret. Advances Neural Information Processing Systems, 35: 15:17699-17666 2022.
[50] Alvin E Roth and Elliott Peranson. The redesign of the matching market for american physicians: Some engineering aspects of economic design. American economic review, (944)7748-78, 1999.
[51] Alvin E Roth, Uriel Rothblum, and John Vande Vate. Stable matchings, optimal as- signments, and linear programming. Mathematics of operations research, 18(4):803-828, 1993.
[52] Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference on Artificial Intelligence and Statistics, pages 1252-1260. PMLR, 2021.
[53] Hugo Steinhaus. Sur la division pragmatique. Econometrica: Journal of the Econometric Society, pages 315-319, 1949.
13

---

[54] Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. Advances in Neural Information Processing Systems, 21, 2008.
[55] Chung-Piaw Teo and Jay Sethuraman. The geometry of fractional stable matchings and its applications. Mathematics of Operations Research, 2344)8874-811 1998.
[56] Hal R Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63-91, 1974.
[57] John H Vande Vate. Linear programming brings marital bliss. Operations Research Letters, (3):147-153, 1989.
[58] John Von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games. 2(0):5-12, 1953.
[59] Dietrich Weller. Fair division measurable space. Journal of Mathematical Economics, 14 (1):5-17, 1985,
[60] YiRui Zhang and Zhixuan Fang. Decentralized two-sided bandit learning in matching market. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction, we accurately present the setting and its motivation, well summary of our contributions, all of which are proved in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations and open challenges of our work in the conclusion
section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: Proofs of all the stated results provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /otee//guudddeeeedSuuuubmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:///haarrps..ccco/paa/////t
Answer: [Yes]
Justification: The paper is purely theoretical and studies a fundamental game theory model; such, it does have any direct ethical implications.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Due to the theoretical nature of the paper, there is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No data or models are released with this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
21

---

A Further Related Work
Fractional Matchings Aside from integral fractioo matchings have also attracted research interests due to their practical implications. For instance, in our running example, consider time-sharing scenario [51]. where each worker could spend five days week at work. An integral matching requires every worker work full-time on a single job, while fractional matchings allow them to switch among different jobs, making it natural in such situations. By the well-known (BvN) theorem [T0] 58 fractional matching could be written as a convex combination of several integral matchings.
In the context of stable matching. fractional matching has also been studied. Considering purely ordinal preferences, several notions of stability have been proposed, such as strong stability [51], ex-post stability [51], and fractional stability [57]. In these works, the stable matching problem is formulated as a linear program, Teo and Sethuraman [55] showed that any fractional solution in the stable matching polytope is a convex combination of integral stable matchings. On the other hand, concerning purely cardinal preferences, Anshelevich et al. [4] proposes the notions of stability and e-stability, while Caragiannis al. 12 shows that the set of stable fractional matchings that satisfies the notion can be non-convex.
In this paper, we consider two-sided market where the worker side has cardinal preferences while the job side has ordinal preferences. We do not concern the notions fractional stable matchings, instead, we focus on finding distribution over integral matchings such that it is fair in the sense that every worker could receive a certain fraction of its optimal stable share in expectation.
Fair Division Fair division is the problem of dividing a set of items among several people in a
fair manner. Steinhaus [53] pioneers this line of research and defines share-based notion, i.e.,
proportionality, where each player gets a 1/N fraction of all items. Foley (20) and Varian [56] define envy-freeness, where player prefers the bundle allocated to another player, and this notion later generalized by Weller [59]. In two-sided matching markets, stable matching eliminates justified envy [I. Regarding the problem of sharing indivisible goods, share-based guarantees such as MMS [I] and envy-based guarantees such as EFI
or EFX [13] are proposed. Recent works have studied best-of-bothh both-world fairness 6. providing random allocation with fairness guarantees both in expectation and for every realization.
Approximation Regret in Bandit Learning combinatorial bandit problems. approximation regret is often considered instead of the standard regret [31] 55 [2] 14
47 49] The reason mainly lies in the complex reward structure and the computational intractability of the problem, i.c., rewards are often dependent on the combination of actions, leading to an exponentially large action space, which makes it computationally prohibitive to find the exact solution.
Besides computational intractability, there is another more fundamental reason for using the approxi- mation regret framework in this paper. The stable regret is defined for each worker, which means the company aims to solve a multi-objective optimization problem while it couldn't 't satisfy everyone simultaneously. Consequently, the approximation regret serves as a compromise between fairness and efficiency.
B Lower bounds on OSS-ratio
B.1 Lower Bound for Distributions over Weakly Stable Matchings
The proof idea of Theorem | could be illustrated through Figure
Proof of Theurem 7 Assume that is even, let W = {wi, W2 wyy } and A = N + and wi > we > ... > wy for all the jobs. The utility {a), 022 ... .g} with K = 2 matrix that encodes the preference of workers over jobs is as follows:
22

---

highly-skilled workers
regular workers
Figure 1: Lower bound Rs. All jobs have the same ordering workers, from top bottom. Any stable matching can be obtained by letting the first worker pick a job, then the second, etc. Hence, each stable matching contains at most one blue edge.
N
2
o 1 1001
N 2
i
0
In any stable matching, every worker wi in {w1, "2, WN/2 } must be assigned to a, or a +1 leading to a utility of for them. Without loss of generality, let μt be the matching such that (uw))) ag 41+1- Then in (4, only worker wy would receive utility of 1, by matching it to job ai while all workers in {WN//21,"" WNN/2+i-: WN/2+i+1:"" [NN would be unmatched and receive utility of O. Indeed, for any * the unique optimal match of worker WN/2+3 is already taken by worker W/.
For every stable matching, at most one of the workers in {WN/241, WN/2+2 ... WN) could be assigned to their optimal match. Since there are 2/2 such workers, then for any distribution D, there must be at least one of the workers for which the probability to be optimally matched is smaller than 2/N, for this worker, holds that U ('(w) N which implies Rs N/2.
(n(w) 2 2
Remark 4. Theorem shows that we only consider random allocations of stable matchings. then in the worst case, workers could only expect O(L/N) profit share compared to their benchmark. On the other hand, define
111 ((w;, : (1,2...../2)),,
#2 {w1,4//2 a:) :
Here, μn is a stable matching while μl2 is non-stable. We construct distribution D as follows:
P(D = = P(D = =2)
then all workers have Up(w) 2. This result implies that if we consider possibly non-stable
(w)
matchings for the support of D, there is space for improvement on the OSS-ratio.
B.2 Lower Bound for Distributions over Matchings
The proof idea of Theorem could be illustrated through Figure
23

---

In-1
In-1
In
Figure 2: Lower bound on RM- In each example, left nodes represent workers while right nodes represent jobs. If there is an edge connecting left node and right node a, we have U(w, a) and U (w, a) = 0 otherwise. All the right nodes without edges connecting to them are hidden from the graph.
Proof of Theorem 2 Consider the following sequence of problem instances, depicted in Figure 2 In each bipartite graph, left nodes represent the set of workers while the right nodes represent the set of jobs. Jobs share global preference over the workers, with the topmost node being the most preferred and the preference decreasing from top to bottom. From the worker side, the utility matrix is binary. Specifically, for worker-job pair (we, a), Uww
if (w, a) is connected, while Uww, a) = 0 otherwise. For example, J is the graph representation the problem instance of Example
Instance I, is constructed recursively. Given I--1, we first duplicate this instance, denoted the replications as upper class and lower class, respectively. Take Kn- as the number of right nodes and Nn-1 as the number of left nodes in In-1, and denote these nodes as aa ag, --. ,
,ak, ) { (wf. wh w..,.h.,)) for the upper and lower classes, respectively. Then, we introduce K2 Kn prioritized workers in In who are uniformly more preferred by the jobs than the workers in the upper and lower classes. In particular, denote the set of prioritized workers as { [W1, W2. WKKK- }. we have
".". w _ and
W1 W2
WKn-1 wi wy
Wi-- > w > w/
W
And for each wi, we have (w,, a Uws, af) = 1, and U U(w,, a) O otherwise. We first prove by induction that the optimal-stann stable---aee (w)) = for any worker w. For To, the unique matching is stable. Suppose that for any worker in In-1, there exists at least one stable matching such that U(w, p(w)) 1. Then in In. all the prioritized workers could matched in any stable matching. Furthermore, as long as they simultaneously choose to be matched to the jobs in the same class, the other class is free, and hence by induction assumption, every worker that class gets chance to be matched in at least one stable matching. Therefore, by breaking ties for the upper (lower) class, all workers the lower (upper) class can be matched.
On the other hand, given that (w) = 1 for any w. the ratio RM is equal to minp max, Un( for these instances, Then, proving lower bound on this quantity is equivalent to establishing bound on maxp min. (Dw particular, we have maxp min, (D( S maxp where N is the number of left nodes. Now notice that Σn, (D(w) is the expected size of the matching under distribution D, since the utility is when a worker is matched and 0 otherwise. We have Σ (w( < K from the fact that the size of any matching is bounded by K. Combining the above derivation, we have
upper Σ. Un(w) N
N RM 2
K
Finally, in instance In. by the recursive construction, we have
K,, 2- Kn-1;
N, 2- Nn-1 + Kn-1-
24

---

Solving the recursive equation with the initial condition Ko No = 1, we know that there are 2" right nodes and (n 2)2 left nodes in I, which implies that RM 2 n/2 + 1. We rewrite N (n + 2)2n-1 to obtain 2 = 2N + 2) and we deduce that
N/n S 2" S 2N.
Taking logarithm in the inequalities, we have
log2 N - logg 11 S S + logg N.
And thus
2 loga N - llgg 2 log2 N - log2(11 + loga N).
Therefore, Q(log N) and hence RM is S2log N).
C Upper Bound on OSS-ratio
C.1 Procedure Illustration of Algorithm 1
We use Example to illustrate the procedure stated in Algorithm 1
Example 3. Let W = {wi, W2, wa). J. A { {a1,02,000 0s). We consider the following preference list Pa
jobs over workers, and utility matrix U that encodes the preference of workers over jobs:
a1 : w2
wi W3.
1
0
02 : W1 > W3 > W2:
U= 0.5
0.1
0.1
0g
wi w2 wz.
0
0.8
0
the preference profile Pw generated from the algorithm is
W1 d1 (1) > a2
(1)
(2)
(2)
(1)
(2)
a
a2
03
0g
(2)
(2) > 03
a > aj
02
03
02
(2)
(2) > 0g
W3 > a
Running Cale-Shapley algorithm on Pw and Pa. the worker-optimal stable matching would be
j {Wi,, (wi,a (1)) (w2, (1)) ); (wa, (2) }}, and can recover two internally stable matchings from
ie., jI [[w), (2), (W2, a1)} and jú2 = {ww3 U2)).
C.2 Proof of Theorem
In Algorithm]] 1 each worker is matched in exactly one matching jús, where we call the index of w, denoted index(w) (w)) In other words, the index of a worker is the index of the job she receives, that is, index(w) i worker w receives a for some j.
Definition 8. Given a problem instance (U, Pa), run Algorithm with duplication number m to generate the oulput distribution D. Then, for any stable matching p with respect to (U, Pa), define a graph G = (Vp: E,)) where
V, (w E. U(w, 2 m .U[(W},
E, = ((w, V22 p(w) = [1,(w') where j = index(w') < iidex(()).
Informally, Gy is the graph of workers who (weakly) prefer to their match in distribution D, where an edge (w, w') means that w' received job that w would have liked. Next, we show properties on the graph G,,, which we illustrate in Figure
Proposition 1. For any stable matching p. the following holds
G is a directed forest (there is no cycle and each vertex has at most one incoming edge),
For every worker w E Vn with index(w) and for every 1 S j < i, there worker w' Vy with j index(w') such that (w, u' E Ey.
25

---

index
workers
jobs
1
K
2
(2)
(2)
M
K
E,
3
(3)
(3)
K
Figure 3: The graph Gy. - (Vμs Ep) is a directed forest. The matching jt, computed in Algorithm 1 matches each worker to a single (copy of) job in jt. In the stable matching μ4, each worker w is connected all copies of p(w) which have lower index.
Proof. The graph Cy is a directed forest by construction. Indeed, it has no cycle because edges connect workers to lower index workers. And every node has at most one incoming edge because ji matches each worker to at most one job, and matches each job to at most one worker.
Fix worker w E V with i = index(w), ). let 1 j < i, and let = u(w). By definition of V worker w weakly prefers μ to D, that Uww, a) 2 m Up(w) Uw, (w))) By definition of w's preference list Pw in Algorithm the lexicographic ordering gives that
a!)) P j((w).
Because ji is stable matching, it should not be blocked by the pair (w, all). Thus, there exists worker w' W such that jiw')) ) a and
>a W.
Finally, because y is stable matching, it should not be blocked by the pair (w', a). thus
U(w', ((ww)) )) 2 U(w', a) m UD(W"), proving that w' E Vp. Hence, there an edge (w, w') E E, which concludes the proof. Proposition 2. the graph G,,. each node of index 2 1 can reach 2 nodes (including itself).
Proof. We show that the property holds by induction on i. The property trivially holds for i = 1. Let i > 1 such that there is a worker w E V, with index(w) = i. Using Proposition I there is an edge (w, wy) E En with index( w,) = for every 1 S j < i. Because the graph is a directed forest, the set of nodes reachable from each Wy are disjoint. Thus, the number of nodes reachable from w (including itself) is + 2 2/-1 = 2
Finally, we conclude with the proof that Algorithm computes a distribution over internally stable matching which guarantees each worker a logarithmic fraction of their optimal stable share.
Proof of Theorem 3 Algorithm I first computes stable matching je for the instance with duplicated jobs, then build m matchings 11, .1..... Pmm. If there were a pair (w, a) with index(w) which blocks matching n., that is U (w, a) Uww, (w)) and > [a),), then (w, al)) would block j., which is contradiction. Thus, each matching fi is internally stable.
Now, let assume, that there is stable matching μ in which worker w with index(w) i receives a μ(w) having utility U U(w, a) > U(w, (.))). In the matching م., job (m)) must be matched to some worker w' such that w' >a w, otherwise (w, a) would block f.. Moreover, we must have U(w', juw')) 2 UD(w") otherwise (w', a) would be blocking p. Thus, there is node w' E Vy. of index m, which proves that there exists at least 2 nodes, and thus that N 2 2 By contrapositive, if set m + log, N, then we have m Un(w) U (w) for every worker w, which concludes the proof
'Interestingly, can show that log, N suffices because each (( is matched in different
worker W, E Vy. who can reach 2 distinct workers in G,., none of them being w (as this would contradict jo being worker-optimal), which gives at least 2 workers in total. However, for the sake of simplicity. we do not present this improved bound.
26

---

C.3 Dominant Strategy Incentive Compatibility of Algorithm
Proof of Theorem We will use the fact that when workers have strict preferences, Gale and Shap- ley's s worker-proposing deferred acceptance procedure is dominant strategy incentive compatible, i.e., is always optimal for workers to report their true preferences [7
First, notice that for each worker w. the ranking Pw used in Algorithm aligns with her utility, ensuring that all copies of higher-utility job are ranked above copies lower-utility ones.
To see that it optimal for a worker w to report her true vector of utility, we will give her more strategic power, and we will let her choose her ranking P over all the duplicated jobs. By the incentive compatibility property of the deferred acceptance procedure with strict preferences, she cannot obtain any job ranked above ((w) in Pw. And because Pw is consistent with w's utility, is optimal to report P Pw-
D
c-Oracle for Approximated Worker Optimal Stable Matching
D.1 e-Oracle
Algorithm 2 c-Oracle for Approximated Worker Optimal Stable Matching
Input: N workers, K jobs, Utility matrix U that encodes the preference of workers over jobs, strict preference profile Pa of jobs, an integer m 2 1, and the instability tolerance 2 0.
1: For each job E A, duplicate it m times and denote the i-th copy as (())
2: Each replica (9) shares the same preference Pa as the original job a.
3: For every worker ws and job (+), define the utility
Uww, a ( == U(w, a) - 1)e
and use it to generate the workers' preference profile Pw (breaking ties favor of lower indices).
4: Run Gale-Shapley algorithm Pa and Pa to compute worker-optimal stable matching j..
5: For each E [m]. build a matching i.. which matches each job with jı<(a) A((())).
Output: The distribution D which selects each matching t4, with probability 1/m.
D.2 Proof of Theorem 5
Similarly to the proof of Theorem we run Algorithm 2 and define the index of a worker as the index of the job she receives in jú, that is, index(we) i if worker receives a. for some j.
Definition 9. Given problem instance (U, Pa), run Algorithm 2 with duplication number m and instability tolerance generate the output distribution D. Then, for any e-stable matching P with respect to (U, Pa), we define graph G₁ = (Vuy E,) where
V = {w E W (w, ((w))= 2 m UD(w) - -E},
Epp : [(w, w/) E V22 ((w)= = (,,(ww) where = index(w') < index(w)).
Once again, Gy, is the graph of workers who prefer j to their match in distribution D, where an edge (w, w') means that w' received a job that w would have liked. Next, we show properties on the graph Gn.
Proposition 3. For any stable matching we have that
G is a directed forest (there is no cycle and each vertex has at most one incoming edge),
For every worker w E Va with index(w), and for every S j < <,, there a worker w/ e Vy with j index(w") such that (w, w/) E Ep.
Fix worker w E V, with index(w:). let and let p(w). By definition of Vu, worker prefers D, that is U a)
Proof. The proof is almost identical that of Proposition] 1
27

---

m UD(w)= - (w, fx(w)) - e. By definition of w's preference list Pa. in Algorithm 2 the lexicographic ordering gives that
a P.. ((w).
Because j is a e-stable matching, it should not be blocked by the pair (w, ab)). Thus, there exists a worker w' W such that ji(w") = al)) and
w.
Finally, because ys is stable matching. should not be blocked by the pair (w', a), thus
Uww', ((w)) 2 Uw',, a) - m (u('')== -,,
proving that w' E Vn Hence, there an edge (w, w') E Eny, which concludes the proof.
We will once again use Proposition to give lower on the number of nodes in the graph G,,. Finally, we conclude with the proof that Algorith@@compee computes distribution over internally e-stable matching which guarantees each worker a logarithmic fraction of their optimal stable share.
Proof of Theorem 5 Algorithm first computes a stable matching jı for the instance with duplicated jobs, then build matchings fi..... Pm. If there were pair (w, a) with index(w) which e-blocks matching jú. that is (ww, a) (ww ju; (w)) + and > (a(a), then (w, a (1) would block jú, which a contradiction. Thus, each matching P4 is internally stable.
Now, let us assume, that there is a stable matching μ in which a worker w with index(w) = receives = (u(w) having utility Uww, a) > U(w, U(w,ū,(w)) + me. In the matching μ., job (1m) must be matched to some worker w' such that w' >a w, otherwise (w, a) would block j.. Moreover, we must have U(w', j(w')) 2 m UD(w") - otherwise (w', would be blocking μ.. Using Proposition 2 there node w' E V₁ of index m, which proves that there exists least 2 nodes, and thus that N 2m-1 By contrapositive, if set m for every worker w, which concludes the proof.
logg N, then have Up(w) 2 U (w)/mn
D.3 Robustness of c-stable matching
Lemma 1. Fix the preferences jobs over workers. Given two utility matrices U1 and U2 such then any stable matching i for Un is also e-stable with respect to U2.
that U1 U2| max <
Proof. If matching μ is stable with respect U1, then for any (w, a) pair such that w >a p(a), must have
U1 Uww a) (w,p(w)),
(10)
from the definition of stable matching (Definition] D
Since |UU - U2 2. we have that for any (w, a) pair, U (w, U2(w, a)l S s. Therefore, U2(w,a) a) < (w, a)
(ww ((w)) < U2(w, H(w)) +e,
(11)
where the first and the last inequality come from ||U - U2llmas S s. while the second incquality holds according Eq. {O). Therefore, combining >a p(a) and Eq, [I]. we can conclude that matching μ is e-stable with respect to U2.
D.4 Proof of Theorem
For convenience, denote S (resp. 5K the stable matchings (e-stable matchings) with respect to U.
Proof. By running Algorithm with U -Ú c,m [log, N + +2), from Theorem 5 get
Un(w) 2 Ú:(w)
Vw W. m
(12)
'ee recall that the max of matrix A = (Ai,), defined by ||A]|ma maxi,) |Aisl-
28

---

By construction, any utility matrix U E U satisfies I Ummax S 2. From Lemma we know that for any matching μ E S YU E l we have μ E St that is Uveu Su C St Therefore, for the optimal stable share, have
(")w) S (w),, Ve e W.
(13)
Combining 12. and
13 the conclusion holds.
E
Explore-then-Chooss-One
Algorithm
Algorithm is the full version of the
algorithm.
Algorithm Explore-then wawioore-tte--hhose--eeeeeeee Choose- (Full version)
Input: N workers, K jobs, horizon T, exploration length To < T, preference profile Pa for all jobs
K. approximation stable-matching oracle O.
1: Initialize: (i, j) 0, T 0, Vi E [ E [K].
2: Initialize: F; 4- False.
> Whether the CIs of the first (N + 1)-ranked jobs are disjoint.
3: Set = 1,7 +- K [To K fm
To have full rounds of round-robin. A Phase I, round-robin exploration.
4: while S Ty and 3 E [N] s.t. F. = False do
5: Match (i( & (((t+i-1) mod K)+1, V [N].
6: Observe (1) (t) and update (i, (1)), Time(()) as follows:
(1i))((1)) = ((l,Me(i) T.mm()) (1) Tepa(() +1
.T,pet)) Ti,pe(t) + 1.
7:
1+1
8:
ift mod
then tm & fm + 1.
> Completed full round of round-robin
9:
Compute UCB. and LCB,, for all i [M].j [K].
See Equation
11:
for i= 1,2, 1,2.... .... N do
12:
Ü (i. t- (o decreasing)
Aimin f- min (i)) - Ù [ 1),5 E [N]]
13:
if min > 2 Gln then
14:
15:
F. + True.
16:
end if end for
17:
18:
if F. = True, Vi [N], then
No ties standard oracle
Compute preference list Pw for all w e W according to Ú
20:
A + worker-optimal stable matching w.r.t Pw and Pa (using GS algorithm) Potential ties approximation oracle
else To then
22:
j < (U) for U s.t. Úi.jj) UCB,, for all i [N].j E [K]
end
24:
end if
25:
end while
26: while < T do
b Phase 2, exploitation with the chosen oracle.
27:
Match (i) < (i),
28: t t +1
29:
end while
F
Technical Lemmas
Lemma 2 (Corollary 5.5 in Lattimore and Szepesvári independent, o-subgaussian random variables centered around p. Then for any > 0,
40
Assume that X1, X2,
Xn, are
ns²
x
ne²
P
X
X
< exp
Σ
X < n
< exp
71
20
71
2n
i=1
29

---

Lemma 3 (Divergence Decomposition, Lemma 15,1 in Lattimore and Szepesvári (00). For two
bandit instances v (Viz [N].je E [K]]. and {V/ : [N], [K]], fix some policy π
and let vv,= and Pu', be the probability measures induced by the T-round interconnection of a and (respectively, x and v/), the following divergence decomposition holds,
D ( (PTTT
(i,)Ni((T) D (Vij.
(14)
Lemma 4 (Data- processing Inequality, Lemma in Garivier al. (24). Consider measurable space F) equipped with two distributions F1 and P2, and any F-measurable random variable Z 1 + [0, 1]. We denote respectively by Ei and Eg the expectations under PP and P2. Then,
KL (P1, 2 (E, E2(1),
where kl denotes the KL divergence for Bernoulli distributions, i.e. vp.g [0, All,, p In 2 + +1 p)ln 1-2
1-4
G Proof of Therorem 7
LCB be the value of Ú(i,)) Tag. UCB LCBi, at the end of round Define [T [N]. E [K] (i,j) - U(1,5)> preference is not estimated well during the horizon.
For convenience, let (i,), T. UCB ig
6ln T
as the bad event that some
Lemma 5.
P(F) 22NK/T.
Proof.
6ln T T
P(F) = P
31 SISTIT [K]: (1,) ( U(I,))
G T T
Σ E
P -
[=1 NE[N] jE[K]
66n
T
i5 = s,100( U(i >
8
NE[N] JE[K] s=1
Σ Σ
1. 2x3
t= [E[N]JE[K]
< 2/TTT,
where the second last inequality results from Lemma 2
Lemma 6. Conditional on "F FFUB < LCB(()
j.j implies U(i,j) U(i.j")
Proof. According the definition of LCB and UCB, we have that conditional FF,
T
6ln
LCB(1 = ÚÚ(() bg
S oV.
+
UCB()
T
T
Therefore, UCBB <CB( ig' we have that
U(i.i) s UCB LCB(}. < <U(,)").
30

---

Lemma 7. In round I, let T: minje[k] T:3 Conditional on FF. i5T > 96 7/ min have LCB (CB(() ippent for any [N]. and LCB UCB k S K.
L.Pii
i,pi for any N +1
Proof. We prove it by contradiction, suppose that there exists E [N] such that LCB UCB S.L.4 or there exists N + 1 - k < K such that LCB()) SPP. S UCB Liikk Without loss of generality, denote as the arm on the LHS and j' as the
S.p.
the RHS.
Conditional on "JF and by the definition of LCB and UCB, we have that
66n S L.B SUCB SU(i))) +2 U(i,5) 2/
6ln 7:
VV
Gln Therefore, A.j.r U(,)) Uni S V
which implies that T(
96
96 T, mnn
which
T.0
a contradiction.
Lemma 8. Conditional on FF, if Amin 96K In To phase and choose the Gale-Shapley oracle at some S To-
Algorithm would enter the exploitation
Proof. If Amin
I6 To
we have To > 96K In
Since for every worker, Algorithm 3 allocates
Amin
jobs in a round-robin fashion, we have that TT(1)
A
UCB()) i.p.at for any k [N]. and LCB,,, UCB(!) k,pi,k for any N < k < K, i.c. the preference utility for the first N-ranked jobs for every worker has been estimated well enough with the confidence intervals disjoint. The flag F, would be set as True as in Line 15 in Algorithm 3 and we would enter Phase 2 at some time t S To.
By Lemma 7 we know that for any worker wy. LCB() LPEA
Lemma Given a utility matrix UNxK K without ties, the worker-optimal stable matching job of each worker must be its first N Nrranked.
Proof. We implement the Gale-Shapley algorithm with the workers as the proposing side. Once a job proposed, has a temporary worker. By contradiction, once jobs have been proposed, we have N workers occupied. Therefore, each worker would be allocated with job and the Gale-Shapley algorithm would stop. Since in the one according to their preference list, then the worker-optimal stable matching job of each worker must be its first N-ranked.
procedure, workers propose jobs one by
Proof of Theorem 7
We consider the two cases separately.
Case 1. Amin
96A In
To
Let Aj,max = max (a(K) UU" (w;) U(i be the maximum worker-optimal stable regret that may be suffered by we in all rounds, we have A Aimax < 1. The worker-optimal stable regret for each
31

---

worker wi by following Algorithm
satisfies
(T) E
(U*(w;) -x((O))
s
Σ (1)(1) # * A,ma
(15)
S
((((1) # (1)) |J
i,max +FFF) T. maax
S E
Σ
(()(() + 1 (1) |T
Aimar + 2N K A max
(16)
1=1
96K 7
A i,aaz + 222K A.KA,,ma m,max
(17)
A min
K In T
0
A
min
where Eq. 15 comes from the fact that in a matching market without ties, there is unique worker- optimal stable matching and hence a unique optimal stable match μ (i) for worker i, (6) holds based on Lemma 5 (q.(7)) holds according to Lemma 8 and [ and the fact that Gale-Shapley
algorithm could always output the worker-optimal stable matching with respect to the given utility matrix by treating worker as the proposing side.
Case 2. Amin
96 To
The objective function is the approximation regret Reg)(T). Denote F(l)) the event that > (CD!!) L.pL+ for all k E [M], and ((t(())
LCB(0 i,pt, i.p..
B. > UCB(!) &pp for all N + 1 s k S K.
We have
Reg (T)
oT U (wx) Σ x,(t) F
-P(F)
T
+B aT UW;; - Σ Xi(1) 175 -P(F)
1=1
T S STT- +E oT a..UU (U")) - - x,(t)
(18)
1=1
T
<2NNK +
of U'((W))
Σ Xi(t) 1
(19)
1=1
(T. (W:)(())) Σ Xi(t) 1( (Tb)
}
<2NNK +E
17F
+E ( OT (OT.UU (T--U((.))) Um(1,) - Σ -xx(() 1 (F( 17
T
T s 2aNK+ + a +E (( aT ( Ex(() 1f (T)) (o) 1
(20)
where Eq. 18) comes from the fact that U*www) < 1 and X,(t) 2 0. Eq. holds according to Lemma 5 Eq. (0) comes from the fact that when the good event 7F that all utilities are well
estimated and the top (N + 1)-ranked CIs are disjoint before To. the Gale-Shapley algorithm would give us the OSS the exploitation phase, and since a (0, 1). the approximation regret would be no larger than aTo + (a - 1). (T - To) I aTo
32

---

Moreover, conditional on FF, we have the ground-trun truth utility matrix U lies in the uncertainty set constructed by the empirical mean utility matrix UTTo) and the UCB(To and LCB(To) i.e., for any
(i,j) E [M] x [K], ( (i,,)) S
6KInT
If we implement an (a, e) e)-oclle, with To
being 2v 5K In follow similar proof that for Theorem in each round t in the exploitation To
phase, we have that
6K In To
(w,) (X.((t))) - 2/
(21)
Since there are total To rounds of exploitation, we have that
B aT (wx) Σ xi(t) 1 F
|
S all +2
6K In T
(T
To).
(22)
To
Therefore, combining Eq. 20 and 22 we have
6K In
(T) S 2o 2aTo + 2V
(T To).
To
H Proof of Theorem
Proof. Let W = fwu, u2, Way wa) and A {ai, 0g dz, as} and w1 > W2 Wy Wa for all the jobs. Throughout the proof, we assume that all observations are Gaussian of unit variance, that is, observe X2(1) (NUUU,, 1). Consider two instances
when matching w; to aj at round and v with the following mean utility matrices U and U", respectively.
2
1
0
07
Y
0
0
U
2
U
0
0
0
2
0
0
where Y <
Lemma 10 (Properties of Instances and v'). Based on the utility matrices U and U', we have the following properties of and v':
1. Under v, the optimal stable shares are U U*ww) $. V. E W; Under v', the optimal stable shares are (U')*ww) + (U2) = 2. (Ua)" = 1. and (w')
(wA) = O.
2. The relevant utility gaps for the two instances are A = 0, and A =
3. Given an offiine oracle that could compute the best approximation ratio, the benchmark utilities for the four workers (after multiplying the approximation ratio) are (22 8 under and (2 + 7, 0) under v'.
We provide the proof of Lemma 10 Appendix !
For a worker Wi E [N], job J E [ and time slot E [T]. denote (t) E NU as the num- ber of times worker w; matched to job aj. up and including time and denote the past information as J : (/1, X (1), N2, X(2), -/4-1, X(t (t- 1)), where X = (t), ...........(((( is the realized reward vector for all N workers in round Finally, let Pe,, be the joint probability measure over the history and E,,x be the expectation induced by instance v and policy म. and Par... .x
Ex', be defined similarly. By divergence decomposition theorem 40 restated in Lemma have that
N Σ
DKL (Pe,. Pur,))
E Noy(T) ) DKL.
i=1
33

---

where Vij is the distribution of utilities obtained when worker w; is matched to job aj in the environment V.
Since the only change in utility distribution happens (101, a1) pair, we have that
DKL (P (Pr,,.Pe,,)) (KI, 1/1) [Nn Eu,= [Nn
(23)
2
where the second equality comes from the fact that for two Gaussian distributions with means & and y and variance the KL divergence is 2
By data-processing inequality [40] restated in Lemma we know that for all meaassuualrll random variable Z E [0, 1). we have that
DEL UR,
(or,,) kl (Bun (Z), Eur Burr, (Z))-
(24)
where kl denotes the KL. divergence between two Bernuulli distributions, i.e., vp,q [0, (llp.()p)))) = pln P p) 1-9"
1-p
Let Z Nan(T)+NNaa11))) then Z E [0, 1]. by Pinsker's inequality, have that
kl (E,, (Z), Eur,, (Z)) 2 [E =x),
(Z))
(25)
Combining Eq. 23 24
we have that
72 By (T)
2 (7) -Ey,, (Z))²
(26)
2
We now divide into two cases, depending on the asymptotic number of matches Ep,, [N (T)).
Case I: lim inf Eu. (N, O. We assume that both Reg. w/) and Regi a' (wi) (T:P)
T
are sublinear for all workers and show that we have a contradiction.
Since cT 1+6 by Eq. (6 we have
E [22 (Ta E. [N2i N2s(T)
lim inf
(27)
T 70000
In v', if the ground-truth utility matrix U is known and we would like to achieve the benchmark utility for W2, we need N21 (T') ) + (T) = T, since worker W2 could only get positive utilitics from jobs aj and ag and her benchmark utility is 1.2 In particular, the regret for this worker is
Reg.(T; v') = (T Ev i [N21 (T) + N2a(T))),
and to guarantee sublinear regret for wz for any large enough T, we must have
Ev [N21 (T) N23 =1
lim inf
T'+00
Therefore, to satisfy Eq. 27
we must also have
liminf Ev.. [Nei (T) + Naa(T)) 7-
(28)
T
On the other hand, since ut4 only gets positive utilities in 34, to achieve the benchmark utility in v, we need (T) = T7. Therefore, to guarantee sublinear approximation regret for W4, we must have
Ep. [Na3(T)]
lim inf T-000
2
T
4'
which implies lim supr-400
4. since the total number of times that jobs ag being allocated cannot be more than the horizon T. Therefore, lim inf Ez. (Nar aacording to Eq. (28). Using again the fact that a job can be allocated no more than T times, we get
Ep,x [Ne1 (T)) 1
lim sup T-000
(29)
T
4
34

---

Finally, we write the regret of Wy as
37
1
Reg (T)
En u
[Nai (T')
- Eu, [N4
37
Ev, [Ns1 (T))
(E [ (T)) Eu, (T))
8
T
P (T)),
8
where the inequality is since w3 is matched at most 7 times, namely, Ex, Regj (Tww.
N24 (T) (T))
T. Combining with Eq. 29). we have lim inf worker w3 suffers linear approximation regret in M.
to which implies
8 4
Thus, summarize, assuming that all workers in both problem exhibit sublinear regret for this case leads to a contradiction.
Case II: inf Fe. (T)) some worker.
0. Our goal is to prove lower bound on the regret in for
T1-28
For a fixed T, denote for brevity N = Ex,= [N (T)), and assume with contradiction that all workers W2, W3s W4 suffer a regret smaller than N/32. Denote the cumulative allocation given by the algorithm by D E [0, 444,, namely ji = Σi= 1l [(m,, .z) E J.). In particular, we know that 1) N and that for all E (2,3, 4), holds that
ΣVGADON
3T
N
E (2,3,4),
(30)
32
We now state set of assumptions on the matching that the policy outputs at each round. Each of these assumptions never decreases the worker utility. Thus, and since we want to prove contradiction in the utility lower bound of Eq. (30). they could be assumed without loss of generality.
1. When wi is matched aj, it always matched to a2 (D(L, + D(L,2) T) so that it suffers zero regret.
2. dg is always matched to either wy or wa (D(,,3) + D(4,3) = T).
3. d1 is always assigned to one of the first three workers (D(1,1) D22, + T).
4. If aj is not assigned to wz, then a4 is assigned wa (D(3, 1) D(3, 4) T)
Notice that changing each individual allocation follow this condition can only require unmatching worker from a job that yields her no utility and matching all conditions is feasible (e.g.. by
a = (( a1), (wa, a4), (W4, {)
We now modify the matching allocation D to allocation while maintaining the above properties as follows:
We initialize = D.
If D(4.3) < 16. we set (44 3T leave (44 = 34. By Eq. (30). we know that (44 2 37
18 and D(2
1 otherwise, we
and combined
IG
with Assumption 2, this change can only decrease the allocation worker w2 by
N 8
D(2 - D(2 = D(4,3)
This decreases the utility of worker wa by - < N modification, the cumulative utility of worker w4 is
16 and after this
3T 5
+ 32'
By Assumption 1, we know that 1) N and D = N. We also know by assumption that in all rounds where d1 was assigned to w1, 04 was assigned to wa, and therefore, D(3, 4) > N. In D, we move all the N assignments of (Wi, a1) to (wi, 02), so that (11, 1) 0 and 2(1 = T; in particular, wn still gets its OSS. We split the allocation of evenly between wa and uz by letting:
35

---

1. D(2.1) min D(2,3)) N/2), thus making sure that the utility of W2 at least either 7/2 37/8 N/16
N + D(2.3) 1 D(2.1)+
N 8
37 N
3N
3T
5N
(D(2.1)
32
16
8
32
where in the last inequality we again used the assumption on the regret of w2 in Eq.330)
2. We move the matches from (wi,a) a1) that were not allocated ( 1) as follows:
(33, 1) - D33, 1) + N (D(2, D(2, 1)) 2 (33, 1) + N/2, and, D(3, 4) = D(3, 4) (N - (D(2,1) D22, 1))) 2 D(3.4) - N/2.
Both allocations are valid since D33, 4) 2 due Assumption 4. In particular, this shift from 0.1 to a increases the utility of wg by at least (1 1) N N ensuring total utility of at least 3T/8 + 3N/32.
Notice that all changes either kept D Hlobbly-soochaae matrix or decreased the sum of row we can w.l.o.g increase another element of D or use partial matchings.
Importantly, at the end of this process, the utility of wh under the matching distribution D re- mained 7/2, while the utility of all other workers increased by at least N/16 contradicting the fact that no matching distribution can collect more than 37/8 to all workers w2, W3, W4. Thus, Eq. (30p cannot hold and at least one worker must suffer a regret of at least N //32. Finally, since lim inf
Ev. Bv.,(N,,
0, we get the same for the regret of one of the workers, concluding the
proof.
I Proof of Lemma 10
Proof. We proof the three properties as follows.
Optimal Stable Share
Under v, consider the following stable matchings: μ1 = {[w], a2). (w2,a1); (wa, 04), (w4, 0z)) and #2 {(w1, a2); (w2, ag), (Wa, a1), (w4, a4)). The optimal stable share is U*(w) 1. Yu
W with wt and W2 receives it in both matchings, W3 receives it in matching #22 and w4 re- ceives it in matching μl1 Under v', the optimal stable shares are (u')"(w)) = 1 + % (w2) = 22
(wa)) = 3. and (ws) = 0, achieved through the stable matching 1' ((11111)))))) (w2, az), (W3, a4), (wa, az)}.
2. Relevant Utility Gap
Besides, the relevant utility gap for v is A = 0 since both μ4 and μز belongs to the Pareto-optimal stable matching set st.. On the other hand, since the jobs have global preference rankings over the workers, i.e., serial dictatorship. μí is the unique stable matching with respect to v', i.e., St" = (u'). perturbation of -y in (1, 1) or y in (1, brings ties for worker w1, and hence would change St' tp Shy On the other hand, a perturbation of in U33 or 1 in U(3,4) would make SU' include both pí' and μ12 [wi a1) (w2, as), (wy, az), (wa, a4)) All other entries need perturbation of scale larger than 1 to change the Pareto-optimal stable matching set. Since 7 < 4 we have that A 7.
3. Benchmark Utility
Let 7 = cT-1/2+ó for some 8 E (0, 1)) Then, under v, we aim to minimize the approxima- tion regret (eg for every worker W;, while under v', the objective is minimize regret (T) for each worker w;. Given an offline oracle that could compute the best possible approx- imation ratio, the benchmark utilities for the four workers (after multiplying the approximation ratio) are (1 3 3) under u and (1 + 7, 2 1. 1.00 under v'. For v', by serial dictatorship. the allocation scheme is equivalent to letting the workers choose their favorite jobs one by one. Do- ing so leads to the matching μ = [(w), (2), (w2, 0a), (w3, a1), (w4,a4)), which is unique since for all workers, when they choose their jobs, only a single unallocated job maximizes their util- ity. Hence, the benchmark utilities are immediately determined by the utility under this matching.
8 8*88*81 8
36

---

For v, since all workers but wi have no utility from job d2, and (w1) = (1, it is always optimal to assign 02 wi deterministically and the benchmark utility for wi 1/2. For the other players, if we match w2 to di, then for wa and wa, there are two possible matchings, i.e., ((w3,as) (Wa, a3)} and { 03), (4)) but the first one is always better since it gives both players higher utilities. Similarly, if we match W2 to dg, it is always better to select the matching (w3,ar a1), (w4, a4) frather than {WW3, a4), (Wa, J. and if wy is matched to as, then we choosing {ww3, a1), (w4, aa)} yields higher utilities than choosing {wwa, 0z), (W4, a1)}. Since all three three players have an OSS of 1/2, to maximize the OSS ratio, we need to compute a distribution D over the three matchings Ha {[w,, 01), (wg, 01), (wa, as)) ), Hb {w2,, 0z). (wy, 01), (Wa, a1)}
and μ. = {( az), (W', a1), (w4, 0g)}. such that min fuD (2)), u (W3), up (p(w))) } is maximized. Noticing that each of the three matchings yields the OSS to two players and lower utility for the third one, we can conclude that the optimal balance would be up(w)) up(w)) = up (wa)) - otherwise, could increase the OSS-ratio by moving utility from the highest rewarded player the lowest rewarded one. This condition is satisfied iff
1 T
F(Pa) = 2' P(())
F(Pe) = 4'
and the benchmark utility for any of these three players
J Discussion Regarding Stable Matching with One-sided Ties and Job Utilities
In this paper, we consider matching market where side has possibly tied cardinal preferences and the other side has strict ordinal preferences. It directly generalizes to the setting that both sides have cardinal preferences but only one side admits ties, by recovering the utility, and we can define the OSS-ratio for the jobs in a similar fashion, denoted as R&: in the following, rename the OSS-ratio for the workers as R for distinguishment. We claim that the setting with one-sided ties is not only practical in reality, but also important for our theoretical results, if we want to consider the OSS-ratio for both sides of the market.
ordinal preference list from
Stable Matching Without Ties The distributive lattice structure is striking feature for matching market without ties (36), which reveals that all workers could be optimally matched simultaneously. by simply running the deferred-ace -ccereedccceetanceee algorithm with worker proposing, denoted as pwo Conversely, job-proposing interred-acceptanee algorithm, denoted as Maa gives every job its corresponding optimal stable match. Therefore, construct the distribution D as follows:
P(D = (w) = 2' PDD = pa) (a)==)a= 1
Since phn and Paa are both stable matchings, with distribution D, we know that R S Rg S 2. and the same result holds for Ry. This implies that both R and R are ((1), and 2(1)) is a trivial lower bound for the two ratios.
Stable Matching With One-sided Ties The lattice structure is absent when ties exist in the preference profiles (5). When only one side of the market admits ties, we have proved that R% Olog N). On the other hand, for R' we have the following result.
Theorem 9. For a matching market where the workers have ties while the jobs have strict preferences, there exists an instance such that R = ((N).
Proof. Consider the following utility matrix for market with N workers and N jobs. The matrix encodes the preferences of the workers and the jobs simultancously.
1
1
E3
U=
E2
62
82
:
0
0
37

---

where > > ... > O. úi 2 ugy implies aj Rw,, ap and ui 2 ur implies Za, wy. In this example, every worker is indifferent among all the jobs, while every job has the preference profile that w1 > W2 > ................................ WN- The optimal stable share for each job is 1, and it is achieved by an appropriate tie-breaking of w1. However, in any matching, exactly one job would receive utility ('(a) of 1. When ε1, E2, approach 0, we have that maxa UD(a) 2 N, with the equality achieved when consider the distribution D that assigns probability 1/N matching Hj, where J4j refers to matching in which job a gets a utility of Therefore, lim RM = 9(N).
Stable Matching with Two-sided Ties When both sides of the market have ties, by symmetry, the OSS-ratio for the worker side and the job side would be of the same order.
Theorem 10. For a matching market where both sides admit ties, there exists an instance, such that RM RM (NV).
Proof. Consider the following N x N utility matrix which simultaneously encodes the preferences of the workers and the jobs.
1 0
1 0
1
U
0_
where the entries of this utility matrix share the same correspondence to the preference profile as those in the example in Theorem [ In this example, worker wi is indifferent among all the jobs, while all the other workers share the same preference over the jobs, that is. a1 > a2 0g The preference of jobs over workers is symmetrically derived. Every matching that involves all the workers and jobs a stable matching, which gives a utility of I to worker wh and job a1, while for the remaining workers and jobs, at most one worker and one job would receive utility of 1, and all the other workers get For every worker and every job, there exists a tie- breaking mechanism such that it gets utility of 1. Therefore, the optimal stable share is U (w) U (a) = 1 for any and a. And
aN-
any distribution D over matchings gives Up(W))
U" (we1)
Up(ar)
(a,)
max (wa,w3," wa. wNx Up(w)
(')w)
(o) N - 1, and o .x3 Up(a) 2 N - 1, with the equality achieved when we adopt the random allocation that assigns probability I/(N 1) matching μ., in which workers Wi and w., jobs aj and a receive a utility of I, while all the other workers and jobs get O.
K Discusssion Regarding Two-sided Bandit Learning in Matching Markets
In this paper, we consider bandit learning for one side of the market, where the preferences of jobs over workers are assumed to be known. A possible future direction would be to consider two-sided bandit learning for matching markets.
For a matching market without ties, a fundamental result indicates that the worker-optimal stable matching necessarily job-pessimal, and no stable matching simultaneously maximizes utility for both sides. Therefore, a reasonable benchmark would be to consider the optimal stable matching for workers and the pessimal stable matching for jobs, leading to the following regret definition:
T
Reg.(T)= = T (Ū:))
Xi(t)
Vw; E W,
1=1
T X
Reg, (T) = T U(a,) -
(()
Vay E
where (ww) represents the utility from the worker-optimal stable matching and U(a;) denotes the utility from the job-pessimal stable matching.
Previous work (60) studied regret minimization for both sides of the market in a setting without ties, adopting the regret definitions above. Zhang and Fang (60] establishes an (K log 2) regret bound for every agent, measured against their respective benchmark (worket-optimal and
38

---

bob-pessimal). Our algorithm directly generalizes to the same setting and matches the theoretical guarantees of Zhang and Fang [60] when there are ties. This is because the initial exploration phase will find the strict preference list for both sides simultaneously w.h.p. and thus, after committing, the resulting Gale-Shapley output will be the worker-optimal job-pessimal stable matching.
In contrast, introducing ties to the market significantly complicates the analysis. The set of stable matchings expands substantially, and single matching simultaneously satisfies the benchmarks defined for both sides. To extend our results to markets with ties, we propose using the Optimal Stable Share (OSS) as the benchmark for workers defined our paper. It is thus natural to introduce the equivalent Pessimal Stable Share (PSS) the minimum utility job can receive across all stable matchings. However, whether efficient algorithms can achieve sublinear regret for all agents in
markets with ties remains open and would be interesting to explore.
39


Reviews:
[{"review_id": "YiKvFcGmYf", "reviewer": "Reviewer_wBg1", "summary": "The paper studies a stable matching problem where there are ties between the preferences. In particular, there is a set of workers and a set of jobs, and both of these sets have preferences over the other set. These preferences might have ties, e.g. an agent-worker might be indifferent between 2 jobs. The goal here is to produce a matching where it is guaranteed that each participant will acquire a utility that is above a certain threshold. The authors define the optimal stable share (OSS), i.e., the  maximum utility that can be achieved at a stable matching, as this threshold, and prove the following results:\n1)\tThe authors design an algorithm that uses distributions over (possibly non-stable) matchings and show that an O(logn), where n is the number of workers, tight approximation to OSS ratio can be achieved\n2)\tThey show that this result extends even when there is (bounded) uncertainty about the utilities of the participants\n3)\tThey further extend these results to a bandit learning setting where utilities are only observed for matched pairs", "questions": "N/A", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper studies a well-motivated and interesting problem and provides a nice collection of results. From a technical point of view, the paper is non-trivial and presents results that are technically involved. As far as I checked, these results appear to be also sound and correct. There is also some conceptual contribution due to the notion of OSS that I would say that I found very interesting in general.\n\nOn the other hand, the writing is not that clear and at least for me the paper was not that easy to follow. There are some structural problems, especially in the introductory sections that I believe should be revised in a way that demonstrates better what this work studies. The same goes for the contributions section. An example is that the paper talks about distributions of matchings, but initially it was not clear for me where these distributions come from, or how they are being used. From a technical perspective, as I said, the paper is involved, but I am not so sure about what new it adds in terms of techniques.\n\nOverall, I would say that this is an interesting paper, but also one that would benefit from a revision so that the model and the overall contribution is more clear.", "was_revised": true, "final_justification": "I confirm that I have read the rebuttal and the other reviews. My opinion and score remain the same.", "rebuttal": "We thank reviewer wBg1 for the valuable comments. We provide our response point by point below.\n\n- **Distributions over Matchings**\n\nIn stable matching without ties, a worker-optimal stable matching -- one that simultaneously maximizes the utility for all workers -- always exists. However, when preferences admit ties, this strong property no longer holds, as different workers may favor different stable matchings. \nTo balance competing interests, we consider distributions over matchings.\nIn our setting, where a company allocates jobs to workers, the allocation could be done in a time-sharing scenario. For example, if workers are employed five days a week, the company could implement a rotating schedule: each day's assignment corresponds to an integral matching. This could be defined as a distribution over matchings where the support contains the daily assignments and the workers' satisfiability could be measured by the matching utility in expectation. Importantly, randomizing over matchings has been a standard approach in fair resource allocation [1-3], where previous work have shown the equivalence with fractional matchings, thanks to Birkhoff-von Neumann (BvN) theorem [4, 5].\n\nDue to space constraints, we initially deferred the above explanations to Appendix A. We thank the reviewer for their valuable feedback -- we agree that integrating this content into the main text will enhance the clarity of our conceptual contribution, and we intend to use the extra page to give more details on it.\n\n- **Techniques Involved and Developed**\n\nThe upper bound on the approximation ratio is the first key technical contribution of our paper. We establish this result via three main steps: 1) Introducing a novel component -- the duplication index -- into the algorithm design; 2) Constructing a directed forest where edges encode conflicts between workers competing for the same job copies across different matchings; 3) Leveraging the tree structure and stability constraints to derive the upper bound inductively.\n\nIn the bandit learning setting, the primary technical challenge and key contribution lie in the lower bound proof. To establish this result, we carefully construct two instances with 4 workers and 4 jobs, where the utility matrices differ in only one critical entry that determines whether meaningful ties exist. This construction reveals how ties in one worker's preferences propagate to affect other workers' regret. Furthermore, we employ an information-theoretic argument to demonstrate that the algorithm must sample this critical entry sufficiently often to avoid incurring linear regret. \nTo our knowledge, we are the first to provably show a tradeoff between standard regret and approximation regret in bandit settings.\n\nTo clarify our technical contributions, we will add a paragraph that highlights our proof sketches to the introduction in the final version.\n\n- **Improvement in the Writing**\n\nWe will incorporate the above discussions and revise the introduction section to further clarify our motivation and contributions in the final version of the paper. Additionally, we are happy to provide further clarification on any other aspects of the paper, as detailed in our response to reviewer tEhw. If there are additional clarity issues that we did not address, we would appreciate it if you could let us know so we could also incorporate these improvements into our final version.\n\n[1] Karp, Richard M., Umesh V. Vazirani, and Vijay V. Vazirani. \"An optimal algorithm for on-line bipartite matching.\" Proceedings of the twenty-second annual ACM symposium on Theory of computing. 1990.\n\n[2] Halpern, Daniel, and Nisarg Shah. \"Fair and efficient resource allocation with partial information.\" arxiv preprint arxiv:2105.10064 (2021).\n\n[3] Benade, Gerdus, et al. \"Fair and efficient online allocations.\" Operations Research 72.4 (2024): 1438-1452.\n\n[4] Birkhoff, Garrett. \"Three observations on linear algebra.\" Univ. Nac. Tacuman, Rev. Ser. A 5 (1946): 147-151.\n\n[5] Von Neumann, John. \"A CERTAIN ZERO-SUM TWO-PERSON GAME EQUIVALENT TO THE OPTIMAL ASSIGNMENT PROBLEM¹.\" Contributions to the Theory of Games 24 (1950): 5."}, {"review_id": "hAdCt0HCfg", "reviewer": "Reviewer_yExD", "summary": "The authors study the stable matching problem where one side (workers) of the market has ties in their preference lists over the other side (jobs). The workers have cardinal utilities over the jobs, and they consider the problem of optimizing for a new notion they define called the optimal stable share (OSS) ratio. This measures the ratio of the utility obtained by a worker compared to the best utility they could have obtained in a stable matching. They extend their results into two other settings, one where the OSS is defined with respect to \\epsilon-stable matchings, and an online bandit setting where the utilities of the workers are not known but learned.", "questions": "Please respond to the concerns raised in the strengths and weaknesses section.", "limitations": "yes", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Overall, they define a notion of fairness for workers and somewhat fully investigate how much this can be achieved. While this is interesting as a theoretical exercise, I have concerns about any kind of practical viability, at least for sections 3, and 4.\n\nTheorem 1 seems like a natural outcome of combining cardinal utilities with a notion more appropriate for ordinal utilities like stability. Theorem 2 and 3 are more interesting, but I think this is where my reservations with their notion of OSS lies. It seems far too restrictive, and leaving top workers unassigned with probability 1-1/log N appears to be necessary to get an optimal matching with rest to OSS. I can't think of a scenario where the jobs would prefer to do this, rather than formulate a different notion of fairness. I also don't see why it makes sense to optimize for the OSS when the ultimate distribution is over unstable matchings. Internal stability seems too weak a criteria for the output matchings.\n\nTheorems 7, 8 seem more technically interesting, although I don't have enough of a learning theory background to comment on their novelty. My concerns persist about the applicability of OSS in this setting as well. Why should this be the metric of choice here?", "was_revised": true, "final_justification": "The paper will benefit from being focused more towards the learning theory results. The offline results do not seem very interesting.", "rebuttal": "We thank reviewer yExD for the valuable comments. We provide our response point by point below.\n\n- **Leaving Top-workers Unassigned with Probability $1 - 1/\\log N$**\n\nIn the proposed algorithm, each worker is indeed assigned a job with a probability of $1 / \\log N$. This is sufficient to prove a tight upper bound in Theorem 3 which matches the lower bound derived Theorem 2. However, some matchings in the support only assign a subset of jobs. In practice, if some job $a$ is not allocated in a matching $\\tilde{\\mu}_j$, but is allocated to worker $w$ in $\\tilde{\\mu}_i$, we can give $a$ to $w$ (which are mostly top workers) in $\\tilde{\\mu}_j$ without breaking internal stability of $\\tilde{\\mu}_j$. This post-processing is a Pareto improvement of our solution, but it does not provide any improved OSS guarantee in the worst case.\n\n- **Optimize for the OSS over Internally Stable Matchings**\n\nBy interpreting the distribution over matchings as a rotating schedule, where each matching in the support represents a daily assignment, we can view the restriction to internally stable matchings as imposing constraints on this schedule. Specifically, it ensures that no worker experiences justified envy toward another worker present on the same day. Theorem 1 demonstrates that no meaningful guarantees can be established when considering justified envy of the workers who are not present, which naturally motivates us to explore the set of internally stable matching.\n\nFurther, we would like to emphasize that the distribution computed by Algorithm 1 is not only \"ex-post\" internally stable, it is also \"ex-ante\" (externally) stable, in the sense that no worker has justified envy towards any other worker's (randomized) allocation. This is related to the notion of fractional stable matching discussed in Appendix A. We will add this as a comment in the final version, but we believe that formally defining ``ex-ante'' stability would distract the reader.\n\n- **Applicability of OSS in the Bandit Learning Setting**\n\nThe bandit learning setting provides a natural and strong motivation for defining the OSS-ratio. Recent years have witnessed a surge of research on bandit learning in matching markets, where the goal is to minimize worker-optimal stable regret as defined in Eq.(3), using OSS as the benchmark. However, existing regret bounds universally scale as $1/\\Delta^2$, where $\\Delta$ represents the minimum utility preference gap across all worker-job pairs. This reveals a fundamental limitation: current methods fail completely when statistical ties exist ($\\Delta = O(1/\\sqrt{T})$).\n\nTo address this challenge, we must refine the regret definition and identify a tractable benchmark. Drawing inspiration from approximation regret in combinatorial bandits, we propose using an $\\alpha$-approximation of the OSS as our benchmark, where $\\alpha$ corresponds precisely to the reciprocal of the OSS-ratio from the offline setting. Our approach first solves the offline problem, yielding an algorithm that serves as an offline oracle for bandit learning. This innovation enables meaningful regret guarantees even with potential statistical ties. Notably, by leveraging the OSS-ratio, we establish the first problem-independent regret upper bound -- a result previously believed impossible, as demonstrated by [1].\n\n[1] Liu, Lydia T., Horia Mania, and Michael Jordan. \"Competing bandits in matching markets.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020."}, {"review_id": "EXyBeMwbct", "reviewer": "Reviewer_SsEk", "summary": "This paper studies the problem of matching workers to jobs in a market where each participant has a preference ordering over the other side. It focuses on a key question: Is it possible to approximate a stable solution in markets with tied preferences that guarantees every worker a fair, minimum level of satisfaction? To address this, the paper defines a worker’s **optimal stable share (OSS)** as the maximum utility the worker can attain across all stable matchings. It then introduces a fairness metric called the **OSS-ratio**, which measures the fraction of a worker’s OSS that is guaranteed under a minimizing distribution over a given set of matchings. The considered sets include all matchings, all stable matchings, and all internally stable matchings.\n\nThe paper first shows that when restricted to distributions over stable matchings, the OSS-ratio is lower bounded by $\\Omega(N)$, where $N$ is the number of workers. It then demonstrates that restricting to internally stable matchings yields an OSS-ratio upper bound of $\\mathcal{O}(\\log N)$, and provides an algorithm that achieves this bound while also being dominant-strategy incentive compatible. This bound is tight, as even without such restrictions, the OSS-ratio is $\\Omega(\\log N)$. Moreover, the positive results are robust to uncertainty in utilities.\n\nThe paper also explores a bandit learning framework. It introduces a key instance-dependent quantity called the **minimum preference gap** and provides a corresponding regret upper bound. Additionally, it defines a **relevant utility gap** and establishes a trade-off between regret and approximation regret.", "questions": "1. Is there a set of matchings that smoothly interpolates the OSS-ratio from $\\mathcal{O}(\\log N)$ to $\\mathcal{O}(N)$? More specifically, for any $p > 1$, can one identify a set of matchings such that the OSS-ratio is $\\Theta(N^{1/p})$?\n2. Is the upper bound in Theorem 7 tight, or is it possible to improve the dependence on $\\Delta_{\\min}$?", "limitations": "No such limitation", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The main novelty of this work lies in the introduction of the fairness metric OSS-ratio, along with the accompanying positive and negative results. This is a valuable contribution to the game theory and fairness and has the potential to open a new line of research in this space. The proposed algorithm incorporates novel components such as the duplication index, which may offer fresh insights into stable matching problems. Additionally, this work is significant for the bandit learning community, as it introduces a new and compelling problem that could inspire a new subfield within the area.", "was_revised": true, "final_justification": "The paper has novel aspects to it (see the Strengths section for more details). Moreover, the authors have responded to my questions in a satisfactory manner. Hence, I am retaining my current rating of '5: Accept'.", "rebuttal": "We thank reviewer SsEk for the valuable comments. We provide response point by point below.\n\n- **Set of Matchings that Interpolates the OSS-ratio from $O(\\log N)$ to $O(N)$**\n\nWe thank the reviewer for raising this insightful question. While this topic falls outside the scope of our current paper, we agree it represents an interesting direction for future research. Although we do not yet have a definitive answer, one promising approach would be to investigate constraints on the number of unmatched workers involved in a blocking pair: with no such workers, the OSS can scale linearly with $N$, while with $N$ potential blocking workers, we recover the $O(\\log N)$ bound.\n\n- **Tightness of the Upper Bound in Theorem 7**\n\nOur upper bound in Theorem 7 matches the lower bound established by [1] in terms of both $T$ and $\\Delta_{\\min}$ when the minimum preference gap $\\Delta_{\\min}$ is sufficiently large.\n\nFor preference profiles that may contain (statistical) ties, by setting the exploration length $T_0$ as $\\tilde{O}(T^{2/3})$, our upper bound achieves the same dependence on $T$ as the lower bound in Theorem 8, though with $\\Delta_{rel}$ replacing $\\Delta_{\\min}$. We emphasize that this represents a computational limitation rather than a fundamental statistical gap. As noted in footnote 2 in page 8, given either unlimited computational resources or an oracle capable of determining whether the uncertainty set contains a unique worker-optimal stable matching, we could close this gap and provide an upper bound that depends on $\\Delta_{rel}$ instead of$\\Delta_{\\min}$.\n\n[1] Sankararaman, Abishek, Soumya Basu, and Karthik Abinav Sankararaman. \"Dominate or delete: Decentralized competing bandits in serial dictatorship.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021."}, {"review_id": "8wEca1EHLg", "reviewer": "Reviewer_tEhw", "summary": "The paper studies the problem of stable matching in a two-sided setting where one side has ties in their cardinal utilities, while the other side has well-separated ordinal preferences. \n\nThe authors begin by analyzing the problem in the known-utilities setting. A key distinction from the classical case without ties is that there is no single matching that is globally preferred by the agents on one side. To characterize matchings in this setting, they propose the Optimal Stable Share Ratio (OSS-ratio), defined as the worst-case utility ratio achieved by any worker, with the general objective of finding a distribution over matchings that minimizes this ratio. They show that distributions over (weakly) stable matchings can result in a linear OSS-ratio in the number of agents, while restricting to internally stable matchings allows for a sublinear OSS-ratio, achievable via a proposed approximation algorithm. They further study a relaxation based on ε-stability, showing that a modified version of their algorithm guarantees expected utility within a logarithmic factor of the optimal ε-stable share.  \n\nThe authors also study the problem in an online setting, where one side of the market learns its preferences through repeated interactions and bandit feedback. They propose an algorithm that achieves optimal regret bounds when the utilities can be easily separated (i.e., large $\\Delta_{\\min}$). In the more challenging regime, where $\\Delta$ is small or zero (as in the case of ties), the algorithm bounds the regret relative to a proposed approximation oracle. Importantly, they highlight a fundamental trade-off in the achievable regret between these two regimes.", "questions": "**Q1.** Similar to Weakness point 1, I would like to ask about the analysis regarding the opposite side of the market. While it is clear that one side has known preferences, it also makes sense to consider the regret of the other side, since the initial observation of stability is an equilibrium in the market. To what extent can the regret be extended to every agent in the market? What potential future work do you foresee from this perspective?\n\nBelow, I enumerate several parts that I found somewhat confusing and believe would benefit from clarification.\n\n**Q2.** In line 330: \"... implementing an approximation oracle guarantees sublinear α-approximation regret.\" I am a bit confused by the term \"sublinear.\" Isn't the bound in equation (7) linear?\n\n**Q3.** In lines 371-372, the arguments are a bit difficult to follow. Could you please elaborate further?\n\n**Q4.** In lines 673-675, I found the arguments somewhat unclear. Could you clarify them in more detail?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "###  Strengths\n\n1. **Clarity and Accessibility**: The paper is well written and easy to follow. It provides a comprehensive overview of the literature, using concrete examples that make the content accessible even to readers unfamiliar with the topic.\n\n2. **Relevant and Practical Setting**: The focus on stable matching with ties is both theoretically interesting and practically relevant. The authors also consider the online learning setting, offering meaningful results for cases.\n\n3. **Theoretical Contributions**: The paper presents a rich set of theoretical results with proofs that are clear and easy to read. I did not identify any errors in the proofs.\n\n4. **Potential for Future Work**: The theoretical framework introduced in the paper can motivate further research, as discussed in the conclusion. Additionally, I find their approach to defining regret potentially interesting, especially in cases where a stable matching does not exist in the market.\n\n### Weaknesses\nBelow, I enumerate several minor weaknesses of the paper.\n\n1. The results of section 5.2 are focused on one side of the market (the workers). While this type of analysis is similar to prior work [39,40], I believe it would be beneficial to include an analysis of the regret on the other side of the market as well, since stability is a notion of equilibrium in the market that concerns both sides. \n\n2.  While the paper is very well written, some parts/statements are difficult to follow (see also Question Q2). These could benefit from further clarification or restructuring. \n\n3.  The paper does not include any experimental study or empirical comparison of methods. As the theoretical approach is well motivated I do not consider empirical evaluation necessary, a discussion of potential directions for future empirical work could enhance the paper and help connect the theoretical contributions to practical applications.", "was_revised": true, "final_justification": "I would like to retain my positive score and recommend accepting the paper. The setting of matching with ties is both challenging and underexplored, and this work provides novel regret formulations, algorithms, and theoretical insights. The contribution is methodologically sound, and I did not identify any significant issues in the technical content. I believe it will be a useful addition to the literature.", "rebuttal": "We thank reviewer tEhw for the valuable comments. We provide response point by point below.\n\n- **Regret Analysis regarding the Other Side of the Market**\n\nThe canonical result in two-sided matching markets without ties establishes that a worker-optimal stable matching is necessarily job-pessimal, demonstrating the fundamental impossibility of simultaneously achieving optimality for both sides of the market. Consequently, a natural approach to regret minimization in this setting involves considering both worker-optimal stable regret and job-pessimal stable regret as benchmarks. Previous work [1] has investigated this scenario, establishing an $O(K \\log T / \\Delta^2)$ regret bound relative to these respective benchmarks.\nIn terms of our algorithm, if there are no ties, i.e., there is a minimal gap on both sides, our results immediately generalize to unknown job preferences and would guarantee the pessimal regret also for jobs.\n\nThe introduction of ties significantly complicates the analysis, as the set of stable matchings expands substantially and loses the lattice structure present in settings with strict preferences. In particular, no single matching simultaneously achieves the benchmark utility for all agents in the market. One potential approach would be to define a Pessimal Stable Share (PSS) for jobs, analogous to our Optimal Stable Share (OSS) for workers, and investigate corresponding regret guarantees. While our work represents the first treatment of optimal stable regret in bandit learning for matching markets with ties, we follow prevailing research conventions by focusing primarily on the worker side. We regard the extension of our analysis to the job side as an important direction for future research. \n\n- **Clarification of the Paper**\n\nWe thank the reviewer for the careful reading and we would incoporate the following explanations in the final version of the paper.\n\n**Q2**: ``Implementing an approximation oracle guarantees sublinear $\\alpha$-approximation regret''\n\nIn our proposed ETCO algorithm, $T_0$ is a hyperparameter. By setting it to an appropriate order relative to $T$, we could achieve an $\\alpha$-approximation regret that is sublinear in $T$. In particular, we provide two choices of $T_0$ and the corresponding regret bounds in Corollary 1 and 2. \n\n**Q3**: Clarification for line 371-372: ``We would suffer linear regret for $\\Delta_{\\min} \\in [\\tilde{\\Omega}(T^{-1/2}), \\tilde{O}(T^{-1/3})]$, while keeping exploring till $\\tilde{O}(T)$ we can have sublinear regret for this range.''\n\nFrom a statistical learning perspective, when the minimum preference gap $\\Delta_{\\min}$ is known to satisfies $\\Delta_{\\min} = \\tilde{\\Omega}(T^{-1/2})$, then $\\tilde{O}(T)$ rounds of exploration suffice to reliably estimate worker preferences, and achieve sublinear regret under the definition in Eq.(3).\nHowever, in our setting where $\\Delta_{\\min}$ is unknown, the choice of exploration length $T_0$ introduces a fundamental trade-off between the two regret objectives in Eq.(3) and Eq.(4).\nBy setting $T_0 = T^{2/3}(K \\ln T)^{1/3}$, we cannot guarantee detection of instances where $\\Delta_{\\min}$ falls in the intermediate regime $[\\tilde{\\Omega}(T^{-1/2}), \\tilde{O}(T^{-1/3})]$. For these cases, we must resort to the approximation oracle during exploitation. Cruicially, since the oracle's solution differs by a constant factor from the Gale-Shapley optimal, each exploitation round incurs constant regret when measured against Eq.(3), resulting in an overall linear regret.\n\n**Q4**: Clarification for line 673-675: ``Given that $U^*(w) = 1$ for any $w$, the ratio $R_{\\mathcal{M}}$ is equal to $\\min_D \\max_w \\frac{1}{U_D(w)}$ for these instances, which is no less than the ratio between the number of left nodes and the number of connected right nodes.''\n\nBy substituting $U^*(w) = 1$ into $R_{\\mathcal{M}}$, we get $\\min_D \\max_w \\frac{1}{U_D(w)}$. Then, proving a lower bound on this quantity is equivalent to establishing an upper bound on $\\max_D \\min_w U_D(w)$. In particular, we have $\\max_D \\min_w U_D(w) \\leq \\max_D \\frac{\\sum_w U_D(w)}{N}$, where $N$ is the number of left nodes. Now notice that $\\sum_w U_D(w)$ is the expected size of the matching under distribution $D$ (since the utility is $1$ when a worker is matched and $0$ otherwise). Since there are $K$ jobs, the size of any matching is bounded by $K$, and we have $\\sum_w U_D(w) \\leq K$, which results in the claim.\n\n- **Empirical Comparison of the Methods**\n\nWhile empirical experiments are valuable, this paper focuses on introducing a novel metric and rigorously analyzing its theoretical properties in both offline and online settings. Notably, no existing algorithms provide theoretical guarantees for our proposed framework.\n\nPrior work has extensively studied bandit learning in matching markets without ties, but these methods fail entirely when ties are introduced, as established by theoretical results. In contrast, our algorithm not only addresses this gap but also naturally reduces to the SOTA method [2] in tie-free settings.\n\nThat said, we fully acknowledge the reviewer's point regarding the importance of empirical validation, given the broad potential applications of our framework. To highlight this, we will include a discussion of promising directions for future experimental research in the paper's concluding section.\n\n\n[1] Zhang, YiRui, and Zhixuan Fang. \"Decentralized two-sided bandit learning in matching market.\" The 40th Conference on Uncertainty in Artificial Intelligence. 2024.\n\n[2] Kong, Fang, and Shuai Li. \"Player-optimal stable regret for bandit learning in matching markets.\" Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023."}]

Author rebuttal:

Meta-review: The paper introduces the Optimal Stable Share (OSS)-ratio, a new fairness metric for stable matching markets with ties, and provides tight approximation and regret bounds in both offline and bandit learning settings. Reviewers agree that the work tackles an important and underexplored problem at the intersection of economics, game theory, and online learning. Key strengths include introducing the OSS metric, tight technical results for both distributions over stable matchings and bandit learning, and a comprehensive theoretical framework potentially inspiring future research. However, concerns remain about the clarity of presentation, the practical motivation for the OSS metric, and the lack of broader consideration of both sides in the market. Notably, reviewers differ on whether to emphasize the offline or online (bandit) contributions. Given the novelty and technical depth recognized by multiple reviewers, especially for the introduction of a tractable fairness metric and rigorous learning results, the paper is recommended for acceptance. The authors are strongly recommended to clarify key motivations, update structural organization as suggested, and discuss more empirical and multi-sided implications in the camera ready (as recommended by the reviewers).
Decision: Accept (poster)