Approximate Mechanisms without Payments
Final Report Abstract
We obtained two main results, concerning mechanisms without payments and a new computational approach to mechanism design. In the first half of the project, we studied approximately efficient mechanisms without payments with a focus on two settings that are highly relevant in practice: kidney exchange involving multiple hospitals and approval voting when the sets of candidates and voters coincide. Kidney exchange improves the situation of patients with severe kidney disease by enabling the transplantation of kidneys from live donors that are incompatible with their intended recipients. While large exchanges provide obvious benefits, they mean that the incentives of hospitals to give priority to their own patients have to be taken into account. We considered mechanisms with stronger incentive properties than existing mechanisms from the economics literature and guaranteed worst-case bounds on solution quality. While unlikely to be used in practice, these mechanisms offer valuable information regarding the tradeoff between robustness of incentives and quality of the outcome. Simulations with realistic parameter values further indicate that performance in practice would be significantly better than the theoretical worst case. Mechanisms with strong incentive properties and good practical rather than worst-case performance thus merit further investigation. Approval voting is routinely used in situations where the sets of candidates and voters coincide, for example by scientific organizations like the American Mathematical Society. Our work is the first study of incentive compatible mechanisms for this type of setting. The second half of the project presented the unique opportunity to contribute to the development of a new computational approach to mechanism design that has the potential to significantly influence the field. The classical approach in mechanism design, to impose incentive compatibility and then derive an optimal mechanism subject to this constraint, faces significant challenges: finding optimal mechanisms for multi-dimensional domains can be analytically cumbersome, and few results are known in this case; adopting incentive compatibility as a hard constraint can preclude mechanisms with useful economic properties; further complications arise when the optimal mechanism has an outcome or payment rule that is computationally intractable. By replacing incentive compatibility with the goal of minimizing expected ex-post regret, we were able to adapt techniques from statistical machine learning to the design of payment rules. Intuitively, the ex-post regret an agent experiences by truthfully reporting its preferences is the amount by which its utility could be increased through a misreport. While a mechanism with zero ex-post regret is obviously incentive compatible, we are not aware of other direct implication in terms of classical equilibrium properties. Support for expected ex-post regret as a quantifiable target for mechanism design rather comes from a simple model of manipulation where agents face a certain cost for strategic behavior. If this cost is higher than the expected gain, agents can be assumed to behave truthfully.
Publications
- Mix and match. In Proceedings of the 11th ACM Conference on Electronic Commerce, pages 305–314. ACM Press, 2010
I. Ashlagi, F. Fischer, I. A. Kash, and A. D. Procaccia
- Simplicity-expressiveness tradeoffs in mechanism design. In Proceedings of the 12th ACM Conference on Electronic Commerce, pages 341–350. ACM Press, 2011
P. Dütting, F. Fischer, and D. C. Parkes
- Sum of us: Strategyproof selection from the selectors. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pages 101–110. ACM Press, 2011
N. Alon, F. Fischer, A. D. Procaccia, and M. Tennenholtz
- Payment rules through discriminant-based classifiers. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 477–494. ACM Press, 2012
P. Dütting, F. Fischer, P. Jirapinyo, J. Lai, B. Lubin, and D. C. Parkes
