Payment Schemes from Limited Information with Applications in Distributed Computing

Nikolaj Ignatieff Schwartzbach

doi:10.1145/3490486.3538342

Payment Schemes from Limited Information with Applications in Distributed Computing

Nikolaj Ignatieff Schwartzbach

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

3 Citations (Scopus)

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 language	English
Title of host publication	EC '22 : Proceedings of the 23rd ACM Conference on Economics and Computation
Number of pages	21
Publication date	Jul 2022
Pages	129-149
ISBN (Electronic)	9781450391504
DOIs	https://doi.org/10.1145/3490486.3538342
Publication status	Published - Jul 2022
Event	EC '22: The 23rd ACM Conference on Economics and Computation - Boulder, CO, United States Duration: 11 Jul 2022 → 15 Jul 2022

Conference

Conference	EC '22: The 23rd ACM Conference on Economics and Computation
Country/Territory	United States
City	Boulder, CO
Period	11/07/2022 → 15/07/2022

Keywords

decentralized commerce
mechanism design
payments
secure multiparty computation
smart contracts

Access to Document

10.1145/3490486.3538342

Cite this

@inproceedings{ac2a159ccc284a1abc8fdb0f8addc048,

title = "Payment Schemes from Limited Information with Applications in Distributed Computing",

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.",

keywords = "decentralized commerce, mechanism design, payments, secure multiparty computation, smart contracts",

author = "Schwartzbach, {Nikolaj Ignatieff}",

year = "2022",

month = jul,

doi = "10.1145/3490486.3538342",

language = "English",

pages = "129--149",

booktitle = "EC '22",

note = "EC '22: The 23rd ACM Conference on Economics and Computation ; Conference date: 11-07-2022 Through 15-07-2022",

}

TY - GEN

T1 - Payment Schemes from Limited Information with Applications in Distributed Computing

AU - Schwartzbach, Nikolaj Ignatieff

PY - 2022/7

Y1 - 2022/7

N2 - 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.

AB - 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.

KW - decentralized commerce

KW - mechanism design

KW - payments

KW - secure multiparty computation

KW - smart contracts

U2 - 10.1145/3490486.3538342

DO - 10.1145/3490486.3538342

M3 - Article in proceedings

SP - 129

EP - 149

BT - EC '22

T2 - EC '22: The 23rd ACM Conference on Economics and Computation

Y2 - 11 July 2022 through 15 July 2022

ER -