The Power and Limits of Money Burning in Bilateral Trade
Moshe Babaioff, Noam Nisan, Ariel Shaulker
原文摘要
We study the power of money burning in bilateral trade. In this problem, a seller owns an indivisible item, a buyer would like to acquire it, and each of these two traders has a private value for the item and the values are sampled from independent distributions. We ask whether the traders can benefit from a mechanism that burns money, that is, one that charges the buyer more than it pays the seller, so that neither trader enjoys the difference (money burnt is a loss for the traders). Is it possible that the traders will ever be better off if the trade mechanism can burn money? For Bayesian incentive-compatible mechanisms and for deterministic dominant-strategy incentive-compatible (DSIC) mechanisms, it is known that money burning is always a waste and can only hurt the traders. Maybe surprisingly, we show that once a DSIC mechanism can use randomization, money burning can significantly benefit the traders, and the gain of each of them can be arbitrarily large. In contrast, we show that the power of DSIC randomized mechanisms that burn money is still very limited in the sense that they cannot guarantee any constant fraction of the first-best gains-from-trade.
cs.GT