ORIE Colloquium: Eric Balkanski (Columbia)

Online Selection via Linear Programming Secretary problems are a fundamental family of online selection problems in which candidates arrive in random order and irrevocable accept-or-reject decisions must be made. In this talk, I will present recent progress on three secretary problems: knapsack secretaries, secretaries with predictions, and truthful secretaries. Our results are obtained using a common two-step approach: we first reduce the original cardinal problem to an ordinal one and then formulate it as a linear program. For the first step, I will present a recent technical tool introduced by Gravin, Sun, and Tang, called order-statistics indistinguishable distributions, which can be used to show that there is no loss in the cardinal-to-ordinal reduction. For the second step, we formulate each ordinal problem as a novel linear program. For knapsack secretaries, constant competitive ratios are known, but it was open whether a 1/e competitive ratio is achievable. We show that 1/e is not achievable and give a new algorithm that improves the best-known competitive ratio. For secretaries with predictions, multiple prediction models have been proposed. We present a flexible linear programming framework that captures existing prediction models and use it to obtain improved algorithms and impossibility results, which are in some cases optimal. For truthful secretaries, the best-known truthful mechanism is ¼-competitive, and we show that ¼ is tight for a broad family of mechanisms. Joint work with Jason Chatzitheodorou, Dimitris Fotakis, Vasilis Gkatzelis, Xizhi Tan, Thanos Tolias, David Yang, and Cherlin Zhu. Bio: Eric Balkanski is an associate professor in the Department of Industrial Engineering and Operations Research at Columbia University, affiliated with the Data Science Institute. His research focuses on approximation algorithms for combinatorial optimization problems under information limitations. He studies two main sources of such limitations: uncertainty about the future, as captured by online algorithms, and strategic behavior by agents, as captured by mechanism design. Balkanski received an Exemplary Theory Track Paper Award at the 2024 ACM Conference on Economics and Computation. Balkanski completed his Ph.D. in computer science from Harvard University, where he was advised by Yaron Singer; his thesis received an ACM SIGecom Doctoral Dissertation Honorable Mention. He also co-founded Robust Intelligence, an AI security startup that was acquired by Cisco.