skip to main content
10.1145/1329125.1329227acmotherconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Incentive compatible ranking systems

Published: 14 May 2007 Publication History

Abstract

Ranking systems are a fundamental ingredient of multiagent environments and Internet Technologies. These settings can be viewed as social choice settings with two distinguished properties: the set of agents and the set of alternatives coincide, and the agents' preferences are dichotomous, and therefore classical impossibility results do not apply. In this paper we initiate the study of incentives in ranking systems, where agents act in order to maximize their position in the ranking, rather than to obtain a correct outcome. We consider several basic properties of ranking systems, and fully characterize the conditions under which incentive compatible ranking systems exist, demonstrating that in general no such system satisfying all the properties exists.

References

[1]
A. Altman and M. Tennenholtz. On the axiomatic foundations of ranking systems. In Proc. 19th International Joint Conference on Artificial Intelligence, pages 917--922, 2005.
[2]
A. Altman and M. Tennenholtz. Ranking systems: the pagerank axioms. In EC '05: Proceedings of the 6th ACM conference on Electronic commerce, pages 1--8, New York, NY, USA, 2005. ACM Press.
[3]
A. Altman and M. Tennenholtz. Quantifying incentive compatibility of ranking systems. In Proc. of AAAI-06, 2006.
[4]
K. Arrow. Social Choice and Individual Values (2nd Ed.). Yale University Press, 1963.
[5]
A. Borodin, G. O. Roberts, J. S. Rosenthal, and P. Tsaparas. Link analysis ranking: algorithms, theory, and experiments. ACM Trans. Inter. Tech., 5(1):231--297, 2005.
[6]
F. Brandt, F. A. Fischer, and Y. Shoham. On strictly competitive multi-player games. In Proc. of AAAI-06, 2006.
[7]
A. Cheng and E. Friedman. Sybilproof reputation mechanisms. In P2PECON '05: Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, pages 128--132, New York, NY, USA, 2005. ACM Press.
[8]
B. Dutta, M. O. Jackson, and M. Le Breton. Strategic candidacy and voting procedures. Econometrica, 69(4):1013--37, 2001.
[9]
A. Gibbard. Manipulation of voting schemes. Econometrica, 41:587--601, 1973.
[10]
J. M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM {see pdf for details}.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems
May 2007
1585 pages
ISBN:9788190426275
DOI:10.1145/1329125
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

  • IFAAMAS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 May 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. incentives
  2. multiagent systems
  3. ranking systems
  4. social choice

Qualifiers

  • Research-article

Conference

AAMAS07
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)1
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2011)IPTV service based on a content-zapping paradigmMultimedia Systems10.1007/s00530-010-0215-817:4(351-364)Online publication date: 1-Jul-2011
  • (2010)An axiomatic approach to personalized ranking systemsJournal of the ACM10.1145/1734213.173422057:4(1-35)Online publication date: 3-May-2010
  • (2010)Routing betweenness centralityJournal of the ACM10.1145/1734213.173421957:4(1-27)Online publication date: 3-May-2010
  • (2010)Clouds at the crossroadsXRDS: Crossroads, The ACM Magazine for Students10.1145/1734160.173416516:3(10-13)Online publication date: 1-Mar-2010
  • (2010)IPTV Service with Automatic Channels PersonalizationProceedings of the 2010 IEEE 24th International Conference on Advanced Information Networking and Applications Workshops10.1109/WAINA.2010.66(1065-1070)Online publication date: 20-Apr-2010
  • (2009)The concept of nondeterminismACM SIGCSE Bulletin10.1145/1595453.159549541:2(141-160)Online publication date: 25-Jun-2009
  • (2009)Cooperative node localization using nonlinear data projectionACM Transactions on Sensor Networks10.1145/1464420.14644215:1(1-26)Online publication date: 11-Feb-2009
  • (2009)Fault tolerance measures for large-scale wireless sensor networksACM Transactions on Autonomous and Adaptive Systems10.1145/1462187.14621894:1(1-28)Online publication date: 9-Feb-2009
  • (2009)Trust Is in the Eye of the BeholderProceedings of the 2009 International Conference on Computational Science and Engineering - Volume 0310.1109/CSE.2009.444(100-108)Online publication date: 29-Aug-2009
  • (2009)Consistent Continuous Trust-Based Recommendation SystemsProceedings of the 5th International Workshop on Internet and Network Economics10.1007/978-3-642-10841-9_12(113-124)Online publication date: 9-Dec-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media