Abstract

We study the integration of game theoretic and computational considerations. In particular, we study, the design of computationally efficient and incentive compatible mechanisms, for several different problem domains. Issues like the dimensionality of the domain, and the goal of the algorithm designer, are examined by providing a technical discussion on four results: (i) approximation mechanisms, for single-dimensional scheduling, where truthfulness reduces to a simple monotonicity condition; (ii) randomness as a tool to resolve the computational vs. incentives clash for Combinatorial Auctions, a central multidimensional domain where this clash is notable; (iii) the impossibilities of deterministic dominant-strategy implementability in multidimensional domains; and (iv) alternative solution concepts that fit worst-case analysis, and aim to resolve the above impossibilities.

Introduction

Algorithms in computer science, and Mechanisms in game theory, are very close in nature. Both disciplines aim to implement desirable properties, drawn from “real-life” needs and limitations, but the resulting two sets of properties are completely different. A natural need is then to merge them – to simultaneously exhibit “good” game theoretic properties as well as “good” computational properties. The growing importance of the Internet as a platform for computational interactions only strengthens the motivation for this.

However, this integration task poses many difficult challenges. The two disciplines clash and contradict in several different ways, and new understandings must be obtained to achieve this hybridization. The classic Mechanism Design literature is rich and contains many technical solutions when incentive issues are the key goal.