Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Regulating the Ocean: Piracy and Protection along the East African Coast

From 2008-2012, a dramatic upsurge in incidents of maritime piracy in the Western Indian Ocean led to renewed global attention to this region: including the deployment of multi national naval patrols, attempts to prosecute suspected pirates, and the development of financial interdiction systems to track and stop the flow of piracy ransoms. Largely seen as the maritime ripple effect of anarchy on land, piracy has been slotted into narratives of state failure and problems of governance and criminality in this region.

This view fails to account for a number of factors that were crucial in making possible the unprecedented rise of Somali piracy and its contemporary transformation. Instead of an emphasis on failed states and crises of governance, my dissertation approaches maritime piracy within a historical and regional configuration of actors and relationships that precede this round of piracy and will outlive it. The story I tell in this work begins before the contemporary upsurge of piracy and closes with a foretaste of the itineraries beyond piracy that are being crafted along the East African coast.

Beginning in the world of port cities in the long nineteenth century, my dissertation locates piracy and the relationship between trade, plunder, and state formation within worlds of exchange, including European incursions into this oceanic space. Scholars of long distance trade have emphasized the sociality engendered through commerce and the centrality of idioms of trust and kinship in structuring mercantile relationships across oceanic divides. To complement this scholarship, my work brings into view the idiom of protection: as a claim to surety, a form of tax, and a moral claim to authority in trans-regional commerce.

To build this theory of protection, my work combines archival sources with a sustained ethnographic engagement in coastal East Africa, including the pirate ports of Northern Somalia, and focuses on the interaction between land-based pastoral economies and maritime trade. This connection between land and sea calls attention to two distinct visions of the ocean: one built around trade and mobility and the other built on the ocean as a space of extraction and sovereignty. Moving between historical encounters over trade and piracy and the development of a national maritime economy during the height of the Somali state, I link the contemporary upsurge of maritime piracy to the confluence of these two conceptualizations of the ocean and the ideas of capture, exchange, and redistribution embedded within them.

The second section of my dissertation reframes piracy as an economy of protection and a form of labor implicated within other legal and illegal economies in the Indian Ocean. Based on extensive field research, including interviews with self-identified pirates, I emphasize the forms of labor, value, and risk that characterize piracy as an economy of protection. The final section of my dissertation focuses on the diverse international, regional, and local responses to maritime piracy. This section locates the response to piracy within a post-Cold War and post-9/11 global order and longer attempts to regulate and assuage the risks of maritime trade. Through an ethnographic focus on maritime insurance markets, navies, and private security contractors, I analyze the centrality of protection as a calculation of risk and profit in the contemporary economy of counter-piracy.

Through this focus on longer histories of trade, empire, and regulation my dissertation reframes maritime piracy as an economy of protection straddling boundaries of land and sea, legality and illegality, law and economy, and history and anthropology.