IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v45y2020i1p323-352.html
   My bibliography  Save this article

Hiring Secretaries over Time: The Benefit of Concurrent Employment

Author

Listed:
  • Yann Disser

    (Graduate School of Computational Engineering, Technical University of Darmstadt, Darmstadt 64293, Germany;)

  • John Fearnley

    (Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom;)

  • Martin Gairing

    (Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom;)

  • Oliver Göbel

    (Department of Computer Science, RWTH Aachen University, Aachen 52062, Germany;)

  • Max Klimm

    (School of Business and Economics, Humboldt University of Berlin, Berlin 10099, Germany;)

  • Daniel Schmand

    (Department of Computer Science, Goethe University Frankfurt, Frankfurt am Main 60054, Germany;)

  • Alexander Skopalik

    (Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede 7500 AE, Netherlands;)

  • Andreas Tönnis

    (Institute of Computer Science, University of Bonn, Bonn 53115, Germany)

Abstract

We consider a stochastic online problem where n applicants arrive over time, one per time step. Upon the arrival of each applicant, their cost per time step is revealed, and we have to fix the duration of employment, starting immediately. This decision is irrevocable; that is, we can neither extend a contract nor dismiss a candidate once hired. In every time step, at least one candidate needs to be under contract, and our goal is to minimize the total hiring cost, which is the sum of the applicants’ costs multiplied with their respective employment durations. We provide a competitive online algorithm for the case that the applicants’ costs are drawn independently from a known distribution. Specifically, the algorithm achieves a competitive ratio of 2.965 for the case of uniform distributions. For this case, we give an analytical lower bound of 2 and a computational lower bound of 2.148. We then adapt our algorithm to stay competitive even in settings with one or more of the following restrictions: (i) at most two applicants can be hired concurrently; (ii) the distribution of the applicants’ costs is unknown; (iii) the total number n of time steps is unknown. On the other hand, we show that concurrent employment is a necessary feature of competitive algorithms by proving that no algorithm has a competitive ratio better than Ω ( n / l o g n ) if concurrent employment is forbidden.

Suggested Citation

  • Yann Disser & John Fearnley & Martin Gairing & Oliver Göbel & Max Klimm & Daniel Schmand & Alexander Skopalik & Andreas Tönnis, 2020. "Hiring Secretaries over Time: The Benefit of Concurrent Employment," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 323-352, February.
    • Handle: RePEc:inm:ormoor:v:45:y:2020:i:1:p:323-352
    DOI: 10.1287/moor.2019.0993
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2019.0993
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2019.0993?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Richard Bellman, 1954. "Some Applications of the Theory of Dynamic Programming---A Review," Operations Research, INFORMS, vol. 2(3), pages 275-288, August.
    2. Shuchi Chawla & Jason Hartline & David Malec & Balasubramanian Sivan, 2010. "Sequential Posted Pricing and Multi-parameter Mechanism Design," Discussion Papers 1486, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    3. Richard Bellman, 1954. "On some applications of the theory of dynamic programming to logistics," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(2), pages 141-153, June.
    4. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    5. Kennedy, D. P., 1987. "Prophet-type inequalities for multi-choice optimal stopping," Stochastic Processes and their Applications, Elsevier, vol. 24(1), pages 77-88, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kleinberg, Robert & Weinberg, S. Matthew, 2019. "Matroid prophet inequalities and applications to multi-dimensional mechanism design," Games and Economic Behavior, Elsevier, vol. 113(C), pages 97-115.
    2. Nima Anari & Rad Niazadeh & Amin Saberi & Ali Shameli, 2018. "Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection," Papers 1807.05477, arXiv.org, revised Mar 2024.
    3. Xiaoyue Li & John M. Mulvey, 2023. "Optimal Portfolio Execution in a Regime-switching Market with Non-linear Impact Costs: Combining Dynamic Program and Neural Network," Papers 2306.08809, arXiv.org.
    4. Yiding Feng & Jason Hartline & Yingkai Li, 2020. "Simple Mechanisms for Agents with Non-linear Utilities," Papers 2003.00545, arXiv.org, revised Oct 2022.
    5. Mahmoud Mahfouz & Angelos Filos & Cyrine Chtourou & Joshua Lockhart & Samuel Assefa & Manuela Veloso & Danilo Mandic & Tucker Balch, 2019. "On the Importance of Opponent Modeling in Auction Markets," Papers 1911.12816, arXiv.org.
    6. Marek Pycia & Peter Troyan, 2021. "A theory of simplicity in games and mechanism design," ECON - Working Papers 393, Department of Economics - University of Zurich.
    7. Boute, Robert N. & Gijsbrechts, Joren & van Jaarsveld, Willem & Vanvuchelen, Nathalie, 2022. "Deep reinforcement learning for inventory control: A roadmap," European Journal of Operational Research, Elsevier, vol. 298(2), pages 401-412.
    8. Dawei Chen & Fangxu Mo & Ye Chen & Jun Zhang & Xinyu You, 2022. "Optimization of Ramp Locations along Freeways: A Dynamic Programming Approach," Sustainability, MDPI, vol. 14(15), pages 1-13, August.
    9. Alaei, Saeed & Hartline, Jason & Niazadeh, Rad & Pountourakis, Emmanouil & Yuan, Yang, 2019. "Optimal auctions vs. anonymous pricing," Games and Economic Behavior, Elsevier, vol. 118(C), pages 494-510.
    10. Chawla, Shuchi & Hartline, Jason D. & Sivan, Balasubramanian, 2019. "Optimal crowdsourcing contests," Games and Economic Behavior, Elsevier, vol. 113(C), pages 80-96.
    11. Harrold, Daniel J.B. & Cao, Jun & Fan, Zhong, 2022. "Data-driven battery operation for energy arbitrage using rainbow deep reinforcement learning," Energy, Elsevier, vol. 238(PC).
    12. Bartłomiej Kocot & Paweł Czarnul & Jerzy Proficz, 2023. "Energy-Aware Scheduling for High-Performance Computing Systems: A Survey," Energies, MDPI, vol. 16(2), pages 1-28, January.
    13. Wadi Khalid Anuar & Lai Soon Lee & Hsin-Vonn Seow & Stefan Pickl, 2021. "A Multi-Depot Vehicle Routing Problem with Stochastic Road Capacity and Reduced Two-Stage Stochastic Integer Linear Programming Models for Rollout Algorithm," Mathematics, MDPI, vol. 9(13), pages 1-44, July.
    14. Debasis Mishra & Kolagani Paramahamsa, 2022. "Selling to a principal and a budget-constrained agent," Discussion Papers 22-02, Indian Statistical Institute, Delhi.
    15. Sundararajan, Mukund & Yan, Qiqi, 2020. "Robust mechanisms for risk-averse sellers," Games and Economic Behavior, Elsevier, vol. 124(C), pages 644-658.
    16. L. Elisa Celis & Gregory Lewis & Markus Mobius & Hamid Nazerzadeh, 2011. "Buy-it-now or Take-a-chance: A New Pricing Mechanism for Online Advertising," Working Papers 11-21, NET Institute, revised Nov 2011.
    17. Peter Schober & Julian Valentin & Dirk Pflüger, 2022. "Solving High-Dimensional Dynamic Portfolio Choice Models with Hierarchical B-Splines on Sparse Grids," Computational Economics, Springer;Society for Computational Economics, vol. 59(1), pages 185-224, January.
    18. Matthias Breuer & David Windisch, 2019. "Investment Dynamics and Earnings‐Return Properties: A Structural Approach," Journal of Accounting Research, Wiley Blackwell, vol. 57(3), pages 639-674, June.
    19. Briest, Patrick & Chawla, Shuchi & Kleinberg, Robert & Weinberg, S. Matthew, 2015. "Pricing lotteries," Journal of Economic Theory, Elsevier, vol. 156(C), pages 144-174.
    20. Hart, Sergiu & Nisan, Noam, 2019. "Selling multiple correlated goods: Revenue maximization and menu-size complexity," Journal of Economic Theory, Elsevier, vol. 183(C), pages 991-1029.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:45:y:2020:i:1:p:323-352. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.