Truthful Mechanisms for Selfish Routing and Two-Parameter Agents

  • We prove a general monotonicity result about Nash flows in directed networks and use it 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. The costs for each edge are assumed to be linear in the load on the edge. To compensate for these costs, the agents impose tolls for the usage of edges. When nonatomic selfish network users choose their paths through the network independently and each user tries to minimize a weighted sum of her latency and the toll she has to pay to the edges, a Nash flow is obtained. Our monotonicity result implies that the load on an edge in this setting can not increase when the toll on the edge is increased, so the assignment of load to the edges by a Nash flow yields a monotone algorithm. By a well-known result, the monotonicity of the algorithm then allows us to design truthful mechanisms based on the load assignment by Nash flows. Moreover, we consider a mechanism design setting with two-parameter agents, which is a generalization of the case of one-parameter agents considered in a seminal paper of Archer and Tardos. While the private data of an agent in the one-parameter case consists of a single nonnegative real number specifying the agent's cost per unit of load assigned to her, the private data of a two-parameter agent consists of a pair of nonnegative real numbers, where the first one specifies the cost of the agent per unit load as in the one-parameter case, and the second one specifies a fixed cost, which the agent incurs independently of the load assignment. We give a complete characterization of the set of output functions that can be turned into truthful mechanisms for two-parameter agents. Namely, we prove that an output function for the two-parameter setting can be turned into a truthful mechanism if and only if the load assigned to every agent is nonincreasing in the agent's bid for her per unit cost and, for almost all fixed bids for the agent's per unit cost, the load assigned to her is independent of the agent's bid for her fixed cost. When the load assigned to an agent is continuous in the agent's bid for her per unit cost, it must be completely independent of the agent's bid for her fixed cost. These results motivate our choice of linear cost functions without fixed costs for the edges in the selfish routing setting, but the results also seem to be interesting in the context of algorithmic mechanism design themselves.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Clemens Thielen
Serie (Series number):Report in Wirtschaftsmathematik (WIMA Report) (119)
Document Type:Report
Language of publication:English
Year of Completion:2009
Year of Publication:2009
Publishing Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2009/01/15
Tag:algorithmic game theory; mechanism design; selfish routing
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B20 Traffic problems
91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES / 91Axx Game theory / 91A10 Noncooperative games
91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES / 91Axx Game theory / 91A43 Games involving graphs [See also 05C57]
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011