We propose a model for games in which the players have shared access to a blockchain that allows them to deploy smart contracts to act on their behalf. This changes fundamental game-theoretic assumptions about rationality since a contract can commit a player to act irrationally in specific subgames, making credible otherwise non-credible threats. This is further complicated by considering the interaction between multiple contracts which can reason about each other. This changes the nature of the game in a nontrivial way as choosing which contract to play can itself be considered a move in the game. Our model generalizes known notions of equilibria, with a single contract being equivalent to a Stackelberg equilibrium, and two contracts being equivalent to a reverse Stackelberg equilibrium. We prove a number of bounds on the complexity of computing SPE in such games with smart contracts. We show that computing an SPE is $\textsf{PSPACE}$-hard in the general case. Specifically, in games with $k$ contracts, we show that computing an SPE is $\Sigma_k^\textsf{P}$-hard for games of imperfect information. We show that computing an SPE remains $\textsf{PSPACE}$-hard in games of perfect information if we allow for an unbounded number of contracts. We give an algorithm for computing an SPE in two-contract games of perfect information that runs in time $O(m\ell)$ where $m$ is the size of the game tree and $\ell$ is the number of terminal nodes. Finally, we conjecture the problem to be $\textsf{NP}$-complete for three contracts.
翻译:我们提出一个游戏模式,让球员可以共享进入一个连锁链的共享机会。 这可以让球员使用智能合同代表他们采取行动。 这改变了关于理性的基本游戏理论假设, 因为合同可以让球员在特定的子游戏中采取不合理的行动, 使得其他无法令人相信的威胁变得可信。 考虑多种合同之间的相互作用, 这在一般情况下会以非边际方式改变游戏的性质, 选择哪项合同本身可以被视为游戏中的动作。 我们的模型一般化了已知的equilibria概念, 单项合同相当于Stackelberg平衡, 和两项合同相当于逆向的Stackelberg平衡。 我们证明, 在智能合同中计算SPE的复杂程度是$\P{PSPC} 。 在普通案件中,我们用SPEEE的精确值是一美元。 我们在SPEA中可以计算一个不完善的SPE值。