Publication:

GrowRange: Anytime VCG-Based Mechanisms

Thumbnail Image

Open/View Files

Primary Parkes_GrowRange.pdf (175.1 KB)

Date

2004

Authors

Published Version

Published Version

http://www.aaai.org/Papers/AAAI/2004/AAAI04-006.pdf

Journal Title

Journal ISSN

Volume Title

Publisher

AAAI Press / MIT Press
The Harvard community has made this article openly available. Please share how this access benefits you.

Research Projects

Organizational Units

Journal Issue

Citation

Parkes, David C. and Grant Schoenebeck. 2004. GrowRange: Anytime VCG-based mechanisms. In Proceedings of the 19th national conference on artifical intelligence(AAAI-04): Sixteenth innovative applications of artificial intelligence conference (IAAI-04), ed. American Association for Artificial Intelligence, 34-41. Menlo Park, C.A.: AAAI Press; Cambridge, M.A.: MIT Press.

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.

Description

Other Available Sources

http://www.eecs.harvard.edu/econcs/pubs/anytime.pdf

Research Data

Keywords

Terms of Use

This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service

URI

http://nrs.harvard.edu/urn-3:HUL.InstRepos:4039784

Collections

FAS Scholarly Articles

Endorsement

Review

Supplemented By

Related Stories