Approximation Algorithms and Mechanism Design for Minimax Approval Voting.
Ioannis CaragiannisDimitris KalaitzisEvangelos MarkakisPublished in: AAAI (2010)
Keyphrases
- approximation algorithms
- mechanism design
- combinatorial auctions
- worst case
- preference aggregation
- social choice
- np hard
- special case
- game theory
- incomplete information
- vertex cover
- incentive compatible
- multiagent planning
- minimum cost
- upper bound
- precedence constraints
- lower bound
- constant factor
- approximately optimal
- auction mechanisms
- approximation ratio
- double auction
- prediction markets
- cooperative
- disjoint paths
- greedy algorithm
- evaluation function
- computational complexity