Overcoming rational manipulation in mechanism implementation
Previous work in computational mechanism design has largely focused on the problem of revelation of private information by selfinterested agents. In contrast, this work addresses the rational manipulation that can occur when mechanisms are implemented by the agents themselves. We are interested in d...
Main Authors: | , |
---|---|
Other Authors: | |
Format: | Text |
Language: | English |
Published: |
2004
|
Subjects: | |
Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.203.1414 http://www.gsb.stanford.edu/facseminars/events/economics/pdfs/ccac.pdf |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.203.1414 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.203.1414 2023-05-15T18:12:13+02:00 Overcoming rational manipulation in mechanism implementation Jeffrey Shneidman David C. Parkes The Pennsylvania State University CiteSeerX Archives 2004 application/pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.203.1414 http://www.gsb.stanford.edu/facseminars/events/economics/pdfs/ccac.pdf en eng http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.203.1414 http://www.gsb.stanford.edu/facseminars/events/economics/pdfs/ccac.pdf Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://www.gsb.stanford.edu/facseminars/events/economics/pdfs/ccac.pdf text 2004 ftciteseerx 2016-01-07T17:31:12Z Previous work in computational mechanism design has largely focused on the problem of revelation of private information by selfinterested agents. In contrast, this work addresses the rational manipulation that can occur when mechanisms are implemented by the agents themselves. We are interested in distributed implementations, when agents may selfishly deviate from algorithms imposed by a mechanism designer and damage the performance of the overall system. We define two properties for non-manipulable mechanism implementations, communication- and algorithm compatibility and identify techniques that can be used to achieve these properties. A proof technique is introduced to show how a distributed mechanism implementation can be proven to be an ex post Nash equilibrium, inclusive of the private information revelation and mechanism actions within an agent’s strategy space. We focus in particular on the lowest cost interdomain routing problem proposed by Feigenbaum, Papadimitriou, Sami, and Shenker (FPSS) [5]. Our approach relies primarily on problem partitioning and redundancy and does not add significant new processing or communication overhead to the distributed FPSS algorithm. 1. Text sami Unknown Nash ENVELOPE(-62.350,-62.350,-74.233,-74.233) |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
description |
Previous work in computational mechanism design has largely focused on the problem of revelation of private information by selfinterested agents. In contrast, this work addresses the rational manipulation that can occur when mechanisms are implemented by the agents themselves. We are interested in distributed implementations, when agents may selfishly deviate from algorithms imposed by a mechanism designer and damage the performance of the overall system. We define two properties for non-manipulable mechanism implementations, communication- and algorithm compatibility and identify techniques that can be used to achieve these properties. A proof technique is introduced to show how a distributed mechanism implementation can be proven to be an ex post Nash equilibrium, inclusive of the private information revelation and mechanism actions within an agent’s strategy space. We focus in particular on the lowest cost interdomain routing problem proposed by Feigenbaum, Papadimitriou, Sami, and Shenker (FPSS) [5]. Our approach relies primarily on problem partitioning and redundancy and does not add significant new processing or communication overhead to the distributed FPSS algorithm. 1. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
Jeffrey Shneidman David C. Parkes |
spellingShingle |
Jeffrey Shneidman David C. Parkes Overcoming rational manipulation in mechanism implementation |
author_facet |
Jeffrey Shneidman David C. Parkes |
author_sort |
Jeffrey Shneidman |
title |
Overcoming rational manipulation in mechanism implementation |
title_short |
Overcoming rational manipulation in mechanism implementation |
title_full |
Overcoming rational manipulation in mechanism implementation |
title_fullStr |
Overcoming rational manipulation in mechanism implementation |
title_full_unstemmed |
Overcoming rational manipulation in mechanism implementation |
title_sort |
overcoming rational manipulation in mechanism implementation |
publishDate |
2004 |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.203.1414 http://www.gsb.stanford.edu/facseminars/events/economics/pdfs/ccac.pdf |
long_lat |
ENVELOPE(-62.350,-62.350,-74.233,-74.233) |
geographic |
Nash |
geographic_facet |
Nash |
genre |
sami |
genre_facet |
sami |
op_source |
http://www.gsb.stanford.edu/facseminars/events/economics/pdfs/ccac.pdf |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.203.1414 http://www.gsb.stanford.edu/facseminars/events/economics/pdfs/ccac.pdf |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766184771438772224 |