|
Optimal Stopping with Interdependent Values| title | Optimal Stopping with Interdependent Values |
|---|
| start_date | 2024/06/11 |
|---|
| schedule | 11h |
|---|
| online | no |
|---|
| location_info | Salle 3052 |
|---|
| summary | Consider the problem of selling a single item to one of n buyers arriving sequentially, whereupon the arrival of each buyer we need to decide whether to accept this value and stop the process (before seeing the values of the future bidders), or irrevocably and irreversibly reject this bidder and continue on to the next. The objective is to maximize the accepted value, which poses a fundamental question: how effectively can an online algorithm perform compared to the offline optimal solution? Further, adding to the challenge in many scenarios a bidder's value for the item may depend on private information of other bidders. For example, in an art auction, a buyer's value for the item may be influenced by how other buyer's so far have liked it, and in fact, may even depend on how the future buyers will value the item as that would affect its resale value.
We study online selection problems in both the prophet and secretary settings, when arriving agents have interdependent values. In the interdependent values model, introduced in the seminal work of Milgrom and Weber [1982], each agent has a private signal and the value of an agent is a function of the signals held by all agents. Results in online selection crucially rely on some degree of independence of values, which is conceptually at odds with the interdependent values model. For prophet and secretary models under the standard independent values assumption, prior works provide constant factor approximations to the welfare. On the other hand, when agents have interdependent values, prior works in Economics and Computer Science provide truthful mechanisms that obtain optimal and approximately optimal welfare under certain assumptions on the valuation functions. We bring together these two important lines of work and provide the first constant factor approximations for prophet and secretary problems with interdependent values. We consider both the algorithmic setting, where agents are non-strategic (but have interdependent values), and the mechanism design setting with strategic agents. All our results are constructive and use simple stopping rules.
Joint work with Simon Mauras and Rebecca Reiffenhäuser. |
|---|
| responsibles | Hamoudi |
|---|
Workflow history| from state (1) | to state | comment | date |
|---|
| submitted | published | | 2024/05/31 14:47 UTC |
| |
|