Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
A Constant Factor Prophet Inequality for Online Combinatorial Auctions
How to Incentivize Hospitals in Dynamic Kidney Exchange
"How to Incentivize Hospitals in Dynamic Kidney Exchange" - Duygu Sili
Abstract: We study a multi-hospital dynamic kidney exchange setting: there are two hospitals at which incompatible patient-donor pairs arrive under the Poisson process. First, we consider full centralization where hospitals' pairs are pooled and matched through a centralized mechanism. We show that, unlike the static exchange model (where centralization always yields an increase in the exchange surplus), under this dynamic setting, pooling might have the adverse effect of decreasing the total exchange surplus compared to decentralization, where hospitals match their own pairs separately. Second, we propose a hybrid design where hospitals utilize inter-hospital exchanges only when certain conditions are met. We then show that this hybrid design (with partial centralization) is incentive compatible for hospitals and improves the exchange surplus upon full centralization benchmark.
"A Constant Factor Prophet Inequality for Online Combinatorial Auctions"- Andrés Cristi
Abstract: In online combinatorial auctions m indivisible items are to be allocated to n agents who arrive online. 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. 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. Despite many efforts, for the more general case of subadditive valuations, the best-known prophet inequality has an approximation guarantee of O(log log m).
We prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area.
Our prophet inequality is achieved by a novel, but elementary, sampling idea which we call the Mirror Lemma. This lemma is essentially concerned with understanding algorithms for which the set of items that are allocated and those that are not, distribute equally. The other main ingredient is a nonstandard application of Kakutani's fixed point theorem.
 |
"How to Incentivize Hospitals in Dynamic Kidney Exchange" - Duygu Sili
|