pith. sign in

arxiv: 2504.17916 · v3 · submitted 2025-04-24 · 💻 cs.DM · econ.TH

All finite lattices are stable matching lattices

Christopher En , Yuri Faenza This is my paper

Pith reviewed 2026-05-22 18:47 UTC · model grok-4.3

classification 💻 cs.DM econ.TH
keywords stable matchingsfinite latticespath-independent choice functionsdistributive closurejoin constraintsrepresentation of latticesNP-hard optimization
0
0 comments X

The pith

Every finite lattice can be realized as the lattice of stable matchings using path-independent choice functions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that every finite lattice arises as the lattice of stable matchings when agents use path-independent choice functions. This extends previous results limited to distributive lattices and answers an open question from 1988. The authors introduce a partial representation for lattices, the distributive closure, and join constraints to construct the required market. These tools also allow proving that finding the minimum cost stable matching is NP-hard under the same assumptions. The result means stable matching theory can now represent any finite lattice structure.

Core claim

We show that all finite lattices, including non-distributive lattices, arise as stable matching lattices when all agents have path-independent choice functions. This result answers an open question of Blair. In the process, we introduce new tools to reason on general lattices for optimization purposes: the partial representation of a lattice, which partially extends Birkhoff's representation theorem to non-distributive lattices; the distributive closure of a lattice, which gives such a partial representation; and join constraints, which can be added to the distributive closure to obtain a representation for the original lattice. Then, we use these techniques to show that the minimum cost 0-1

What carries the argument

Join constraints added to the distributive closure of the target lattice, which are used to define path-independent choice functions that enforce the original join and meet operations in the stable matching market.

If this is right

  • Stable matching lattices are not restricted to distributive lattices.
  • The minimum cost stable matching problem is NP-hard even when all choice functions are path-independent.
  • General finite lattices can be studied and optimized through stable matching markets.
  • The partial representation and distributive closure provide new tools for lattice-based optimization problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Stable matching markets could serve as a general-purpose model for optimization over arbitrary finite lattices.
  • The link to antimatroid theory may allow importing greedy algorithms from choice function theory into matching problems.
  • The construction technique might extend to represent other combinatorial structures as stable outcomes.

Load-bearing premise

Path-independent choice functions can be constructed for any finite lattice to enforce its specific join and meet operations through the join constraints on its distributive closure.

What would settle it

A specific finite lattice together with a proof that no market of agents with path-independent choice functions has a stable matching lattice isomorphic to it.

Figures

Figures reproduced from arXiv: 2504.17916 by Christopher En, Yuri Faenza.

Figure 1
Figure 1. Figure 1: Hasse diagrams of a non-distributive lattice ( [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The functions connecting the non-distributive lattice ( [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An antimatroid, and its path poset. The nodes correspon [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The stable matching lattice, and poset of rotations. [PITH_FULL_IMAGE:figures/full_fig_p022_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The stable matching lattice S ′′ after applying the join constraint augmentation corresponding to (α, β). We can now examine the lattice of stable matchings S ′′ in the instance post-augmentation. The stable matchings are given by µ ′′ 1 = {(f1, w1),(f1, w0),(f2, w2),(f2, w0),(f3, w3),(f3, w0),(f4, w4),(f4, w0), (f5, w5),(f5, w0),(f6, w6),(f7, w7),(f0, w′′ 3 ),(f0, w′′ 4 ),(f0, w′′ 6 ),(f0, w′′ 7 )} µ ′′ 2… view at source ↗
read the original abstract

We show that all finite lattices, including non-distributive lattices, arise as stable matching lattices when all agents have path-independent choice functions. This result answers an open question of Blair~\cite{blair1988lattice}. In the process, we introduce new tools to reason on general lattices for optimization purposes: the \emph{partial representation} of a lattice, which partially extends Birkhoff's representation theorem to non-distributive lattices; the \emph{distributive closure} of a lattice, which gives such a partial representation; and \emph{join constraints}, which can be added to the distributive closure to obtain a representation for the original lattice. Then, we use these techniques to show that the minimum cost stable matching problem under the same standard assumptions on choice functions is NP-hard, by establishing a connection with antimatroid theory.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that every finite lattice, including non-distributive ones, can be realized as the lattice of stable matchings in a two-sided market in which all agents have path-independent choice functions. This resolves an open question of Blair (1988). The proof proceeds by first forming the distributive closure of the target lattice (which admits a Birkhoff-style representation) and then imposing join constraints, defined via forbidden sub-configurations, to recover the original lattice operations. The paper also establishes NP-hardness of the minimum-cost stable matching problem under the same choice-function assumptions by reduction to antimatroid theory.

Significance. If the central representation theorem holds, the result gives a complete characterization of stable-matching lattices under path-independent choice functions, extending earlier work limited to distributive lattices. The auxiliary notions of partial representation, distributive closure, and join constraints supply new tools for optimization over general lattices. The NP-hardness corollary is a concrete computational consequence with potential implications for algorithmic matching theory.

major comments (2)
  1. § on join constraints and the reduction from lattice to choice-function market: the claim that join constraints can be realized by path-independent choice functions while producing exactly the target lattice (no extraneous stable matchings, no proper quotient) is load-bearing. The manuscript must supply an explicit argument that the forbidden-subconfiguration constraints preserve path-independence and do not introduce new fixed points of the choice operators; without this, the representation may fail for some non-distributive lattices.
  2. Proof of the main representation theorem: the construction first takes the distributive closure and then adds join constraints. It is necessary to verify that the resulting stable-matching poset is order-isomorphic to the input lattice rather than a proper extension or quotient. A concrete check for a small non-distributive lattice (e.g., M3 or N5) would make the argument verifiable.
minor comments (2)
  1. Abstract: the phrase 'path-independent choice functions' is used without a one-sentence reminder of its relation to the standard substitutable-choice assumption; a brief clarification would aid readers.
  2. Notation: the symbols for the partial representation and distributive closure are introduced without an explicit comparison table to Birkhoff's representation; adding such a table would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We agree that the exposition of the join constraints and the verification of the representation theorem can be strengthened with additional explicit arguments and examples. We address each major comment below and will incorporate the suggested revisions.

read point-by-point responses

  1. Referee: § on join constraints and the reduction from lattice to choice-function market: the claim that join constraints can be realized by path-independent choice functions while producing exactly the target lattice (no extraneous stable matchings, no proper quotient) is load-bearing. The manuscript must supply an explicit argument that the forbidden-subconfiguration constraints preserve path-independence and do not introduce new fixed points of the choice operators; without this, the representation may fail for some non-distributive lattices.

    Authors: We agree that an explicit argument is needed for full rigor. In the revised manuscript we will add a dedicated lemma proving that the forbidden-subconfiguration constraints preserve path-independence: each constraint is defined so that the choice operator on any path remains unchanged outside the forbidden configurations, satisfying the path-independence axiom directly. We further show that no new fixed points are introduced because any candidate matching violating a join constraint is eliminated by the choice functions, while the distributive closure ensures that all original lattice elements remain as stable matchings. This construction works uniformly for non-distributive lattices. revision: yes

  2. Referee: Proof of the main representation theorem: the construction first takes the distributive closure and then adds join constraints. It is necessary to verify that the resulting stable-matching poset is order-isomorphic to the input lattice rather than a proper extension or quotient. A concrete check for a small non-distributive lattice (e.g., M3 or N5) would make the argument verifiable.

    Authors: We thank the referee for this helpful suggestion. To make the isomorphism verifiable, the revision will include a new subsection with an explicit worked example for the lattice M3. We will compute its distributive closure, specify the join constraints via the forbidden sub-configurations, define the path-independent choice functions, enumerate the resulting stable matchings, and confirm that the induced poset is order-isomorphic to M3 with no extraneous elements or collapsed relations. The same verification for N5 follows by the same steps and can be sketched or included depending on space. revision: yes

Circularity Check

0 steps flagged

No circularity; construction extends external lattice theory independently

full rationale

The paper constructs a representation of arbitrary finite lattices (including non-distributive ones) as stable matching lattices via the distributive closure of the lattice plus join constraints, building explicitly on Birkhoff's theorem for the distributive case and citing Blair (1988) only for the open question being resolved. The NP-hardness reduction invokes antimatroid theory as an external connection. No equation, definition, or central claim reduces by construction to a fitted parameter, self-citation chain, or renamed input; the proof is self-contained against standard lattice-theoretic benchmarks and does not rely on load-bearing self-references.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 3 invented entities

The proof introduces three new technical objects (partial representation, distributive closure, join constraints) whose existence is asserted rather than derived from prior literature; these function as invented entities needed to bridge arbitrary lattices to choice-function markets.

axioms (2)
  • domain assumption Path-independent choice functions exist for any finite lattice and can be constructed via the distributive closure plus join constraints.
    Invoked to realize the lattice operations as stable matchings; stated as the modeling assumption enabling the representation.
  • standard math Standard lattice axioms (idempotence, commutativity, associativity of join and meet) hold for the target structure.
    Background assumption from lattice theory used throughout the representation construction.
invented entities (3)
  • partial representation of a lattice no independent evidence
    purpose: Extends Birkhoff's representation theorem to non-distributive lattices by mapping to a distributive lattice plus constraints.
    New object introduced to handle non-distributive cases; no independent evidence supplied beyond the construction itself.
  • distributive closure no independent evidence
    purpose: Produces a distributive lattice that partially represents the original lattice.
    Invented intermediate structure used to reduce the general case to the distributive case.
  • join constraints no independent evidence
    purpose: Added to the distributive closure to recover the exact original lattice.
    New mechanism to enforce non-distributive relations; central to the representation but defined within the paper.

pith-pipeline@v0.9.0 · 5660 in / 1501 out tokens · 27561 ms · 2026-05-22T18:47:33.940902+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Given a set T of workers, the new choice function C′′ f1 (T ) for f1 is given by the following process: i

    As an example, we consider f =f1,f 7. Given a set T of workers, the new choice function C′′ f1 (T ) for f1 is given by the following process: i. If w5∈ T , select w5. ii. Else, select T∩{ w1,w 0}. This is equivalent to the preference list P ′′ f1 given by P ′′ f1 = ({w5},{w0,w 1},{w1},{w0}). The new choice function C′′ f7 (T ) for f7 is given by the follo...

    work page

  2. [2]

    if ρ1 and ρ2 occur, then ρ3 and ρ4 occur

    Notice that we can “project” each matching µ ′′ i back to the original instance by taking its intersection µ ′′ i ∩ (F× W ) with the original firms and workers. Then, µ ′′ i∩ (F× W ) = µi, for i∈{ 1, 2, 3, 5, 6, 9, 10}. These are exactly the matchings in the original instance that satisfy the join constraint ( α,β ). In terms of the original target lattice...

    work page

  3. [3]

    That is, one auxiliary worker, and additional copies W ′′ β are added

    W ′′=W ′⊎{ w0}⊎ W ′′ β . That is, one auxiliary worker, and additional copies W ′′ β are added

    work page

  4. [4]

    That is, only one firm is added, and this is auxiliary

    F ′′=F ′∪{ f0}. That is, only one firm is added, and this is auxiliary

    work page

  5. [5]

    24 We now present proofs omitted from the main body, as well as additio nal intermediate lemmas

    For each f∈ F and T⊆ W ′′, C′′ f (T )∩ copy′′(wj )̸=∅ for at most one wj∈ W . 24 We now present proofs omitted from the main body, as well as additio nal intermediate lemmas. We start by showing that the preference lists after the join constra int augmentation satisfy substitutability and consistency. Lemma 47 (Join constraint augmentation satisfies substi...

    work page

  6. [6]

    First, set µ ′′← µ ′

    work page

  7. [7]

    If µ (f )⪯f w, then add ( f,w 0) to µ ′′

    For each f∈ Fα , let w∈ Pf be the unique worker such that ( f,w )∈ ρ− for some ρ∈ Πα (see Proposition 21). If µ (f )⪯f w, then add ( f,w 0) to µ ′′

    work page

  8. [8]

    If α (π (Fα\µ ′′(w0))) = 1, then add to µ ′′: (a) (f0,w 0); 26 (b) (µ (w),w ′′) for each w∈ Wβ and w′′∈ W ′′ β ∩ copy(w)

    work page

  9. [9]

    Our goal is to show that µ ′′ is stable in I ′′, and that ζS ′′(µ ′′) = µ ′

    Else, add ( f0,w ′′) to µ ′′, for each w′′∈ W ′′ β . Our goal is to show that µ ′′ is stable in I ′′, and that ζS ′′(µ ′′) = µ ′. Individual rationality of µ ′′. First we show individual rationality of µ ′′. It is easily verified by inspection that, for a∈ F ′′∪ W ′′\W ′′ β , µ ′′(a) =C′′ a (µ ′′(a)). Now consider w′′ j∈ W ′′ β ∩ copy(wj). Note that either...

    work page

  10. [10]

    We know by Lemma 47 that all agents in I ′′ have substitutable and consistent choice functions

    work page

  11. [11]

    We know by definition of the join constraint augmentation that the agents in F ′′∪ W ′′ can be partitioned into firms Faux⊎ F and workers Waux⊎ Wreg , and the set of regular workers Wreg can be partitioned into sets ⨄ w∈Wcopy(w)

    work page

  12. [12]

    by assumption

    The preference list P ′′ w forw∈ W ′ are unchanged fromP ′ w, which already satisfied 3. by assumption. For agents w′ j ∈ W ′ β , by definition the preference list P ′′ w′ j is also of the form ( f0,f ℓ,f ℓ+1,...,f k), as desired

    work page

  13. [13]

    By definition, for every f∈ F the choice function C′′ f is a standard choice function

    work page

  14. [14]

    C Proofs from Section 5 For the sake of completeness, we reproduce here the proof of Th eorem 36, which appeared in Merckx (2019)

    We know by Lemma 49 that ξS ′′ is an order-embedding, and that the maximal and minimal elements ofS are in the image of ξ. C Proofs from Section 5 For the sake of completeness, we reproduce here the proof of Th eorem 36, which appeared in Merckx (2019). Proof. We reduce from the maximum independent set problem, which is well-kn own to be NP-Hard Karp (200...

    work page 2019