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

Competition and Recall in Selection Problems

  • Research
  • Published:
Dynamic Games and Applications Aims and scope Submit manuscript

A Correction to this article was published on 23 October 2024

This article has been updated

Abstract

We extend the prophet inequality problem to a competitive setting. At every period, a new realization of a random variable with a known distribution arrives, which is publicly observed. Then, two players simultaneously decide whether to pick an available value or to pass and wait until the next period (ties are broken uniformly at random). As soon as a player gets a value, he leaves the market and his payoff is the value of this realization. In the first variant, namely the “no recall” case, the agents can only bid at each period for the current value. In a second variant, the “full recall” case, the agents can also bid for any of the previous realizations which has not been already selected. For each variant, we study the subgame-perfect Nash equilibrium payoffs of the corresponding game. More specifically, we give a full characterization in the full recall case and show in particular that the expected payoffs of the players at any equilibrium are always equal, whereas in the no recall case the set of equilibrium payoffs typically has full dimension. Regarding the welfare at equilibrium, surprisingly the best equilibrium payoff a player can have may be strictly higher in the no recall case. However, the sum of equilibrium payoffs is weakly larger when the players have full recall. Finally, we show that in the case of 2 arrivals and arbitrary distributions, the prices of Anarchy and Stability in the no recall case are at most 4/3, and this bound is tight.

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
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Data Availability

This declaration is not applicable to this article.

Change history

Notes

  1. We assume that the support of F is contained in [0, 1] to not overload the notation, but the results can be easily extended to the general case.

  2. Precisely, it corresponds to case 2 in the analysis of the game described in Fig. 9, see the proof of Theorem 1

  3. Precisely, it corresponds to case 3 in the analysis of the game described in Fig. 10, see the proof of Theorem 3

References

  1. Abdelaziz FB, Krichen S (2007) Optimal stopping problems by two or more decision makers: a survey. Comput Manag Sci 4(2):89–111

    Article  MathSciNet  Google Scholar 

  2. Aubin JP, Frankowska H (2009) Set-valued analysis. Springer

    Book  Google Scholar 

  3. Baston V, Garnaev A (2005) Competition for staff between two departments. Game Theory Appl 10:13–20

    MathSciNet  Google Scholar 

  4. Chawla S, Hartline JD, Malec DL, et al (2010) Multi-parameter mechanism design and sequential posted pricing. In: Proceedings of the forty-second ACM symposium on theory of computing, pp 311–320

  5. Correa J, Foncea P, Hoeksma R, et al (2017) Posted price mechanisms for a random stream of customers. In: Proceedings of the 2017 ACM conference on economics and computation, pp 169–186

  6. Correa J, Foncea P, Pizarro D et al (2019) From pricing to prophets, and back! Oper Res Lett 47(1):25–29

    Article  MathSciNet  Google Scholar 

  7. Ezra T, Feldman M, Kupfer R (2021) On a competitive secretary problem with deferred selections. In: Proceedings of the thirtieth international joint conference on artificial intelligence, IJCAI 2021, Virtual Event/Montreal, Canada, 19–27 August 2021, pp 175–181

  8. Ezra T, Feldman M, Kupfer R (2021) Prophet inequality with competing agents. In: International symposium on algorithmic game theory, Springer, pp 112–123

  9. Ferguson TS (1989) Who solved the secretary problem? Stat Sci 4(3):282–289

    MathSciNet  Google Scholar 

  10. Freeman P (1983) The secretary problem and its extensions: a review. Int. Stat. Rev. 51(2):189–206

    Article  MathSciNet  Google Scholar 

  11. Fudenberg D, Tirole J (1991) Game theory, vol 393, No. 12. MIT Press, Cambridge

  12. Garnaev AY (2006) A game-theoretical model of competition for staff between two departments, vol 71. Banach Center Publications, pp 137–145

    Google Scholar 

  13. Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J Am Stat Assoc 61(313):35–73

    Article  MathSciNet  Google Scholar 

  14. Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. In: AAAI, pp 58–65

  15. Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of IID random variables. Ann Probab 10:336–345

    Article  MathSciNet  Google Scholar 

  16. Immorlica N, Kleinberg R, Mahdian M (2006) Secretary problems with competing employers. In: International workshop on internet and network economics. Springer, pp 389–400

  17. Karlin A, Lei E (2015) On a competitive secretary problem. In: Twenty-ninth AAAI conference on artificial intelligence

  18. Kertz RP (1986) Stop rule and supremum expectations of IID random variables: a complete comparison by conjugate duality. J Multivariate Anal 19(1):88–112

    Article  MathSciNet  Google Scholar 

  19. Kesselheim T, Psomas A, Vardi S (2023) On hiring secretaries with stochastic departures. Oper Res. Articles in Advance. https://doi.org/10.1287/opre.2023.2476

  20. Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. Probab Banach spaces 4:197–266

    MathSciNet  Google Scholar 

  21. Lindley DV (1961) Dynamic programming and decision theory. J R Stat Soc Ser C (Appl Stat) 10(1):39–51

    MathSciNet  Google Scholar 

  22. Mazalov VV, Banin MV (2003) N-person best-choice game with voting. Game Theory Appl 9:45–53

    MathSciNet  Google Scholar 

  23. Radzik T, Szajowski K (1990) Sequential games with random priority. Seq Anal 9(4):361–377

    Article  MathSciNet  Google Scholar 

  24. Ramsey DM, Szajowski K (2006) Correlated equilibria in competitive staff selection problem, vol 71. Banach Center Publications, pp 253–265

    Google Scholar 

  25. Roughgarden T, Tardos É (2002) How bad is selfish routing? J ACM 49(2):236–259

    Article  MathSciNet  Google Scholar 

  26. Sakaguchi M (2005) Optimal stopping games where players have weighted privilege. In: Nowak AS, Szajowski K (eds) Advances in dynamic games. Annals of the International Society of Dynamic Games. Birkhäuser, Boston, pp 285–294

    Chapter  Google Scholar 

  27. Sakaguchi M, Mazalov VV (2004) A non-zero-sum no-information best-choice game. Math Methods Oper Res 60:437–451

    Article  MathSciNet  Google Scholar 

  28. Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann Probab 12:1213–1216

  29. Sweet T (1994) Optimizing a single uncertain selection by recall of observations. J Appl Probab 31(3):660–672

    Article  MathSciNet  Google Scholar 

  30. Yang MC (1974) Recognizing the maximum of a random sequence based on relative rank with backward solicitation. J Appl Probab 11(3):504–512

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors are grateful to Victor Verdugo and the two anonymous referees for their input that helped us improve the paper.

Funding

The authors gratefully acknowledge funding from ANITI ANR-3IA Artificial and Natural Intelligence Toulouse Institute, grant ANR-19-PI3A-0004, and from the ANR under the Investments for the Future program, grant ANR-17-EURE- 0010. J. Renault also acknowledges the support of ANR MaSDOL-19-CE23-0017-01. One page abstract of this work appeared in SAGT 2022.

Author information

Authors and Affiliations

  1. Toulouse School of Economics, University of Toulouse Capitole, Toulouse, France

    Fabien Gensbittel & Jérôme Renault

  2. Instituto de Ciencias de la Ingeniería, Universidad de O’Higgins, Rancagua, Chile

    Dana Pizarro

Authors
  1. Fabien Gensbittel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dana Pizarro
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jérôme Renault
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed equally to this work.

Corresponding author

Correspondence to Dana Pizarro.

Ethics declarations

Conflict of interest

The authors have no competing interests to declare.

Ethical Approval

Ethical approval not applicable to this article.

Additional information

Publisher's Note

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

The original version of the article was revised: Given and Family name of 1st and 2nd authors were incorrect. It has been corrected.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gensbittel, F., Pizarro, D. & Renault, J. Competition and Recall in Selection Problems. Dyn Games Appl 14, 806–845 (2024). https://doi.org/10.1007/s13235-023-00539-2

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13235-023-00539-2

Keywords

Search

Navigation