Truthful mechanism design for cooperative cost sharing and congestion games [Elektronische Ressource] / vorgelegt von Janina Alexandra Brenner

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2010
• Nombre de lectures: 14
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Truthful Mechanism Design
for
Cooperative Cost Sharing and Congestion Games
vorgelegt von
Dipl.-Math. Janina Alexandra Brenner
Hamburg
Von der Fakultat II – Mathematik und Naturwissenschaften¨
der Technischen Universit¨at Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
– Dr. rer. nat. –
genehmigte Dissertation.
Vorsitzender: Prof. Dr. Michael Scheutzow
Gutachter: Prof. Dr. Guido Scha¨fer
Prof. Dr. Rolf H. Mo¨hring
Prof. Dr. Burkhard Monien
Zusatzlicher Gutachter: Prof. Dr. Tim Roughgarden¨
Tag der wissenschaftlichen Aussprache: 17. Mai 2010
Berlin 2010
D 83CONTENTS
1 Introduction 1
2 Preliminaries 7
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 General Setting . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 Equilibria and the Revelation Principle . . . . . . . . . . . 10
2.2.3 Implementable Social Choice Functions . . . . . . . . . . . 12
2.2.4 Maximizing Social Welfare – VCG Mechanisms . . . . . . . 13
2.2.5 Single Parameter Domains. . . . . . . . . . . . . . . . . . . 15
2.2.6 Cooperative Games . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Cost Sharing Games . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Binary Demand Model . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Strategic Behavior . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.3 Social Welfare vs. Social Cost . . . . . . . . . . . . . . . . . 21
2.3.4 General Demand Model . . . . . . . . . . . . . . . . . . . . 22
2.3.5 Classes of Cost Functions . . . . . . . . . . . . . . . . . . . 23
2.4 Design Techniques and Classes of Cost Sharing Mechanisms . . . . 24
2.4.1 Cost Sharing Methods . . . . . . . . . . . . . . . . . . . . . 25
2.4.2 Moulin Mechanisms . . . . . . . . . . . . . . . . . . . . . . 25
2.4.3 Characterizing Group-Strategyproof Mechanisms . . . . . . 28
2.4.4 Acyclic Mechanisms . . . . . . . . . . . . . . . . . . . . . . 28
2.4.5 Sequential Mechanisms . . . . . . . . . . . . . . . . . . . . 30
2.5 Combinatorial Optimization Problems . . . . . . . . . . . . . . . . 31
2.5.1 Parallel Machine Scheduling . . . . . . . . . . . . . . . . . . 31
2.5.2 Network Design . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6 Congestion Games . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
iiiiv CONTENTS
3 Group-Strategyproof Cost Sharing 39
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2 A Lower Bound for Social Cost Approximation . . . . . . . . . . . 42
3.3 Optimal Cost Sharing Method for Makespan Scheduling . . . . . . 44
3.3.1 Cross-Monotonic Cost Shares . . . . . . . . . . . . . . . . . 44
3.3.2 Approximate Cost Shares . . . . . . . . . . . . . . . . . . . 46
3.4 A General Lower Bound on Budget Balance . . . . . . . . . . . . . 48
3.4.1 Weighted Completion Time Scheduling . . . . . . . . . . . 50
3.4.2 Average Completion Time Scheduling . . . . . . . . . . . . 51
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4 Weakly Group-Strategyproof Cost Sharing 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 Generalized Incremental Mechanisms . . . . . . . . . . . . . . . . . 59
4.2.1 Construction and Basic Properties . . . . . . . . . . . . . . 59
4.2.2 No Positive Transfer . . . . . . . . . . . . . . . . . . . . . . 62
4.2.3 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3.1 Network Design Applications . . . . . . . . . . . . . . . . . 67
4.3.2 Scheduling Applications . . . . . . . . . . . . . . . . . . . . 69
4.4 Bounding Social Cost . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.5 Completion Time Scheduling . . . . . . . . . . . . . . . . . . . . . 74
4.5.1 Weighted Completion Time . . . . . . . . . . . . . . . . . . 74
4.5.2 Completion Time with Release Dates and Preemption . . . 76
4.6 Connections to Other Frameworks . . . . . . . . . . . . . . . . . . 81
4.6.1 Acyclic Mechanisms . . . . . . . . . . . . . . . . . . . . . . 81
4.6.2 Scheduling with Rejection . . . . . . . . . . . . . . . . . . . 82
4.7 Makespan Scheduling with Unit Processing Times . . . . . . . . . 83
4.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5 Online Cost Sharing 87
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2 Online General Demand Cost Sharing . . . . . . . . . . . . . . . . 90
5.3 Incentive Compatibility . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3.1 Strategyproofness. . . . . . . . . . . . . . . . . . . . . . . . 92
5.3.2 Weak Group-Strategyproofness . . . . . . . . . . . . . . . . 93
5.3.3 Group-Strategyproofness . . . . . . . . . . . . . . . . . . . 94
5.4 Incremental Online Mechanisms . . . . . . . . . . . . . . . . . . . . 95
5.4.1 Binary Demand Examples . . . . . . . . . . . . . . . . . . . 96
5.4.2 General Demand Examples . . . . . . . . . . . . . . . . . . 98
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99CONTENTS v
6 Mechanism Design with Congestion 101
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.3 Conditions for Truthfulness . . . . . . . . . . . . . . . . . . . . . . 106
6.4 Approximation via Disjoint Strategies . . . . . . . . . . . . . . . . 110
6.4.1 Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.4.2 Optimal Mechanism for Singleton Congestion Games . . . . 113
6.5 Implications and Applications . . . . . . . . . . . . . . . . . . . . . 115
6.5.1 Network Congestion Games . . . . . . . . . . . . . . . . . . 115
6.5.2 Hypergraph Models . . . . . . . . . . . . . . . . . . . . . . 115
6.6 Hardness Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.6.1 Symmetric Bottleneck Congestion Games . . . . . . . . . . 117
6.6.2 Matroid Bottleneck Congestion Games . . . . . . . . . . . . 118
6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1191
INTRODUCTION
The joint usage of infrastructures in today’s world imposes a new line of math-
ematical challenges. On the one hand, one seeks efficient ways to install and
use common infrastructures such that desirable global properties are met. On
the other hand, one has to cope with the diverse interests of their users. Often,
numerous participants contribute to the installation by providing money or rele-
vant personal data. To reach their individual goals, they attempt to influence the
outcome as much as they can.
One of the simplest examples for such a setting is a single item auction: A
number of bidders are interested in a single indivisible good. At the end of the
day, this good is allocated to at most one of the bidders. Say our global goal is
to give the item to the bidder who values it the most. How do we find out who
this is? If we endow the item to the bidder who declares the highest valuation
for the item, all bidders clearly have incentives to exaggerate their valuations. If
we additionally charge the winneran amount equal to her declared value, rational
bidders will stop submitting arbitrarily high valuations. But can we be sure that
the highest biddersubmits the highest valuation? As a matter of fact, in this case
the winner is better off understating her valuation as long as she still wins.
A solution to this problem is the second price auction: Allocate the item to
the bidder who declares the highest value, and charge her the value of the second
highest bid. It can be verified by a simple case analysis that in this auction, no
bidder can improve by exaggerating or understating her true valuation. Thus,
assuming that bidders behave rationally, we gather the necessary information to
achieve our global goal of maximizing the value obtained by a player.
12 Introduction
The single item auction has an extremely simple structure: The possible out-
comes of the global decision process are allocations of the good to at most one
user. In general, there is a wide range of problems with much richer structures.
For instance, in networkdesign problems, userswishto be connected to a network
or a specific point of interest. In routing problems, agents want their goods or in-
formation to be transferred from one point to another. In the scheduling context,
we can imagine both machines or jobs to be owned by agents who follow their
own selfish interests. Similarly, almost every combinatorial optimization problem
yields an interesting application when equipped with the additional complexity
of dealing with selfish interests. Many of these problems are hard to solve even
without a game-theoretic component.
Further, in the single item auction, each bidder distinguishes only two types
of outcomes – those in which she loses and those in which she wins. In general,
players may submit complex information about their requests and have compli-
cated valuation functions. The various ways to model the private contributions of
participants determine the extent to which they can manipulate a global process.
This thesis studi