A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications

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, cloud computing, and communicating over a network. This model is quit...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-04
Main Authors: Devanur, Nikhil, Garg, Jugal, Mehta, Ruta, Vazirani, Vijay V, Sadra Yazdanbod
Format: Article
Language:English
Subjects:
Algorithms
Cloud computing
Combinatorial analysis
Communication
Economic models
Equilibrium
Graph algorithms
Markets
Optimization
Polynomials
Pricing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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, cloud computing, and communicating over a network. This model is quite different from the traditional models, 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 equilibria seem to apply directly. We give a proof of existence of equilibrium and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. We observe that in our market model, the set of equilibrium prices could be a connected, non-convex set. To the best of our knowledge, this is the first natural example of the phenomenon where the set of solutions could have such complicated structure, yet there is a combinatorial polynomial time algorithm to find one. Finally, we show that our model inherits many of the fairness properties of traditional equilibrium models.
ISSN:2331-8422