Affinely representable lattices, stable matchings, and choice functions
Affinely representable lattices, stable matchings, and choice functions
复制标题
仿射可表示格、稳定匹配和选择函数
DOI：
10.1007/s10107-022-01838-z
复制
发表时间：
2023
影响因子：
2.7
通讯作者：
Zhang, Xuan
中科院分区：
文献类型：
--
作者：
Faenza, Yuri;Zhang, Xuan
Birkhoff的表示定理（Birkhoff，杜克数学J 3（3）：443-454，1937）定义了分配格的元素与相关联的偏序集的上集族之间的双射。虽然没有明确地使用，但这个结果是欧文等人（J ACM 34（3）：532-543，1987）的组合算法的基础，用于在Gale和Shapley的稳定婚姻模型（Gale和Shapley，Am Math Monthly 69（1）：9-15，1962）中的稳定匹配集合上最大化线性函数。在本文中，我们介绍了分配格的性质，我们称之为仿射表示，并显示其作用，有效地解决线性优化问题的分配格的元素，以及描述凸船体的特征向量的格元素。我们将这一概念应用到具有路径无关的配额填充选择函数的稳定匹配模型中，从而给出了该模型的有效算法和一个紧凑的多面体描述。据我们所知，这个模型概括了所有那些类似的结果是已知的，我们的论文是第一个提出有效的算法，稳定的匹配与选择功能，超越经典的延期接受算法的扩展。
Birkhoff’s representation theorem (Birkhoff, Duke Math J 3(3):443–454, 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. (J ACM 34(3):532-543, 1987) for maximizing a linear function over the set of stable matchings in Gale and Shapley’s stable marriage model (Gale and Shapley, Am Math Monthly 69(1):9–15 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 those 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.
登录
查看更多内容
DOI：
10.1145/3350755.3400235
发表时间：
2020
期刊：
Symposium on Parallel Algorithms and Architectures
影响因子：
--
作者：
Garg, Vijay K.
通讯作者：
Garg, Vijay K.
影响因子：
6.8
作者：
AIZERMAN, MA;MALISHEVSKI, AV
通讯作者：
MALISHEVSKI, AV
影响因子：
1.1
作者：
Ba誰ou, M;Balinski, M
通讯作者：
Balinski, M
稳定的接纳多面体
影响因子：
2.7
作者：
Mourad Baïou;M. Balinski
通讯作者：
M. Balinski
DOI：
10.2139/ssrn.2189706
发表时间：
2014
期刊：
Public Choice: Analysis of Collective Decision-Making eJournal
影响因子：
--
作者：
F. Echenique;M. B. Yenmez
通讯作者：
M. B. Yenmez