Digital Good Exchange / 264
Wenyi Fang, Pingzhong Tang, Song Zuo

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.

PDF