Item bidding for combinatorial public projects

作者：Markakis Evangelos; Telelis Orestis^*

来源：Theoretical Computer Science, 2017, 678: 40-55.

DOI：10.1016/j.tcs.2017.04.001

• Mechanism
• Price of anarchy
• Valuation function
• Strong equilibrium
• Bayes-Nash equilibrium
• Combinatorial Public Project Problem

We analyze a simple mechanism for the Combinatorial Public Project Problem (Cppp). The problem asks to select k out of m available items, so as to maximize the social welfare for autonomous agents with combinatorial preferences (valuation functions) over subsets of items. The CPPP constitutes an abstract model for decision making by autonomous agents and has been shown to present severe computational hardness, in the design of tractable truthful approximation mechanisms. We study a non-truthful mechanism that is, however, practically relevant to multi-agent environments, by virtue of its natural simplicity. The mechanism employs an item bidding interface, where every agent issues a separate bid for the inclusion of each distinct item in the outcome; the k items with the highest sums of bids are then chosen. As for the payment scheme, the agents are charged according to a direct adaptation of the VCG payment rule. For fairly expressive classes of the agents' valuation functions, we establish existence of socially optimal pure Nash equilibria, as well as strong equilibria, that are resilient to coordinated deviations of subsets of agents. Particularly with respect to pure Nash equilibria, we prove convergence of an iterative procedure. Subsequently, we derive worst-case bounds on the approximation of the optimum social welfare achieved in (strong) equilibrium by the mechanism. We show that the mechanism's performance improves with the number of agents that can coordinate their bids, and reaches half of the optimum welfare at strong equilibrium. Finally, we derive bounds on the mechanism's performance in Bayes-Nash equilibrium, under an incomplete information setting.

• 出版日期2017-5-23