Robust Equilibria in Shared Resource Allocation via Strengthening Border's Theorem
David X. Lin, Siddhartha Banerjee, Giannis Fikioris, Éva Tardos
我们考虑通过非货币机制反复分配共享资源,其中单个项目必须分配给每轮中的多个代理之一。 我们假设每个代理都有跨轮的项目的 i.i.d. 值,以及附加实用程序。 过去在这个问题上的工作已经提出了机制,代理商可以获得两种保证之一:(i)(近似)贝叶斯-纳什均衡通过基于链接的机制,需要广泛的价值分布知识,以及(ii)简单的分布无关机制,为每个个体代理提供强大的实用保证,这些保证比纳什结果差,但无论其他人的行为如何(包括可能具有勾结行为)都要保持。 最近的工作暗示了同时实现这两个目标的障碍。 然而,我们的工作证明并非如此,通过提出第一个机制,其中每个代理都有自然策略,既是一种贝叶斯 - 纳什平衡,也附带对单个代理公用事业的有力保证。 我们的机制源于在线共享资源分配问题与实施理论之间的惊人联系。 特别是,我们表明,在这种设置中建立稳健的均衡性会降低为显示边界多拓扑的某个特定子集是非空的。 我们通过一个新的联合舒尔-凸率论点来建立这一点。 加强边界取得更有力结论的标准具有独立的技术利益,因为它在其他情况下可能证明是有用的。
We consider repeated allocation of a shared resource via a non-monetary mechanism, wherein a single item must be allocated to one of multiple agents in each round. We assume that each agent has i.i.d. values for the item across rounds, and additive utilities. Past work on this problem has proposed mechanisms where agents can get one of two kinds of guarantees: (i) (approximate) Bayes-Nash equilibria via linkage-based mechanisms which need extensive knowledge of the value distributions, and (ii) ...