UC San Diego

With the growing demand for computation and the increasing prevalence of resource-constrained agents, the importance of leveraging a network of agents to solve complex problems has become often more pronounced. A multi-agent system consists of interconnected agents with computing capabilities, working collaboratively towards a shared objective. Distributed computation using a multi-agent system provides benefits with regards to privacy, reduction of computational load and resources. In this dissertation, we study two problems that benefit from being solved with the help of a multi-agent system namely (i) distributed convex optimization and (ii) distributed fact-checking.

In part I, we consider a set of agents collaboratively solving a distributed convex optimization problem, asynchronously, under stringent communication constraints. In such situations, when an agent is activated and is allowed to communicate with only one of its neighbors, we would like to pick the one holding the most informative local estimate. We propose new algorithms where the agents with maximal dissent average their estimates, leading to an information mixing mechanism that often displays faster convergence to an optimal solution compared to randomized gossip.

In Part II, we explore a distributed fact-checking system to detect fake news using inexpert agents. Each agent labels news as true or false based on its reliability, modeled as a Binary Symmetric Channel (BSC) with some error probability. We develop an algorithm that estimates statement validity by thresholding a linear combination of agents' labels and deriving optimal weights and thresholds to minimize error probability. Moreover, we present an adaptive algorithm to learn the agents' unreliability parameters and prove the convergence of the adaptive estimator. We also propose a broader class of adaptive estimators for the agents' unreliability parameters, providing the necessary conditions for convergence. We show that estimators for ensembles of two and three agents adhere to a consistent update rule, while hard-decoded estimates fail to converge for any number of agents.

This dissertation contributes to the theoretical aspects of distributed optimization and fact-checking in multi-agent systems, offering novel algorithms and insights for efficient and reliable distributed decision-making.