GROWRANGE: Anytime VCG-Based Mechanisms
Abstract
We introduce anytime mechanisms for distributed optimization with self-interested agents. Anytime mechanisms retain good incentive properties even when interrupted before the optimal solution is computed, and provide better quality solutions when given additional time. Anytime mechanisms can solve easy instances of a hard problem quickly and optimally, while providing approximate solutions on very hard instances. In a particular instantiation, GROWRANGE, we successively expand the range of outcomes considered, computing the optimal solution for each range. Truth-revelation remains a dominant strategy equilibrium with a stage-based interruption, and is a best-response with high probability when the interruption is time-based.
Cite
Text
Parkes and Schoenebeck. "GROWRANGE: Anytime VCG-Based Mechanisms." AAAI Conference on Artificial Intelligence, 2004.Markdown
[Parkes and Schoenebeck. "GROWRANGE: Anytime VCG-Based Mechanisms." AAAI Conference on Artificial Intelligence, 2004.](https://mlanthology.org/aaai/2004/parkes2004aaai-growrange/)BibTeX
@inproceedings{parkes2004aaai-growrange,
title = {{GROWRANGE: Anytime VCG-Based Mechanisms}},
author = {Parkes, David C. and Schoenebeck, Grant},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2004},
pages = {34-41},
url = {https://mlanthology.org/aaai/2004/parkes2004aaai-growrange/}
}