ML Anthology

Implementing the Maximum of Monotone Algorithms

Liad Blumrosen
AAAI 2007 pp. 30-35
doi:10.1145/1329125.1329224 /aaai/2007/blumrosen2007aaai-implementing/

Abstract

Running several sub-optimal algorithms and choosing-the optimal one is a common procedure in computer science, most notably in the design of approximation algorithms. This paper deals with one significant flaw of this technique in environments where the inputs are provided by rational agents: such protocols are not necessarily incentive compatible even when the underlying algorithms are. We characterize sufficient and necessary conditions for such best-outcome protocols to be incentive compatible in a general model for agents with one-dimensional private data. We show how our techniques apply in several settings.

PDF AAAI Semantic Scholar

Cite

Text

Blumrosen. "Implementing the Maximum of Monotone Algorithms." AAAI Conference on Artificial Intelligence, 2007. doi:10.1145/1329125.1329224

Markdown

[Blumrosen. "Implementing the Maximum of Monotone Algorithms." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/blumrosen2007aaai-implementing/) doi:10.1145/1329125.1329224

BibTeX

@inproceedings{blumrosen2007aaai-implementing,
  title     = {{Implementing the Maximum of Monotone Algorithms}},
  author    = {Blumrosen, Liad},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {30-35},
  doi       = {10.1145/1329125.1329224},
  url       = {https://mlanthology.org/aaai/2007/blumrosen2007aaai-implementing/}
}