Balancing Bias in Two-sided Markets for Fair Stable Matchings
Authors: Siyuan Wu
Leong Hou U
Panagiotis Karras
Venue: ICLR 2025 Poster (2025)
Keywords: stable marriage; fairness
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We propose an efficient algorithm that returns the exact optimal solution to practical Balanced Stable Marriage problem instances.

Abstract: The Balanced Stable Marriage (BSM) problem aims to find a stable matching in a two-sided market that minimizes the maximum dissatisfaction among two sides. The classical Deferred Acceptance algorithm merely produces an unfair stable marriage, providing optimal partners for one side while partially assigning pessimal partners to the other. Solving BSM is NP-hard, thwarting attempts to resolve the problem exactly. As the instance size increases in practice, recent studies have explored heuristics for finding a fair stable marriage but have not found an exact optimal solution for BSM efficiently. Nevertheless, in this paper we propose an efficient algorithm, Isorropia, that returns the exact optimal solution to practical BSM problem instances. Isorropia constructs two sets of candidate rotations from which it builds three sets of promising antichains, and performs local search on those three sets of promising antichains. Our extensive experimental study shows that Isorropia surpasses the time-efficiency of baselines that return the exact solution by up to three orders of magnitude.

Published as a conference paper at ICLR 2025
BALANCING BIAS IN TWO-SIDED MARKETS FOR FAIR STABLE MATCHINGS
Siyuan Wu" University of Macau asuka wwy.connect....... umac. mo
Leong Hou U University of Macau ryan hyanthu@um.comm Soummeduu edu mo
Panagiotis Karras
U. of Copenhagen & Aarhus U.
p piakarras@gmai 1 cco
ABSTRACT
The Balanced Stable Marriage (BSM) problem aims to find a stable matching in a two-sided market that minimizes the maximum dissatisfaction among two sides. The classical Deferred Acceptance algorithm merely produces an unfair stable marriage, providing optimal partners for one side while partially assigning pessimal partners to the other. Solving BSM is NP-hard, thwarting attempts to resolve the problem exactly. As the instance size increases in practice, recent studies have explored heuristics for finding a fair stable marriage but have not found an exact optimal solution for BSM efficiently. Nevertheless, in this paper we propose an efficient algorithm, ISORROPIA, that returns the exact optimal solution to practical BSM problem instances. ISORROPIA constructs two sets of candidate rotations from which it builds three sets of promising antichains, and performs local search on those three sets of promising antichains. Our extensive experimental study shows that ISORROPIA surpasses the time-efficiency of baselines that return the exact solution by up to three orders of magnitude.
INTRODUCTION
Given a two-sided market, where each agent (conventionally, man woman) ranks those on the
other side by a strict order (Roth 1984), the stable marriage problem (SMP) (Gale & Shapley 1962) seeks stable matching between the two sides, such that no pair of agents in separate matchings would both rather be matched with each other than with their assigned matches. SMP widely finds
real applications involving two-sided markets, such assigning residents to hospitals (Gusfield &
Irving 1989 Askalidis et al. 2013), students to universities (Gale & Shapley 1962 Teo et al. 2001
Bañou & Balinski 2004 Saif et al. 2020), reviewers papers (Long al. 2013 Kou al. 2015).
and jobseekers to jobs (Roth] 1984 Liebowitz. & Simien 2005).
Considering fairness in stable marriage problems, the celebrated Deferred Acceptance (DA) algo-
rithm (Gale & Shapley 1962), offered an allocation optimal for each agent on the one side and pessimal for each one on the other in ((2²) time (McVitie & Wilson 1971 Irving & Leather
1986) Since then, several stable marriage fairness objectives have been suggested (Gusfield & Irving
1989 Iwama Miyazaki (008). The regret cost objective (Gustield 1987) calls to minimize the
dissatisfaction of the worst-off individual among all agents, while it only caters for faimess among individual agents, but not among sides. The egalitarian cost aims to minimize the sum of all agents' dissatisfaction, but not the gap between two sides, which overly gratifies the preferences of one side. The sex-equality cost (Kato) 1993) measures the gap among the two sides' collective dissatisfaction, yet therefore penalizes solutions in which both sides would be better off though the difference among them would be higher. Most consequentially, the balance cost (Feder) 1992 Gupta et al., 2021) aims to minimize the highest collective dissatisfaction among the two sides, raising the Balanced Stable Marriage problem (BSM). Contrariwise, the BSM objective considers the incentives of both sides in balanced manner, endorsing decrease in collective dissatisfaction, which renders both sides better off even at the expense of fairness among the two.
Unfortunately, BSM is hard and calls for algorithms that efficiently explore the solution space (Irving] 2016 Roth 2018 Dworczak| 2021). Technically, the minimization of the balance cost objective is
"The work was done partially while visiting Aarhus University.

---

Published as a conference paper at ICLR 2025
an NP-hard problem (Kato] 1993: Feder 1995 Gupta et al. 2021 Pragmatically, the set of possible
stable matchings can grow large in practice (Hassidim et al., 2017). while the problem instance size is also usually large. In China, over 10 million students apply for admission to higher education
annually via a centralized process (Manlove 2013). Similar schemes, in which students are ranked
by some score (Biró& & Kiselgof 2015), are used in several national schemes (Braun et al., 2010
Biró, 2008 Chomero-Meding 1998 Balinski & Sönmez 1999; Biró & Kiselgof 2015 Agoston et al. 2016) and US school districts (Abdulkdirogllu & Sönmez,
Abdulkadddi et al. 2005b a).
Even when the problem instance size is small, the number of all stable matchings grows exponentially in the worst case (Knuth, 1976, 1997). For some hard instances, the exact maximum number of stable matchings an instance can have is known be at least 2.28" and most c for some universal constant c (Karlin et al.) 2018). Mostly heuristic methods try to find a 'fair' stable marriage without seeking a specific objective score but using unbiased proposal and acceptance strategies to search the solution space (Viet et al. 2016b Dworczak] 2016 2021 Tziavelis et al., 2019). Tziavelis et al. (2019) propose a local-search heuristic,
(HMS), that finds a stable marriage with high equity in quadratic time, yet provide no guarantees with respect to any objective. As detailed in Section 2 no previous study finds the exact solution to BSM in practice, while existing heuristics focus on devising proposal aacoosalland-ccee accepptce strategies.
SybridMulliSSaant
In this paper, we propose ISORROPIA an algorithm that effectively finds exact balanced stable marriages in practical problem instances, via efficient local search and intensive pruning of the solution space. The structure of all feasible stable marriages in a problem instance can be compactly represented by a partially ordered set of rotation structures (Gusfield & Irving 1989 Irving & Leather| 1986), viewed as a directed acyclic graph (DAG), the rotation graph. Each stable marriage corresponds to set of rotations known as antichain. Contrariwise to previous heuristies, our solution performs local search in subset of promising antichains in the rotation graph. To facilitate this search, we delimit and search three sets of promising antichains, built from two sets of candidate rotations, by exploiting locally optimal constructs of the dissatisfaction function under a domination relationship among stable marriages. Notably, ISORROPIA finds the exact solution, despite using local search. We extend ISORROPIA to find the exact sex-equal stable marriage and show that it surpasses the time-efficiency of baselines that return the exact solution by up to three orders of magnitude.
RELATED WORK
Fairness objectives and tractability. The Gale-Shapley algorithm (1962) finds a one-side optimal stable marriage in O(n²) time, trading the satisfaction of one side in favor of the other. Several prob- lem variants define different objectives, such as regret cost (Gusfield 1987). egalitarian cost (Irving al. 1987), and sex-equality cost (Kato 1993). Feder (1995) proves that BSM is NP-complete and Gupta et al. (2021) give a parameterized complexity analysis. Let Pm. (P..) denote the indi- vidual dissatisfaction of a man m (woman w) and Cm (or Cw) the accumulated dissatisfaction of men (women). Pa represents the individual dissatisfaction of an agent (i.e, man or woman) and Ui {21. the space of all stable marriages. Table I |summarizes the fairness objectives.
BSM is approximable within a factor of 2 in O(v log(w²/u / + 2)) time (Feder 1995). where v is the number of clauses and w is the explicit width in the related balanced 28 problem. From the view- point of parameterized complexity, a prior work (Gupta et al. (021)) gives two parameterizations of BSM by two versions of the parameter L, i.e., I = k min [CM, Cw) and / = k max {CM, Cw }} such that the balance cost is not larger than k; where the first one has an FPT algorithm and another one is W[1]-hard. Contrariwise, we find the exact solution to BSM in a manner that performs efficiently in practical problem instances.
Existing methods that find a fair stable marriages (Table I follow one of these orientations:
Proposal algorithms. These algorithms adopt a procedure similar to the Gale-Shapley algo- rithm (1962). letting agents reach stable matching by exchanging, accepting, and rejecting proposals across the two sides. The randomized order mechanism (ROM) generates a finite chain of matchings that terminates a stable matching. In each iteration, it randomly introduces indi- vidual (Ma 1996) or a pair (Roth & Sotomayor 1990) into the proposal procedure. However, ROM cannot enumerate all stable marriages and is inherently biased in favor of each randomly selected
From Greek iropporío, balance, equipoise'.
2

---

Published as a conference paper at ICLR 2025
Table I: Fairness objectives in the Stable Marriage (SM) Problem
Problem
Objective
Tractability
Minimum Regret SM (Gusfield
1987
min max max (Pmm Pa(m))
O(r²)
peM (m.w))
Egalitarian SM
(Irving al.
1987
min Car (n) Cw (p)
O(x")
yeu
Sex-equal SM
Kato
1993
Iaama et al. 2010
C Cw (w))
NP-hard
Balanced SM Foder 1992
Gupta al. 2021
min max (Cxr())(((C))Coe HEN
NP-hard
individual (Tziavelis et al. 2020). Other works have proposed alternative orders of proposals to
enhance fairness via an unbiased treatment of the two sides. EROM (Romero-Medinal 2005) lets
agents propose to each other with progressive receptiveness. SWING (Everaere al. 2013 and
ESMA (Giannakopoulos et al. 2015) let all individuals re- propose to others in iterations. Deferred
Acceptance with Compensation Chains (DACC) (Dworczak 2016 2021 reaches practically fair stable matching by compensating abandoned agents in O(n") time, while PowerBalance (Tziavelis) ct al. 2019) finds a fair stable matching (n²) by using stricter proposal acceptance criterion.
Linear programming and satisfiability. The matching problem with stability constraints can be formulated as a linear programming problem under set of linear inequality constraints (Rothblum) 1992) and by a SAT formula (Siala & O'Sullivan! (017). LOTTO (Aldershof et al. 1999) follows a similar formulation, eliminating redundant constraints in each iteration and assigning a random agent to its best available preference, hence also exhibits bias (Tziavelis et al. 2019).
Local search on the stable marriage lattice. In any SMP instance, the set of all possible stable marriages forms a distributive lattice (Irving& & Leather 1986). SML.2 (Gelain et al. 2013) starts from random matching and iteratively eliminates selected blocking pairs (i.e., pairs of agents who would rather be matched with each other than with their assigned matches) to transform it stable one by local search on the lattice. BiLS (Viet al., 201 a) performs local search on the lattice with a greedy strategy and probability for random movement. Nevertheless, these empirical methods are constrained by the size of stable matching lattice, which can grow up to exponential size in n (Irving & Leather 1986). while local search may get stuck in local optima.
Rotation-based model. While computing and storing the distributive lattice structure may be unattainable, a more compact structure, the rotations poset, i.e., a directed acyclic graph organizing rotations (i.e., sub-matchings) (Irving & Leather 1986; Gusfield & Irving 1989) also represents all stable solutions. To minimize egalitarian cost, it suffices to find a minimum cut on this graph in O(n²) time (Gusfield & Irving 1989). A recent work BBozec-Chiffoleat et al. 2024) solves the robust stable marriage problem via rotation- based model, which reduces the search space and speed up the exploration on rotation graph. Nevertheless, some algorithms based on the rotation graph are unclear. For example, an algorithm for sex-equal stable marriages by Romero-Meding (2001) requires finding rotations that change signs, without suggesting an implementation.
Further, some hybrid methods embody more than one of these orientations. Deferred Local Search (DLS) and HybridMulttSearce (HMS) generate additional fair stable marriages by pursuing local search strategies starting from the output of PowerBalance (Tziavelis al.) 2019). However, these algorithms are mostly heuristics, aiming for procedural fairness without targeting a specific equity cost measure (e.g., sex-equality cost or balance cost). Contrariwise, our algorithm efficiently finds the exact balanced stable marriage via local search on rotation graph.
PROBLEM STATEMENT AND PRELIMINARIES
A stable marriage instance is defined as I = (M, W, P). where M and W are the two sets of agents (conventionally exemplified as men and women) of the same size n, and P is a set of 2n preference lists, list P. for agent i, which rank in descending order those on the other side. An example instance is provided in Appendix A. Pn, (w) denotes the position of w in Pm and P.. (m) that of m in P... In effect, P,()) also expresses the extent of i's dissatisfaction with j. A matching has disjoint (m, w) pairs. We use μ(m) w and j(w)) m denote that (m, w/ is a pair in
3

---

Published as a conference paper at ICLR 2025
matching μ. If prefers to pl() and prefers m to p(ww), then (w, m) is blocking pair in pa. A stable marriage is a matching without blocking pairs.
Balanced Fairness. Given stable matching μ. let (p)(H) and Cw (p) represent the sum of preferences for the assigned matches on the two sides:
Cas(u)=
Σ (m(()) (m0,0)E
Cw(u)= =
E Pu(m) (m,,))ER
(1)
(N)( and (w()) reflect the cumulative dissatisfaction of all agents the M-side and W-side, respectively. The balanced stable marriage problem (Gupta et al.] (022)) aims to find a stable
marriage f² that minimizes the worst dissatisfaction of the disadvantage side:
C(p") ) = min max (Car()),
(2)
well
where 4 = (1),, (22, ..... (.N) is the set of all stable marriages, whose size N is exponential in the worst case (Irving & Leather 1986).
To facilitate the discussion, we introduce the function Worse(p), which determines the disadvantager side stable marriage y and hence yields the balance cost:
(orse( Widiee
Csr S (w) if if Cw(p)
(3)
M-side
The Structure of All Stable Marriages. Given stable marriage instance I, all stable marriages U are composed of (1) two side-pessimal stable marriages (uw and μ.M and (2) other stable marriages. First, two side-pessimal stable marriages can be generated by Deferred Acceptance (DA) algorithm upon its first termination. Then, other stable marriages can be generated by re-assigning some pairs from jww and finally it can reach at μMM- The re-assignment follows a set of DA procedures (i.e., break stable marriages and apply DA algorithm for multiple times), which can be compactly represented by set of rotation nodes
The Deferred Acceptunce (DA) algorithm (Gale & Shapley 1962) lets each man m start from the first preference and sequentially propose to the next most preferable woman in the order of P... as long as the man finds itself being single. Each woman w accepts a (m, w) proposal if the woman is single or prefers m to the current partner (w). The DA algorithm (Gale & Shapley 1962) outputs stable marriage optimal for each agent on one side and pessimal for each agent on the other side (Miie & Wilson 1971 Irving & Leather 1986), i.e., get μg if men propose women and get fo4 if women propose to men. As shown in Table we denote these two outputs as μa and μM, where the subscript denotes the side that gets pessimal outcome.
A stable marriage μu dominates another μ², or < nl, if each agent on the M-side gets a no less preferable partner in μ than μ², and, as stability implies, each agent on the W-side gets no more preferable partner in μ than in μ². The set of all stable marriages forms distributive lattice (Gusfield Irving 1989,, where Pw dominates, and Pas dominated by, any other stable marriage.
To compactly represent the breakable pairs and the corresponding re-assigned pairs for each DA process, we use the construct of rotation (Irving) 1985 Irving Leather 1986). A rotation belonging to (or exposed in) μ is an ordered sub-list of matched pairs r ((r))) (M++1 ( ...:: (me+d, {) Given a μ that exposes a rotation r, we can break the marriage of in rotation and apply the DA algorithm to let m; pro- pose to the next most preferable woman, eventually being assigned with woman μ(m(+11 who abandons man m4+1; likewise, m4+1 will then be matched with u(m++2), and on until we reach ((m;) in full cycle. Intuitively, each of the men m,, m,+1..... Mi+d is matched to woman less preferable to him, p(m;41) 1), p(m442) (((,,) respectively, while each of the woman μ(m;), p(m;+1); p(m;+a) is matched to a man more preferable to the woman, mi+d; M.,..., Mi4d-1 respectively. Thus, the ensuing matching μí is still stable. We call this re-coupling rotation elimination, denoted as ju/r μ². By eliminating the rotation r, we can obtain a new stable marriage p'. Certainly, a dominates p'.
Mi+d
For more details, readers can refer Gusfield & Irving 1989 Irving & Leather 1986) and Appendix A.1
4

---

Published as a conference paper at ICLR 2025
Table 2: Rotation elimination and balance costs for all stable marriages
T1
f3
Matches
Car(p)
Cw (pt)
Worse(xs)
Balance Cost
polow)
[awyy Mr
Jowo, Miy] (reay Mia) (rit,, Mt (19g, us?
8
9
W-ssde
18
r2
[mg
(mng Srggy Myg (mn stg
1mg
fr.)
11
16
W-sdde
16
[ms,
May M04) sta
Ems.
12
M-sdde
12
(194.09)
(ong. Mongy No
saa
M-sdd
14
Figure 1: Rotation
(mg [al(tar)
(mgg Mraay Maa)
(mm, (mn.. mgg
[ca)
Graph
The set all rotations Rt forms a partially ordered set (poset) (R, (R) [rving & Leather 1986).
A partial order - r' indicates that r' is only exposed after eliminating r. The poset (R. +)
denoted by a directed acyclic graph G = E), where nodes stand for rotations and an edge (r; for direct partial order - r', i.e., fr.|r + r. r', guaranteeing connectivity. Figure shows an example of a rotation graph G. We denote the predecessors of as Pred(r), i.e., for each r' Pred(r). reachable from r'. Finding all rotations and edges in G costs (n²)) time (Irving ct al. 1987 Gusfield 1987); this construction is preprocessing step beneath the core of our problem.
An antichain antichain we can construct unique closed subset = Unce [r] U Pred(r), which contains all rotations in a and their predecessors. For a = {rr} in Figure we should eliminate rotations in its (r, according partial order relationship starting from jww, that each rotation is exposed in the elimination process.
subset of such that no rotation in
predecessor of another. Given an
closed subset,
Let A be the set of antichains and S the of closed subsets in G. Theorem 1986) provides a foundational fact on the structure of all stable marriages.
I Irving & Leather
Theorem 1 (Relationship between antichains, closed subsets, and stable marriages). (Irving & Leather 1986 In any stable marriage instance there is one-to-one relationship among antichains A. closed subsets S and stable marriages U. Enumerating all stable marriages is #P-complete.
In other words, for any antichain a, we can find corresponding closed subset and stable marriage j via rotation elimination Ww /ss + Ha. We refer to these concepts (i.e., (4, and s) interchangeably without loss of clarity. As all stable marriages listed Table 2 the balanced stable marriage is j12-
LOCAL SEARCH ALGORITHM
In this section, we introduce our algorithm, ISORROPIA, which efficiently returns the exact solution to the BSM problem by locally searching three sets of promising antichains, Ar, Au. Am build from two sets of candidate rotations, Rig, Rp.
4.1 LOCAL OPTIMALITY
To find the balanced stable marriage '² (cf. Equation 2}. exploit four properties of the variation of Cm and Cw along the rotation elimination process from the extreme jww to μMM- As rotation elimination degrades the matches of the M-side and upgrades the matches on the W-side (Irving & Leather 1986; Gusfield 1987). the following monotonicity property follows.
Property 1. Starting from pw, a rotation elimination p/r > μl, increases Cas and decreases Cw. ie., (p) < CM (n²) and Cw (μ) Cw (w'))..
Remark. Given a rotation the rotation elimination results in that each agent m in gets a less preferable partner and each agent w r gets more preferable partner (see Section 3) bringing to the strict increase of OM and the strict decrease of Cw respectively by Equation] 7
When eliminating a set of rotations, n/R,, + p for each man y E and E R., ((m) is better partner than p'(m) the agent m. while other agents in M follow that / (m) ((m). In effect, the resulting matching j is dominated by (i.e., l - n²). From Property [ we derive Property 2 which determines the worse-off side of one stable marriage from the worse-off side of another stable marriage via the domination relationship.
Property For < μl, Worse(p) = M-side = Worse(p') = M-side and Worse(y') = Wiside Worse(n) = Widide
5

---

Published as a conference paper at ICLR 2025
Remark. The property holds because μ < pl implies that Cw(pe) < Cw( and Car(p) (p') while Worse( = M-side implies that Cw (4) < Cas(p), hence Cw((y') < Cw (w()) < CC (u) < Cas (μ²), therefore Worse(p') side. The implication from Worse((") W- follows by analogous reasoning.
The local optimality properties follow from Property 2
Property 3.1. If f < pL, Worse((') W side Cw(wc) < (w()) (f.e., p is better).
Property 3.2. If Je - p², Worse(p) = M-side = Cm(u) < Car(u') (i.e., P is better).
Remark. 1f < pl, it follows that both μs and yL have W Widide as the disadvantaged side (Property 2) and Cw()') < (w(u) (Property 7. where p' has better balance cost as Property 3.1 The
implication from Property follows by analogous reasoning.
4.2
MAIN IDEA
Given a rotation r, the r-related antichain contains only r, ar = {r}, while the r-related closed subset is 8, = {r} U Pred(r). We derive the r-related stable marriage by rotation elimination as pww /w/ss. + μ,,. We divide all rotations in two subsets based on the side of the market on which their r-related stable marriages are disadvantaged, i.e., the value of Worse((,,) by Equation 3
Definition 1 (Side-Diee Disadvantaged rotations, RM and Rw). The set of rotations disadvantaged on the side is the set Ry = [r|Worse(1u, (4r) M-side) and the set of rotations disadvantaged on the W-side is the sel Rw = (r/Worse((r,) = W-side).
Clearly, it is RM U Rw R and Ry Rw 0. Since an antichain is a set of rotations, we distinguish three disjoint sets of antichains: (i) Antichains E AM that a only contains rotation(s) in RM: (ii) Antichains E Aw that a only contains rotation(s) in Rw: (iii) Antichains E AMw that a contains rotations in both RM and Rw.
Figure deppics the disjoint sets of the three types of antichains, where Aas U Aw U
Since each stable marriage can be generated by its corresponding antichain (Theorem I the matching problem is transformed into graph searching problem that finds a set of rotations. Our algorithm, ISORROPIA, reduces the search space by extracting and locally searching three sets of promising antichains, namely A C Aw, An C. Aw and All C AM, while discarding AMw.
4.3 MIN-MAX OPTIMIZATION
The BSM problems calls for min-max optimization where the max operator in Equation leads to non-convex objective function. To render the objective more manageable, we drop the max operator in Equation 2 splitting it in two cases as follows:
(w)
if Worse(u) = W-side
14" arg min
(4)
PEll
Car(u)
if Worse( M-side
Thereby, we aim to find the minimum Cw (1) when Car(u) < Cw(n) and the minimum Cm (1) when CM (p) > Cw (p), and return the stable marriage having the least score among these two. Building upon it, We search the rotation graph G while minimizing the two possible manifestations of the balance cost, that is, Cas (4) for Worse(μ) = side and Cw (1) for Worse(μu = widie. Unfortunately, G is not neatly divided in subgraphs such that Worse(μu) and (jrse( = Wiside in the other. As each stable matching corresponds to a closed subset (i.e., combination) of rotations, a rotation r exposed in one stable matching a with Worse(p) Widi may also be exposed in another stable marriage jí' with Worse(p") = M-side. For example in Table 5 both ars and ay have rs while their worse-off sides are different. We achieve the above purpose by exploring three sets of promising antichains, AI, and Al articulated in Table 4 Ai and Aur. First, we consider antichains a E Aw, which only contain rotations in Rw (pink area in (). We partition antichains in Aw in two blocks depending on the disadvantaged side in their corresponding stable marriages Na:
M-side in one
It should be Au U Aw U AAw U (0) = A. In ISORROPIA, we have to check two extreme cases of JAM and jaw, corresoonding ( and R, hence can ignore these corresponding antichains in A.

---

Published as a conference paper at ICLR 2025
Table 3: The exact solution can be found in the local search space by Theorem 2 For each theorem, an antichain in unpromis- ing antichains cannot yield better result in terms of balance cost than the optimal result found in promising antichains.
Aw
AM
3 4
Jand
A
An
Am
Local Search
P9
P10
Amw
Has perent in Rac
Promising
Unpromising
Figure 2:
We first divide the scarch
Theorem
Antichains
Antichains
Adr
(mbrs.no)
space into Ass (blue arca), Aw
Theorem Theorem
A J.An An Ani
Aw (A, U U.A U (ar 1)
N rr E Rey
0 c RM
(pink area) and Aus (gray area). Theorem
Au Amn
Anow
Ore R.,
R2
ISORROPIA only locally searches AI, An and Au (dotted box).
Figure 3: Rs and RS
Table 4: Three sets of promising antichains
Table 5: Examples of stable marriages.
Promising Antichains
Contained
(aose(Hta)
Car(u)
(w(R))
Worse(w)
Balance Cost
Rotations
Pr.
(14)
19
W-side
A
(rlty Rw Br Re)
W-side
(rs
fra (a.
25
31
W-side
31
Am
Au
Fre E Ro J. [o]
We Rw A 3r Ro)
M-side
sidi
Ps
Pr.
(rr)
(rs)
28
26
33
30
24
M-side
M-side
W-side
E Aw (orse((a) = W-side); Some antichains in Aw derives W W-disadvantaged stable mar-
riages. For example, in Figure 3 and Table both r3 and ra are W-disadvantaged rotations. Mr, is disadvantaged on W-side, and fa,. corresponding to antichain {r3, r4 also derives W W-disadvantaged stable marriage.
{a Au (Wors((ua) = M-side]:: Some antichains in Aw derives M wantsaed stable mar- riages For example, both and ra are in Rw. frr, and pr, are both disadvantaged on W-side, but My corresponds to antichain {ra. deriving a M -disadvanttaged stable marriage.
follows that, for the former antichains, our objective is particularized as minimizing Cw, while for the latter antichains, it turns to minimize CM. Next, we characterize the rotations contained in these antichains to delimit the search space i.e., we prune the pink hatched area in Figure 2 and extract Ai and AuI, Table 4
Definition 2 (Layer rotations, R(E). Let the layer of denoted as L(r). be the length of longest path
from fa to rotation r on G. The set of layer-l rotations is R[C] = {rl [(r) f}.
In particular, we can find the largest layer ww arg max
a= {}), such that the antichain
Worse(u..)= sidd side
formed with layer-lw rotations derives stable marriage disadvantaged on Widdee
Nonetheless, is not neatly divided in two subgraphs by Worse(μ)) (Equation 3.. We exploit A and Au with candidate rotations by lw-
Definition 3 (Candidate rotations, Ra))- We define that antichain as atw = R[ew] and the set of candidate rotations after layer ww that still in Rw as Rg = [rr[[(r) lw A Ar E Rw).
For example, in Figure 3 and Table Worse(pa)= W -side with a= (r1, F2, [2) and Worse(Hu) M-side with a = (ra. Ts, r=). As a result, Ew = 1 and a&w = (21, r3). Mra Hrg and pra all have Worse()ı,) = sidee. By Definition 3
we have R = {ra, rs. rs).
We delimit the antichain sets Ai and An to antichains a that contain least one rotation r Ra. By the following theorem, it suffices to search in Ar U An U (asw) J. hence we can eschew searching in the rest of Aw, i.e., Aw \ (Ar U An U (asw)) }) (i.e., the pink hatched area in Figure 2.
Theorem 2 (Sufficiency of Ar U An U (aew }). An antichain in Aw \ (Ar U An U Kaew }) cannot yield a better result in terms of balance cost than the optimal result found in Ai U Au U U }.
Proof. By definition, any antichain a' E Aw \ (Ai U Au U (or, 1) avoids rotations in layer Lw and beyond, hence Hla < Parw By the definition of Ew and R4, Worse(Haryy = Wiside. By Property 3.1 it is Cw Cw (Mazy) ) Cw (Paa)) hence Poey has better balance cost than Paa-
Li
'These antichains correspond to stable marriages resulting from rotation elimination Rr/R.. + pa.
where r E Rw and R. C. Rw; by Property [] starting with Cxr(s)) <, Cw((t)), eliminating the rotations in R. increases Cs (F+) Cas (Pa) and decreases Cw (147) to Ow (Jaa), where it may be Cae (Ha) > Cw (pa).
7

---

Published as a conference paper at ICLR 2025
By Theorem 2 it suffices to search in Ar and Au to generate any stable marriage better than Harw"
Aur Next, we consider antichains that only contain rotations in RM, a E AM in Figure (blue area). Given such an antichain a, its corresponding stable marriage Pea is either identical to, or may be derived from, an prr with
RM by rotation elimination, ur/R, - Pa. By Property 2 since Worse(u,, = M-side and < Paa it follows that (orse(pa) M-side. Thus, we need only find the minimum Cλr in Aas. We also delimit the rotations contained in these antichains to delimit Aun. i.e., prune the blue hatched area in Figure and extract ALII as Table
Definition 4 (Candidate rotations Rz)) We define the set of candidate rotations in RM with all parents in Rw Rs {rlr RM A Parents(r) S Rw}.
For example, in Figure we first focus on rotations in RM and then extract R = (17, R does not contain ry and 710. since both have parent in RM.
We delimit the antichain set Am to antichains a that contain only a single rotation, which is in Rp. i.e. (rlr Rz}, |a| 1.
The following Theorem shows that it suffices to search in Am as defined.
Theorem 3 (Sufficiency of Amu). An antichain in AM \ AAu cannot yield a better result in terms of balance cost than the optimal result found in AlII-
Proof. Any antichain a E AM \ Am contains rotation with a parent in Ry or more than one rotation in RM. Thus, we can generate pa by pr/ R, + -aa with E Rg. Since (orse(pr) = M-side and Hr, x Ma, Property 3.2 implies that Car (J+) < CM (Ma). Thus, we can derive more stable marriage from antichains in Anl-
Other antichains. The remaining antichains, Aww, contain rotations in both Ras and Rw, i.e., the gray area in Figure By virtue of Theorem we ignore A&w in the search process.
Theorem 4 (Am dominates AMw). The antichain set Aww cannot yield a stable marriage of better balance cost than the best stable marriage derived from Am-
Proof. Any stable marriage μ corresponding to an antichain E A.w derives pr/RR, -> Pa with rE Rp. By Property 3.2 Cas ((a)) CM (J+), while Worse((4r) M-side and Worse( = M-side. Thus, antichain Am yields stable marriage more balanced than μ.
In effect, AI, Au and An suffice to find the exact solution to BSM, summarized in Table
4.4 LOCAL SEARCH ALGORITHM
Naïve approach (ENUM). A naïve way to find the balanced stable marriage jı" is to enumerate all stable marriages and apply Equation 2 An efficient algorithm for enumerating stable marriages, ENUM (Gusfield & Irving 1989), expands closed subset with rotation in each step; its time complexity is O(n" + n.V The pseudocode is detailed in Appendix A.2 As N can be extremely
large in some instances (Irving & Leather 1986), design efficient and practical algorithm that
reduces the search space.
Algorithm 1 ISORROPIA
Input: Rotation Graph G
Output: Balanced Stable Marriago s²
1: it ('x((pw) 2 Cw (pw) then return
# check pw
2: it Cw (Mas) ) >> Cza (192) then return
% check pa
3: for do Caculate Cm (f.)) and (w())))
4: Collect candidate rotation subscts Ray Rs
* Definitions 3 Band
5: Pi LOCAL SEARCH IN Rg-
% find the minimum Cal in Am
6: p² LoLoaa SEARCH IN R.g
* find the minimun Cw in At and the minimum C's in An
7: return n +- n4, or Pi. by Equation
ISORROPIA gathers two sets of candi- date rotations Rg and Rp and searches three sets of promising antichains (Table corresponding
Our algorithm (ISORROPIA). By the analysis in Section 4
Note that R. C Ra is not necessary, since r' aa) (r) may have predecessors in Ry that are needed in R..
8

---

Published as a conference paper at ICLR 2025
to subset of all stable marriages to find the exact solution μ=" Algorithm T shows the pseudocode of ISORROPIA. First, Lines| 2 check μM and paw for extreme cases. If Ca (pw) 2 Ow (pw). we directly return fa as the optimal cost μt, since, by Property 2 Ca (x((w)) < Csr(p) for any other stable matching (i.e., jAw is pessimal for W-side and optimal for M-side). Symmetrically if (w(Ju)) > Cas ((ar)) we return JAM- Otherwise, in the general case, we calculate Cau (pr) and (w+) for all rotations, and collect the subsets R4 and Rs (Lines 3 and find the locally optimal stable marriages 2² in Am and St in A U Arr U (ae via local search on Rs and R4. The pseudocode of local search can be found in Appendix A.3
Overall, the time complexity is O ((R) + (w) nn² n.Na), where Na is the number of stable marriages enumerated in local search. While potentially exponential, as the problem is NP-hard ISORROPIA reduces the search space N to Na + R + lw. The details of time cost can be found in Appendix A.3
We extend ISORROPIA to find the exact sex-equal stable marriage, which calls minimize the difference of satisfaction among two sides, detailed in Appendix A.4
5 EXPERIMENTS
We compare the runtime and balance cost of ISORROPIA to those of baselines: (1) ENUM our revised version of ENUM (Gusfilld & Irving 1989) (Section and and Appendix A.2), an enumeration algorithm the rotation graph that returns the exact solution: (2) BILS (Viet et al., 2016b a). greedy local search method on the stable marriage lattice; we set the probability of random movement to p 0.05; (3) DACC (Dworczak 2016 2021), Deferred Acceptance with Compensation Chains, a heuristic that finds a fair stable marriage by allowing proposals from both sides and ensuring the compensation of abandoned partners: (o) BALANCE (Tziavelis al. [201)), a heuristic that goes through a series of proposal iterations from both sides by strongly deferred acceptance, whereby unmatched agents only accept proposals more preferable than their own target, with the maximum
number of proposal rounds fixed / n log2 n/ /10]: (5) HMS (Tziavelis al. 2019), heuristic that improves upon the results of POWERBALANCE by an m-step local search over k rounds, with complexity Otn + kmm²).. We emphasize that ENUM and ISORROPIA (our algorithms) find the exact solution to BSM, while BILS, DACC, POWER BALANCE and HMS are only heuristics.
We use synthetic and real datasets in our assessment, as follows: (i) Following prior work (Tziavelis) iet al. 2020), we construct a dataset, Uniform, with preference lists drawn from the uniform distribu- tion. (ii) We use the settings in (Siala & O' O'Sullivan 2017) to generate Hard instances by the method outlined in (Irving & Leather 1986), which yields teasible stable marriages growing exponentially with n, hence instances of this family become unnaturally hard as n grows; to ameliorate this hardness, we randomly pick 10% of individuals in each preference list and reshuffle their positions. (iii) Taxi reflects the two-sided market of taxis and users, drawn from the NYC Taxi datase we define preferences for the sides using distances and amounts. (iv) Adm captures a two-sided market of university admissions; we employ university rankings and GRE and TOFEL scores to define R preferences two sides. Table 6 presents the parameters and statistics of these datasets.
Table 6: Data sets: size n, rotations |R] and edges E in the rotation graph.
Uniform
Hard
Taxi
Adm
[/]]
[
n
[7]]
[F]
n
[R]]
[
T
[/]]
|||
2.5k
1k
5k
103
256
1,597
3k
4.354
1.5k
168
1,296
7.5k
673
60.235
512
229
4,780
4k
452
9.945
2%
279
2,444
10k
820
92,236
1024
362
13,834
5k
579
15,761
2.5k
318
4,806
We ran experiments
Intel i5-13500H machine @2.60 GHz with 32G memory running Windows.
All methods were implemented in C++; the code is available our Github repository P
Figure 4 presents our results on runtime and balance cost. As the brute-force method, ENUM
cnumerates all feasible stable matchings N, to ensure termination we let it enumerate at most 10?

---

Published as a conference paper at ICLR 2025
stable marriages per instance. All methods are terminated after time limit of 600 seconds. As POWERBALANCE and HMS perform very similarly in both balance cost and time, we report results for POWERBALANCE only for the sake of readability.
ENUM
PowerBalance
ISORROPIA
PowerBsiance
SORROPIA
0.0
5.0-
121
6.0-
137
6.0
2.0
Tsctezee Ston
Instance Sov,
Taathncs 500
(a) Time(s). Uniform
(b) Balance Cost, Uniform
(c) Time(s), Hard
(d) Balance Cost, Hard
10-
104
2.0
101
165
10"
1.0
12a
0.-
Incracee
5.1k
Tastunes 6
(e) Time(s), Taxi
(1) Balance Cost, Taxi
(g) Time(s), Adm
(h) Balance Cost, Adm
Figure 4: Time and balance cost (only ISORROPIA guarantees the exact solution.)
We observe the hardness of instances with different perferences. Instances in Uniform inherently have fewer feasible stable matchings than those in Hard, hence the brute-force enumeration the rotation graph is time-consuming on hard instances. ISORROPIA decreases the search space by factor of about 10 to 10a (detailed in Appendix A.5). improving runtime by factor of 1 to ENUM (Figure 4(c) and a factor of 2 to heuristics (Figure 4(a) Further, ISORROPIA can be faster than DACC and BILS, but is slower than heuristic algorithms. Even though instance sizes are only up to 1024 in these data sets, the number of stable matchings increases to 10%, yet ISORROPIA manages this increase in a scalable manner. For instances in the real spatial dataset, Taxi, the number of feasible stable matchings grows up 10 yet ISORROPIA improves runtime by factor of up to 10 (Figures 4(e)). For instances in Adm, the improvement about a factor of 10
We compare the balance costs of stable matchings by ISORROPIA and basclines, by the percentage of balance cost over the optimal, in Figure 4 As we show in Section 4 ISORROPIA finds the exact solution to BSM. In the instances where ENUM terminates naturally (i.e., N < 10") and returns the exact solution, ISORROPIA finds the stable marriage with same balance cost as ENUM In instances where ENUM terminates by the enumeration constraint (i.e., N 10?) and may not return the exact solution, ISORROPIA finds the best balance cost. The three heuristics, BILS, DACC and POWERBALANCE do not guarantee the balance cost, having gap of at worst 9 times from the exact balance cost (Figure 4Kb) and 4(h). These heuristics may suffer heavy losses on the worst-off side satisfaction as n increases, as the range of balance cost [n, n²). For example, in Adm, n 2500, the balance costs generated by ISORROPIA, BIL.S, DACC and POWERBAIANG are 273353, 30010001101 3000590++280000 (66806))) 718918 (00018844445550 445565), and 556764(++2341)) finds stable marriage of optimal balance cost and also exhibits competitive time performance. To understand the internal workings of the search (discussed in Section 4.3 operation in Appendix A.5
respectively. ISORROPIA
we report statistics on its
CONCLUSION
We addressed the NP-hard problem of finding fair stable matching that balances the satisfaction levels of both parties involved. As real-world two-sided markets, the number of stable matchings can be large, efficient traversal of the search space is imperative. We proposed an exact algorithm, ISORROPIA, that locally searches a reduced search space of three sets of antichains on the rotation graph. Our extensive experimental study demonstrates that ISORROPIA not only performs efficiently on synthetic and real datasets, including hard instances, but also, quite remarkably, outperforms in terms of time-efficiency heuristics that, we also show, do not return optimal balance cost.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work received support from the Science and Technology Development Fund Macau SAR (0003/2023/RIC, 0052/2023/RIAL, 0031/2022/A, 001/2024/SKL for SKL-IOTSC), the Research Grant of the University of Macau (MYRG2002-00252-F31 and the Shenzhen- Hong Kong-Macur The work was also
Science and Technology Program Category C BSGDX2223002119515590 performed in part at SICC, which supported by SKL-IOTSC, University of Macau. Additionally, this work was supported by an International Network Programme grant from the Danish Agency for Higher Education and Science.
REFERENCES
Atila Abdulkadiroglu and Tayfun Sönmez. School choice: A mechanism design approach. American economic review, 93(3):729 747, 2003.
Atila Abdulkadiroğlu, Parag A. Pathak, and Alvin Roth. The new york city high school match. American Economic Review, 95(2)3644336,, 2005a.
Atila Abdulkadiroğlu, Parag A. Pathak, Alvin E. Roth, and Tayfun Sönmez. The boston public school match. American Economic Review, 95(2):368 371, 2005b.
Kolos Csaba Ágoston, Péter Biró, and lain McBride. Integer programming methods for special college admissions problems. J. Comb, Optim,, 327 2016.
Brian Aldershof, Olivia Carducci, David C. Lorenc. Refined inequalities stable marriage. Constraints, 4(3):281 (00:281-229,, 292, 1999.
Georgios Askalidis, Nicole Immorlica, Augustine Kwanashic, David E. Manlove, and Emmanouil Pountourakis. Socially stable matchings in the hospitals/residents problem. In Algorithms and Data Structures 13th International Symposium (WADS), pp. 85-96, 2013.
Mourad Baïou and Michel Balinski. Student admissions and faculty recruitment. Theor, Comput. Sci., 322(2):
245 265, 2004.
Michel Balinski and Tayfun Sönmez. A tale of two mechanisms: Student placement. Journal of Economic Theory, 84(1):33-94, 1999.
Péter Biró. Student admissions in Hungary Gale and Shapley envisaged. Technical Report TR-2008-291, University of Glasgow, 2008.
Péter Biró and Sofya Kiselgof. College admissions with stable score-limits. CEJOR, 23(4):727-741, 2015.
Sulian Le Bozee-Chiffoleau, Charles Prud' hundhh and Gilles Simonin. Polynomial time presolve algorithms rotation-based models solving the robust stable matching problem. In Proceedings of the Thirty-Thir Third International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024, pp. 2860-2867. ijcai.org, 2024.
Scbastian Braun, Nadja Dwenger, and Dorothea Kübler. Telling the truth may not pay off: An empirical study of centralized university admissions in germany. The B.E. Journal of Economic Analysis & Policy, 10(1):1-38, 2010.
Piotr Dworczak. Deferred acceptance with compensation chains. In ACM EC, pp. 65 66. 2016
Piotr Dworczak. Deferred acceptance with compensation chains. Oper. Res., 69(2):456 468, 2021.
Patricia Everaere, Maxime Morge, and Gauthier Picard. Minimal concession strategy for reaching fair, optimal and stable marriages. In AAMAS, 2013.
Tomás Feder. Stable Networks and Product Graphs. PhD thesis, Stanford, CA, USA, 1992.
Tomás Feder. Stable networks and product graphs, volume 555. American Mathematical Soc., 1995.
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathmattcal Monthly, 69(1) 15, 1962.
Mirco Gelain, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Local search approaches stable matching problems. Algorithmss, 6(4):591-617, 2013.

---

Published as a conference paper at ICLR 2025
Ioannis Ciannakopoulos, Panagiotis Karras, Dimitrios Tsoumakos, Katerina Doka, and Nectarios Koziris, An equitable solution the stable marriage problem. /CTAL, pp. 989-996, 2015.
Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Balanced stable marriage: How close close enough? Theor. Comput. Sci., 883:19-43. 2021.
Dan Gusfield. Three fast algorithms for four problems in stable marriage. SIAM J. Comput., 16(1):111-128, 1987.
Dan Gusfield and Robert W. Irving. Stable marriage problem structure and algorithms. Foundations of computing series. MIT Press, 1989.
Avinatan Hassidim, Assaf Romm, and Ran Shorrer. Need vs. merit: The large core of college admissions markets. 2017.
Robert W. Irving. An efficient algorithm for the "stable roommates" problem. J. Algorithms, 6(4):577-595, 1985.
Robert W. Irving. Optimal stable marriage. In Ming- Yang Kao (ed.), Encyclopedia of Algorithms, pp. 1470-1473. 2016.
Robert W. Irving and Paul Leather. The complexity of counting stable marriages. SIAM J. Comput., 15(3):
655-667, 1986.
Robert W. Irving, Paul Leather, and Dan Gusfield. An efficient algorithm for the "optimal" stable marriage. J. ACM, 34(3):332-554, 1987.
Kazuo Iwama and Shuichi Miyazaki. A survey of the stable marriage problem and its variants. In International conference informatics education and research for showledge-circulatig society, pp. 131-136. IEEE, 2008
Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa. Approximation algorithms for the sex-equal stable marriage problem. ACM Trans. Algorithmss, 7(1):2:1-2:17, 2010.
Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber. A simply exponential upper bound the maximum number of stable matchings. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, Los Angeles, CA. USA, pp. 920 925. ACM, 2018.
Akiko Kato. Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics, 10(1):1-19, 1993.
Donald Ervin Knuth. Mariages stables leurs relations avec d' autres problèmes combinatoires: : introduction I' l'analyse mathématique des algorithmes. Montréal Presses de l'Université de Montréal, 1976.
Donald Ervin Knuth. Stable marriage and its relation to other combinatorial problems : an introduction to the mathematical analysis of algorithms. CRM proceedings & lecture notes. American Mathematical Society, 1997.
Ngai Meng Kou, Leong Hou U. Nikos Mamoulis. and Zhiguo Gong. Weighted coverage based reviewer assignment. In Proceedings of the 2015 ACM SIGMOD International Conference Management Data, Melbourne, Victoria, Australia, May June 4. 2015, pp. 2031-2046 ACM, 2015.
Jay Licbowitz and James Simien. Computational efficiencies for multi-agents: look at multi-agent system for sailor assignment. Electronic Government, 2(4):384 402, 2005.
Cheng Long, Raymond Chi-Wing Wong, Yu Peng, and Liangliang Yc. On good and fair paper-reviewer assignment. 2013 IEEE 13th International Conference on Data Mining, Dallas, TX, USA, December 7-10, 2013, pp. 1145-1150 150. IEEE Computer Society, 2013.
Jinpeng Ma. On randomized matching mechanisms. Economic Theory, 8(2):377-311, 1996.
David Manlove. Algorithmics of Matching Under Preferences. World Scientific, 2013.
D. G. McVitie and I.. B. Wilson. The stable marriage problem. Commun. ACM, 14(7):486-490, 1971.
Antonio Romero-Medina. Implementation of stable solutions in restricted matching market. Review of Economic Design, 3(2):377-477 1998.
Antonio Romero-Medina. 'Sex-equal' stable matchings. Theory and Decision, 50(3):197-212, 2001.
12

---

Published as a conference paper at ICLR 2025
Antonio Romero-Medina. Equitable selection in bilateral matching markets. Theory and Decision, 58(3): 305-324, 2005.
Alvin E. Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 9216):911-1016 1984.
Alvin E. Roth. Private Communication, 2018.
Alvin E. Roth and Marilda A. Oliveira Sotomayor. Two-sided matching: study in game-theoretic modeling
and analysis, volume 18 of Econometric Society Monographs. Cambridge University Press, 1990. ISBN 052139015X.
Uriel G Rothblum. Characterization of stable matchings extreme points of polytope. Mathematical Programming, 54:57-67, 1992.
A. M. Saifuddin Saif, Mokaddesh Rashid, Imran Ziahad Bhuiyan, Md. Wasim Sajjad Ift,, and Md. Rawnak Sarker. Stable marriage algorithm for student-college matching with quota constraints. In ICCA 2020: International Conference on Computing Advancements, pp.
2020.
Mohamed Siala and Barry O'Sulivv.n. Rotation-batt based formulation stable matching. Principles and Practice of Construint Programming 23rd International Conference (CP). pp. 262-277, 2017.
Chung-Piaw Tea, Jay Sethuraman, and Wee-Peng Tan. Gale-Shapley stable marriage problem revisited: Strategic
issues and applications. Management Science, 47(9):1252 1267, 2001. ISSN 1025-1909
Nikolaos Tziavelis, Joannis Giannakopoulos, Katerina Doka. Nectarios Koziris, and Panagiotis Karras. Equitable stable matchings in quadratic time. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 455 465,465522 2019.
Nikolaos Tziavelis, Ioannis Ciannakopoulos, Rune Quist Johansen. Katerina Doka, Nectarios Koziris, and Panagiotis Karras. Fair procedures for fair stable marriage outcomes. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 7269-7276. AAAI Press, 2020.
Hoang Huu Viet, Le Hong Trang, SeungGwan Lee, and TaeChoong Chung. A bidirectional local search for the stable marriage problem. In ACOMP, pp. 18 24, 2016a.
Hoang Huu Viet, Le Hong Trang, SeungGwan Lee, and TaeChoong Chung. An empirical local search for the stable marriage problem. In PRICAL, pp. 556 664,,,442222 2016b.
13

---

Published as a conference paper at ICLR 2025
A APPENDIX / SUPPLEMENTAL MATERIAL
A.1 THE STRUCTURE OF ALL STABLE MARRIAGES
Given stable marriage instance I, all stable marriages U are composed of (1) two side- sade-pessimal stable marriages (nw and (M) and (2) other stable marriages. Figure shows a conceptual framework of the structure of all stable marriages. First, two side-pessing peeseeel stable marriages can be generated by Deferred Acceptance (DA) algorithm upon its first termination. Then, other stable marriage be generated by re-assigning some pairs from paw and finally it can reach at paM. The re- assignment follows set of DA procedures (i.e., break stable marriagss and apply DA multiple times), which can be compactly represented by a set of rotation nodes.
Table 7: Notations
Notation
Description
JAM, jaw
M ppessmmal [W] ppessimal stable marriages dissanisfactoons of side [M] and W" [[[Qquaiionn
Eliminate a closed subset of cotations
CM: Ciy
A1
Jaw \ (r, - Pda
R
rotation poset
rotation graph predecessors o an antichuin, closed subser and stable manriage all antichuins, closed subsets and stable marragess instance size, ie., size of agent sets M and number of all stablc marriages ie., size of 2t stable marriage derived from antichain rellteed antichain, closed subset stable maniaae
Pred(r)
A48
MMM
A.S.M
pessimal on W-side
* pessimal M-side eliminate all rotations
n
N Ha
Eliminate rotation jay \ T2 - f4g
tue Pe
Rig Ray
the (ar (r/[W) dissdvanntgged rotations (Definition
RRoasssinn pairs from ja
Ast Auy Asow
three subsets of a divided by disadivantaped rotatees three sets proenising antichains (Table
Figure 5: The structure of all stable marriages
An. Am
Dout
out- out-degree list all ratations
Bo Pgg
double ended quese of rotations in running closed subset local optimal stable marriages (Table
DA algorithm. The Deferred Acceptance (DA) algorithm (Gale & Shapley 1962) lets each man m from the first preference and sequentially propose to the next most preferable woman in the order Pms as long as the man finds itself being single. Each woman w accepts a (m, w) proposal if the woman is single or prefers m to the current partner p(w). Example 1 (All stable marriages). Given the instance in Table X we discuss four DA procedures that generates all stable marriages in Table [0 The corresponding re-assigned pairs of each DA procedure highlighted respectively with black, green, red and blue boxes in Table B and Table [70
First, we start the proposal sequence: (I) mi to ws (accepts mı): ): (2) m2 to w2 (accepts ma): (3) ms to ws (accepts my, abandons my)): (4) my to wi (accepts m.), etc. When DA algorithm first terminates (i.e., each man gets assigned), we get the stable marriage po in Table and the placements on preference lists are highlighted with the black box in Table E
Next, if we break (mi, wi) (or (ms, wi)) in pl, and then apply DA algorithm that makes m. proposes to W2 (or ma proposes to W2). we re-assign pairs (highlighted with the green box) from and get a new stable matching ps. If we break any pair of (m2, ( (ma, wa) (m4, wa) in μio and then apply DA algorithm, we re-assign pairs (highlighted with the red box) from po and get the stable marriage μ22-
We can as-assign pairs highlighted with red and green box logether from μo and get the stable marriage pay Further, based on ua. by breaking (ma, ws) or (ms, wi), and then applying DA algorithm. we can re-assign pairs (highlighted with the blue box) from pa and get the stable marriage ps- We can no longer apply DA
algorithm for pa, since each woman has no better choices. In other words, woman are unwilling to accept new proposals.
The DA algorithm (Gale & Shapley 1962) outputs a stable marriage optimal for each agent on one side and pessimal for each agent on the other side VMiie & Wilson 1971 Irving & Leather 1986). i.e., we get μo if men propose to women and we get μr if women propose to men. Shown in Table 10 we denote these two outputs as faw and jas, where the subseript denotes the side that gets pessimal outcome.
Domination relationships. A stable marriage μ dominates another stable marriage μ¹, or < p²', if each agent on the M-side gets no less preferable partner in μ than in p², and, as stability implics, cach agent on the W-side gets no more preferable partner in μ than in n.. The set of all stable marriages forms distributive lattice (Gusfield Irving 1989), where wa dominates, and μm is dominated by, any other stable marriage. Meanwhile, no stable marriage can achieve a better choice ahead the black boxes for men and a worse choice afterwards the black boxes for women.
Rotation elimination. To compactly represent the breakable pairs and the corresponding re-assigned pairs for each DA process, we use the construct of rotation (Irving 1985 Irving & Leather 1986). A rotation
14

---

Published as a conference paper at ICLR 2025
Table 8: Preference lists
Preference lists of men
Preference lists of women
Pm
W2
W74
W/3
P
m4
mm
12
07
05g
004
W11
Pat
M1
m3
74
72
mm
17g
012
011
P
F0g
174
701
7/
17g
P
W4
125
012
P
77
Ping
122
101
606
03
775
mgg
122
mg
m1
Table 9: Rotations
T1
After elimination
r== (m1, wi) (ms, Wa)
(ma, (2) ma)
T2
12= (m2, mt) (ma, Wa) (ma, u4))
(ma, M0g) (ma,, maa (m4, M%)
-3= (ma, ws) (ma, wh)
(ma, (m), Mt?
P1 Figure 6: G, Rotation Graph
Table 10: Rotation elimination and balance costs for all stable marriages
Matches
Cas(u)
Cw (w)
Worse(s)
Balance Cost
volpw)
(19g wyy My) (mig Mrm ony fong, a12)
W-side
(mo, ws)
(mus, My) (ona, (ome, ond
(ons,
[n)
(n)
16
W-side
(0g un)
(0t, Myy (mis, frne, sos)
(mss, my)
[ru)
fra)
12
11
Af-idd
12
M4
(m) Wg)
(mg. Myy Myy Mtym ans)
(mg. my
M-side
(ma un)
(my, myy (mna, uta)
(mr,, (mng,
(ra]
17
M-side
belonging to (or exposed in) μ is an ordered sub-list of matched pairs r r= [(m,, _(m))) (mi+1, p(m;==)) .... (17z4d p(m;==)))] Given that exposes rolation we can break the marriage of m. in rotation and apply the DA algorithm let m. propose the most preferable user, eventually being assigned with user (( ) who abandons may1i likewise, m4+1 will then matched with ( and so on until we reach p(m,) in full cycle. Intuitively, each of the tasks m,, M4+1,.... Ma4d d is matched to a user less preferable to it. ((m=+1), p ((ms+2)..... ((m;) respectively, while each of the user p(m:), {(mi++1) ............ p(ma+a) +d) is matched to a task more preferable to the user, mi+d; M....... Mi+dd1 respectively. Thus, the ensuing match- ing n² is still stable. We call this re-coupling rotation elimination, denoted p/r p². By eliminating the rotation r, we can obtain new stable marriage μ². Certainly, μ dominates μ².
Example 2 (Rotation Elimination). Table shows the breakable pairs and the corresponding re-assigned pairs of rotations r2, exposed in the W -pssiimal stable marriage pww is computed by DA algoritium and follows the movements from black boxes to red boxes in Table For m22 ma, ma each of them gets a less preferable choice (i.e., the movement of boxes are from high to low), while each of wa, WS, W4 gets a more preferable choice (i.e. the movement of boxes are from low to high). As shown in Table 10 after eliminating 12 from pw, PW /ww.r. we get new stable marriage μ2.
Eliminating a set of rotations. The set of all rotations R constitutes partially ordered set (poset) (R, ) (Irving Leather 1986). A partial order r' indicates that r' is only exposed after eliminating The poset (R) is represented by directed acyelic graph G = (R, E). where nodes stand for rotations and an edge (r, (') denotes a direct partial order r - r', i... fralr - r. + guaranteeing connectivity. We denote the predecessors of r as Pred(r), i.c., for cach r' E Pred(r), r is reachable from r'.
Finding all rotations and all edges in G cost O(n²) time (Irving et al. 1987 preprocessing step beneath the core of problem.
Gusfield 1987] this construction is
Example 3 (Poset and Rotation Graph). Figure shows an example of rotation graph G with partial order relationships representing rotation poset. As rotations and are predecessors of each other, may eliminate them an arbitrary order, as pw//fr ww//fr,, r2) or pw /rr, r1). However, as both rı and r2 are predecessors of r3, we expose r's only after we eliminate both Ti and ra, Le., T3 exposed in stable marriage ps but not in fı and p2, as shown in Table 70
Antichains and Closed Subsets. An antichain a subset of such that no rotation in a predecessor of another. Given an antichain a, we can construct a unique closed subset s = Urea (r) U Pred(r), which contains all rotations in and their predecessors. Recall that for {ra} in Example should climinate
15

---

Published as a conference paper at ICLR 2025
rotations in its closed subset, (r1, ra). according to partial order relationship starting from μaw, so that each rotation is exposed in the elimination process.
Example 4 (Antichain and Closed Subset). As shown in Figure GigureGand Table 10 [ri, ] is an antichain and
(ri, } is its corresponding closed subset. A single rotation also Jorms antichaun, e.g., {ra} corresponds s {ri, r2, ra). A counterexample of an antichain is (ra, Pa), where
predecessor of
All Stable Marriages. Let A be the set of antichains and S the set of closed subsets in G. Theorem Irvvng & Leather 1986) provides foundational fact the structure of all stable marriages.
Theorem 5 (Relationship between antichains, closed subsets, and stable marriages), (Irving & Leather 1986 In any stable marriage instance there is one-to-one relationship among antichaiiss A, closed subsets S and stable marriages U. Enumerating all stable marriages #PP-omplete
In other words, for any antichain a, we can find corresponding closed subset and stable marriage μ via rotation elimination jow/ /s + paa. For simplicity, refer to these concepts (i.e., μr, and a) interchangeably without loss of clarity. As all stable marriages listed in Table 10 calculate the side dissatisfactions (C'sr Cw ). the worse-off side (Worse(u)) and balance cost by Equation and respectively. The balanced stable marriage is μ22.
A.2 NAIVE APPROACH (ENUM AND ENUM
A naïve way to find the balanced stable marriage y is to enumerate all stable marriages and apply Equation equa- 2 An efficient algorithm for enumerating stable marriages, ENUM (Gusfield & Irving] 1989), expands closed subset with rotation in each step; its time complexity O(n² + n.N.. As N extremely large in some instances (Irving Leather 1986), we design an efficient and practical algorithm that reduces search space.
Unfortunately, we cannot use ENUM to find promising antichains either, as it enumerates closed subsets in an order from 0 to R (i.c., from μW to (M)) Intuitively, the enumeration has tendency from dominating stable marriages dominated stable marriages. By Property 3.T unpromising antichains will be enumerated before promising antichains. To overcome this problem, we reverse the enumeration order of ENUM craft ENUM which enumerates closed subsets from I to 0 (i.e., from jaar to (.w). thus benefits from pruning AM to Am (i.e., by Table 4 Am only consists the antichains of length 1), and devise our approach based on ENUM In this process, say that rotation node having out-degree 0 in subgraph terminal node therein; the of terminal nodes within closed subset the antichain corresponding
Algorithm 2 ENUM
Input: Rotation Graph G Output: Balanced Stable Marriage jt'
I: Initialize Dout, Ro, 8 :
2: ENUMERATTiC Dont, Ro)
# start enumeration from G * return the exact BSM solution
3: return 11
4: function ENUMERATE(S, Dant, Ro)
Ro * # then
6: 7 = Ro-pop_from
7:
s.remove(r).
rotation
new closed subset {r}
climination
Update 4² to μ by Equation 2
9:
for E parents(r)) do Dout(r') = Dour(r') 1
10:
* out-neighhor o' removed
11:
if Dous (r') )²) then Co.push_back(r"
12:
ENUMERATEO ATM(S, Dout. Ro) for r' E parenta(r) do Doni = (r.r(r')+
* recursive call (i)
13:
15:
if D = then Ra.pop_barr back
16:
s.add(r)
17:
ENUMERATE(S, Dout, Ro) (h.push_front(1)
* recursive call (ii)
18:
Algorithm shows the pseudocode of ENUM", Using an array Dont to record the out-degree of all rotations in a shrinking rotation graph and double-ended queue Ro to store the running terminal nodes in closed subset ENUM recursively performs two operations: (i) it removes terminal node E Ro from the running closed subset (Line 7. reduces the out-degrees Dour of parent nodes and enters them if they hecome terminal
16

---

Published as a conference paper at ICLR 2025
nodes thereby (Lines 9
and proceeds recursively (Line 12 and (ii) restores the out-degrees Dout and any
corresponding terminal nodes from Ro s (Lines[33 [5 and previously removed r (Line [6 proceeds to recursively remove from s other terminal nodes in Ru (Line 17). and eventually restores r to Rg (Linc 18
A.3 LOCAL SEARCH IN ISORROPIA
The pscudocode of local search strategies ISORROPIA shown Algorithm B
particular:
Local Search in Rs. As Thcorem F shows and in Aut that minimizes Cm. only need consider all μr, with Rp.
to find the locally optimal stable marriage pi
Local Search on Ra. First, we set plg to Pary and update the balance cost by Equation equation 4 (Line Then we create the subgraph of G induced by Rw (Lines O which corresponds Aw. and starting with & = Rw. enumerate closed subsets s, hence stable marriages fr. while keeping track their corre- sponding antichains a. This enumeration proceeds while the antichain contains at least one rotation in Rs (Line TO), hence belongs to Ar U An. The enumeration removes rotations from progressively generating stable marriage p' from another such that μ¹ n.. Thus, if Worse(p) WWside, by Properties 3.1 it is (J) Cw Cw(1))) and μ' is better. effect, it terminates when reaches a stable marriage Hou with Worse( = W side while the best solution at hand is better than μ. (Line IT).
Algorithm 3 Local Search Strategies
I: function LOCAL SEARCH RG-
2: return min (Mr(p)
* |a|
ffrrr a E Au
rER
function LOCAL SEARCH IN Ra
4: Update μa using Paew
5: Initialize Daut, Ro for Rw
the subgraph of G corresponding to Aw
ENUMERATE(RWW: Ro. Dont, Ro)
* At An
7: return jaa
function ENUMERATERS ATF(s, a, Dout: Ro)
9:
if Ro # then
10:
if Ra then return
antichain must contain Ra
11:
if Worse(p..) = W side and (wa) 2 C(2a) then return
12:
r: Ra-pop_front s.remove(r). a.remov((r).
13:
* new closed subset {r}
14:
Update HL using
15:
for r' E parenta(r) do
16:
Dour = Dour(r')
17:
Dowa (r') = then Ra.push_ saassh_hack(r)) a.add(r')
18:
ENUMERATE(S: a, Dout, Ra) for r' E prrents(r) do
# recursive call (i)
19:
20:
Dowilr) = (ouc(r')+ if Dous (r') then Re-pop_ back, remooer("")
21:
22:
s.add(r), a.add(r). s ENUMERATE(s, a, Dout, Ro) Ro.push_ ffass_rrootrr
23:
* recursive call (ti)
24:
Time Cost. The time cost of ISORROPIA dominated (i) gathering candidate rotations subsets R.g and Rs- (ii) searching those. First, we gather Ras and Rw by calculating μr, for all rotations ( xz²). We avoid calculating all r-related stable marriages, since a rotation is in Ras if its parent is in R&s (Property 2 In practice, we calculate about 50% of μt, constructs, as detailed in Section 5 In Ra. we find the maximal layer Ew in OlEw n²?) deriving
R[1). R[2).... R(ew), Rlew + 1). Since there are more layers than rotations, it lw R In Re, we check most //2 parents of cach rotation RM O( n). Thus, most cases. Then, the local search in Rs only scans r-related stable marriages μe in Rs. already calculated in the previous step (to collect Ras and Rw), ), in O(RRa By definition, Rs. cannot be larger than n/2, the width of G. On the other hand, for local search in R., apply ENUM with time complexity O(n" n.Va), where No. is the number of stable marriages enumerated that local search. Overall, the time complexity (( fw) n² nNv2). While potentially exponential, as the problem is Wardd ISORROPIA reduces the search space N to No + [A] + Lw. with No < 50%N in practice.
this step requires ((IR) (w).-r .n²) in total, where [R] εw <
17

---

Published as a conference paper at ICLR 2025
A.4 APPLICATION TO SESM
Here we apply ISORROPIA to sex-equal stable marriage problem (SESM) Kato 1993). As Table shows, the SESM and BSM problems have difterent objectives defined in terms of Cas and Cw.
C.c (() = min Car Cw (+))
(5)
PEl
We rewrite the sex-oquality cost using the notation of Equation 4 as:
(w(()) Cxr())
Worse(()) = W-side
MCe = arg min
(6)
PEM Cue(p) Cw (p) Worse(1) = M -sdee
This minimization prohlem is also non-convex and NP-hard (Tziavelis al. 2019)) Yet can apply ISoRRopia SESM using objective function in Equation 6 to find the exact solution for SESM. The following result ensures the correctness of ISORROPIA for SESM, namely that Ar, An and Anr remain promising antichains.
Theorem 6 (Ai, An and Am for SESM), Theorems 2
and and applyy SESM.
Proof. the proof Theorem we have Mut K Horw" By Property and Property 2 it is Worse((u.) W-side, Worse(Maas)) W-side, (wwr) Cw (Mar ) and Che (pa') Cat (pa ) Therefore,
(wa))) Car(pa)) Cw (Hazy Car (Hossw ). hence Norw has better sex-equality cost than par. In
3 and 4 we infer that [r- Ma. Worse( = M-side, Worse(ma) M-side, and (M,) < Carl (pa). Thanks Property 1 is Cw (1.)) Cw(Ho), hence Car(Ha) Cw (w(Hu) >
the proof of Theorems
Cm (n.)) Ow (Mr).
A.5 STATISTICS ISORROPIA
To understand the internal working of the search (detailed in Section 4.3). we also report statistics on the operation of ISORROPIA. [ statistics on rotations and stable marriages, the following average percentages per instance size:
MMaayl/N, [Rw))/N percentage of stable matchings having Worse( M-side and Worse(ıt W-side the worst case.
#u/N: #u is the number of stable matchings explored by ISORROPIA. Clearly, #y Na.
|Al//awyy |Aul/ |erry) and |Aurl/ percentage of Ai among ((W)) An among M(M) and Am among ((ar)- (Table 4
[Ral//M), [R /|R]: percentage of the two sets of disdavantaged rotations among all rotations. (Definition)
R Rw |. |R- Raz] percentage of candidate rotations R& among Rw and Ro among Rıs (Definition and[4]
Table 11: Statistics rotations and stable marriages
[[A)
Re /|Rrr
[Rol//Au
#w/N
Au //ecar]
[Auzl//e
Unifomn
7.5L
50.25%
50.09%
0.21%
0.15%
7,243
50.57%
49,05%
$4.95%
9.47%
0.04%
0.02%
$1.79%
0.02%
128
100
50.51%
19.49%
0.65%
1330%
648
49.15%
50.82%
3.65%
6.09%
0.00%
0.426
Hard
256
512
220
140
49.32%
7856
51 1276
50.68%
1.01%
1668
0.44%
0.74%
13,229
1,341
40 5876
50.99%
49.01%
59.42%
0.88%
01307
0.555
1.399
0.15%
0.08%
0.095
0.26%
1024
362
90.78%
40.32%
0.962
0.36%
3,426.000
35-4076
64.607
0.18%
0.209
5.00F006
0.00%
7k
44.95%
2,8388
0.75%
74,304
51
48.92%
0.05%
0.40%
49.1%
$0.99%
0.37%
1.573.916
5k
52,78%6
47.2225
7.15%
0,2915
1,977.611
36.81%
53.19%
45.915
66.13%
3,37%
9,796
$4.00%
40
0.121
Adm
2k
50.9616
0.52%
339 197
32
67.255%
49.80%
0,02%
6.33E
2.5k
319
53.
76%
46.24%
2.39%
0.35%
1.256.356
47
27.55%
$2.75%
24.389
40.56%
3,424
3.25E-05
In accordance with the analysis of time cost in Section 4.4 the number of rotations smaller than the number of all stable marriages, i.c., - fw & N. We note that the two sets of disadvantaged rotations are almost equal-sized. ISORROPIA filters out most rotations to extract the candidate rotations R.; and Re. which are about 0.1% 10% of all rotations.
18

---

Published as a conference paper at ICLR 2025
On the other hand, among stable matchings, the worst cases rotations Hard and Adm. Further, the of promising antichains comprise only small subset of all stable matchings (Table I1 columns 12, 13, 14). In effect, ISORROPIA drastically reduces the search space and thereby improves upon efficiency. In effect, based on the compact representation of a rotation graph, we extract hidden relationships among stable matchings than would have been require to explore the stable matching lattice (Irving) 1987 Notably, stop the enumeration of stable matchings in ENUM and ENUM when their number exceeds 10", hence do not report the results of these instances in Table
evenly shared the sets of
19


Reviews:
[{"review_id": "JDOL5rPrC3", "reviewer": "Reviewer_8Cf2", "summary": "This paper develops an exact algorithm using carefully designed heuristics to solve the balanced stable marriage problem which is known to be NP-hard and demonstrates that the proposed algorithm is faster in practice than existing exact algorithms. In a stable marriage instance, there are two disjoint subsets or sides of agents, e.g., men and women, with each side having ranked preferences over agents on the other side. The goal is to find a matching \\mu, a collection of disjoint pairs of men and women, that is stable, i.e., no pair of man and women prefer each other than their partner in \\mu. Here, the rank that an agent i has for their partner \\mu(i) can be thought of as a proxy for their dissatisfaction with the matching \\mu. The total dissatisfaction of a side is the sum of dissatisfactions of agents on that side. \n\nIn the balanced stable marriage problem (BSM), the goal is to find a stable marriage which minimizes the maximum among the dissatisfaction of the two sides, i.e., to balance the dissatisfaction of the two sides. This is motivated by a well known property of the set of all stable marriages that there is a man-optimal (which is also woman-pessimal) and a woman-optimal (which is also man-pessimal) stable marriage, and that the set of all stable marriages form a distributive lattice, and that it is possible to explore all stable marriages, from the man-optimal to woman-optimal stable matching through a series of operations called rotation elimination, each of which increases dissatisfaction of the men's side and decreases the dissatisfaction of the women's side. The set of rotations forms a poset and can be represented by a directed acyclic graph (DAG). \n\nThe proposed algorithm performs an intelligent search of the space of all stable matchings using heuristics and pruning strategies obtained from a careful analysis of the structure of stable matchings and a classification of the set of rotations and \"anti-chains\", sets of rotations with no shared predecessors in the DAG or rotations. The paper identifies that it is sufficient to explore three sets of anti-chains (and induced stable matchings) in order to find a balanced stable matching from which they identify two sets of candidate rotations. This is the main technical contribution of the paper. The proposed algorithm takes as input the DAG of rotations, computable in polynomial time, and produces a balanced stable matching as output. The algorithm works by performing a local search by enumeration of stable matchings due to a restricted set of rotations. The local search is potentially exponential.\n\nThe section on experiments validates their approach with the proposed algorithm performing better than a naive approach in practice in terms of running time. A comparison with approximation algorithms is also included showing to what extend the minimax BSM objective is achieved by various algorithms in comparison with the proposed exact algorithm.", "questions": "- Is there a typo in line 304?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed method is novel and interesting. BSM is an interesting and well motivated problem in the stable matchings research community with several potential applications. The paper is overall well written but has some typos which makes it confusing to read.\n- In terms of running time proposed exact algorithm outperforms the naive enumeration approach and compares favorably with approximation algorithms.", "weaknesses": "- I do not find a major weakness except the fit within ICLR. My lower score for the contribution is due to the review criteria which clearly states \"Are the results valuable to share with the broader ICLR community\". I am not confident that they are.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fatNoSs72G", "reviewer": "Reviewer_sQQa", "summary": "This paper looks at the problem of stable matching in two-sided matching markets, which is a well-studied problem in the field of matching / mechanism design. In particular, the authors tackle the problem of finding a fair matching, as measured by comparing the two sides of the market, that is NP hard in its standard formulations: namely looking at the Balanced Stable Marriage problem. The balanced cost objective is non-convex and its minimization is NP hard. They are specifically motivated by the bottleneck created by the fact that the search space of all stable matching can grow exponentially in the size of the problem, and finding such a matching is infeasible in various real world applications. They authors present an algorithm, ISORROPIA, which uses a local search heuristic to reduce the search space and give an exact solution for instantiations that are reasonable in size. They do so by leveraging the structure of all feasible solutions to compactly represent them as a partially ordered sets. They present a theoretical analysis of this algorithm and experiments, using synthetic and real data, to show that ISORROPIA is more time and cost efficient than standard heuristics.", "questions": "See weakness section above.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Two-sided matching is a well-studied and well-motivated problem, from both a theoretical and practical perspective. The version of it that they study, called the Balanced Stable Marriage problem, aims to tackle a discrepancy that exists in the standard formulation of this two-sided matching which is optimal for individuals on one side of the market and pessimal for the other side. The efficiency bottleneck they aim to address in this problem is a practical barrier and the insights they present about the structure of these antichains may also prove useful for future work. The problem presentation in this work is well-motivated and the authors also do a reasonable job giving the key takeaways upfront. The experiments they present performed better than I would have expected and the authors present these results both on larger instances of synthetic data and real data from various domains.", "weaknesses": "There are two key concerns with this work\n\n(1) Specific to the results, while the first few sections of this paper were well-presented, the results are at times hard to decipher and follow along. It would be great if the authors revised the paper to provide intuition throughout the presentation of the algorithm. In particular, how are these anti-chains constructed and why does the pruning of the search space not seem to lead to significantly suboptimal solutions? \n\n(2) Since one of the most compelling things about this  ISORROPIA is that it may be of practical use, it would be great if the authors included several more synthetic experiments to show how the performance degrades in size and complexity of the problem. \n\n(3) Setting aside the above questions, it is not clear that ICLR is the right venue for this work as there doesn't seem to be any learning component.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K8laF63t4b", "reviewer": "Reviewer_kArv", "summary": "This paper addresses the Balanced Stable Marriage (BSM) problem, which aims to achieve fair, stable matchings in two-sided markets by balancing dissatisfaction across both sides. The authors introduce ISORROPIA, which finds exact, balanced stable marriages by focusing on promising subsets within the solution space. Through experimentation, ISORROPIA outperforms existing approaches, particularly in time efficiency, without sacrificing the fairness objective.", "questions": "1. ISORROPIA narrows down the search space by focusing on promising antichains, yet the complexity of identifying these subsets is not thoroughly discussed. What is the theoretical bound on time complexity for extracting and evaluating these promising antichains, and under what conditions might this process become infeasible as the market size grows?\n\n2.  Given that ISORROPIA minimizes the balance cost by searching over three specific sets of antichains, is there a mathematical guarantee that this focus always yields the exact minimum balance cost? If not, what bounds can be established for the deviation of ISORROPIA's solution from the true optimum?\n\n3. What is the sensitivity of ISORROPIA’s performance to these initial stable marriages?\n\n4. The rotation graph forms the basis for ISORROPIA’s local search, where each rotation represents a possible move in the solution space. How does the structure of the rotation graph (e.g., density of edges, distribution of antichains) affect the convergence and efficiency of ISORROPIA? Can we quantify the relationship between graph properties and the number of steps required to reach the optimal solution?\n\n5. The paper states that the balance cost objective is non-convex, adding complexity to the optimization process. Can ISORROPIA guarantee convergence to a global minimum in all instances of the BSM problem, or are there instances where the algorithm might get stuck in local minima? If so, under what mathematical conditions does ISORROPIA ensure it escapes local minima?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper aims to achieve an exact solution to the Balanced Stable Marriage (BSM) problem, addressing fairness by minimizing dissatisfaction across both sides.  The introduced algorithm reduces computational overhead compared to baseline methods.", "weaknesses": "1. The paper lacks a comprehensive analysis of performance in diverse real-world applications.\n\n2. The algorithm assumes static, pre-defined preference lists on both sides, which may not align with real-world two-sided markets where preferences are changing over time. \n\n3.  The algorithm focuses on a subset of promising antichains to reduce computational costs. However, this selection could inadvertently introduce bias by excluding other potentially fair matchings that fall outside the selected subset.\n\n4. The paper compares ISORROPIA primarily with traditional baselines and established heuristics. Including comparisons with more recent advancements or adaptive heuristics in stable matching (such as learning-based stable matching) could be more better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HnvuFRIIRj", "reviewer": "Reviewer_fH5T", "summary": "This paper considers the Balanced Stable Marriage (BSM) problem. In a two-sided market where each agent from one side has a preference list over agents from the other side, a stable matching is a matching in which no pair of agents prefers each other over their current partners. The seminal Gale-Shapley algorithm finds a stable matching in polynomial time. Subsequent work has focused on finding a stable matching that is optimal in some measure, such as regret cost, egalitarian cost, and sex-equality cost. The authors consider a specific measure of performance: the balance cost, which is the maximum of the total dissatisfaction of the two sides. The problem has been shown to be NP-hard, and the authors provide a heuristic algorithm that finds the optimal stable matching in balance cost. Although the algorithm is not guaranteed to run in polynomial time, the authors provide empirical evidence that it runs efficiently on practically relevant instances, outperforming existing algorithms in terms of running time or solution quality.", "questions": "1. In practical applications, what algorithm and performance measure are typically used for the stable marriage problem? Is the balance cost the dominant measure in practice? And does brute-force enumeration suffice in practice?\n2. Have you considered how to construct instances where the proposed algorithm performs poorly? What are the limitations of the proposed algorithm?\n3. Feel free to respond to the points raised in the \"Weaknesses\" section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is remarkably well-written and easy to follow, and the background on the problem is well-explained.\n2. The main algorithm is rigorously stated and analyzed, with intuitive graphical illustrations to aid understanding.\n3. The empirical evaluation against existing algorithms is solid and convincing, showing that the proposed algorithm is competitive in terms of running time and solution quality.", "weaknesses": "I have no major concerns about this paper and am happy to see it accepted. However, I have a few minor comments that the authors may consider addressing.\n\n1. **Relevance.** This paper is of high quality, and I personally appreciate the results. However, it seems to me that the results are mainly of interest to the discrete algorithms community. It would be helpful if the authors could discuss the paper’s relevance to the broader AI community and why ICLR would be the right venue for this paper.\n2. **Experiment design.** Some aspects of the experiments could be improved. For example, when reading Figure 4(d), I was initially surprised that `ENUM-` performs worse on smaller instances than on larger ones. Then I realized that this is because you limited the number of iterations for `ENUM-`, and for some reason, the smaller instances required more iterations for `ENUM-`. However, the running time of `ENUM-` on smaller instances is still much shorter than on larger instances. From a practical perspective, I think it would be more informative to limit the running time of the algorithms instead of the number of iterations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)