Designing Game-theoretically Sound, Fair, and Private Multi-agent Systems

Abstract

Multi-agent systems (MAS) are distributed systems composed of multiple autonomous agents interacting to achieve a common or conflicting goal. MAS tackles complex and dynamic problems that a single agent cannot solve, resulting in better problem-solving skills, enhanced reliability, and improved scalability. This thesis explores the challenges facing MAS, particularly related to their game-theoretic, fairness, security, and privacy guarantees. A game-theoretically sound MAS is one where the agent interaction can be modeled as a game and analyzed using game-theoretic concepts. This leads to a more stable and efficient system, as agents are incentivized to make decisions that align with the system goals. This thesis focuses on civic crowdfunding, a method for raising funds through voluntary contributions for public projects (e.g., public parks). Our work enriches the existing literature by designing more inclusive mechanisms and providing fairer rewards and efficiency over the blockchain. Fairness is also an essential aspect of MAS as it ensures that the actions and outcomes of agents are equitable and just, resulting in MAS’s long-term stability and sustainability. This thesis looks at fair incentives in Transaction Fee Mechanisms (TFM). Blockchains employ TFMs to include transactions from the set of outstanding transactions in a block. We argue that existing TFMs’ incentives are misaligned for a cryptocurrency’s greater market adoption. We propose TFMs that provide fairer rewards to the transaction creators and minimize the surplus collected to the creators Last, security and privacy are crucial aspects of MAS, as the autonomy and decentralization of agents in MAS can lead to the exposure of sensitive information. In this thesis, we specifically focus on privacy guarantees for MAS like (i) auctions, (ii) voting, and (iii) distributed constraint optimization (DCOPs). We propose privacy-preserving applications that preserve agents’ sensitive information while proving the computation’s verifiability