Research Project

Optimal Mechanisms for Efficient Broadcast Auctions with Costly Actions

Speaker:Yuqian Li
yuqian at
Date: Friday, May 11, 2012
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke
Kamesh Munagala, Aleksandar Pekec


Online second-hand transactions (or auctions) are very popular, including examples such as eBay, mailing lists, craigslist and so on. In spite of their convenience, current mechanisms are mainly first-come first-served mechanisms, which are not good in efficiency (allocating items to the buyers with the highest value) or revenue (maximizing revenue to sellers). Thus the question is: is there a better mechanism for this kind of application and whatís the optimal one among them.

We firstly characterize these applications. Broadcast capability and costly actions are properties of many Internet applications. Being efficient is also important. It not only maximizes social welfare, but also maximizes the sellerís revenue if he/she cannot commit to withholding the item (which is common for many moving-sale applications) or prevent re-sale between buyers [2].

Then we model and analyze some mechanisms. Itís proved that one class of mechanisms are optimal among all mechanisms in terms of minimizing the cost. We further discover that minimizing the cost is very related to increasing the revenue. This might give us good insight into why sellers prefer simple first-come first served mechanisms to theoretically revenue-optimal mechanisms such as the Myerson auction [4]. The key is that traditional works either overlook the cost or oversimplify the cost so they no longer apply to Internet applications very well. By better modeling the cost and discovering relationships between cost and revenue, we may be able to design a significantly better mechanism.

Advisor(s): Vincent Conitzer