Strategy-indifferent games of best choice

DOI10.1016/J.DISC.2021.112666MaRDI QIDQ2237240zbMATH OpenOpenAlexFDO

Authors Brant C. Jones, Katelynn Kochalski, Sarah Loeb, Julia C. Walk

Publication date 27 October 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

incentive paradoxpattern avoidancesecretary problem

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Other game-theoretic models (91A40) Decision theory (91B06)

Abstract: The game of best choice (or "secretary problem") is a model for making an irrevocable decision among a fixed number of candidate choices that are presented sequentially in random order, one at a time. Because the classically optimal solution is known to reject an initial sequence of candidates, a paradox emerges from the fact that candidates have an incentive to position themselves immediately after this cutoff which challenges the assumption that candidates arrive in uniformly random order. One way to resolve this is to consider games for which every (reasonable) strategy results in the same probability of success. In this work, we classify these "strategy-indifferent" games of best choice. It turns out that the probability of winning such a game is essentially the reciprocal of the expected number of left-to-right maxima in the full collection of candidate rank orderings. We present some examples of these games based on avoiding permutation patterns of size 3, which involves computing the distribution of left-to-right maxima in each of these pattern classes.

Recommendations

• Positional strategies in games of best choice
• Avoiding patterns and making the best choice
• Weighted games of best choice
• A unified approach to a class of best choice problems with an unknown number of options
• A full-information best-choice game with two stops

Cites work

• Avoiding patterns and making the best choice
• Catalan continued fractions and increasing subsequences in permutations
• Combinatorics of geometrically distributed random variables: Value and position of large left-to-right maxima
• Combinatorics of permutations
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 783365 (Why is no real title available?)
• scientific article; zbMATH DE number 3226601 (Why is no real title available?)
• Longest alternating subsequences in pattern-restricted permutations
• Longest increasing subsequences in pattern-restricted permutations
• Positional strategies in games of best choice
• Secretary Problems via Linear Programming
• Secretary Problems with Non-Uniform Arrival Order
• Structure of random 312-avoiding permutations
• The On-Line Encyclopedia of Integer Sequences
• The Secretary Problem and Its Extensions: A Review
• The shape of random pattern-avoiding permutations
• Weighted games of best choice
• Who solved the secretary problem

Cited in

(5)

• Meager-nowhere dense games. I: n-tactics
• Avoiding patterns and making the best choice
• Positional strategies in games of best choice
• On choosing which game to play when ignorant of the rules
• Weighted games of best choice

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Strategy-indifferent games of best choice

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