Paper Info
Title
Truthful Mechanisms for Selfish Routing and Two-Parameter Agents
Abstract
We prove a general monotonicity result about Nash flows in directed networks, which generalizes earlier results and can be used for the design of truthful mechanisms in the setting where each edge of the network is controlled by a different selfish agent, who incurs costs when her edge is used. Moreover, we consider a general mechanism design setting with two-parameter agents, which generalizes the well-known setting of one-parameter agents in two directions by allowing nonlinear cost functions and a fixed cost component as part of each agent’s private data. We give complete characterizations of the sets of output functions that can be turned into truthful mechanisms for two-parameter agents in the case that an agent always incurs her fixed costs and in the case that she only incurs her fixed costs when she is assigned a positive amount of work. Moreover, we give explicit formulas for the payment functions in both cases and show that the truthful payments are uniquely determined by the output function up to a constant as in the one-parameter setting.
Year
DOI
Venue
2009
10.1007/s00224-010-9281-8
Theory of Computing Systems - Special Issue: Algorithmic Game Theory
Keywords
DocType
Volume
Algorithmic mechanism design,Selfish routing,Nash flows
Conference
49
Issue
ISSN
Citations 
1
1432-4350
0
PageRank 
References 
Authors
0.34
17
2
Name
Order
Citations
PageRank
Clemens Thielen17515.11
Sven O. Krumke230836.62