Approximate efficiency and strategy-proofness for moneyless mechanisms on single-dipped policy domain

Qiaoming Han, Donglei Du, Dachuan Xu () and Yicheng Xu
Additional contact information
Qiaoming Han: Zhejiang University of Finance and Economics
Donglei Du: University of New Brunswick
Dachuan Xu: Beijing University of Technology
Yicheng Xu: Beijing University of Technology

Journal of Global Optimization, 2018, vol. 70, issue 4, No 8, 859-873

Abstract: Abstract The single-dipped domain can be used to model any allocation problem where a single output must be chosen in an interval with the assumption that agents’ preferences have a single most loathful point (the dip) in the interval, and the preferences are increasing as one moves away from that dip. Practical domains like this appear in political voting system where each voter has his most-hated candidate and alternative candidates are evaluated by their proximity to this candidate or in obnoxious location problem, where each agent prefers to have the obnoxious location to be distant from his own location, among others. We first characterize deterministic and anonymous strategy-proof and group strategy-proof mechanisms on single-dipped public policy domain, complementing the well-known results on single-peaked policy domain first investigated by Moulin (Pub. Choice 35:437–455, 1980). Then we consider the tradeoff between strategy-proofness and efficiency by applying our characterization. As concrete applications of our results, we extend existing models and results, and resolve several open questions related to the obnoxious facility location game from the algorithmic mechanism design literature.

Keywords: Mechanism design; Approximation algorithm; Strategy-proof; efficiency; Pareto-optimal; Anonymous (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0586-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:70:y:2018:i:4:d:10.1007_s10898-017-0586-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0586-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().