Detailansicht

Combinatorial auctions with bidding constraints and network externalities

Martin Starnberger

Art der Arbeit

Dissertation

Universität

Universität Wien

Fakultät

Fakultät für Informatik

Studiumsbezeichnung bzw. Universitätlehrgang (ULG)

Dr.-Studium der technischen Wissenschaften (Dissertationsgebiet: Informatik, IK: Computer-unterstützte Optimierung)

Betreuer*in

Monika Henzinger

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.39602

URN

urn:nbn:at:at-ubw:1-29349.71812.681459-6

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Kombinatorische Auktionen ermöglichen den zeitgleichen Verkauf mehrerer heterogener Güter mit Abhängigkeiten (bspw. Substitute). Beispiele für solche Auktionen sind Spektrumauktionen bei welchen Regierungen Lizenzen für Bänder des Frequenzspektrums verkaufen und Auftragsauktionen bei welchen der Auktionator Dienstleistungen oder Güter erwirbt. Ein weiteres bedeutendes Beispiel sind Auktionen für Sponsored-Search. Hierbei bieten Werbung schaltende Unternehmen Geld an Suchmaschinen damit ihre Werbung neben den Suchergebnissen für bestimmte Suchbegriffe angezeigt wird. Einer der Standardmechanismen für kombinatorische Auktionen ist der bekannte VCG-Mechanismus. Dieser Mechanismus hat die Eigenschaft, dass Bieter motiviert werden genau ihre Bewertung für die Güter zu bieten. Diese Eigenschaft wird Anreizkompatibilität genannt. Darüber hinaus besitzt der Mechanismus weitere Eigenschaften wenn Bieter tatsächlich ihre Bewertung bieten: (1) Kein Bieter hat einen negativen Nutzen. Diese Eigenschaft wird individuelle Rationalität genannt. (2) Die Allokation der Güter die der Mechanismus bestimmt maximiert die Wohlfahrt. Das bedeutet, dass die Summe der Bewertungen maximiert wird. Jedoch können diese Eigenschaften nur unter bestimmten Voraussetzungen erreicht werden: (1) Es ist notwendig, dass die Nutzenfunktionen der Bieter quasilinear sind. Die Bieter dürfen daher keine Budgetbeschränkungen haben. (2) Außerdem ist es notwendig, dass die Berechnung der wohlfahrtsmaximierenden Allokation in der zur Verfügung stehenden Zeit möglich ist. In Fällen wo diese Voraussetzungen verletzt werden ist die Verwendung des VCG-Mechanismus nicht anzuraten. In dieser Dissertation werden für genau diese Fälle neue Auktionsmechanismen entwickelt. (A) Zuerst befassen wir uns mit Szenarien in denen die Bieter Budgetbeschränkungen haben. Wir entwickeln anreizkompatible, individuell rationale und Pareto-optimale Mechanismen für Auktionen mit heterogenen Gütern und Bietern mit additiven Bewertungen und Budgetbeschränkungen. (1) Insbesondere berücksichtigen wir Szenarien mit eindimensionalen Bewertungen und zeigen positive Resultate für randomisierte Mechanismen. Zudem zeigen wir das Fehlen deterministischer Mechanismen. Die positiven Resultate gelten auch für private Budgetbeschränkungen und die negativen Resultate selbst für öffentliche Budgetbeschränkungen. (2) Des Weiteren berücksichtigen wir Szenarien mit mehrdimensionalen Bewertungen. Wir zeigen das Fehlen von deterministischen und randomisierter Mechanismen, selbst im Fall öffentlicher Budgetbeschränkungen. Zusammengenommen zeigt das die Wichtigkeit von Randomisierung in bestimmten Szenarien mit heterogenen Gütern, jedoch zeigt dies auch die Grenzen von Randomisierung auf. (3) Darüber hinaus berücksichtigen wir Sponsored-Search-Auktionen für mehrere Suchbegriffe und Bieter mit Budgetbeschränkungen. Hierbei hat die Ergebnisseite jedes Suchbegriffs mehrere Plätze für Werbung mit einer sogenannten Click-Through-Rate. Zusätzlich nehmen wir an, dass die Anzahl der Werbeplätze pro Suchbegriff die einem Bieter zugeteilt werden kann beschränkt ist. Wir präsentieren den ersten Mechanismus für mehrere Suchbegriffe und Click-Through-Raten die vom Werbeplatz abhängen, welcher in Erwartung anreizkompatibel und individuell rationell ist und der ex-post Pareto-Optimalität erfüllt. (B) Als Nächstes befassen wir uns mit Szenarien mit komplexen Bewertungsfunktionen für die das Maximieren der Wohlfahrt NP-schwer und daher für große Instanzen nicht praktikabel ist. Wir berücksichtigen zahlreiche Klassen von Bewertungsfunktionen und Gebotsfunktionen und analysieren die Wohlfahrt des VCG-Mechanismus wenn Bieter gezwungen sind ihre Gebote aus einer Unterklasse der Klasse der Bewertungsfunktionen zu wählen. Hierbei beschränkt der Auktionator die Klasse der Gebotsfunktionen damit das VCG-Ergebnis effizient berechnet werden kann. Wir bewerten die durch die Mechanismen erreichte Wohlfahrt mit Hilfe des Price-of-Anarchy, dem Verhältnis der maximalen Wohlfahrt über alle Allokationen und der minimalen Wohlfahrt wenn die Gebote ein strategisches Gleichgewicht bilden. Wir zeigen verbesserte obere Schranken für den Price-of-Anarchy für Beschränkungen auf additive Gebote und obere und untere Schranken für Beschränkungen auf nicht-additive Gebote. Unsere Schranken zeigen, dass erhöhte Ausdrucksstärke zur Existenz zusätzlicher Gleichgewichte mit geringer Effizienz führen kann. (C) Zuletzt verallgemeinern wir das Standardmodell für kombinatorische Auktionen in welchen der Nutzen eines Bieters einzig von den zugeordneten Gütern und den Kosten hierfür abhängt. Beispielsweise mögen manche Werbung schaltende Unternehmen im Bereich der Onlinewerbung nicht wenn ihre Werbung auf der selben Seite angezeigt wird, wie die Werbung eines direkten Konkurrenten. Wir definieren und analysieren mehrere natürliche und einfache graphentheoretische Modelle für kombinatorische Auktionen die negative konfliktbasierte Externalitäten aufweisen. Hierbei bilden Bieter einen gerichteten Konfliktgraphen und D ist der maximale Ausgangsgrad jedes Knotens. Wir entwickeln O(D log log D / log D)-approximative Algorithmen und O(D)-approximative anreizkompatible Mechanismen bezüglich der maximalen Wohlfahrt. Diese Approximationsfaktoren sind aufgrund bestehender Komplexitätsresultate für das Stabilitätsproblem beinahe optimal. Für Sponsored-Search-Auktionen zeigen wir mehrere Algorithmen für eine kleine Anzahl an Gütern, dem in der Praxis relevantesten Szenario. Insbesondere zeigen wir wie ein im maximalen Ausgangsgrad D sublinearer Approximationsfaktor erreicht werden kann wenn die Anzahl der Güter lediglich logarithmisch in der Anzahl der Bieter ist. Darüber hinaus können alle unsere Algorithmen für Sponsored-Search-Auktionen in anreizkompatible Mechanismen umgewandelt werden.

Abstract

(Englisch)

Combinatorial auctions allow to simultaneously sell multiple heterogeneous items with interdependencies. Examples for such auctions are spectrum auctions, where the government sells licenses for bands of the radio spectrum, and procurement auctions, where the auctioneer buys services or goods. Another prominent example are auctions for sponsored search. Here a search engine company shows advertisements next to the search results on its website and the advertisers bid money for their ads being shown next to the search results for certain keywords. One of the standard mechanisms for combinatorial auctions is the seminal VCG mechanism. This mechanism has the property that every bidder is incentivized to bid his valuation; this property is called incentive compatibility. Moreover, it has other desirable properties if bidders indeed bid their valuation: (1) No bidder has a negative utility; this property is called individual rationality. (2) The allocation of the items selected by the mechanism maximizes social welfare; that is, the allocation maximizes the sum of the valuations. However, these properties can only be achieved under certain conditions. It is necessary that (1) the utility functions of the bidders are quasi-linear, this implies that they cannot have budget constraints, and that (2) the computation of the social welfare maximizing allocation is possible in the available time. Thus, in settings where this is not the case it is not recommended to use the VCG mechanism. These are exactly the settings for which we design new auction mechanisms in this dissertation. (A) First, we study settings where bidders are budget constrained. We design incentive compatible, individually rational, and Pareto-optimal mechanisms for auctions with heterogeneous items and bidders with additive valuations and budget constraints. (1) Specifically, we first study settings with single-dimensional valuations and prove a positive result for randomized mechanisms and an impossibility result for deterministic mechanisms. While the positive result allows for private budgets, the negative result is for public budgets.(2) Next, we study settings with multi-dimensional valuations. Here, we prove an impossibility result that applies to deterministic and randomized mechanisms even if budgets are public. Together with the previous results this shows the power of randomization in certain settings with heterogeneous items, but it also shows its limitations. (3) Furthermore, we study multiple keyword sponsored search auctions with budgets. Here, each keyword has multiple ad slots with so-called click-through rates. The bidders have single-dimensional additive valuations, which are linear in the click-through rates. Additionally, we assume that the number of slots per keyword assigned to a bidder is bounded. We give the first mechanism for multiple keywords and click-through rates differing among slots that is incentive compatible in expectation, individually rational in expectation, and that satisfies Pareto-optimality ex-post. (B) Next, we study settings with complex valuations for which maximizing social welfare is NP-hard and is thus impracticable for large instances. We consider various classes of valuation functions and bidding functions and study the performance of the VCG mechanism when bidders are forced to choose their bids from a subclass of the class of valuation functions. Thus, the auctioneer restricts the class of bidding functions such that the VCG outcome can be computed efficiently. The performance of the mechanisms is measured in terms of the Price of Anarchy, which is the ratio of the maximum social welfare of all allocations and the minimum social welfare of outcomes when the bids form a strategic equilibrium. We show improved upper bounds on the Price of Anarchy for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. Our bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency. (C) Finally, we generalize the standard model for combinatorial auctions where the utility of a bidder depends solely on the item set assigned to him and on his payment. For instance, in online advertisement an advertiser might not want his ads to be displayed on the same page as the ads of his direct competitor. We propose and analyze several natural, simple graph-theoretic models for combinatorial auctions that incorporate negative, conflict-based externalities. Here bidders are embedded into a directed conflict graph, and D is the maximum out-degree of any node. We design O(D log log D / log D)-approximate algorithms and O(D)-approximate incentive compatible mechanisms for social welfare maximization. These ratios are almost optimal given existing hardness results for the independent set problem. For the prominent application of sponsored search, we present several algorithms when the number of items is small---the most relevant scenario in practice. In particular, we show how to obtain an approximation ratio that is sublinear in D when the number of items is only logarithmic in the number of bidders. All our algorithms for sponsored search can be turned into incentive compatible mechanisms.

Autor*innen

Martin Starnberger

Haupttitel (Englisch)

Combinatorial auctions with bidding constraints and network externalities

Paralleltitel (Deutsch)

Kombinatorische Auktionen mit Gebotsbeschränkungen und Netzwerkexternalitäten

Publikationsjahr

2015

Umfangsangabe

xvii, 124 Seiten : Diagramme

Sprache

Englisch

Beurteiler*innen

Guido Schäfer ,

Martin Bichler

Klassifikation

54 Informatik > 54.99 Informatik: Sonstiges

AC Nummer

AC13026027

Utheses ID

35082

Studienkennzahl

UA | 786 | 880 | |

Detailansicht

Abstracts

Schlagwörter