acceptodds
Under review as a conference paper at ICLR 2027

Islands of Stability: Tractable Lattice Structures for No-Regret Learning of Super-Stable Matchings

Abstract

The stable matching problem has long served as a foundational model for two-sided market design, yet classical solutions assume that complete preference orderings are known in advance. We study an online version of this setting, motivated by the challenges of learning a stable matching in a repeated game—specifically as it relates to super stability and efficient learning under partial information. Our model is designed to operate directly on pairwise comparative feedback, making it practical in settings where agents observe only comparative outcomes. This forms a more natural representation of preference elicitation, obviating the need to assign ordinal scores to outcomes (common in previous work). Operating on direct pairwise feedback, we first present a learning algorithm, , with provable sublinear regret guarantees with respect to achieving any stable matching. Next, as a crucial extension, we present , an algorithm which exploits the lattice structure of stable matchings and the concept of super-stability, connecting common stable matchings among different refinements of a bipartite partial order into connected graphs, called islands. We demonstrate that these islands reveal structural properties of the preference-refinement space that can be exploited for more efficient super-stable matching search over partial orders. This allows to sample more efficiently, making only the pairwise comparisons needed to resolve the problem structure within a single island. We provide a tractable means to construct this island structure, enabling its use in an efficient online setting and demonstrating that it achieves no-regret performance while avoiding full preference resolution. We illustrate the applicability of our approach through a natural application to LLM routing, where agents must be matched to tasks in a streaming setting, and further provide corresponding empirical results to corroborate the theoretical properties.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Stable matching, Online learning, Lattice structures, Preference elicitation, LLM routing

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 2 reviews, above 9% of the others.
Reviewer_A7g1OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies online learning in stable matching markets with partial rankings. It introduces two methods that adapt explore-then-commit. The first algorithm, Pairwise Two-Sided Explore-then-Gale–Shapley algorithm (P2ETG), combines explore-then-commit together with Bradley-Terry maximum-likelihood estimates and Gale-Shapley. PrefLID then modifies P2ETG using properties of lattices of stable matchings.

Critical strengths

To the best of my knowledge, studying partial rankings in the paper’s setting and using properties of lattices are novel.

Critical weaknesses
  1. As also declared by the authors in the AI use statement, they relied on AI tools in writing. However, there’s a lot of AI involvement here without much human review afterwards that really hurts the submission. The writing relies heavily on long dashes everywhere. Also, the paper is full of inaccurate statements, vague and unusual phrasings, and overly verbose text (most of the paper spends nearly 6 pages before even getting to the main results/setting partially because of this verbosity). The very first line of the abstract is the most immediate example. Many parts of the paper read like insufficiently edited AI-generated text (e.g., the abstract jumps between concepts without properly defining any of them, the introduction suddenly discusses lattices in line 63 without defining them, Figures 2-3 are never referenced/discussed in the text and so on). There are also (numerous) issues in the references, as detailed in my “other comments” below. Though it is permissible to use AI tools for writing, the paper requires substantial human editing to improve readability. The authors need to go back and rewrite the paper properly in their own words while fixing the references. Below are the most problematic examples (other examples appear in the subsequent comments):

    • Probably the most critical issue is calling the expression in equation (2) regret in the first place. It is actually the algorithm’s overall error in obtaining a stable matching. It does not measure regret since there’s no comparator against which regret is measured here. Any reference related to this metric that wrongly positions it as “regret” should be revised accordingly.

    • The phrase "assigns ordinal scores to outcomes" is somewhat ambiguous. Numerical scores can represent ordinal preferences, but only their relative ordering should matter. It may be clearer to say "assigns numerical ranks" or "represents ordinal preferences using numerical scores”.

    • There are a lot of repetitions in close proximity, which are other signs of not properly edited text. For example, lines 290-292 repeat what is said in lines 294-297, while lines 295-297 are then repeated (again) in lines 303-306.

  2. Several key notions are either not properly defined, not defined where they should be defined or not defined at all. The most critical one: Lines 229-240 discuss the most critical terms of the paper, including lattices and rotations, but they are never defined (not even informally). Another example: the paper considers strict rankings, but definition 2.4 of super-stability suddenly uses terminology of rankings with ties. Further, several notations in section 3 are not well-defined, such as partition functions (which is also ambiguous, as detailed later). Partial rankings are discussed multiple times in section 1-2, but are only defined in section 3 together with an awkward statement “the hat denotes that only some pairwise relations have been established with high confidence”, which seems to refer to the online version of the problem. However, the online setting is only defined later in section 4 so this part of the discussion is not really meaningful at this point. Below are more details on those issues:

    • There seem to be a lot of issues surrounding super-stability. The descriptions of super-stability in the abstract and definition 2.4 are inaccurate. For partial rankings, super-stability characterizes matchings that remain stable under every linear extension of the partial preferences. The abstract should be revised based on that. In the abstract, it is also unclear how super-stability relates to the connected graphs referred to as "islands" and this connection should be explained more carefully in the abstract. For definition 2.4, the discussion before it deals with partial orderings (as the title of section 2.1 also suggests), but definition 2.4 is actually defined for a different setting. First, the authors consider strict rankings (see, e.g., the beginning of section 2), but definition 2.4 suddenly discusses agents that may “weakly prefer” other agents. Also, definition 2.4 seems to be defined for complete rankings and does not discuss partial ones. After the definition, the discussion suddenly gets back to partial orderings but says “a matching remains stable under every refinement of the ties into strict orders”. Yet, the paper assumes strict rankings, so the statement should instead be “every linear extension of the partial (strict) orders”.

    • Lines 198-199 defined “partition functions”, which seems underspecified. There is no precise definition for a coarsening of the bipartite ordering topology and what properties must the mapping satisfy. Is coarsening defined by removing pairwise preference comparisons? It should also then be formally defined how the collection partitions are actually obtained. Do you mean that any mapping can partition its domain through the preimages of its outputs? This should be made explicit. Also, the term “bipartite ordering topology” used throughout the paper is not very conventional.

    • The completely uninformed ordering in lines 206-207 could be defined more formally as an empty strict preference relation or equivalently as a single unresolved block containing all opposing agents. One possible formulation would be as follows. For each agent a∈Aa\in A, define a strict partial preference relation ≻^a\widehat{\succ}_a over BB. The completely uninformed two-sided preference profile is ≻^AB0=((∅)a∈A,(∅)b∈B)\widehat{\succ}_{AB}^{0} = \left( (\varnothing)_{a\in A}, (\varnothing)_{b\in B} \right). No strict preference comparison is known on either side. It would also be useful to clarify whether agents within a block are genuinely indifferent or whether their relative preferences are simply unknown.

    • Lines 222-240 throw around terms that haven’t been defined yet. Lines 222-228 uses terms that are only referred to later in section 4.

    • Line 220 is inconsistent with the notation used earlier in, e.g., lines 202-203. Line 237 also contains a weird notation: the sentence says “denote each rotation as”, but then why does a rotation appear inside curly brackets? They seem redundant. Also, “associated to” should be “associated with”. In line 239, it is already weird to use L\\{\mathcal{L}\\} to denote the set of all such lattices. I would simply use LL. There are other weird notations.

    • The formulation of the feedback model in line 312-322 is really informal and non-conventional. The distinction between stochastic rewards, realized outcomes and latent preference parameters is unclear. The Bradley-Terry model often defines pairwise comparison probabilities via latent scores associated with alternatives, but here the formulation compares outcomes observed at different time steps. The authors should clarify whether preferences are defined over partners or realized outcomes and formally define how pairwise feedback is generated and observed.

  3. The non-novelty in using Bradely-Terry is not properly acknowledged here. The authors must clarify how their Bradley-Terry feedback model differs from the Plackett-Luce-based relative feedback considered by Kong et al. (2026), given that Bradley-Terry is the pairwise special case of Plackett-Luce. So the novelty not only diminishes, but the paper does not properly attribute the approach to prior work.

  4. Given the above issues, I chose to also try running the submitted code. I focused on the files experiment.py and experiment_preflid.py in the main directory, since the README files says that the main experiments should be run using experiment.py (which seems to run the experiments for P2ETG). It seems that experiment_preflid.py is supposed to be for PrefLID. However, I observed the critical issues below, which question whether the empirical results reported in the paper are actually credible. So it makes me wonder what code was actually used for the experiments, because it seems that the submitted code is not really aligned with what is reported in the submission.

    1. After running experiment.py, the plot for the regret curve is really different from the ones shown in the paper. For N=5,K=5N=5,K=5 and N=8,K=5N=8,K=5, the curves look almost piecewise linear, while in figure 3 they look quite different from that. The title of the plot says “Expected regret with 95% band across seeds”, which is not what is shown in the paper. The titles of each axis are also different.
    2. experiment_preflid.py crashes and I get “ImportError: cannot import name 'SignalProvider' from 'p2etg'”. Even after commenting this import in the file (i.e., deleting “from p2etg import SignalProvider”), the code still crashes because of an undefined variable (NameError: name 'provider' is not defined).

Other Comments

  • In definition 2.3, “denoted as M~\tilde{\mathcal{M}}” is presented awkwardly. The authors actually mean that M~\tilde{\mathcal{M}} denotes the set of stable matchings, so this part should be revised.

  • The paragraph “Existence of Stable Matchings” in section 2 starts with “This is the central solution concept”, but the solution concept is stability not the existence itself. I suspect that “This is the central solution concept” is supposed to refer to Definition 2.3, but having “Existence of Stable Matchings” before this statement makes this unclear.

  • Line 208 is missing brackets in c∈c \in.

  • Line 227: (See Lemma A.1 in §A.1.) is not supposed to be after the dot and it shouldn’t contain a dot inside the brackets. Similar issues appear in other places, like Lemma A.2.

  • The paper sometimes uses §\S for sections and sometimes Sec. Stick to one of them for consistency.

  • Line 220 says ∪iPi(n)(B)=K\cup_i \mathcal{P}_i^{(n)}(B) = K, but it should be ∣∪iPi(n)(B)∣=K|\cup_i \mathcal{P}_i^{(n)}(B)| = K.

  • Line 232: M~∈M\tilde{\mathcal{M}} \in \mathcal{M} should be M~⊆M\tilde{\mathcal{M}} \subseteq \mathcal{M}.

  • Line 255: “effectively the all” → “all”

  • Lines 296-297: “Typically this uses an explore-then-commit (ETC) framework” → “Prior work typically uses an explore-then-commit (ETC) approach”

  • Line 316: A\mathcal{A}-side → AA-side

  • The references are really inconsistent. Certain references contain DOI, ISSN, ISBN, a URL to the paper and so on, while some do not. Some citations have volume and page numbers while some do not. It is preferable to include volume and page numbers for any citation that has those.

  • There are also several inaccuracies in certain citation entries. In the citation entry of the paper “Improved bandits in many-to-one matching markets with incentive compatibility”, the venue is inaccurate. It should be simply “Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence”. Many words should be capitalized but there are not by putting curly brackets around the word inside the .bib file to protect capitalization. For example:

    • “Pac rank elicitation through adaptive sampling of stochastic pairwise preferences” → “{PAC} rank elicitation through adaptive sampling of stochastic pairwise preferences”
    • “Putting gale & shapley to work: Guaranteeing stability through learning” → “Putting {G}ale & {S}hapley to work: Guaranteeing stability through learning”
    • “Routerbench: A benchmark for multi-llm routing system” → “Router{B}ench: A benchmark for multi-{LLM} routing system"
  • Section 1 and Table 1 are missing a few papers, such as:

    • George, A. M., & Dimitrakakis, C. Probably Correct Optimal Stable Matching under Two-Sided Uncertainty. In Forty-Second Annual Conference on Uncertainty in Artificial Intelligence.
    • Mirfakhar, A., Wang, X., Xu, M., Beyhaghi, H., & Hajiesmaili, M. (2026). Bandit Learning in Matching Markets with Interviews.
Questions for authors
  1. Please explain what you by "coarsening" in your definition of partition functions.
  2. I would appreciate clarifications on the issues with the code. Was the submitted code the one used for the experiments in the paper?
Reviewer_nPm8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies online stable matching when agents learn preferences through pairwise comparisons rather than knowing complete rankings in advance. It introduces P2ETG, which achieves sublinear regret, and PrefLID, which uses structural connections called “islands” among preference refinements to guide the search for superstable matchings. PrefLID achieves no-regret performance while avoiding unnecessary comparisons and full preference resolution. Experiments on streaming LLM-to-task routing support the theoretical results.

Critical strengths
  1. The paper is clearly written and well organized, and the method is easy to follow.
  2. A good literature review with a comprehensive comparison table has been done.
Critical weaknesses
  1. There is no connection between figures and content. Figures have not been cited in the content.
  2. Experiments are not comprehensive. Just one experiment (Fig. 3) included that is an ablation study and comparison with other works in literature has not been considered.
  3. The developed solutions have not even been proven mathematically.
Questions for authors
  1. In Table 1, the authors highlight that their work can work under Two-Sided Unknown, Relative Feedback, Partial Prefs., and Stable Structure conditions. Could you please how it works for each one and in which part of the paper each is explained?
  2. On page 7, "Previous work in this area typically defines..." which work?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.