Payment Schemes from Limited Information with Applications in Distributed Computing

Nikolaj Ignatieff Schwartzbach

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Abstract

We propose a generic mechanism for incentivizing behavior in an arbitrary finite game using payments. Doing so is trivial if the mechanism is allowed to observe all actions taken in the game, as this allows it to simply punish those agents who deviate from the intended strategy. Instead, we consider an abstraction where the mechanism probabilistically infers information about the outcome of the game. We show that payment schemes can be used to implement any set of utilities if and only if the mechanism can essentially infer completely what happened. We show that finding an optimal payment scheme for games of perfect information is P-complete, and conjecture it to be PPAD-hard for games of imperfect information. We prove a lower bound on the size of the payments, showing that the payments must be linear in the intended level of security. We demonstrate the applicability of our model to concrete problems in distributed computing, namely decentralized commerce and secure multiparty computation, for which the payments match the lower bound asymptotically.
Original languageEnglish
Title of host publicationEC '22 : Proceedings of the 23rd ACM Conference on Economics and Computation
Number of pages21
Publication dateJul 2022
Pages129-149
ISBN (Electronic)9781450391504
DOIs
Publication statusPublished - Jul 2022
EventEC '22: The 23rd ACM Conference on Economics and Computation - Boulder, CO, United States
Duration: 11 Jul 202215 Jul 2022

Conference

ConferenceEC '22: The 23rd ACM Conference on Economics and Computation
Country/TerritoryUnited States
CityBoulder, CO
Period11/07/202215/07/2022

Keywords

  • decentralized commerce
  • mechanism design
  • payments
  • secure multiparty computation
  • smart contracts

Cite this