DP15831 Strong Substitutes: Structural Properties, and a New Algorithm for Competitive Equilibrium Prices
We show the Strong Substitutes Product-Mix Auction (SSPMA) bidding language provides
an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets
that are easy to identify.We prove that competitive equilibrium prices for agents with strong substitutes
preferences can be computed by minimizing the difference between two linear programs for the positive
and the negative bids with suitably relaxed resource constraints. This also leads to a new algorithm
for computing competitive equilibrium prices which is competitive with standard steepest descent
algorithms in extensive experiments.