资源论文Digital Good Exchange

Digital Good Exchange

2019-11-25 | |  58 |   36 |   0
Abstract Over the past decade, computer-automated barter exchange has become one of the most successful applications at the intersection of AI and economics. Standard exchange models, such as house allocation and kidney exchange cannot be applied to an emerging industrial application, coined digital good exchange, where an agent still possesses her initial endowment after exchanging with others. However, her valuation toward her endowment decreases as it is possessed by more agents. We put forward game theoretical models tailored for digital good exchange. In the first part of the paper, we first consider a natural class of games where agents can choose either a subset of other participants’ items or no participation at all. It turns out that this class of games can be modeled as a variant of congestion games. We prove that it is in general NP-complete to determine whether there exists a non-trivial pure Nash equilibrium where at least some agent chooses a nonempty subset of items. However, we show that in a subset of games for single-minded agents with unit demand, there exist non-trivial Pure Nash equilibria and put forward an efficient algorithm to find such equilibria. In the second part of the paper, we investigate digital good exchange from a mechanism design perspective. We ask if there is a truthful mechanism in this setting that can achieve good social welfare guarantee. To this end, we design a randomized fixed-price-exchange mechanism that is individually rational and truthful, and for two-player case yields a tight log-approximation with respect to any individually rational allocation.

上一篇:To Give or Not to Give: Fair Division for Single Minded Valuations

下一篇:Role Assignment for Game-Theoretic Cooperation

用户评价
全部评价

热门资源

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...