A Globally Convergent Alternating One-Track Auction for Gross Substitutes and Complements

We propose a new globally convergent dynamic auction for selling multiple indivisible items. There are two sets of items, items in each set can be heterogenous but are substitutes, and items across the two sets are complements. Each bidder may demand several items. In each round of the auction, every bidder reports his demand of items at the current prices and the auctioneer responds by either increasing prices or exclusively decreasing prices. We show that the auction converges globally to a Walrasian equilibrium