Strategic and Secure Interactions in Networks

The goal of this dissertation is to understand how network plays a role in shaping certain strategic interactions, in particular biased voting and bargaining, on networks; and to understand how interactions can be made secure when they are constrained by the network topology. Our works take an interdisciplinary approach by drawing on theories and models from economics, sociology, as well as computer science, and using methodologies that include both theories and behavioral experiments. First, we consider biased voting in networks, which models distributed collective decision making processes where individuals on a network must balance between their private biases or preferences with a collective goal of consensus. Our study of this problem is two-folded. On the theoretical side, we start by introducing a diffusion model called biased voter model, which is a natural extension of the classic voter model. Among other results, we show in the presence of private biases, no matter how small, there exists certain networks where it takes exponential time to converge to a consensus through distributed interaction in networks. This is a stark and interesting contrast to the well-known result that it always takes polynomial time to converge in the voter model, when there are no private biases. On the experimental side, a group human subjects were arranged in various carefully designed virtual networks to solve the biased voting problem. Along with analyses of how collective and individual performance vary with network structure and incentives generally, we find there are well-studied network topologies in which the minority preference consistently wins globally, and that the presence of “extremist” individuals, or the awareness of opposing incentives, reliably improve collective performance Second, we consider bargaining in networks, which has long been studied by economists and sociologists. A basic premise behind the many theoretical study of bargaining in networks is that pure topological differences in agents’ network positions endow them with different bargaining power. As a complementary to these theories, we again conducted a series of highly controlled behavioral experiments, where human subjects were arranged in various carefully designed virtual networks to playing bargaining games. Along with other findings of how individual and collective performance vary with network structures and individual playing styles, we find that the number of neighbors one can negotiate with confers bargaining power, whereas the limit on the number of deals one can close undermines it, and we find that competitions from distant part of the network that are invisible locally also play a significant and subtle role in shaping bargaining powers. And last, we consider the question of how interactions in networks can be made secure. Traditional methods and tools from cryptography, for example secure multi-party computation, can be applied only if each party can talk to everyone else directly; but cannot be directly applied if interactions are distributed over a network without completely eradicating the distributed nature. We develop a general ‘compiler’ that turns each algorithm from a broad class collectively known as message-passing algorithms into a secure one that has exactly the same functionality and communication pattern. And we show a fundamental trade-off between preserving the distributed nature of communication and the level of security one can hope for