A combinatorial auction is an auction where bidders can buy (or sell) entire bundles of goods in a single transaction. Although computationally very complex, selling items in bundles has the great advantage of eliminating the risk for a bidder of not being able to obtain complementary items at a reasonable price in a follow-up auction (think of a combinatorial auction for a pair of shoes, as opposed to two consecutive single-item auctions for each of the individual shoes). This talk introduces a generalisation of the standard model of combinatorial auctions and discusses the issues of bidding and winner determination.
Winner determination is the problem, faced by the auctioneer, of choosing which goods to award to which bidder so as to maximise its revenue. Bidding is the process of transmitting one's valuation function over the set of goods on offer to the auctioneer. In principle, it does not matter how the valuation function is being encoded, as long as sender (bidder) and receiver (auctioneer) agree on the semantics of what is being transmitted, i.e. as long as the auctioneer can understand the message(s) sent by the bidder. In practice, however, the choice of bidding language is of central importance. Early work on combinatorial auctions has typically ignored the issue of bidding languages. The standard assumption used to be that if a particular bidder submits several atomic bids (a bundle together with a proposed price), then the auctioneer may accept any set of bids from that bidder for which the bundles do not overlap, and charge the sum of the specified prices.
This is now sometimes called the OR-language. But other interpretations of a set of atomic bids are possible. For instance, we may take it to mean that the auctioneer may accept at most one bid per bidder; this is now known as the XOR-language. Previous work in the field of bidding languages covers languages for direct single-unit combinatorial auctions. That is, the auctioneer is selling (rather than buying) goods, and all goods are distinguishable. Our first aim in this talk is to generalise this to multi-unit combinatorial auctions. As a second generalisation, we show how to integrate direct and reverse auctions, i.e. the auctioneer will be able to both sell and buy goods within a single auction. As a third and final generalisation, we are going to show how to integrate the idea of transformability relationships between goods into our auction model. For instance, if the auctioneer is interested in obtaining cars, but is also able to transform various components into a working car (at a certain cost), then it may solicit bids offering both ready-made cars and individual components. We further extend the idea of these transformability relationships by allowing agents to also bid for transformation services, i.e. an agent may submit a bid offering to transform a certain set of goods into another set of goods. We call the resulting auction model mixed multi-unit combinatorial auctions (MMUCA). These are not to be confused with double auctions. In particular, the order in which agents consume and produce goods is of central importance in our model and affects the definition of the winner determination problem.
Andrea Giovannucci, male and Italian citizen, was born in Bellano, Italy, on March, the 8t, 1976. He took his graduation in Electronic Engineering with mathematical-physical specialization at the Politecnico di Milano, Milan. He is actually a last year PhD student within the Electronic Institution Group at the Artificial Intelligence Research Institute of Bellaterra, Spain. His research interests focus on combinatorial optimization and combinatorial auctions for supply chain formation. He is a visiting researcher at the University of Southampton within the IAM group until December, the 19th, 2006.