Constrained multi-object auctions and b-matching
Auctions become a most popular tool in various computational and e-commerce settings. Most auction theory deals either with auctions of a single object, or with multi-object setups where each good is sold by an independent auction. However, multi-object auctions might not satisfy such independence assumptions, either because the agents' valuations for the allocation of goods might be non-additive, or because there are (social) constraints on the set of possible allocations. In such cases the determination of an optimal allocation of the goods is a nontrivial computational problem. Some recent work in Operations Research (OR) and Artificial Intelligence (AI) have dealt with computational aspects of multi-object auctions, and relates to the non-additive nature of valuations. This paper deals with the complementary part, where there are simple constraints on the possible allocations of goods. We deal with the complexity of constrained multi-object auctions, and expose a connection of the related computational problem with the optimal b-matching problem. In particular, we show that a basic variant of the constrained multi-object auction is polynomially solvable. Then we deal with two natural extensions of this basic problem; we prove the NP-hardness of one of them and use b-matching techniques for presenting a polynomial algorithm for the other. (C) 2000 Elsevier Science B.V. All rights reserved.
auctions algorithms combinatorial problems matchings