Explicit Payments for Obviously Strategyproof Mechanisms

The design of mechanisms where incentives are simple to understand for the agents has attracted a lot of attention recently. One particularly relevant concept in this direction has been Obvious Strategyproofness (OSP), a class of mechanisms that are so simple to be recognized as incentive compatible even by agents with a limited form of rationality. It is known that there exist payments that lead to an OSP mechanism whenever the algorithm they augment is either greedy or reverse greedy (a.k.a., deferred acceptance). However, to date, their explicit definition is unknown. In this work we provide payments for OSP mechanisms based on greedy or reverse greedy algorithms. Interestingly, our results show an asymmetry between these two classes of algorithms: while for reverse greedy the usual strategyproof payments work well also for OSP, the payments for greedy algorithms may break individual rationality or budget balancedness. Thus, the designer needs to subsidize the market in order to simultaneously guarantee these properties and simple incentives. We apply this result to analyze the amount of subsidies needed by a well-known greedy algorithm for combinatorial auctions with single-minded bidders.