Payment Schemes from Limited Information with Applications in Distributed Computing
Nikolaj I. Schwartzbach
This widget computes an optimal payment scheme to incentivize a specified behavior in extensive-form games of perfect information. Specifically, by augmenting a finite game G
with a payment scheme, we obtain ε
-robust game-theoretic security. This means the honest strategy profile s*
is a t
-robust subgame perfect equilibrium, and for every pure strategy s
) with |C
| ≤ t
, and every i
, it holds that:
ui (s* ) ≥ ui (s) + ε
The widget is supplementary material to (Schwartzbach, 2022).
Both the tree and emissions matrix are inputted as raw JS code and parsed using
- To make a leaf, use the syntax
ui is the payoff of player i.
- To make a branch, use the syntax
i is the index of the player to whom the node belongs, and
cj is the jth child.
- Note: in every branch there must be a unique honest child. To denote the honest strategy, use a star
* as suffix on the label, i.e.
- Emissions must be formatted as
m matrix, i.e.
k lists of size
k is an integer, denoting the number of symbols in the alphabet, and
m is the number of leaves in the game.
- Note: each column in the emissions matrix must be a pdf, i.e. each entry must be nonnegative and the columns should sum to one.
is used for solving the linear programs.
Department of Computer Science. Aarhus University
- Nikolaj I. Schwartzbach. 2022. Payment Schemes from Limited Information with Applications in Distributed
Computing. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC ’22), July 11–15,
2022, Boulder, CO, USA. ACM, New York, NY, USA, 21 pages. https://doi.org/10.1145/3490486.3538342