Tutorial: Computational Issues in
Auction Design
This
tutorial focuses on the interaction between computational and incentive
constraints in auction design. The tutorial is designed for a computer science
audience, and it should have interest to both novices and experts in
computational mechanism design. No background is assumed in game theory or
auction theory. We will being with a broad taxonomy of auction problems, a
brief introduction of some necessary terms from game theory, and an overview of
mechanism design as it applies to auction theory. The central focus of the
tutorial is on four main areas of computational interest:
We
first consider the computational complexity placed on the center, in computing
the outcome and payments given agent bids; special attention is given to
implications on the strategic aspects of the auction. Particular topics
include: (a) tractable special cases; (b) leveraging the structure in bidding
languages; (c) maximal-in-range approximations; (d) decentralized and indirect
implementations; (e) very fast and scalable implementations.
II.
Communication and Valuation complexity.
We
review the communication and preference-elicitation complexity of auction
mechanisms, and consider the following computational approaches: (a) compact
bidding languages (incl. interdependent valuations); (b) restricted bidding
languages; (c) iterative auctions; (d) communication-and information-
constrained auction design; (e) incremental revelation principles.
III.
Strategic Complexity/ Solution concepts
Another
problem facing agents in an auction is the strategic complexity, or the
complexity of computing an equilibrium in an
auction. We review a number of methods
and issues with strategic complexity, including: (a) verification vs.
computation; (b) strategyproofness
and building blocks; (c) alternative solution concepts; (d) providing and
exploiting structure;
IV.
Design complexity/automated mechanism design
Finally,
we consider the design complexity of the auction problem itself, and consider
methods to automate this problem and also to fold in an explicit consideration
of computational constraints into auction design. We review the basic ``design
as optimization'' approach of mechanism design, outline challenges and open
problems, and consider the space of automated methods to construct mechanisms,
including systematic search, analysis, and evolutionary computation.
Biosketch of the
presenter:
Dr.
David Parkes is a Gordon McKay Assistant Professor of
Computer Science at
received
his Ph.D. degree in Computer and Information Science from the