Weighted games of best choice

DOI10.1137/19M1266587MaRDI QIDQ5215902zbMATH OpenFDO

Authors Brant C. Jones

Publication date 13 February 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.10163

zbMATH Keywords

permutation statisticspositional strategysecretary problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40) Decision theory for games (91A35) Combinatorial games (91A46) Probabilistic games; gambling (91A60)

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 are 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.

Recommendations

• Strategy-indifferent games of best choice
• Positional strategies in games of best choice
• Avoiding patterns and making the best choice
• Opportunity costs in the game of best choice
• Optimal stopping games under winning probability maximization and player's weighted privilege

Cites work

• A generalization of the classical secretary problem: dependent arrival sequences
• Avoiding patterns and making the best choice
• Decision Making: A Golden Rule
• Extremal processes, secretary problems and the 1/e law
• scientific article; zbMATH DE number 783365 (Why is no real title available?)
• Logarithmic combinatorial structures: A probabilistic approach
• NIST handbook of mathematical functions
• Positional strategies in games of best choice
• Strategies in the secretary problem
• The probability of avoiding consecutive patterns in the Mallows distribution
• The Secretary Problem and Its Extensions: A Review
• Who solved the secretary problem

Cited in

(12)

• Choosing from a weighted tournament
• Avoiding patterns and making the best choice
• Finding the second-best candidate under the Mallows model
• Strategy-indifferent games of best choice
• On weighted balls-into-bins games
• Positional strategies in games of best choice
• Weighted Matching in Chess Tournaments
• scientific article; zbMATH DE number 7533361 (Why is no real title available?)
• Query-based selection of optimal candidates under the Mallows model
• Optimal stopping methodology for the secretary problem with random queries
• Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings
• Classical patterns in Mallows permutations

Describes a project that uses

Uses Software

• DLMF

This page was built for publication: Weighted games of best choice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215902)