A combinatorial auction (CA) 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). The study of the mathematical, game-theoretical and algorithmic properties of combinatorial auctions has recently become a popular research topic in AI. This is due not only to their relevance to important application areas such as electronic commerce or supply chain management, but also to the range of deep research questions raised by this auction model. In our work [1] we introduce a generalisation of the standard model of combinatorial auctions and discuss 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 .
Nisan’s survey article [3], the reference 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 [1] 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 generalisation, we show how to integrate the idea of transformability relationships between goods into our auction model [2]. 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. As a fourth generalisation, we 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). We should stress that there are important differences between our mixed auctions and models known as double auction or combinatorial exchanges [4]. The most important difference is that these models do not have the concept of a sequence of exchanges, which is required if the intention is to model some sort of production process.
MMUCAs extend the idea of combinatorial auctions for supply chain formation (SCF) originally introduced in [5] by Walsh et al.. Walsh et al. observe that production technologies often have to deal with strong complementarities: the inputs and outputs of a production process are strongly connected since a producer may risk to produce unsold goods as well as fail to produce already sold goods when failing to obtain the inputs, thus losing credibility on the market. Hence, a supply chain can be regarded as an intricate network of producers (entities transforming input goods into output goods at a certain cost), suppliers (entities introducing goods into the market) and consumers interacting in a complex way. Nevertheless, the complementarities arising in SCF are different from the ones we do find in CAs. The complementarities in SCF arise because of the preconditions and postconditions of production processes: precedences and dependences along the supply chain must be taken into account. Hence, whilst in CAs the complementarities can be simply represented as relationships among goods, in SCF the complementarities involve not only goods, but also interrelated transformation (production) relationships along several levels of the supply chain. Although Walsh et al. contribution is very significant, it could be extended along three dimensions. Firstly, they do not allow a provider to submit bids on combinations of transformations. Secondly, they do not define a bidding language (in fact, their agents submit a bid with a single transformation each). Finally, the transformation net that defines the supply chain has to fulfil strict criteria: acyclicity, transformations can only produce one output good, etc. This paper mainly adopts a game-theoretic perspective, and thus does not address either the WDP or bidding languages in depth.
In [1] we formally define a bidding language extending several previous languages, and we provide an Integer Programming solver for the MMUCA WDP. First, we demonstrate that the XOR-language is fully expressive over finitely-peaked valuations for MMUCA. Then, we mathematically model the concept of sequence of transformations by introducing a decision variable for each transformation and its possible positions in the sequence of transformations. For instance, say we have five possible transformations, then the maximum length of the revenue maximizing solution sequence will be 5. We create a decision variable for each transformation and each possible position in the solution sequence.
Future work should address the expressive power of different fragments of the bidding language and compare the succinctness of different fragments for certain classes of valuations: which languages can express what valuations, and which languages can do so using less space than others? For the case of direct single-unit combinatorial auctions, several such results are given by Nisan [3], and some of these results may be relatively easy to transfer to our model. Another interesting question to consider in future work would be what exactly the auctioneer should announce when opening an MMUCA. In the case of direct auctions this is the set of goods to be sold. If bidding for transformations is possible, however, it may be difficult to foresee what types of goods will be relevant to a solution, as this depends on the transformation capabilities of the bidders in the market. Time is an important dimension that is not considered in our model at the moment. Therefore, a promising development could be studying a possible extension of MMUCA allowing for the expression of time deadlines and production processes duration directly into the bidding language. Finally, our work also poses a computational challenge since the number of variables of our IP grows quadratically with the number of transformations mentioned in the bids. Thus, we plan to investigate the use of special-purpose or local algorithms.
References