Analysing Product-Mix Auctions by Linear Programs

Speaker
Omer Edhan
Date
07/11/2017 - 13:00 - 11:30Add To Calendar 2017-11-07 11:30:00 2017-11-07 13:00:00 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. Economics building (504), faculty lounge on the first floor אוניברסיטת בר-אילן - Department of Economics Economics.Dept@mail.biu.ac.il Asia/Jerusalem public
Place
Economics building (504), faculty lounge on the first floor
Affiliation
Manchester University
Abstract

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.

Last Updated Date : 04/12/2022