A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications
复制标题
一类具有覆盖约束的新型组合市场：算法和应用
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sadra Yazdanbod
中科院分区：
文献类型：
--
作者：
Nikhil R. Devanur;J. Garg;R. Mehta;V. Vazirani;Sadra Yazdanbod
我们引入了一类新的组合市场中，代理覆盖所需的资源的限制，并有兴趣在延迟最小化。我们的市场模型适用于多种设置，包括调度和通过网络进行通信。这个模型与传统的模型有很大的不同，在某种程度上，经典的平衡存在性结果似乎既不适用于它，也不适用于任何有效的算法技术来计算平衡。特别是，我们的模型不满足条件的非饱和，这是关键用于显示在传统的市场模型中的均衡的存在，我们观察到，我们的一组均衡价格可以是一个连接，非凸集。我们给出了一个证明的存在的平衡和多项式时间算法找到一个，借鉴大量的技术从LP对偶和次模最小化。最后，我们表明我们的模型继承了传统均衡模型以及CEEI等新模型的许多公平性。
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 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. 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 polynomial 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 fairness properties of traditional equilibrium models as well as new models, such as CEEI.