针对网上资源分配机制设计的统一方法(cs.GT)---用户7199428

这篇论文是关于网上资源分配在战略制定方面的机制设计。在该设定中，一个单独的供应者通过分配有限量的资源以求资源以顺序任意的方式到达。代理者则与每一个请求息息相关。代理者有可能以利己主义的方式误报自己的需求和评估。供应者在代理者的需求得到满足以后，将会收取一定的费用，但是这也会带来由负荷而定的供应成本。目标是设计一个激励相容的在线机制，该机制的主导因素将不再仅仅是针对每个请求的资源分配，并且还要考虑到代理人的报偿，来近似最大化整体利润（总值-供应成本）。我们在竞争分析的框架下研究此问题，而这篇论文最大的贡献就在于，研究出了一个统一的方法用于基于不同的供应成本获取最优竞争比。具体来说，当不存在供应成本，亦或是供应成本线性分布时，我们模型本质上就成了一个0-1背包问题，并且我们的方法将活得一个对数级的竞争比，这是与世界前沿水平相当的（最优情况）。相对于更富有挑战性的假设：当供应成本为严格凸函数时，我们的线上机制也会首次产生一个最优的竞争比。据我们所知，这也是第一个在不同的供应成本：0，线性和严格凸函数下，将网上资源分配最优竞争比的特征描述统一化的方法。

原文题目：Mechanism Design for Online Resource Allocation: A Unified Approach

原文This paper concerns the mechanism design for online resource allocation in a strategic setting. In this setting, a single supplier allocates capacity-limited resources to requests that arrive in a sequential and arbitrary manner. Each request is associated with an agent who may act selfishly to misreport the requirement and valuation of her request. The supplier charges payment from agents whose requests are satisfied, but incurs a load-dependent supply cost. The goal is to design an incentive compatible online mechanism, which determines not only the resource allocation of each request, but also the payment of each agent, so as to (approximately) maximize the social welfare (i.e., aggregate valuations minus supply cost). We study this problem under the framework of competitive analysis. The major contribution of this paper is the development of a unified approach that achieves the best-possible competitive ratios for setups with different supply costs. Specifically, we show that when there is no supply cost or the supply cost function is linear, our model is essentially a standard 0-1 knapsack problem, for which our approach achieves logarithmic competitive ratios that match the state-of-the-art (which is optimal). For the more challenging setup when the supply cost is strictly-convex, we provide online mechanisms, for the first time, that lead to the optimal competitive ratios as well. To the best of our knowledge, this is the first approach that unifies the characterization of optimal competitive ratios in online resource allocation for different setups including zero, linear and strictly-convex supply costs.

原文作者：Xiaoqi Tan, Bo Sun, Alberto Leon-Garcia, Yuan Wu, Danny H.K. Tsang

原文地址：https://arxiv.org/abs/2004.09640