Organizer:  Vince Conitzer

Meeting Schedule: (Not currently open for scheduling. Please contact the seminar organizer listed above.)

    All meetings will be held in the same location as the seminar unless otherwise noted.

   12:00pm - Seminar Presentation (12:00pm to 1:00pm)

    Additional Comments:  Abstract We revisit the well-studied problem of budget-feasible procurement, where a buyer with a strict budget constraint seeks to acquire services from a group of strategic providers (the sellers). During the last decade, several strategyproof budget-feasible procurement auctions have been proposed, aiming to maximize the value of the buyer, while eliciting each seller’s true cost for providing their service. These solutions predominantly take the form of randomized sealedbid auctions: they ask the sellers to report their private costs and then use randomization to determine which subset of services will be procured and how much each of the chosen providers will be paid, ensuring that the total payment does not exceed the buyer’s budget. Our main result in this paper is a novel method for designing budget-feasible auctions, leading to solutions that outperform the previously proposed auctions in multiple ways. First, our solutions take the form of descending clock auctions, and thus satisfy a list of very appealing properties, such as obvious strategyproofness, group strategyproofness, transparency, and unconditional winner privacy; this makes these auctions much more likely to be used in practice. Second, in contrast to previous results that heavily depend on randomization, our auctions are deterministic. As a result, we provide an affirmative answer to one of the main open questions in this literature, asking whether a deterministic strategyproof auction can achieve a constant approximation when the buyer’s valuation function is submodular over the set of services. In addition to this, we also provide the first deterministic budget-feasible auction that matches the approximation bound of the best-known randomized auction for the class of subadditive valuations. Finally, using our method, we improve the best-known approximation factor for monotone submodular valuations, which has been the focus of most of the prior work. This is joint work with Eric Balkanski, Pranav Garimidi, Daniel Schoepflin, and Xizhi Tan. Short Biography Vasilis Gkatzelis is an assistant professor of computer science in the College of Computing & Informatics at Drexel University. Gkatzelis' research interests include algorithmic mechanism design, multiagent resource allocation and approximation algorithms. Prior to joining Drexel's faculty in 2016, Gkatzelis served as a postdoctoral scholar at the University of California, Berkeley's Department of Electrical Engineering and Computer Sciences; at UC Berkeley's International Computer Science Institute and Simons Institute; and at Stanford University. His professional experience includes working for Microsoft Research in Mountain View, CA; HP Labs in Palo Alto, CA; and Google in New York, NY.