Weighted games of best choice

DOI10.1137/19M1266587zbMATH Open1431.91059arXiv1902.10163MaRDI QIDQ5215902FDOQ5215902

Authors: Brant C. Jones 

Publication date: 13 February 2020

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

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.

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

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

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)

Cites Work

• NIST handbook of mathematical functions
• Logarithmic combinatorial structures: A probabilistic approach
• The Secretary Problem and Its Extensions: A Review
• Who solved the secretary problem
• Title not available (Why is that?)
• Extremal processes, secretary problems and the 1/e law
• Strategies in the secretary problem
• Lannes’ T functor on injective unstable modules and Harish-Chandra restriction
• Positional strategies in games of best choice
• Decision Making: A Golden Rule
• A generalization of the classical secretary problem: dependent arrival sequences
• The probability of avoiding consecutive patterns in the Mallows distribution
• Avoiding patterns and making the best choice

Cited In (9)

• Strategy-indifferent games of best choice
• Query-based selection of optimal candidates under the Mallows model
• Weighted Matching in Chess Tournaments
• 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
• Optimal stopping methodology for the secretary problem with random queries
• Choosing from a weighted tournament
• Title not available (Why is that?)

Uses Software

• Digital Library of Mathematical Functions

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)