论文标题
多商品流游戏无需支付的经验核心
The Empirical Core of the Multicommodity Flow Game Without Side Payments
论文作者
论文摘要
政策制定者专注于稳定的策略，因为理性参与者采用了策略。如果有许多这样的解决方案，那么一个重要的问题是如何在其中选择。我们研究了多商品流程联盟游戏的这个问题，用于建模互联网中自动群体（AS）之间的合作。简而言之，策略是电容网络中的流动。节点的回报是终止的总流量。 Markakis-Saberi表明此游戏是平衡的，因此围巾定理具有非空的核心。在可转移的实用程序（TU）版本中，这给出了多项式时间算法以查找核心元素，但是对于屁股侧支付并不自然。在NTU游戏中找到核心元素往往更加困难。对于此游戏，唯一的结果给出了一个过程，可以在供应图是一条路径时找到核心元素。我们通过合并算法扩展了他们的工作，该算法产生了许多不同的核心元素。 我们使用算法通过生成许多核心向量来评估特定实例。我们将这些称为游戏的经验核心。我们发现，采样核心向量在社会福利（SW）方面比公平（最低支出）更一致。对于SW，它们往往会和最佳线性程序值$ LP_ {SW} $一样。相比之下，经验核心的公平性范围更大。公平值往往比最佳公平性LP值$ LP_ {fair} $更糟糕。我们研究了具有单冲洗需求的一般图表的环境。在这种情况下，我们提供了一种算法，该算法会产生同时最大化SW和公平性的核心向量。这导致了一般游戏的以下两批位结果。给定任何产生核心的算法和（0,1）$中的任何$λ\，一个人可以至少$λlp_{fair} $（reves $（1-λ）lp_ {sw} $）产生近似核心向量（分别社会福利）。
Policy makers focus on stable strategies as the ones adopted by rational players. If there are many such solutions an important question is how to select amongst them. We study this question for the Multicommodity Flow Coalition Game, used to model cooperation between autonomous systems (AS) in the Internet. In short, strategies are flows in a capacitated network. The payoff to a node is the total flow which it terminates. Markakis-Saberi show this game is balanced and hence has a non-empty core by Scarf's Theorem. In the transferable utility (TU) version this gives a polynomial-time algorithm to find core elements, but for ASs side payments are not natural. Finding core elements in NTU games tends to be computationally more difficult. For this game, the only previous result gives a procedure to find a core element when the supply graph is a path. We extend their work with an algorithm, Incorporate, which produces many different core elements. We use our algorithm to evaluate specific instances by generating many core vectors. We call these the Empirical Core for a game. We find that sampled core vectors are more consistent with respect to social welfare (SW) than for fairness (minimum payout). For SW they tend to do as well as the optimal linear program value $LP_{sw}$. In contrast, there is a larger range in fairness for the empirical core; the fairness values tend to be worse than the optimal fairness LP value $LP_{fair}$. We study this discrepancy in the setting of general graphs with single-sink demands. In this setting we give an algorithm which produces core vectors that simultaneously maximize SW and fairness. This leads to the following bicriteria result for general games. Given any core-producing algorithm and any $λ\in (0,1)$, one can produce an approximate core vector with fairness (resp. social welfare) at least $λLP_{fair}$ (resp $(1-λ) LP_{sw}$).
