Approximately maximizing efficiency and revenue in polyhedral environments
Approximately maximizing efficiency and revenue in polyhedral environments
复制标题
在多面体环境中近似最大化效率和收入
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
É. Tardos
中科院分区：
文献类型：
--
作者：
T. Nguyen;É. Tardos
我们考虑多面体环境中的资源分配博弈。多面体环境模拟了一系列的问题，包括带宽共享、Adword拍卖的一些模型和一般资源分配。我们扩展了这类资源分配博弈的公平分享机制。我们证明了我们的机制同时创造了近似有效的配置和近似最大化的收益。我们还开发了一种新的方法来分析这些类型的游戏。这种方法的核心是博弈的纳什均衡条件与某一线性规划的对偶之间的关系。
We consider a resource allocation game in polyhedral environments. Polyhedral environments model a wide range of problems, including bandwidth sharing, some models of Adwords auctions and general resource allocation. We extend the fair sharing mechanism for such resource allocation games. We show that our mechanism simultaneously creates approximately efficient allocations andallapproximately maximizes revenue. We also develop a new approach for analyzing games of these types. At the core of this approach is the relation between the condition for Nash equilibriums of the game and the dual of a certain linear program.