Overcoming Rational Manipulation in Distributed Mechanism Implementations
Distributed systems are increasingly made up of nodes governed by disparate self-interested parties. These parties can be modeled as rational (in a game theoretic sense) utility-maximizing players that participate in a distributed algorithm. These rational nodes may choose to deviate from a given sp...
Main Authors: | , , |
---|---|
Format: | Other/Unknown Material |
Language: | English |
Published: |
2003
|
Subjects: | |
Online Access: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:25104435 |
id |
ftharvardudash:oai:dash.harvard.edu:1/25104435 |
---|---|
record_format |
openpolar |
spelling |
ftharvardudash:oai:dash.harvard.edu:1/25104435 2023-05-15T18:13:05+02:00 Overcoming Rational Manipulation in Distributed Mechanism Implementations Shneidman, Jeffrey Parkes, David C. Seltzer, Margo I. 2003 application/pdf http://nrs.harvard.edu/urn-3:HUL.InstRepos:25104435 en_US eng Shneidman, Jeffrey, David C. Parkes, and Margo Seltzer. 2003. Overcoming Rational Manipulation in Distributed Mechanism Implementations. Harvard Computer Science Group Technical Report TR-12-03. http://nrs.harvard.edu/urn-3:HUL.InstRepos:25104435 Research Paper or Report 2003 ftharvardudash 2022-04-05T09:37:02Z Distributed systems are increasingly made up of nodes governed by disparate self-interested parties. These parties can be modeled as rational (in a game theoretic sense) utility-maximizing players that participate in a distributed algorithm. These rational nodes may choose to deviate from a given specification to increase their utility, but alternatively can be incented to correctly implement part of a distributed mechanism. In dealing with rational agents in distributed systems, computer science has taken a cue from the economics subfield of mechanism design (MD) with recent work in distributed algorithmic mechanism design (DAMD). Previously, work in MD and DAMD has focused on manipulation in agent strategy. However, there are other manipulations available to agents that can damage mechanism implementations. As designers begin to inject mechanism design ideas into distributed systems, non-manipulatability of mechanisms becomes more important. The main contributions of this paper are as follows: We identify four areas of manipulation in mechanism implementations, as well as environmental assumptions that can affect agent behavior. We introduce two properties for non-manipulatable mechanism implementations, communication- and algorithm compatibility, and identify techniques that can be used to achieve these properties. Our wider agenda is that future mechanism design implementation work (centralized or distributed) be done with consideration of these two non-manipulatability properties. To illustrate how this might be done, we demonstrate one way to bring communication- and algorithm compatibility to a well-defined lowest cost interdomain routing problem proposed by Feigenbaum, Papadimitriou, Sami, and Shenker (FPSS) [11]. Our approach does not add significant new processing or communication overhead to the distributed FPSS algorithm. Our end result is an incentive-compatible, communication-compatible, and algorithm-compatible distributed mechanism. Engineering and Applied Sciences Version of Record Other/Unknown Material sami Harvard University: DASH - Digital Access to Scholarship at Harvard |
institution |
Open Polar |
collection |
Harvard University: DASH - Digital Access to Scholarship at Harvard |
op_collection_id |
ftharvardudash |
language |
English |
description |
Distributed systems are increasingly made up of nodes governed by disparate self-interested parties. These parties can be modeled as rational (in a game theoretic sense) utility-maximizing players that participate in a distributed algorithm. These rational nodes may choose to deviate from a given specification to increase their utility, but alternatively can be incented to correctly implement part of a distributed mechanism. In dealing with rational agents in distributed systems, computer science has taken a cue from the economics subfield of mechanism design (MD) with recent work in distributed algorithmic mechanism design (DAMD). Previously, work in MD and DAMD has focused on manipulation in agent strategy. However, there are other manipulations available to agents that can damage mechanism implementations. As designers begin to inject mechanism design ideas into distributed systems, non-manipulatability of mechanisms becomes more important. The main contributions of this paper are as follows: We identify four areas of manipulation in mechanism implementations, as well as environmental assumptions that can affect agent behavior. We introduce two properties for non-manipulatable mechanism implementations, communication- and algorithm compatibility, and identify techniques that can be used to achieve these properties. Our wider agenda is that future mechanism design implementation work (centralized or distributed) be done with consideration of these two non-manipulatability properties. To illustrate how this might be done, we demonstrate one way to bring communication- and algorithm compatibility to a well-defined lowest cost interdomain routing problem proposed by Feigenbaum, Papadimitriou, Sami, and Shenker (FPSS) [11]. Our approach does not add significant new processing or communication overhead to the distributed FPSS algorithm. Our end result is an incentive-compatible, communication-compatible, and algorithm-compatible distributed mechanism. Engineering and Applied Sciences Version of Record |
format |
Other/Unknown Material |
author |
Shneidman, Jeffrey Parkes, David C. Seltzer, Margo I. |
spellingShingle |
Shneidman, Jeffrey Parkes, David C. Seltzer, Margo I. Overcoming Rational Manipulation in Distributed Mechanism Implementations |
author_facet |
Shneidman, Jeffrey Parkes, David C. Seltzer, Margo I. |
author_sort |
Shneidman, Jeffrey |
title |
Overcoming Rational Manipulation in Distributed Mechanism Implementations |
title_short |
Overcoming Rational Manipulation in Distributed Mechanism Implementations |
title_full |
Overcoming Rational Manipulation in Distributed Mechanism Implementations |
title_fullStr |
Overcoming Rational Manipulation in Distributed Mechanism Implementations |
title_full_unstemmed |
Overcoming Rational Manipulation in Distributed Mechanism Implementations |
title_sort |
overcoming rational manipulation in distributed mechanism implementations |
publishDate |
2003 |
url |
http://nrs.harvard.edu/urn-3:HUL.InstRepos:25104435 |
genre |
sami |
genre_facet |
sami |
op_relation |
Shneidman, Jeffrey, David C. Parkes, and Margo Seltzer. 2003. Overcoming Rational Manipulation in Distributed Mechanism Implementations. Harvard Computer Science Group Technical Report TR-12-03. http://nrs.harvard.edu/urn-3:HUL.InstRepos:25104435 |
_version_ |
1766185571391111168 |