Document Open Access Logo

Combinatorial Secretary Problems with Ordinal Information

Authors Martin Hoefer, Bojana Kodric

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.133.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Martin Hoefer
Bojana Kodric

Cite As Get BibTex

Martin Hoefer and Bojana Kodric. Combinatorial Secretary Problems with Ordinal Information. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 133:1-133:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.133

Abstract

The secretary problem is a classic model for online decision making. Recently, combinatorial extensions such as matroid or matching secretary problems have become an important tool to study algorithmic problems in dynamic markets. Here the decision maker must know the numerical value of each arriving element, which can be a demanding informational assumption. In this paper, we initiate the study of combinatorial secretary problems with ordinal information, in which the decision maker only needs to be aware of a preference order consistent with the values of arrived elements. The goal is to design online algorithms with small competitive ratios.

For a variety of combinatorial problems, such as bipartite matching, general packing LPs, and independent set with bounded local independence number, we design new algorithms that obtain constant competitive ratios. 

For the matroid secretary problem, we observe that many existing algorithms for special matroid structures maintain their competitive ratios even in the ordinal model. In these cases, the restriction to ordinal information does not represent any additional obstacle. Moreover, we show that ordinal variants of the submodular matroid secretary problems can be solved using algorithms for the linear versions by extending [Feldman and Zenklusen, 2015]. In contrast, we provide a lower bound of Omega(sqrt(n)/log(n)) for algorithms that are oblivious to the matroid structure, where n is the total number of elements. This contrasts an upper bound of O(log n) in the cardinal model, and it shows that the technique of thresholding is not sufficient for good algorithms in the ordinal model.

Subject Classification

Keywords
  • Secretary Problem
  • Matroid Secretary
  • Ordinal Information
  • Online Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. David Abraham, Robert Irving, Telikepalli Kavitha, and Kurt Mehlhorn. Popular matchings. SIAM J. Comput., 37(4):1030-1045, 2007. Google Scholar
  2. Elliot Anshelevich and Martin Hoefer. Contribution games in networks. Algorithmica, 63(1-2):51-90, 2012. Google Scholar
  3. Elliot Anshelevich and John Postl. Randomized social choice functions under metric preferences. In Proc. 25th Intl. Joint Conf. Artif. Intell. (IJCAI), pages 46-59, 2016. Google Scholar
  4. Elliot Anshelevich and Shreyas Sekar. Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Proc. 13th Conf. Artificial Intelligence (AAAI), pages 390-396, 2016. Google Scholar
  5. Elliot Anshelevich and Shreyas Sekar. Truthful mechanisms for matching and clustering in an ordinal world. In Proc. 12th Conf. Web and Internet Economics (WINE), pages 265-278, 2016. Google Scholar
  6. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Proc. 10th Workshop Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 16-28, 2007. Google Scholar
  7. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Online auctions and generalized secretary problems. SIGecom Exchanges, 7(2), 2008. Google Scholar
  8. Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. 18th Symp. Discrete Algorithms (SODA), pages 434-443, 2007. Google Scholar
  9. MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Morteza Zadimoghaddam. Submodular secretary problem and extensions. ACM Trans. Algorithms, 9(4):32, 2013. Google Scholar
  10. Deeparnab Chakrabarty and Chaitanya Swamy. Welfare maximization and truthfulness in mechanism design with ordinal preferences. In Proc. 5th Symp. Innovations in Theoret. Computer Science (ITCS), pages 105-120, 2014. Google Scholar
  11. Sourav Chakraborty and Oded Lachish. Improved competitive ratio for the matroid secretary problem. In Proc. 23rd Symp. Discrete Algorithms (SODA), pages 1702-1712, 2012. Google Scholar
  12. Ning Chen, Martin Hoefer, Marvin Künnemann, Chengyu Lin, and Peihan Miao. Secretary markets with local information. In Proc. 42nd Intl. Coll. Automata, Languages and Programming (ICALP), volume 2, pages 552-563, 2015. Google Scholar
  13. Nedialko Dimitrov and Greg Plaxton. Competitive weighted matching in transversal matroids. Algorithmica, 62(1-2):333-348, 2012. Google Scholar
  14. Michael Dinitz and Guy Kortsarz. Matroid secretary for regular and decomposable matroids. SIAM J. Comput., 43(5):1807-1830, 2014. Google Scholar
  15. Eugene Dynkin. The optimum choice of the instant for stopping a Markov process. In Sov. Math. Dokl, volume 4, pages 627-629, 1963. Google Scholar
  16. Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. In Proc. 26th Symp. Discrete Algorithms (SODA), pages 1189-1201, 2015. Google Scholar
  17. Moran Feldman and Moshe Tennenholtz. Interviewing secretaries in parallel. In Proc. 13th Conf. Electronic Commerce (EC), pages 550-567, 2012. Google Scholar
  18. Moran Feldman and Rico Zenklusen. The submodular secretary problem goes linear. In Proc. 56th Symp. Foundations of Computer Science (FOCS), pages 486-505, 2015. Google Scholar
  19. Amos Fiat, Ilia Gorelik, Haim Kaplan, and Slava Novgorodov. The temp secretary problem. In Proc. 23rd European Symp. Algorithms (ESA), pages 631-642, 2015. Google Scholar
  20. Marshall Fisher, George Nemhauser, and Laurence Wolsey. An analysis of approximations for maximizing submodular set functions-II. In Polyhedral combinatorics, pages 73-87. Springer, 1978. Google Scholar
  21. Byrn Garrod and Robert Morris. The secretary problem on an unknown poset. Random Struct. Algorithms, 43(4), 2013. Google Scholar
  22. Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Vöcking. Online independent set beyond the worst-case: Secretaries, prophets and periods. In Proc. 41st Intl. Coll. Automata, Languages and Programming (ICALP), volume 2, pages 508-519, 2014. Google Scholar
  23. Martin Hoefer and Bojana Kodric. Combinatorial secretary problems with ordinal information. CoRR, abs/1702.01290, 2017. URL: http://arxiv.org/abs/1702.01290.
  24. Patrick Jaillet, José Soto, and Rico Zenklusen. Advances on matroid secretary problems: Free order model and laminar case. In Proc. 16th Intl. Conf. Integer Programming and Combinatorial Optimization (IPCO), pages 254-265, 2013. Google Scholar
  25. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In Proc. 21st European Symp. Algorithms (ESA), pages 589-600, 2013. Google Scholar
  26. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on online packing LPs in the random-order model. In Proc. 46th Symp. Theory of Computing (STOC), pages 303-312, 2014. Google Scholar
  27. Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proc. 16th Symp. Discrete Algorithms (SODA), pages 630-631, 2005. Google Scholar
  28. Nitish Korula and Martin Pál. Algorithms for secretary problems on graphs and hypergraphs. In Proc. 36th Intl. Coll. Automata, Languages and Programming (ICALP), pages 508-520, 2009. Google Scholar
  29. Ravi Kumar, Silvio Lattanzi, Sergei Vassilvitskii, and Andrea Vattani. Hiring a secretary from a poset. In Proc. 12th Conf. Economics and Computation (EC), 2011. Google Scholar
  30. Oded Lachish. O(log log rank) competitive ratio for the matroid secretary problem. In Proc. 55th Symp. Foundations of Computer Science (FOCS), pages 326-335, 2014. Google Scholar
  31. José Soto. Matroid secretary problem in the random-assignment model. SIAM J. Comput., 42(1):178-211, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact