Ph.D Thesis

Ph.D StudentKfir Dahav Noa
SubjectMechanism Design for Resource-Bounded Agents
DepartmentDepartment of Industrial Engineering and Management
Supervisors PROF. Moshe Tennenholtz


One of the most significant results of the theory of mechanism design is the existence of efficient, truth revealing, budget balanced mechanisms - the VC (Vickrey-Clarke) mechanisms. However, the computer science literature challenges the basic assumptions of applying a VC mechanism: The amount of communication required in following the classical truth revealing dominant strategy might be infeasible, and optimizing social surplus is computationally hard. Thus, in a realistic setting, where the agents or the designer of the mechanism are resource bounded, we would need to relax the basic assumptions, and therefore re-examine the agents’ behavior and the properties of the mechanism.

We study the ramifications of communication considerations on the analysis of VC mechanisms in the context of combinatorial auctions. We deal with non-restricted VC auctions, in which the buyers restrict themselves to (truthful) bids on bundles in some family of bundles of goods, S, because it is rational for them to do so. We fully characterize those S that induce individually rational equilibrium in every VC auction, and we refer to the associated equilibrium as a bundling equilibrium. We analyze the tradeoff between communication complexity and economic efficiency (social optimality) of bundling equilibrium, focusing on partition-based equilibrium.

In another part of our work we examine the implications of the need to use heuristics or approximations for optimizing social surplus on the properties of VC mechnisms, other than efficiency. In a somewhat limited group decision-making model, we show that by setting some restrictions on the heuristic we use, we can still obtain a truth revealing, budget balanced mechanism.