Weak monotonicity suffices for truthfulness on convex domains

Michael Saks, Lan Yu

Research output: Contribution to conferencePaperpeer-review

99 Scopus citations

Abstract

Weak monotonicity is a simple necessary condition for a social choice function to be implementable by a truthful mechanism. Roberts [10] showed that it is sufficient for all social choice functions whose domain is unrestricted. Lavi, Mu'alem and Nisan [6] proved the sufficiency of weak monotonicity for functions over order-based domains and Gui, Muller and Vohra [5] proved sufficiency for order-based domains with range constraints and for domains defined by other special types of linear inequality constraints. Here we show the more general result, conjectured by Lavi, Mu'alem and Nisan [6], that weak monotonicity is sufficient for functions defined on any convex domain.

Original languageEnglish (US)
Pages286-293
Number of pages8
DOIs
StatePublished - 2005
EventEC'05: 6th ACM Conference on Electronic Commerce - Vancouver, Canada
Duration: Jun 5 2005Jun 8 2005

Other

OtherEC'05: 6th ACM Conference on Electronic Commerce
Country/TerritoryCanada
CityVancouver
Period6/5/056/8/05

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Keywords

  • Dominant strategy
  • Mechanism design
  • Strategyproof
  • Truthful
  • Weak monotonicity

Cite this