Multi-Agent Decision Systems: From Computational Social Choice to Privacy-Preserving Distributed Learning in Complex Environments

As we see the world is getting so interconnected, the study of multi-agent systems has become an important area for addressing complex decision-making processes across various domains. This dissertation investigates the theoretical foundations and practical applications of multi-agent systems, focusing on three interconnected topics: computational social choice, defensive security mechanisms, and privacy-preserving learning paradigms. The first contribution lies in the systematic analysis of random sample voting schemes in elections under bribery attacks. While traditional research in computational social choice has primarily focused on fixed voter sets, this research explores the emerging paradigm of random sample voting – a technique adopted in decentralized systems. These systems randomly select a subset of participants to form a decision-making committee, introducing randomness to enhance resistance against any kind of manipulation during collective decision-making process. Through rigorous theoretical analysis, this research shows that for most of the voting rules, bribing becomes computationally intractable and can be classified as an NP-hard problem. Interestingly, for plurality and veto voting rules, we develop a polynomial-time approximation scheme leveraging novel integer programming formulations and n-fold integer programming techniques. It can efficiently compute and find near-optimal solutions. This dissertation also investigates honeypot deployment strategies as defensive mechanisms in adversarial multi-agent environments. First, we formalized the Honeypot Deployment problem, which tries to find a strategic blending of honeypot systems among production computers such that the utility in exposing novel attacks can be maximized while minimizing asset comprise. This problem falls in bilevel optimization and NP-hard. We develop a near-optimal approximation algorithm and evaluate the impact of varying attacker capabilities through extensive simulations. In privacy-preserving collaborative learning, this dissertation addresses the challenges of federated learning particularly in Internet of Drones (IoD) networks. Our proposed framework, Sky of Unlearning (SoUL), can demonstrate efficient federated unlearning by selectively removing some neurons which have adversarial or private data influences. However, at the same time it maintains the model performance while reducing computational and communication overhead.