论文标题
可依靠代表的晶格，稳定的匹配和选择功能
Affinely representable lattices, stable matchings, and choice functions
论文作者
论文摘要
伯克霍夫（Birkhoff）的代表定理（Birkhoff，1937年）定义了分布晶格的元素与相关Poset的上部集合的家族之间的两次试验。尽管未明确使用，但该结果是在Irving等人的组合算法的骨架上。 （1987年）在大风和沙普利稳定的婚姻模型中最大化线性功能（Gale and Shapley，1962）。在本文中，我们介绍了分布晶格的属性，我们将其称为仿射性，并在有效地解决分布晶格元素上的线性优化问题中表现出作用，并描述了晶格元素的特征载体的凸面。我们将此概念应用于具有与路径无关的配额选择功能的稳定匹配模型，从而为该模型提供了有效的算法和紧凑的多面体描述。据我们所知，该模型从已知相似结果的文献中概括了所有模型，而我们的论文是第一个提出了具有选择功能的稳定匹配算法的有效算法，除了递延接受算法的经典扩展外。
Birkhoff's representation theorem (Birkhoff, 1937) defines a bijection between elements of a distributive lattice and the family of upper sets of an associated poset. Although not used explicitly, this result is at the backbone of the combinatorial algorithm by Irving et al. (1987) for maximizing a linear function over the set of stable matchings in Gale and Shapley's stable marriage model (Gale and Shapley, 1962). In this paper, we introduce a property of distributive lattices, which we term as affine representability, and show its role in efficiently solving linear optimization problems over the elements of a distributive lattice, as well as describing the convex hull of the characteristic vectors of the lattice elements. We apply this concept to the stable matching model with path-independent quota-filling choice functions, thus giving efficient algorithms and a compact polyhedral description for this model. To the best of our knowledge, this model generalizes all models from the literature for which similar results were known, and our paper is the first that proposes efficient algorithms for stable matchings with choice functions, beyond classical extensions of the Deferred Acceptance algorithm.
