Online Truthful Mechanisms (άμεσοι Φιλαληθείς Μηχανισμοί)

Abstract

In this thesis, we deal with limited supply and unLimited supply online auctions,as a subfield of online mechanism design. For the former case, we define a generalmodel, on which we examine problems such as single-item and multi-item auc-tion and also knapsack problem. We talk about the famous secretary problemand its applications-ideas to the previous auctions. Finally, we make a friendlyintroduction to matroids and their relationship with the online auctions where wehave some restrictions (such as the size of the supply etc). For the latter case,we also define a general model and deal with randomized algorithms that man-age to have good approximation ratio with respect to optimal fixed price revenuefor both single-price and multi-price auctions. We also consider two cases for themodel that depend on the information the auctioneer takes from the bidders afterafter their acceptance or rejection of the product. Finally, we mention results foronline pricing in other settings and give some implementations that valuate thealgorithms described in this thesis.