Pricing Valid Cuts for Price-Match Equilibria

Abstract

We use valid inequalities (cuts) of the binary integer program for winner determination in a combinatorial auction (CA) as "artificial items" that can be interpreted intuitively and priced to generate Artificial Walrasian Equilibria. While the lack of an integer programming gap is sufficient to guarantee a Walrasian equilibrium, we show that it does not guarantee a "price-match equilibrium" (PME), a refinement that we introduce, in which prices are justified by an iso-revenue outcome for any hypothetical removal of a single bidder. We prove the existence of PME for any CA and characterize their economic properties and computation. We implement minimally artificial PME rules and compare them with other prominent CA payment rules in the literature.

Tasks

Reproductions