Weighted Games of Best Choice
Author:
- Brant JonesBJBrant Jones
- 1 January 2020
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 34 (1) , 399-414
Abstract
The game of best choice (also known as the secretary problem) is a model for sequential decision making with a long history and many variations. The classical setup assumes that the sequence of candidate rankings is uniformly distributed. Given a statistic on the symmetric group, one can instead weight each permutation according to an exponential function in the statistic. We play the game of best choice on the Ewens and Mallows distributions that are obtained in this way from the number of left-to-right maxima and number of inversions in the permutation, respectively. For each of these, we give the optimal strategy and probability of winning. Moreover, we introduce a general class of permutation statistics that always produces games of best choice whose optimal strategies are positional, which simplifies their analysis considerably.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Avoiding patterns and making the best choiceDiscrete Mathematics, 2019
- Positional strategies in games of best choiceInvolve, a Journal of Mathematics, 2019
- The probability of avoiding consecutive patterns in the Mallows distributionRandom Structures & Algorithms, 2018
- Online auctions and generalized secretary problemsACM SIGecom Exchanges, 2008
- Decision Making: A Golden RuleThe American Mathematical Monthly, 1999
- Extremal processes, secretary problems and the 1/e lawJournal of Applied Probability, 1989
- Who Solved the Secretary Problem?Statistical Science, 1989
- A generalization of the classical secretary problem: dependent arrival sequencesJournal of Applied Probability, 1988
- The Secretary Problem and Its Extensions: A ReviewInternational Statistical Review, 1983
- Recognizing the Maximum of a SequenceJournal of the American Statistical Association, 1966