Ξεκινάμε πάλι το theory tea, τα απογεύματα της Παρασκευής, με νεες ομιλίες, και αυτή την Παρασκευή θα έχουμε και βασιλόπιτα!
Η πρώτη ομιλία θα γίνει από τον κ. Μαρκάκη, αυτή την Παρασκευή 2/2, στις 17:00.
Ως συνήθως, αίθουσα Α36.
Η ομιλία αφορά δημοπρασίες και ακολουθούν ο τίτλος και η περίληψη.
Title: On the Performance of Deferred- Acceptance Auctions
Abstract:
Deferred Acceptance (DA) auctions were introduced by Milgrom and Segal (2014), motivated by the design of spectrum auctions. This framework is based on backward-greedy algorithms and yields mechanisms with remarkable incentive properties. In particular, auctions that fit under this framework are group-strategyproof, and can be implemented as an obviously-strategyproof ascending auction. Most existing works on DA auctions however considered only binary single-parameter problems, where each bidder is either accepted or rejected by the mechanism. In this talk, we will first overview the framework along with results on the binary setting. We will then provide a generalization of the DA auction framework to non-binary settings, that allow outcomes with multiple "levels of service" instead of an accept/reject decision. We will then describe how to apply this in order to obtain approximately welfare-maximizing DA auctions for a number of basic mechanism design problems, including: problems with polymatroid constraints or multiple knapsack constraints, the problem of scheduling jobs to minimize their total weighted completion time, and multi-unit auctions.
This is joint work with Vasilis Gkatzelis and Tim Roughgarden.