Book Description

As our understanding of complex social, economic, and technological systems improves, it is increasingly apparent that a full account of a system's macroscopic level properties requires us to carefully explore the structure of local, pairwise interactions that take place at the microscopic level. Over the past two decades, networks have emerged as the de facto representation of such systems, leading to the genesis of the interdisciplinary field of network science. During this same period, we have witnessed an explosion of participation and consumption of social media, advertising, and e-commerce on the internet; an ecosystem that is the embodiment of and whose success is fundamentally coupled to the use and exploitation of complex networks. What are the processes and mechanisms responsible for shaping these networks? Do these processes posses any inherent fairness? How can these structures be exploited for the benefit of strategic actors? In this dissertation, I explore these questions and present analytical results couched in a theory of strategic decision making -- algorithmic game theory. First, research is presented on the pairwise inequality that is inherent to strategic models of network formation. The network formation games that we consider model the creation of communication links between rational, self-interested individuals. We use the inequality ratio, defined as the ratio between the highest and lowest costs incurred by individual players in a given outcome, to quantify pairwise inequality. Tight upper bounds for the inequality ratio are derived for pure Nash equilibrium outcomes of the network formation games, and the relationship between inequality and efficiency (outcomes that are globally optimal) is characterized. Next, a multi-level network formation game modeled on the sociological principle of networked social capital is introduced and analyzed. Motivated by the observation that networks found in nature are rarely isolated from one another, this research examines a scenario in which individuals form intra-group links to maximize group cohesion and inter-group links to maximize their group's standing relative to other groups. Our model formulation draws heavily from the empirical research of sociologist Ronald S. Burt and his theory of structural holes, and we derive constructive proofs of the existence of equilibrium outcomes. Departing from the topic of network formation games, I next present research on the strategic seeding of opinions in social networks. This work, which is best introduced in terms of a political election, involves candidates (players) each choosing subsets of voters (nodes in a social network) to seed opinions that are subsequently spread through the voters' social connections by a dynamic process. After the opinions have been allowed to diffuse for a predetermined amount of time, the voters' opinions are aggregated in an election. Voters cast their votes probabilistically, where the probability that they choose a particular candidate is proportional to that voter's opinion toward the candidate relative to their opinion toward the other candidates. Players -- each representing a single candidate -- strategically choose a set of seed nodes that will maximize the probability that their candidate will win the election. We establish the guaranteed existence of pure Nash equilibrium outcomes in the special case where the opinion dynamics are allowed sufficient time to converge to a consensus opinion. We prove that this guarantee does not carry over to cases where the dynamics are not given sufficient time to reach a consensus. We also derive bounds on the budget multiplier, which characterizes the extent that any initial inequality (in terms of players' respective seed budgets) is amplified by the opinion dynamic over the social network into greater inequality in players' utilities. Finally, we analyze the computational problem of finding a player's best response (pure) strategy, proving that it is NP-complete but approximable to within a (1 - 1/e) factor of optimal by a simple greedy algorithm. The concluding chapter of this dissertation presents my work on algorithm instance games, which are a class of games that I have identified as being characterized by having outcomes that are derived from strategy profiles algorithmically. Primarily a conceptual contribution, this research identifies a class of games that includes algorithmic mechanism design as a special case. Two variants of a simple game from this class that is based on the Set Cover optimization problem are presented and analyzed to demonstrate how algorithmic design decisions can influence strategic behavior.