Scalable and Expressive Iterative Combinatorial Exchanges

Combinatorial auctions (CAs) allow one seller to allocate a collection of heterogeneous and discrete goods to multiple buyers, each of which may have complex valuations, e.g. "I only want A if I get B" , "I only want A or B", etc. Yet, many real world problems (such as resource allocation on Federated systems like PlanetLab) are more naturally two-sided, with multiple buyers and sellers. Combinatorial Exchanges (CEs) extend CAs to this two-sided setting. In this talk, I outline three key components in our exchange design: a tree-based bidding language, adaptive preference elicitation, and a payment rule to promote simple and truthful bidding. In moving towards a deployment of such a market for computational resources, I discuss some of the wider, institutional and technological, issues that must be addressed. In closing, I mention some additional directions in computational mechanism design that will impact resource allocation and arbitration in real systems.