Weighted games of best choice

DOI10.1137/19M1266587MaRDI QIDQ5215902zbMATHFDO

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

secretary problempermutation statisticspositional strategy

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Decision theory for games (91A35) Stopping times; optimal stopping problems; gambling theory (60G40) 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

• scientific article; zbMATH DE number 783365 (Why is no real title available?)
• 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
• Logarithmic combinatorial structures: A probabilistic approach
• NIST handbook of mathematical functions
• Positional strategies in games of best choice
• Strategies in the secretary problem
• The Secretary Problem and Its Extensions: A Review
• The probability of avoiding consecutive patterns in the Mallows distribution
• Who solved the secretary problem

Cited in

(11)

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

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)