Strategy-proof mechanisms for the k-winner selection problem

Yuko Sakurai, Tenda Okimoto, Masaaki Oka, Makoto Yokoo

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The goal of this paper is to develop a strategy-proof (SP) mechanism for the k-winner selection problem, which finds a set of (at most) k winners among participants. Here, we assume the winners can have positive/negative externalities with each other; the gross utility of a winner not only depends on whether she wins, but also on the other winners. If the types of agents, i.e., the gross utilities of agents, are known, we can obtain a Pareto efficient (PE) allocation that maximizes the sum of the gross utilities of winners in polynomial time, assuming k is a constant. On the other hand, when the types of agents are private information, we need a mechanism that can elicit the true types of agents; it must satisfy SP. We first show that there exists no SP mechanism that is PE, individual rational (IR), and non-deficit (ND) in a general setting where we put no restrictions on possible agent types. Thus, we need to give up at least one of these desirable properties. Next, we examine how a family of Vickrey-Clarke-Groves (VCG) based mechanisms works for this problem. We consider two alternative VCG-based mechanisms in this setting, both of which are SP and PE. We show that one alternative, called VCG-ND, is ND but not IR, and the other alternative, called VCG-IR, is IR but not ND. Also, we show special cases where VCG-ND satisfies IR, or VCG-IR satisfies ND. Moreover, we propose mechanisms called VCG-ND+ and VCG-IR+, which can be applied to a general setting, where a mechanism designer has partial knowledge about the possible interactions among agents. Both VCG-ND+ and VCG-IR+ are SP, IR, and ND, but they are not PE. Finally, we present a concise graphical representation scheme of agant types.

Original languageEnglish
Title of host publicationPRIMA 2013
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 16th International Conference, Proceedings
Number of pages16
Publication statusPublished - 2013
Event16th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2013 - Dunedin, New Zealand
Duration: Dec 1 2013Dec 6 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8291 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2013
Country/TerritoryNew Zealand

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Strategy-proof mechanisms for the k-winner selection problem'. Together they form a unique fingerprint.

Cite this