[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Stable Secretaries

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. This assumption may be appropriate in some cases (e.g., the taxi dispatch example above), and overly simplistic in other cases. But then again, simplification is a standard tool when coping with problems. Indeed, even in the original secretary problem, we make the dubious simplifying assumption that the compatibility of people to a job can be linearly ordered.

  2. To see why this holds, consider an instance with 2n applicants and 2n jobs and suppose that the algorithm is provided with additional information so that upon arrival of the applicant whose ranking is \(1 \le i \le 2 n\), the algorithm is reported that its ranking is either \(2 \lceil i/2 \rceil - 1\) or \(2 \lceil i/2 \rceil \). In this (clearly easier) case, the algorithm is left with n (independent) binary decisions, hence the problem reduces to correctly guessing the outcome of n (unbiased) coin tosses.

  3. Such services for matching professional companions for the elderly are popular in some countries.

  4. Note that these are absolute numbers, whereas the table shows approximation ratios.

  5. Throughout, the terms weak and strong refer to the preference order \(\succ \) in the natural manner.

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)

  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)

  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)

  4. Ashlagi, I., Kanoria, Y., Leshno, J.D.: Unbalanced random matching markets: the stark effect of competition. J. Polit. Econ. 125, 69–98 (2016)

    Article  Google Scholar 

  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)

  6. Baccara, M., Lee, S., Yariv, L.: Optimal dynamic matching. Available at SSRN: http://ssrn.com/abstract=2641670, (2015)

  7. Birnbaum, B.E., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80–87 (2008)

    Article  Google Scholar 

  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)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  11. Dinitz, M.: Recent advances on the matroid secretary problem. ACM SIGACT News 44(2), 126–142 (2013)

    Article  MathSciNet  Google Scholar 

  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)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  15. Ferguson, T.S.: Who solved the secretary problem? Stat. Sci. 4(3), 282–296 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9–15 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  19. Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)

    MATH  Google Scholar 

  20. Hassidim, A., Mansour, Y., Vardi, S.: Local computation mechanism design. ACM Trans. Econ. Comput. 4(4), 21:1–21:24 (2016)

    Article  MathSciNet  Google Scholar 

  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)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  27. Miyazaki, S.: On the advice complexity of online bipartite matching and online stable marriage. Inf. Process. Lett. 114(12), 714–717 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  30. Roth, A.E.: New physicians: a natural experiment in market organization. Science 250(4987), 1524–1528 (1990)

    Article  Google Scholar 

  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)

Download references

Author information

Authors and Affiliations

  1. Technion, Haifa, Israel

    Yakov Babichenko, Yuval Emek & Rann Smorodinsky

  2. Tel Aviv University, Tel Aviv, Israel

    Michal Feldman & Boaz Patt-Shamir

  3. Bar Ilan University, Ramat Gan, Israel

    Ron Peretz

Authors
  1. Yakov Babichenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuval Emek
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michal Feldman
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Boaz Patt-Shamir
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ron Peretz
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Rann Smorodinsky
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Boaz Patt-Shamir.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Y. Babichenko was supported by the Israel Science Foundation Grant Number 2021296.

The work of Y. Emek was supported in part by an Israeli Science Foundation Grant Number 1016/17 and by grants from the Bernard M. Gordon Center for Systems Engineering and the Center for Security Science and Technology at the Technion.

The work of M. Feldman was partially supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement number 337122.

The work of B. Patt-Shamir was supported in part by the Israel Science Foundation Grant Number 1444/14.

R. Smorodinsky was supported by GIF research Grant No. I-1419-118.4/2017, Technion VPR grants, the Bernard M. Gordon Center for Systems Engineering at the Technion, and the TASP Center at the Technion.

Appendices

Appendix

Additional Proofs

Proof of Observation 2.6

Fix \(q = \lceil k/\ell \rceil \) and observe that for every \(r \le \ell \), we have

$$\begin{aligned} \Pr (R > r) \, = \, \frac{k - q}{k} \cdot \frac{k - q - 1}{k - 1} \cdots \frac{k - q - (r - 1)}{k - (r - 1)} \, . \end{aligned}$$

It follows that

$$\begin{aligned} \Pr (R > r) \, \le \, \frac{k - k/\ell }{k} \cdot \frac{k - k/\ell - 1}{k - 1} \cdots \frac{k - k/ \ell - (r - 1)}{k - (r - 1)} \, \le \, \left( 1 - \frac{1}{\ell } \right) ^{r} \, < \, e^{- r/\ell } \end{aligned}$$

and

$$\begin{aligned} \Pr (R> r) \, \ge \, \frac{k - k/\ell - 1}{k} \cdot \frac{k - k/ \ell - 2}{k - 1} \cdots \frac{k - k/\ell - r}{k - (r - 1)} \, > \, \left( 1 - \frac{k/\ell + 1}{k - r} \right) ^{r} \, . \end{aligned}$$

By taking \(c \ge 3\) so that \(r \le \ell \le k/3\), we ensure that

$$\begin{aligned} \ell \le k - 2 r \, \Longleftrightarrow \, k + \ell \le 2 k - 2 r \, \Longleftrightarrow \, \frac{k/\ell + 1}{k - r} \le \frac{2}{\ell } \, , \end{aligned}$$

thus

$$\begin{aligned} \Pr (R> r) \,> \, \left( 1 - \frac{2}{\ell } \right) ^{r} \, > \, e^{-4 r/\ell } \, , \end{aligned}$$

where the second transition follows by taking \(c \ge 2.54\) so that \(2/\ell \le 0.79\). Therefore,

$$\begin{aligned} \Pr (\ell /5 < R \le \ell ) \, = \, \Pr (R> \ell /5) - \Pr (R> \ell ) \, > \, e^{-4/5} - e^{-1} \end{aligned}$$

which establishes the assertion as \(e^{-4/5} - e^{-1} \approx 1/12.28\). \(\square \)

Proof of Observation 3.4

Recall the classical secretary problem in which \(\mathtt {DM}\) has to stop upon the arrival of some x and the objective is to maximize the probability that x is the most preferred boy. The optimal strategy in the secretary problem is to wait until time \(k\approx \tfrac{1}{e} n\), and then stop upon the first arrival of a boy who is more preferred than all of the previous boys. The probability of success converges to \(\tfrac{1}{e}\), as n grows.

From the solution to the secretary problem we device a matching strategy as follows: in the first \(k=\lfloor \tfrac{1}{e} n\rfloor \) steps, match the boys with arbitrary girls who are neither the most preferred nor the least preferred girl. Continue in the same manner while reserving the most and least preferred girls for the first arrivals of boys who are either more preferred or less preferred than all previous boys. Upon the first arrival of a boy x who is more preferred than all previous boys, match x with the most preferred girl. Similarly, match the first boy who is less preferred than all previous boys with the least preferred girl. At times \(n-1\) and n match the arriving boys arbitrarily.

In any matching in which the most (resp. least) preferred boy and girl are matched together, they form a satisfied pair; therefore, by the guarantee of the secretary problem solution and the additivity of expectation, the proposed algorithm guarantees an expected number of \(\frac{2}{e} -o(1)\) satisfied pairs. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Babichenko, Y., Emek, Y., Feldman, M. et al. Stable Secretaries. Algorithmica 81, 3136–3161 (2019). https://doi.org/10.1007/s00453-019-00569-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-019-00569-6

Keywords

Search

Navigation