Contribution Games in Networks
Contribution Games in Networks
复制标题
DOI：
10.1007/s00453-011-9520-7
复制
发表时间：
2010-04
期刊：
影响因子：
1.1
通讯作者：
Elliot Anshelevich;M. Hoefer
中科院分区：
文献类型：
--
作者：
Elliot Anshelevich;M. Hoefer
我们考虑网络贡献游戏，其中网络中的每个代理都有一个努力预算，他可以为不同的协作项目或关系做出贡献。根据所涉及代理的贡献，关系将蓬勃发展或淹没，并且为了衡量成功，我们对每个关系使用奖励函数。每个代理都试图从它所涉及的所有关系中最大化奖励。我们考虑这个博弈的成对均衡，并根据所涉及的奖励函数的类型来描述均衡的存在性、计算复杂性和质量。当所有奖励函数都是凹函数时，我们证明无政府状态的代价至多为 2。对于凸函数，同样的情况仅在某些特殊但非常自然的条件下成立。广泛讨论的另一个特殊情况是最小努力游戏，其中关系的回报仅取决于任何参与者的最小努力。在这些博弈中，我们可以证明凹函数和具有凸函数的特殊博弈类存在成对均衡和无政府状态价格 2。最后，我们展示了这些博弈中近似均衡和动力学收敛的严格界限。
We considernetwork contribution games, where each agent in a network has a budget of effort that he can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved. When all reward functions are concave, we prove that the price of anarchy is at most 2. For convex functions the same only holds under some special but very natural conditions. Another special case extensively treated are minimum effort games, where the reward of a relationship depends only on the minimum effort of any of the participants. In these games, we can show existence of pairwise equilibrium and a price of anarchy of 2 for concave functions and special classes of games with convex functions. Finally, we show tight bounds for approximate equilibria and convergence of dynamics in these games.