Wolfram Conen and Tuomas Sandholm
Auctions and exchanges are important coordination mech-anisms for multiagent systems. Most multi-good markets are combinatorial in that the agents have preferences over bundles of goods. We study the possibility of determining prices so as to support (efficient) allocations in combinatorial economies where a seller (or arbitrator) wants to implement an efficient allocation. Conditions on the existence of equi-libria are presented and a particularly attractive, anonymous pricing scheme is studied in detail. A constructive test for the existence of supporting prices is given. A procedure based on the controlled formation of alliances is suggested that shrinks economies to ensure the existence of prices coherent with the preferred pricing scheme. The relation of equilibrium prices to Vickrey payments is considered, and extensions to two-sided markets are discussed.