Νέα / Ανακοινώσεις / Συζητήσεις

ECE Colloquium - Ομιλία Γιώργου Αμανατίδη, Τρίτη 2 Μαρτίου, 16:00

  • 1
  • Συντάχθηκε 24-02-2021 14:54 Πληροφορίες σύνταξης

    Ενημερώθηκε: 24-02-2021 14:54

    ECE Colloquium

    When / Where: Tuesday, March 2 , 16:00 Athens time

    at: https://tuc-gr.zoom.us/j/85176713430?pwd=bCtqMk1LeEVTRTFMSFFQNkU5RWFWZz09 

     

    Speaker: Georgios Amanatidis

    Assistant Professor, University of Essex

     

    Title: Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives

     

    Abstract: The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible and O(1)-approximation mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Since the introduction of the problem by Singer (FOCS 2010), obtaining efficient mechanisms for objectives that go beyond the class of monotone submodular functions has been elusive. Prior to our work, the only O(1)-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries.
    At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). Ours is the first mechanism for the problem where, crucially, the agents are not ordered according to their marginal value per cost. This allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present, e.g., at most k agents can be selected.

     

    About the Speaker 

     

    http://amanatidis.info/

     

    Georgios Amanatidis is an assistant professor in the Department of Mathematical Sciences at the University of Essex and an associate member of the Institute for Logic, Language and Computation at the University of Amsterdam. Prior to joining the University of Essex, he spent one year as a senior postdoctoral researcher at the Sapienza University of Rome, and two years as a postdoctoral researcher at the Centrum Wiskunde & Informatica (CWI) in Amsterdam. He holds a PhD in computer science from Athens University of Economics and Business, an MSc in mathematics from Georgia Institute of Technology, and a Diploma in applied mathematics from the National Technical University of Athens. He is the recipient of an NWO Veni Grant (2020-23) in algorithmic fair division.


  • 1
© Πολυτεχνείο Κρήτης 2012