Finding a Stable Allocation in Polymatroid Intersection

Satoru Iwata () and Yu Yokoi ()
Additional contact information
Satoru Iwata: Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8656, Japan;
Yu Yokoi: Principles of Informatics Research Division, National Institute of Informatics, Tokyo 101-8430, Japan

Mathematics of Operations Research, 2020, vol. 45, issue 1, 63–85

Abstract: The stable matching (or stable marriage) model of Gale and Shapley [Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.] has been generalized in various directions, such as matroid kernels by Fleiner [Fleiner T (2001) A matroid generalization of the stable matching polytope. Aardal K, Gerards AMH, eds. Proc. 8th Internat. Conf. Integer Programming Combin. Optim., Lecture Notes in Computer Science, vol. 2081 (Springer-Verlag, Berlin), 105–114.] and stable allocations in bipartite networks by Baïou and Balinski [Baïou M, Balinski M (2002) Erratum: The stable allocation (or ordinal transportation) problem. Math. Oper. Res. 27(4):662–680.]. Unifying these generalizations, we introduce the concept of stable allocations in polymatroid intersection. Our framework includes both integer and real variable versions. The integer variable version corresponds to a special case of the discrete concave function model of Eguchi et al. [Eguchi A, Fujishige S, Tamura A (2003) A generalized Gale-Shapley algorithm for a discrete-concave stable-marriage model. Ibaraki T, Katoh N, Ono H, eds. Proc. 14th Internat. Sympos. Algorithms Comput ., Lecture Notes in Computer Science, vol. 2906 (Springer-Verlag, Berlin), 495–504.], who established the existence of a stable allocation by showing that a simple extension of the deferred acceptance algorithm of Gale and Shapley finds a stable allocation in pseudopolynomial time. It has been open to develop a polynomial time algorithm even for our special case. In this paper, we present the first strongly polynomial algorithm for finding a stable allocation in polymatroid intersection. To achieve this, we utilize the augmenting path technique for polymatroid intersection. In each iteration, the algorithm searches for an augmenting path by simulating a chain of proposes and rejects in the deferred acceptance algorithm. The running time of our algorithm is O ( n 3 γ), where n and γ denote the cardinality of the ground set and the time for computing the saturation and exchange capacities, respectively. Moreover, we show that the output of our algorithm is optimal for one side, where this optimality is a generalization of the man optimality in the stable marriage model.

Keywords: stable matching; polymatroid intersection; strongly polynomial algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2018.0976 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:1:p:63-85

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().