Optimal single threshold stopping rules and sharp prophet inequalities

Bibliographic Details
Title:	Optimal single threshold stopping rules and sharp prophet inequalities
Authors:	Goldenshluger, Alexander, Malinovsky, Yaakov, Zeevi, Assaf
Publication Year:	2024
Collection:	Computer Science Mathematics Statistics
Subject Terms:	Mathematics - Probability, Computer Science - Computer Science and Game Theory, Mathematics - Optimization and Control, Mathematics - Statistics Theory, 60G40, 62L12, 91A05
More Details:	This paper considers a finite horizon optimal stopping problem for a sequence of independent and identically distributed random variables. The objective is to design stopping rules that attempt to select the random variable with the highest value in the sequence. The performance of any stopping rule may be benchmarked relative to the selection of a "prophet" that has perfect foreknowledge of the largest value. Such comparisons are typically stated in the form of "prophet inequalities." In this paper we characterize sharp prophet inequalities for single threshold stopping rules as solutions to infinite two person zero sum games on the unit square with special payoff kernels. The proposed game theoretic characterization allows one to derive sharp non-asymptotic prophet inequalities for different classes of distributions. This, in turn, gives rise to a simple and computationally tractable algorithmic paradigm for deriving optimal single threshold stopping rules.
Document Type:	Working Paper
Access URL:	http://arxiv.org/abs/2404.12949
Accession Number:	edsarx.2404.12949
Database:	arXiv

FullText	Text: Availability: 0 CustomLinks: – Url: http://arxiv.org/abs/2404.12949 Name: EDS - Arxiv Category: fullText Text: View this record from Arxiv MouseOverText: View this record from Arxiv – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20240419&spage=&pages=&title=Optimal single threshold stopping rules and sharp prophet inequalities&atitle=Optimal%20single%20threshold%20stopping%20rules%20and%20sharp%20prophet%20inequalities&aulast=Goldenshluger%2C%20Alexander&id=DOI: Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries
Header	DbId: edsarx DbLabel: arXiv An: edsarx.2404.12949 RelevancyScore: 1085 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 1085.41955566406
IllustrationInfo
Items	– Name: Title Label: Title Group: Ti Data: Optimal single threshold stopping rules and sharp prophet inequalities – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Goldenshluger%2C+Alexander%22">Goldenshluger, Alexander</searchLink><br /><searchLink fieldCode="AR" term="%22Malinovsky%2C+Yaakov%22">Malinovsky, Yaakov</searchLink><br /><searchLink fieldCode="AR" term="%22Zeevi%2C+Assaf%22">Zeevi, Assaf</searchLink> – Name: DatePubCY Label: Publication Year Group: Date Data: 2024 – Name: Subset Label: Collection Group: HoldingsInfo Data: Computer Science<br />Mathematics<br />Statistics – Name: Subject Label: Subject Terms Group: Su Data: <searchLink fieldCode="DE" term="%22Mathematics+-+Probability%22">Mathematics - Probability</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Computer+Science+and+Game+Theory%22">Computer Science - Computer Science and Game Theory</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics+-+Optimization+and+Control%22">Mathematics - Optimization and Control</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics+-+Statistics+Theory%22">Mathematics - Statistics Theory</searchLink><br /><searchLink fieldCode="DE" term="%2260G40%2C+62L12%2C+91A05%22">60G40, 62L12, 91A05</searchLink> – Name: Abstract Label: Description Group: Ab Data: This paper considers a finite horizon optimal stopping problem for a sequence of independent and identically distributed random variables. The objective is to design stopping rules that attempt to select the random variable with the highest value in the sequence. The performance of any stopping rule may be benchmarked relative to the selection of a "prophet" that has perfect foreknowledge of the largest value. Such comparisons are typically stated in the form of "prophet inequalities." In this paper we characterize sharp prophet inequalities for single threshold stopping rules as solutions to infinite two person zero sum games on the unit square with special payoff kernels. The proposed game theoretic characterization allows one to derive sharp non-asymptotic prophet inequalities for different classes of distributions. This, in turn, gives rise to a simple and computationally tractable algorithmic paradigm for deriving optimal single threshold stopping rules. – Name: TypeDocument Label: Document Type Group: TypDoc Data: Working Paper – Name: URL Label: Access URL Group: URL Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2404.12949" linkWindow="_blank">http://arxiv.org/abs/2404.12949</link> – Name: AN Label: Accession Number Group: ID Data: edsarx.2404.12949
PLink	https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2404.12949
RecordInfo	BibRecord: BibEntity: Subjects: – SubjectFull: Mathematics - Probability Type: general – SubjectFull: Computer Science - Computer Science and Game Theory Type: general – SubjectFull: Mathematics - Optimization and Control Type: general – SubjectFull: Mathematics - Statistics Theory Type: general – SubjectFull: 60G40, 62L12, 91A05 Type: general Titles: – TitleFull: Optimal single threshold stopping rules and sharp prophet inequalities Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Goldenshluger, Alexander – PersonEntity: Name: NameFull: Malinovsky, Yaakov – PersonEntity: Name: NameFull: Zeevi, Assaf IsPartOfRelationships: – BibEntity: Dates: – D: 19 M: 04 Type: published Y: 2024
ResultId	1