Abstract
Human society, transportation networks, financial markets, ecological environments are prominent examples of large-scale networked systems. One defining characteristics of these systems is their dynamic and interconnected nature, where the state of a system evolves over time (i.e., the dynamics), and the behavior and welfare of each entity are influenced by its neighbors (i.e., the peer effects). This thesis examines the following two fundamental challenges in networked systems and proposes efficient solutions.
The first issue involves the efficient allocation of scarce resources across a network to maximize social welfare under the peer effect. Key applications of this problem are allocating students to schools, people to urban housing, and matching users on social platforms. Here, this thesis introduces a unified mathematical framework for resource allocation in networked systems and propose efficient algorithms that are provably optimal or arbitrarily close to optimal under board classes of utility functions.
The second problem concerns the inference of latent components in networked systems from their observed dynamics. In particular, due to the large scale of real-world cascades, a complete specification of the underlying system is often not available. Towards this end, this thesis proposal several efficient methods for learning individuals’ behaviors and system topology, with provable accuracy guarantees.
Overall, this thesis establishes a theoretical foundation for the resource planning and learning of networked systems, with wide-ranging applications in computer science, social science, and economics.
