2011/07/22 by Shyam S. Chandramouli, Shyam S Chandramouli, Chandramouli, Shyam S +2
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #cs.GT
paper · pdf · doi:10.48550/arxiv.1107.4566
arxiv created 2011/07/22 · openalex publication_date 2011/07/22 · arxiv updated 2011/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The key contribution of the paper is a comprehensive study of the egalitarian mechanism with respect to manipulation by a coalition of agents. Our main result is that the egalitarian mechanism is, in fact, peak group strategyproof : no coalition of agents can (weakly) benefit from jointly misreporting their peaks. Furthermore, we show that the egalitarian mechanism cannot be manipulated by any coalition of suppliers (or any coalition of demanders) in the model where both the suppliers and demanders are agents. Our proofs shed light on the structure of the two models and simpify some of the earlier proofs of strategyproofness in the earlier papers. An implication of our results is that the well known algorithm of Megiddo to compute a lexicographically optimal flow in a network is group strategyproof with respect to the source capacities (or sink capacities).