DIMACS Workshop on Auctions with Transaction Costs

March 22 - 23, 2007
DIMACS Center, CoRE Building, Rutgers University

Eric Rasmusen, Indiana University, erasmuse@indiana.edu
Michael Rothkopf, Rutgers University, rothkopf@rutcor.rutgers.edu
Tuomas Sandholm, Carnegie Mellon University, sandholm+@cs.cmu.edu
Presented under the auspices of the Special Focus on Computation and the Socio-Economic Sciences.


Larry Ausubel, University of Maryland

Title: The Hungarian Auction

In auctioning a homogeneous good, may the seller ever find it desirable to convert the product being sold into a heterogeneous good (e.g., by dividing the product into small lots and large lots)? This paper provides an affirmative answer, by illustrating economic environments where efficiency and/or revenues may thereby be enhanced. In the process, the paper also motivates and develops an auction design that has been used for the auctioning of natural gas in Hungary.

Dirk Bergemann, Yale Dept. of Economics

Title: Efficient Dynamic Auctions

We consider the truthful implementation of the socially efficient allocation in a dynamic private value environment in which agents receive private information over time. We show that a suitable generalization of the Vickrey-Clark-Groves mechanism, based on the marginal contribution of each agent, leads to truthtelling in every period. A leading example of a dynamic allocation model is the sequential auction of a single good in which the current winner of the object receives additional information about her valuation. We show that a modified sequential second price auction in which only the current winner makes a positive payment leads to truthtelling. In general allocation problems, the marginal contribution mechanism continues to induce truthtelling in every period but may now include positive transfers for many agents.

Complete abstract

Jason Hartline

Title: Money Burning and Implementation

Complete abstract

Ronald Harstad, University of Missouri Economics

Title: Endogenous Competition Alters the Structure of Optimal Auctions

Potential bidders respond to a seller's choice of auction mechanism for a common-value or affiliated-values asset by endogenous decisions whether to incur a participation cost (and observe a private signal), or forego competing. Privately informed participants decide whether to incur a bid-preparation cost and pay an entry fee, or cease competing. Auction rules and information flows are quite general; participation decisions may be simultaneous or sequential. The resulting revenue identity for any auction mechanism implies that optimal auctions are allocatively efficient; a nontrivial reserve price is revenue-inferior for any common-value auction. Optimal auctions are otherwise contentless: any auction that sells without reserve becomes optimal by adjusting any one of the continuous, spanning parameters, e.g., the entry fee. Sellers' surplus-extracting tools are now substitutes, not complements. Many econometric studies of auction markets are seen to be flawed in their identification of the number of bidders.

Complete abstract

Otto Koppius

Title: The Need for Speed: Non-Price Considerations in Auction Design at the Dutch Flower Auctions

Most work on auction design takes as starting point that the auction designer wants to maximize his selling price. However, in many empirical settings, auction transactions are part of a larger business process that may impose additional and sometimes conflicting demands on the transaction process. For instance in auctions for perishable products such as flowers, the speed of the auction becomes a paramount concern in order to get the product to the end-customer as fast as possible. We analyze several auction design choices at the Dutch Flower Auctions that, although suboptimal from a purely price- optimizing perspective, can be explained by taking into account the impact of those choices on the other business processes, in particular the speed of the logistical process.

Kate Larson

Title: Reducing Costly Information Acquisition in Auctions

Most auction research assumes that potential bidders have private information about their willingness to pay for an item. In reality, bidders often have to go through a costly information-gathering process in order to learn their valuations. Recent attempts at modelling this phenomena has brought to light complex strategic behaviour arising from information-gathering, and has shown that traditional approaches to auction and mechanism design are not able to overcome it.

Thayer Morrill, University of Maryland

Title: The Stable Roommates Problem Revisited

One of the oldest but least understood matching problems is the "roommates problem": is there a stable way to assign 2N students into N roommate pairs? Unlike the classic marriage and college admissions problems, there need not exist a stable solution to the roommates problem. However, the traditional notion of stability ignores a key physical constraint -- that roommates require a room -- and it is therefore too restrictive. With a new definition of stability, which incorporates the scarcity of rooms, this paper proves that a stable assignment always exists and provides an efficient algorithm for finding one. In this way, a classic matching problem, which previously had no general solution, becomes both solvable and economically more meaningful.

David Parkes, Harvard University

Title: Efficient Meta-Deliberation Auctions

We consider a resource allocation problem in a multi-agent system with deliberative agents. A finite set of resources are available to allocate to a population of agents. Each agent has available a costly deliberation process with which it can deliberate about how to best use the resources and thus maximize its value for a given allocation. Each agent has a private model of its own deliberation process, where this model describes its cost for deliberation and its belief about how deliberation will improve its plan for how to use resources and therefore improve its ultimate value for an allocation. One convenient representation of this information is as a "performance profile tree."

The social objective is to design a deliberation schedule that optimally, in the sense of maximizing expected total value net of deliberation cost, interleaves deliberation across agents before terminating with a final allocation decision. We assume here that no more deliberation takes place once resources are allocated and that the final agent plans are executed. We frame this as a problem in mechanism design and discuss the merits of adopting a dynamic Vickrey- Clarke-Groves mechanism to implement the social objective.

Part of our interest here is in pushing an agenda in multi-agent metadeliberation. While single agent metadeliberation is quite well studied within artificial intelligence, there are few algorithms for optimal multi-agent metadeliberation even in cooperative multi-agent systems. We will discuss whether progress in multi-agent metadeliberation can be effectively leveraged within the active mechanism design agenda of expanding the reach of mechanisms so that they are actively involved in the coordination of information acquisition (and here in agent deliberation).

Eric Rasmusen, Indiana University Business Economics

Title: Getting Carried Away in Auctions as Imperfect Value Discovery

Bidders have to decide whether and when to incur the cost of estimating their own values in auctions. This can explain sniping-- flurries of bids late in auctions with deadlines-- as the result of bidders trying to avoid stimulating other bidders into examining their bid ceiling more carefully.

Getting Carried Away in Auctions as Imperfect Value Discovery

Strategic Implications of Uncertainty over One's Own Private Value in Auctions

Tuomas Sandholm, Carnegie Mellon University

First Talk Title: Overview of our work on costly valuation computation/information acquisition in auctions:
Strategy, counterspeculation, and deliberation equilibrium

Issues in Computational Vickrey Auctions

Costly Valuation Computation in Auctions

Computationally Limited Agents in Auctions

Experiments on Deliberation Equilibria in Auctions

Mechanism Design and Deliberative Agents

Tuomas Sandholm, Carnegie Mellon University

Second Talk Title: Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges

Complete abstract

David Thompson, Lab for Computational Intelligence, UBC

Title: Valuation Uncertainty and Imperfect Introspection in Second-Price Auction

In auction theory, agents are typically presumed to have perfect knowledge of their valuations. In practice, though, they may face barriers to this knowledge due to transaction costs or bounded rationality. Modeling and analyzing such settings has been the focus of much recent work, though a canonical model of such domains has not yet emerged. We begin by proposing a taxonomy of auction models with valuation uncertainty, and showing how it categorizes previous work. We then restrict ourselves to single-good sealed-bid auctions, in which agents have (uncertain) independent private values and can introspect about their own (but not others') valuations through possibly costly and imperfect queries. We investigate second-price auctions, performing equilibrium analysis for cases with both discrete and continuous valuation distributions. We identify cases where every equilibrium involves either randomized or asymmetric introspection. We contrast the revenue properties of different equilibria, discuss steps the seller can take to improve revenue, and identify a form of revenue equivalence across mechanisms.

Complete abstract

Zhixi Wan and Damian R. Beil

Title: RFQ Auctions with Supplier Qualification Screening

Complete abstract

Okan Yilankaya, University of British Columbia

Title: Optimal Auctions with Participation Costs

We study the optimal auction problem with participation costs in the symmetric independent private values setting, where bidders know their valuations when they make independent participation decisions. After characterizing the optimal auction in terms of participation cut-off, we provide an example where it is asymmetric. We then inves- tigate when the optimal auction will be symmetric/asymmetric and the nature of possible asymmetries. We also show that, under some conditions, the seller obtains her maximal profit in an (asymmetric) equilibrium of an anonymous second price auction. In general, the seller can also use non-anonymous auctions that resemble the ones that are actually observed in practice.

Complete abstract

Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on March 19, 2007.