Economics and Computation in Decentralized Systems

Abstract

Algorithmic game theory studies algorithmic design under incentive constraints, and, in its foundations, the contributions between computer science and economics in this area go both ways. In one direction, economics provides new perspectives in designing secure computer systems: real-world adversaries are often not intentionally malicious but rather rational and economically driven. In the other direction, the emergence of decentralized applications poses challenges to traditional assumptions from economic theory. Here, we study the problem of designing decentralized applications implemented by autonomous rational agents. First, we provide efficient constructions of credible and strategyproof optimal auctions where neither bidders nor the auctioneer has the incentive to be strategic, overcoming prior impossibility results from the literature. Our auctions are revenue optimal, which shows the auctioneer need not sacrifice revenue to implement a more transparent auction. Blockchains are a promising tool for designing generic decentralized applications, but constructions relying on Proof-of-Work (PoW) are energy inefficient. We show that energy-efficient alternatives, notably Proof-of-Stake blockchains, can approximate the incentive guarantees of PoW when given access to public randomness. Thus we reduce the problem of designing energy-friendly blockchains to designing a trusted public source of randomness such as the NIST randomness beacon. Third, we show the connections between credible auction design with the problem of allocation block space in blockchains through a transaction fee mechanism. We propose dynamic mechanisms that provide a better user experience than the status quo and are robust manipulation from miners. Under natural conditions, we provide stability and welfare guarantees at equilibrium. In the last part, we investigate the role of policy and regulation in designing a secure decentralized system. Although technical advances have contributed significantly to the security of Internet systems, the proliferation of large-scale DDoS attacks shows how incentive misalignment between users and manufacturers of computer devices drives the risk of computer vulnerabilities. Optimal regulations might require intervention from users and manufacturers and might be highly complex. However, we give theoretical evidence that interventions that impact only users or manufacturers can approximate the outcome of optimal ones.