Online Combinatorial Auctions
Event details
| Date | 12.01.2023 |
| Hour | 14:00 › 15:00 |
| Speaker | Dr. Andrés Cristi |
| Location | |
| Category | Conferences - Seminars |
| Event Language | English |
Abstract:
In online combinatorial auctions, a set of indivisible items are to be allocated to a set of agents who arrive sequentially. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. Because of their connections to ad auctions and pricing problems in e-commerce platforms, the study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents’ valuation functions are submodular or fractionally subadditive. In this talk I will present two innovative ideas in the context of algorithm design for online allocation: a sample-based approach to protect items from being allocated too early, and fixed-point arguments to prove the existence of good online policies. I will explain how we used these techniques to find the first constant prophet inequality when valuations are subadditive (a.k.a. complement-free), resolving a central open problem in the area, and to find item prices with the best-possible guarantee when we bound the number of items any agent can get. I will also discuss connections with my research in sample-based optimal stopping and future directions in online resource allocation problems.
Bio:
Andrés Cristi is a final year PhD student at Universidad de Chile, advised by José Correa and Paul Dütting. He previously graduated as a Mathematical Engineer and an MS in Operations Management. His research is focused on the interplay between optimization and incentives, this is, situations where the outcome depends on the actions of strategic agents. He is particularly interested in allocation problems with a dynamic aspect, where decisions are made on the fly, and data-driven approaches, in which decisions are directly made using observations rather than distributional assumptions. Modern platforms like routing apps, online advertisers, and online marketplaces face these challenges on a daily basis, and his work is centered on understanding the fundamental aspects that drive decision-making in these settings.
In online combinatorial auctions, a set of indivisible items are to be allocated to a set of agents who arrive sequentially. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. Because of their connections to ad auctions and pricing problems in e-commerce platforms, the study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents’ valuation functions are submodular or fractionally subadditive. In this talk I will present two innovative ideas in the context of algorithm design for online allocation: a sample-based approach to protect items from being allocated too early, and fixed-point arguments to prove the existence of good online policies. I will explain how we used these techniques to find the first constant prophet inequality when valuations are subadditive (a.k.a. complement-free), resolving a central open problem in the area, and to find item prices with the best-possible guarantee when we bound the number of items any agent can get. I will also discuss connections with my research in sample-based optimal stopping and future directions in online resource allocation problems.
Bio:
Andrés Cristi is a final year PhD student at Universidad de Chile, advised by José Correa and Paul Dütting. He previously graduated as a Mathematical Engineer and an MS in Operations Management. His research is focused on the interplay between optimization and incentives, this is, situations where the outcome depends on the actions of strategic agents. He is particularly interested in allocation problems with a dynamic aspect, where decisions are made on the fly, and data-driven approaches, in which decisions are directly made using observations rather than distributional assumptions. Modern platforms like routing apps, online advertisers, and online marketplaces face these challenges on a daily basis, and his work is centered on understanding the fundamental aspects that drive decision-making in these settings.
Practical information
- General public
- Free
Organizer
- Prof. Daniel Kuhn
Contact
- amandine.weissbrodt@epfl.ch