Solving Optimization Problems Among Selfish Agents

Abstract

v 1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Game theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Some fundamental concepts of theoretical computer science . . . . . . . . . . 6 1.1.4 Game theoretic considerations in computer science . . . . . . . . . . . . . . . 8 1.2 Overview of the results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Algorithmic Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Computationally Feasible VCG Mechanisms . . . . . . . . . . . . . . . . . . . 12 2 Algorithmic Mechanism Design 13 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.2 This Work ....