Contents
Abstract
Dissertation
Proposal
Home

Proposal April, 2000
[PS]
[PDF]
Full Dissertation May, 2001
[diss.ps]
[diss.pdf]
[abstract.ps]
[abstract.pdf]
Abstract
[ch1.ps]
[ch1.pdf]
Introduction
[ch2.ps]
[ch2.pdf]
Classic Mechanism Design
[ch3.ps]
[ch3.pdf]
Computational Mechanism Design
[ch4.ps]
[ch4.pdf]
Linear Programming and Auction Design
[ch5.ps]
[ch5.pdf]
iBundle: An Iterative Combinatorial Auction
[ch6.ps]
[ch6.pdf]
Linear Programming and Vickrey Payments
[ch7.ps]
[ch7.pdf]
iBundle Extend & Adjust
[ch8.ps]
[ch8.pdf]
BoundedRational Compatible Auctions & Myopic BestResponse
[ch9.ps]
[ch9.pdf]
Extended Example: Distributed Train Scheduling
[ch10.ps]
[ch10.pdf]
Conclusions
[bib.ps]
[bib.pdf]
Bibliography
Abstract
A fundamental problem in building open distributed systems is to design
mechanisms that compute optimal systemwide
solutions despite the selfinterest of individual users and
computational agents. Classic gametheoretic solutions are often
prohibitively expensive computationally.
For example, the Generalized Vickrey Auction (GVA) is an
efficient and strategyproof solution to the combinatorial allocation problem
(CAP), in which agents demand bundles of items, but
every agent must reveal its value for all possible bundles and the
auctioneer must solve a sequence of NPhard optimization problems to
compute the outcome.
I propose iBundle, an
iterative combinatorial auction in which agents can bid for
combinations of items and adjust their
bids in response to bids from other agents. iBundle computes the
efficient allocation in the CAP when
agents follow myopic bestresponse bidding strategies,
bidding for the bundle(s) that maximize
their surplus taking the current prices as fixed.
iBundle solves problems without complete information revelation from
agents and
terminates in competitive equilibrium.
Moreover, an agent can follow a myopic bestresponse strategy with approximate
values on bundles, for example with lower and upper bounds.
My approach to iterative mechanism design decomposes the problem into
two parts. First, I use linear programming theory to
develop an efficient iterative auction under the assumption that
agents will follow a myopic bestresponse bidding strategy. Second, I
extend the approach
to also compute Vickrey payments at the end of the auction. This
makes myopic bestresponse a sequentiallyrational strategy for agents
in equilibrium, inheriting many of the useful gametheoretic
properties of the GVA.
iBundle implements a primaldual algorithm, CombAuction,
for the CAP, computing a feasible primal (the
provisional allocation) and a feasible dual (the ask prices) that
satisfy complementary slackness conditions.
An extended auction, iBundle
Extend & Adjust, interprets a primaldual algorithm,
VickAuction, as an iterative auction. VickAuction computes
the efficient allocation and Vickrey payments with only bestresponse
information from agents.
Experimental results demonstrate that
iBundle Extend & Adjust, which
keeps iBundle open for a second phase before adjusting prices
towards Vickrey payments, computes Vickrey payments across a suite of
problems.

