Approximation Guarantee of OSP Mechanisms : the Case of Machine Scheduling and Facility Location
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 139011734
- Type
- D - Journal article
- DOI
-
10.1007/s00453-020-00771-x
- Title of journal
- ALGORITHMICA
- Article number
- s00453-020-00771-x
- First page
- -
- Volume
- 0
- Issue
- 0
- ISSN
- 0178-4617
- Open access status
- Compliant
- Month of publication
- October
- Year of publication
- 2020
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Obviously strategy-proof (OSP) mechanisms received a lot of attention in the economics literature, as they allow one to analyse the incentives of people with imperfect rationality. This is the first work to use a computer science perspective for these mechanisms, by rigorously studying the approximation guarantee of these mechanisms for basic optimization problems paradigmatic of the area. The results, preliminarily published at AAAI’17, constitute the basis for follow-up work introducing a general technique for OSP (ESA’19, pp. 46:1-46:15 and WINE’19, pp. 171-185) and studying approximation in the absence of monetary transfers (AAMAS’19, pp. 1574-1581).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -