Prophet Inequalities via Linear Programming
Halil İbrahim Bayrak
Prophet inequalities bound the expected reward that can be obtained in a stopping problem by the optimal reward of its corresponding off-line version. We propose a systematic technique for deriving prophet inequalities for stopping problems associated with selecting a point in a polyhedron. It utilizes a reduced-form linear programming representation of the stopping problem. We illustrate the technique to derive a number of known results as well as some new ones. For instance, we prove a 1/2K-prophet inequality when the underlying polyhedron is the intersection of K on-line polymatroid; one whose underlying submodular function depends upon the realized rewards.
Short Bio
Halil Ibrahim Bayrak is an Assistant Professor in the Department of Industrial Engineering at Bilkent University. His research sits at the interface of optimization and economic theory, with a focus on robust and distributionally robust mechanism design, auction theory, bilateral trade, and prophet inequalities. He is particularly interested in problems where agents have private information and the designer must act under uncertainty about the underlying distribution of types. He received his Ph.D. in Industrial Engineering from Bilkent University, under the supervision of Prof. Mustafa Ç. Pınar and Prof. Nuh Aygün Dalkıran. During his doctoral studies he was a visiting researcher at the University of Pennsylvania, hosted by Prof. Rakesh Vohra. Prior to joining Bilkent, he was a postdoctoral researcher at the Chair of Decision Sciences & Systems, Technical University of Munich, working with Prof. Martin Bichler.
Venue
Friday, November 20, 2026, 4.00 pm
IE Building, Halim Doğrusöz Auditorium (IE 03)