×

Stable secretaries. (English) Zbl 1423.68605

Summary: In the classical secretary problem, multiple secretaries arrive one at a time to compete for a single position, and the goal is to choose the best secretary to the job while knowing the candidate’s quality only with respect to the preceding candidates. In this paper we define and study a new variant of the secretary problem, in which there are multiple jobs. The applicants are ranked relatively upon arrival as usual, and, in addition, we assume that the jobs are also ranked. The main conceptual novelty in our model is that we evaluate a matching using the notion of blocking pairs from Gale and Shapley’s stable matching theory. Specifically, our goal is to maximize the number of matched jobs (or applicants) that do not take part in a blocking pair. We study the cases where applicants arrive randomly or in adversarial order, and provide upper and lower bounds on the quality of the possible assignment assuming all jobs and applicants are totally ordered. Among other results, we show that when arrival is uniformly random, a constant fraction of the jobs can be satisfied in expectation, or a constant fraction of the applicants, but not a constant fraction of the matched pairs.

MSC:

68W27 Online algorithms; streaming algorithms
60G40 Stopping times; optimal stopping problems; gambling theory
91A60 Probabilistic games; gambling
91B68 Matching models
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abraham, D.J., Biró, P., Manlove, D.: “Almost stable” matchings in the roommates problem. In: Proceedings of Approximation and Online Algorithms, Third International Workshop (WAOA), pp. 1-14 (2005) · Zbl 1125.68425
[2] Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1253-1264 (2011) · Zbl 1375.68221
[3] Ashlagi, I., Burq, M., Jaillet, P., Manshadi, V.H.: On matching and thickness in heterogeneous dynamic markets. In: Proceedings of the 2016 ACM Conference on Economics and Computation (EC), p. 765 (2016) · Zbl 1455.91162
[4] Ashlagi, I., Kanoria, Y., Leshno, J.D.: Unbalanced random matching markets: the stark effect of competition. J. Polit. Econ. 125, 69-98 (2016) · doi:10.1086/689869
[5] Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 434-443 (2007) · Zbl 1302.68133
[6] Baccara, M., Lee, S., Yariv, L.: Optimal dynamic matching. Available at SSRN: http://ssrn.com/abstract=2641670, (2015) · Zbl 1466.91205
[7] Birnbaum, B.E., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80-87 (2008) · doi:10.1145/1360443.1360462
[8] Chen, N., Hoefer, M., Künnemann, M., Lin, C., Miao, P.: Secretary markets with local information. In: Proceedings of Automata, Languages, and Programming—42nd International Colloquium (ICALP), pp. 552-563 (2015) · Zbl 1447.91082
[9] Cheng, C.T.: On the stable matchings that can be reached when the agents go marching in one by one. SIAM J. Discrete Math. 30(4), 2047-2063 (2016) · Zbl 1353.68211 · doi:10.1137/140996690
[10] Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of RANKING for online bipartite matching. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 101-107 (2013) · Zbl 1421.68244
[11] Dinitz, M.: Recent advances on the matroid secretary problem. ACM SIGACT News 44(2), 126-142 (2013) · doi:10.1145/2491533.2491557
[12] Emek, Y., Kutten, S., Wattenhofer, R.: Online matching: haste makes waste! In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 333-344 (2016) · Zbl 1376.68174
[13] Eriksson, K., Häggström, O.: Instability of matchings in decentralized markets with various preference structures. Int. J. Game Theory 36(3), 409-420 (2008) · Zbl 1139.91025 · doi:10.1007/s00182-007-0081-6
[14] Feldman, M., Svensson, O., Zenklusen, R.: A simple o(log log(rank))-competitive algorithm for the matroid secretary problem. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1189-1201 (2015) · Zbl 1372.68285
[15] Ferguson, T.S.: Who solved the secretary problem? Stat. Sci. 4(3), 282-296 (1989) · Zbl 0788.90080 · doi:10.1214/ss/1177012493
[16] Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9-15 (1962) · Zbl 0109.24403 · doi:10.1080/00029890.1962.11989827
[17] Gardner, M.: New Mathematical Diversions from Scientific American, chapter 3, problem 3. Simon and Schuster, 1966. Reprint of the original column published in February 1960 with additional comments
[18] Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 982-991 (2008) · Zbl 1192.68482
[19] Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989) · Zbl 0703.68046
[20] Hassidim, A., Mansour, Y., Vardi, S.: Local computation mechanism design. ACM Trans. Econ. Comput. 4(4), 21:1-21:24 (2016) · doi:10.1145/2956584
[21] Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing (STOC), pp. 352-358 (1990)
[22] Kesselheim, T., Radke, K., Tönnis, A., Vöcking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: Proceedings of the 21st Annual European Symposium on Algorithms (ESA), pp. 589-600 (2013) · Zbl 1394.68448
[23] Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255-267 (1994) · Zbl 0938.68934 · doi:10.1016/0304-3975(94)90042-6
[24] Korula, N., Pál, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part II, pp. 508-520 (2009) · Zbl 1248.68573
[25] Lachish, O.: O(log log rank) competitive ratio for the matroid secretary problem. In: Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 326-335 (2014)
[26] Ma, J.: On randomized matching mechanisms. Econ. Theory 8(2), 377-381 (1996) · Zbl 0859.90009 · doi:10.1007/BF01211824
[27] Miyazaki, S.: On the advice complexity of online bipartite matching and online stable marriage. Inf. Process. Lett. 114(12), 714-717 (2014) · Zbl 1366.68097 · doi:10.1016/j.ipl.2014.06.013
[28] Naor, J., Wajc, D.: Near-optimum online ad allocation for targeted advertising. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC), pp. 131-148 (2015)
[29] Ostrovsky, R., Rosenbaum, W.: Fast distributed almost stable matchings. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), pp. 101-108 (2015) · Zbl 1333.68283
[30] Roth, A.E.: New physicians: a natural experiment in market organization. Science 250(4987), 1524-1528 (1990) · doi:10.1126/science.2274783
[31] Rubinstein, A.: Beyond matroids: Secretary problem and prophet inequality with general constraints. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing (STOC), pp. 324-332 (2016) · Zbl 1373.68457
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.