We study a multi-unit single-demand auction in a setting where agents can arbitrarily commit to strategies that may depend on the commitments of other agents. Such commitments non-trivially change the equilibria of the auction by inducing a metagame, in which agents commit to strategies. We demonstrate a strategy an attacker may commit to that ensures they receive one such item for free, while forcing the remaining agents to enter a lottery for the remaining items. The attack is detrimental to the auctioneer, who loses most of their revenue. We show that the strategy works as long as the agents have valuations that are somewhat concentrated. The attack is robust to a large fraction of the agents being either oblivious to the attack or having exceptionally high valuations. The attacker may coerce these agents into cooperating by promising them a free item. We show that the conditions for the attack to work hold with high probability when (1) the auction is not too congested, and (2) the valuations are sampled i.i.d. from either a uniform distribution or a Pareto distribution. The attack works for first-price auctions, second-price auctions, and the transaction fee mechanism EIP-1559 used by Ethereum.

We study a scenario where an adjudication task (e.g., the resolution of a binary dispute) is outsourced to a set of agents who are appointed as jurors. This scenario is particularly relevant in a Web3 environment, where no verification of the adjudication outcome is possible, and the appointed agents are, in principle, indifferent to the final verdict. We consider simple adjudication mechanisms that use (1) majority voting to decide the final verdict and (2) a payment function to reward the agents with the majority vote and possibly punish the ones in the minority. Agents interact with such a mechanism strategically: they exert some effort to understand how to properly judge the dispute and cast a yes/no vote that depends on this understanding and on information they have about the rest of the votes. Eventually, they vote so that their utility (i.e., their payment from the mechanism minus the cost due to their effort) is maximized. Under reasonable assumptions about how an agent's effort is related to her understanding of the dispute, we show that appropriate payment functions can be used to recover the correct adjudication outcome with high probability. Our findings follow from a detailed analysis of the induced strategic game and make use of both theoretical arguments and simulation experiments.

Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdős-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implici" means that the collection is represented by a poly-sized circuit inducing an exponentially large number of objects. We show that several other well-known theorems from extremal combinatorics - including Erdős-Ko-Rado, Sperner, and Cayley's formula - give rise to complete problems for PWPP and PPP. This is in contrast to the Ramsey and Erdős-Rado problems, for which establishing inclusion in PWPP has remained elusive. Besides significantly expanding the set of problems that are complete for PWPP and PPP, our work identifies some key properties of combinatorial proofs of existence that can give rise to completeness for these classes. Our completeness results rely on efficient encodings for which finding collisions allows extracting the desired substructure. These encodings are made possible by the tightness of the bounds for the problems at hand (tighter than what is known for Ramsey's theorem and the sunflower lemma). Previous techniques for proving bounds in TFNP invariably made use of structured algorithms. Such algorithms are not known to exist for the theorems considered in this work, as their proofs "from the book" are non-constructive.

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.

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 \(\varSigma _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.