We show that a competitive equilibrium always exists in combinatorial auctions with anonymous graphical valuations and pricing, using discrete geometry. This is an intuitive and easy-to-construct class of valuations that can model both complementarity and substitutes, and to our knowledge, it is the first class besides gross substitutes that have guaranteed competitive equilibrium. We prove through counter-examples that our result is tight, and we give explicit algorithms for constructive competitive pricing vectors. We also give extensions to multi-unit combinatorial auctions (also known as product-mix auctions). Combined with theorems on graphical valuations and pricing equilibrium of Candogan, Ozdagar and Parrilo, our results indicate that quadratic pricing is a highly practical method to run combinatorial auctions.
翻译:我们通过反证证明我们的成果是紧密的,我们给出了具有建设性竞争性定价矢量的明确算法。我们还延长了多单元组合拍卖(也称为产品混合拍卖 ) 。 加上Candogan、Ozdagar和Parrilo的图形估值和定价平衡理论,我们的结果表明,二次定价是一种非常实用的组合拍卖方法。