A new class of combinatorial markets with covering constraints: Algorithms and applications

Nikhil R. Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling and communicating over a network. This model is quite different from the traditional mod-els, to the extent that neither do the classical equilibrium existence results seem to apply to it nor do any of the efficient algorithmic techniques developed to compute equilib-ria. In particular, our model does not satisfy the condition of non-satiation, which is used critically to show the existence of equilibria in traditional market models and we observe that our set of equilibrium prices could be a connected, non-convex set. We give a proof of the existence of equilibria and a poly-nomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. Finally, we show that our model inherits many of the fair-ness properties of traditional equilibrium models as well as new models, such as CEEI.

Original languageEnglish (US)
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsArtur Czumaj
PublisherAssociation for Computing Machinery
Pages2311-2325
Number of pages15
ISBN (Electronic)9781611975031
DOIs
StatePublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
CountryUnited States
CityNew Orleans
Period1/7/181/10/18

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A new class of combinatorial markets with covering constraints: Algorithms and applications'. Together they form a unique fingerprint.

Cite this