The Power of Two Prices: Beyond Cross-Monotonicity
Yvonne Bleischwitz, Burkhard Monien, Florian Schoppmann, Karsten Tiemann
Faculty of CS, EE and Math,
University of Paderborn
A cost-sharing mechanism is budget-balanced (BB) if it guarantees that the service provider recovers the cost incurred by servicing the selected set of agents; it is no-free-riders (NFR) if no agent gets the service for free; it is group-strategyproof (GSP) if no coalition of agents can improve the utility of one of its members. When can a cost-sharing mechanism be simultaneously BB, NFR and GSP? A variant of this general question was already investigated by Moulin (1999), who showed that for submodular cost-functions, cross-monotonicity guarantees BB and GSP. In this work, we consider arbitrary (not necessarily submodular) symmetric cost functions, which only depend on the number of serviced agents. Furthermore, we add NFR to the list of requirements. We obtain the following results:
-
We introduce a novel general technique for constructing BB, GSP, and NFR mechanisms. The key here is a two-price cost-sharing form that describes agents' cost-shares. We give a generic mechanism that is GSP for any such form.
As an application of the technique, we consider the problem of scheduling identical jobs on related machines with costs emerging as the optimal makespan. We derive a two-price cost-sharing form to achieve 3/4-approximate BB; this is the best our technique can yield. However, this is a significant improvement to the tight bound of (m+1)/(2m) for m machines achieved by cross-monotonic cost-sharing methods.
-
We next give a positive result for the existence of a BB, GSP, and NFR mechanism when there are at most three agents. The generic mechanism we give here also works for an arbitrary number of agents when costs are given by the makespan of scheduling identical jobs on identical machines. However, on the negative side, we establish that symmetry is not sufficient for BB, GSP, and NFR mechanisms with more than three agents.
A common key feature of all mechanisms we propose is to keep a preference order on the set of agents: whenever a set of receiving agents is selected, the cost of each agent in the set is solely determined by his rank in the set.