Das Suchergebnis hat sich seit Ihrer Suchanfrage verändert. Eventuell werden Dokumente in anderer Reihenfolge angezeigt.
  • Treffer 2 von 831
Zurück zur Trefferliste

Implementing efficient outcomes in combinatorial allocation problems

  • Allocating scarce resources efficiently is a major task in mechanism design. One of the most fundamental problems in mechanism design theory is the problem of selling a single indivisible item to bidders with private valuations for the item. In this setting, the classic Vickrey auction of~\citet{vickrey1961} describes a simple mechanism to implement a social welfare maximizing allocation. The Vickrey auction for a single item asks every buyer to report its valuation and allocates the item to the highest bidder for a price of the second highest bid. This auction features some desirable properties, e.g., buyers cannot benefit from misreporting their true value for the item (incentive compatibility) and the auction can be executed in polynomial time. However, when there is more than one item for sale and buyers' valuations for sets of items are not additive or the set of feasible allocations is constrained, then constructing mechanisms that implement efficient allocations and have polynomial runtime might be very challenging. Consider a single seller selling $n\in \N$ heterogeneous indivisible items to several bidders. The Vickrey-Clarke-Groves auction generalizes the idea of the Vickrey auction to this multi-item setting. Naturally, every bidder has an intrinsic value for every subset of items. As in in the Vickrey auction, bidders report their valuations (Now, for every subset of items!). Then, the auctioneer computes a social welfare maximizing allocation according to the submitted bids and charges buyers the social cost of their winning that is incurred by the rest of the buyers. (This is the analogue to charging the second highest bid to the winning bidder in the single item Vickrey auction.) It turns out that the Vickrey-Clarke-Groves auction is also incentive compatible but it poses some problems: In fact, say for $n=40$, bidders would have to submit $2^{40}-1$ values (one value for each nonempty subset of the ground set) in total. Thus, asking every bidder for its valuation might be impossible due to time complexity issues. Therefore, even though the Vickrey-Clarke-Groves auction implements a social welfare maximizing allocation in this multi-item setting it might be impractical and there is need for alternative approaches to implement social welfare maximizing allocations. This dissertation represents the results of three independent research papers all of them tackling the problem of implementing efficient allocations in different combinatorial settings.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Stephen Raach
URN:urn:nbn:de:hbz:385-1-20307
DOI:https://doi.org/10.25353/ubtr-xxxx-c56e-0aaa
Dokumentart:Dissertation
Sprache:Englisch
Datum der Fertigstellung:17.05.2023
Veröffentlichende Institution:Universität Trier
Titel verleihende Institution:Universität Trier, Fachbereich 4
Datum der Abschlussprüfung:10.02.2023
Datum der Freischaltung:17.05.2023
GND-Schlagwort:Greedy-Algorithmus; Kombinatorische Optimierung; Matroidtheorie; Mechanismus-Design-Theorie; Wohlfahrtstheorie
Seitenzahl:vi, 105 Seiten
Erste Seite:iii
Letzte Seite:105
Lizenz (Deutsch):License LogoCC BY: Creative-Commons-Lizenz 4.0 International

$Rev: 13581 $