An approximate truthful mechanism for combinatorial auctions with single parameter agents
- Aaron Archer ,
- Christos Papadimitriou ,
- Kunal Talwar ,
- Eva Tardos
SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms |
Published by Society for Industrial and Applied Mathematics
mechanism design seeks algorithms whose inputs are provided by selfish agents who would lie if advantageous. Incentive compatible mechanisms compel the agents to tell the truth by making it in their self-interest to do so. Often, as in combination auctions, such mechanisms involve the solution of NP-hard problems.