Online Auctions, Strategyproofness and Random Valuations

Опубликовано 6 сентября 2016, 5:05

We discuss the limited-supply online auction problem, in which an auctioneer has k goods to sell and bidders arrive and depart dynamically, from a theoretical point of view and show how Economics, Scheduling theory, Probability theory and finally Graph theory have a nice intersection in this area. First we present a background on recent work in this area. Then we consider the notion of value- and time-strategyproofness (truthfulness) and show for the k=1 problem we have a strategyproof variant on the classic Secretary's problem. Next, we consider the case in which we have re-usable goods and present the relation to finding a maximum weight matching in bipartite graphs or more generally scheduling theory. During the talk we present several algorithms which are constant competitive for revenue and/or efficiency (we define these simple terms in the talk). This talk is from two papers joint work with Mohammad Mahdian, Robert Kleinberg and David Parkes.