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 ε-strong, t-robust game-theoretic security. This means the honest strategy profile s^* is a t-robust subgame perfect equilibrium, and for every pure strategy s = (s_C, s_-C^*) with |C| ≤ t, and every i ∈ C, it holds that:

u_i(s^*) ≥ u_i(s) + ε
The widget is supplementary material to (Schwartzbach, 2022).

Instructions

Both the tree and emissions matrix are inputted as raw JS code and parsed using eval(...).

Tree format

To make a leaf, use the syntax ["leaf",u₁,u₂,...u_n] where u_i is the payoff of player i.
To make a branch, use the syntax ["node",i,c₁,c₂,...,c_m] where i is the index of the player to whom the node belongs, and c_j is the j^th 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. "leaf*" or "node*".

Emissions format

Emissions must be formatted as kxm matrix, i.e. k lists of size m, where 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.

Tree structure ["node",1, ["node",2, ["leaf",3,3], ["leaf",10,0] ], ["node",2, ["leaf*",5,5], ["leaf",0,10] ] ]	Emission matrix [[1,0,0,1], [0,1,0,0], [0,0,1,0] ]
Minization	Additional properties Honest invariance Ensures the utility for the honest strategy remains unchanged. Strong budget balance Ensures the deposit scheme does not lock away funds.
Security parameters t = ε =	Output Print linear program

Input game

Resulting game

jsLPsolver is used for solving the linear programs.

References

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

Department of Computer Science. Aarhus University