Algorithms for Winner determination and Precification problems in combinatorial Auctions

Abstract

Auctions are considered the most general way to allocate and to pricing of goods and services when it is not know the real value of them. Traditionally in an auction, it is negotiated a item or group of items where the agents involved, known as bidders, can only submit bids on one item or a package of items. This type of trading may not lead to economic efficiency of the market because the bidders may not be able to express their preferences completely. To work around this issue, the combinatorial auctions allow bidders to submit multiple bids for different subsets of items, not necessarily disjoint, and thus can express complementarity and substitutability among the items they want. The challenges of these types of auctions are the size of instances that are usually exponential in the number of bids made, and the winner determination problem that is NP-hard (even with a polynomial input), which requires a large computational effort. We are interested in the recent strategies to address these problems, such as specialized exact algorithms and heuristics that can ensure desirable economic properties, such as certain euiqlibria and fair pricing. For this, we propose the research and development of exact methods and heuristics, discussion and comparison with recent results from the literature, as well as computational experiments to prove the effectiveness and efficiency of the methods. (AU)