Analysing Product-Mix Auctions by Linear Programs

Paper: https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxvbWVyZWRoYW58Z3g6NzFlMmUyM2ZkMjc4ZTM0Nw

Existence of competitive equilibrium with indivisible goods in TU markets is reduced to integer linear programming. Thus, we extend the ``unimodularity theorem", suggested in Baldwin and Klemperer's seminal paper, to more general utilities and constraint, including budget sets which were not previously considered. Essentially, equilibrium existence with indivisibles follows from its existence in a ``divisible market", with unimodularity assuring it is integer valued. We advance beyond unimodularity, studying equilibrium existence in general markets with concave valuations and only feasibility constraints. Again, this problem is well understood within the framework of integer linear programming. We give a necessary and sufficient condition for an equilibrium to exist, in terms of a decomposition into unimodular building blocks. While competitive equilibrium computation turns out to be NP-hard, existence turns out to be in P.