Προσεγγίσεις της ωφέλειας κανονικοποιημένης με βάση τη ρευστότητα σε συνδυαστικές δημοπρασίες - Ποδηματά, Χαρίκλεια (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών, 2016)
In this diploma thesis we study truthful mechanisms for Combinatorial Auctions; auctions where they are many items and the bidders are interested in getting a subset of these items (bundles), with the additional constraint that each bidder has a private budget. Our goal was to study the behavior of a recently proposed new objective function: the Liquid Welfare function. Liquid Welfare is a metric which was proposed by Dobzinski and Paes Leme and manages to balance between the willingness of a user to pay for an item and his/her ability to pay for it, due to budget constraints. In other words, Liquid Welfare is the minimum between the bidder's valuation for a certain allocation and the budget of this bidder. We focus our interests in extending and improving recent results of the approximation of Liquid Welfare for single item multi unit auctions and submodular combinatorial auctions. Intuitively, we combine ideas from the known Multiplicative Weights Update Method from the field of Ma- chine Learning, which can produce truthful mechanisms together with ideas from the work of Dobzinski and Paes Leme, who manage to design mechanisms for budgeted settings. For the purposes of this diploma thesis, we study and analyze extensively the relevant bliography and we present, at the end, our conclusions together with suggestions for future work.