I am broadly interested in theoretical computer science, with a particular emphasis on the intersection of economics and computer science, namely in algorithm design, game theory, learning theory, and networks. Much of my research seeks to further and fortify our quantitative understanding of the emergent properties of strategic, multi-agent systems, primarily through the lens of theoretical computer science. I also maintain active interests in spectral graph theory, analysis of Boolean functions, and probability theory.
Conference Papers
- Stability and Learning in Strategic Queuing Systems, with Éva Tardos.
The Twenty-First ACM Conference on Economics and Computation (EC 20).
[Abstract] [PDF] [EC Talk]
Bounding the price of anarchy, which quantifies the damage to social welfare due to selfish behavior of the participants, has been an important area of research. In this paper, we study this phenomenon in the context of a game modeling queuing systems: routers compete for servers, where packets that do not get service will be resent at future rounds, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. We model this as an (infinitely) repeated game, where the system holds a state (number of packets held by each queue) that arises from the results of the previous round. We assume that routers satisfy the no-regret condition, e.g. they use learning strategies to identify the server where their packets get the best service.
Classical work on repeated games makes the strong assumption that the subsequent rounds of the repeated games are independent (beyond the influence on learning from past history). The carryover effect caused by packets remaining in this system makes learning in our context result in a highly dependent random process. We analyze this random process and find that if the capacity of the servers is high enough to allow a centralized and knowledgeable scheduler to get all packets served even with double the packet arrival rate, and queues use no-regret learning algorithms, then the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority. This paper is the first to study the effect of selfish learning in a queuing system, where the learners compete for resources, but rounds are not all independent: the number of packets to be routed at each round depends on the success of the routers in the previous rounds.
- Adversarial Perturbations of Opinion Dynamics in Networks, with Jon Kleinberg and Éva Tardos.
The Twenty-First ACM Conference on Economics and Computation (EC 20).
[Abstract] [PDF] [EC Talk]
We study the connections between network structure, opinion dynamics, and an adversary's power to artificially induce disagreements. We approach these questions by extending models of opinion formation in the social sciences to represent scenarios, familiar from recent events, in which external actors seek to destabilize communities through sophisticated information warfare tactics via fake news and bots. In many instances, the intrinsic goals of these efforts are not necessarily to shift the overall sentiment of the network, but rather to induce discord. These perturbations diffuse via opinion dynamics on the underlying network, through mechanisms that have been analyzed and abstracted through work in computer science and the social sciences. We investigate the properties of such attacks, considering optimal strategies both for the adversary seeking to create disagreement and for the entities tasked with defending the network from attack. We show that for different formulations of these types of objectives, different regimes of the spectral structure of the network will limit the adversary's capacity to sow discord; this enables us to qualitatively describe which networks are most vulnerable against these perturbations. We then consider the algorithmic task of a network defender to mitigate these sorts of adversarial attacks by insulating nodes heterogeneously; we show that, by considering the geometry of this problem, this optimization task can be efficiently solved via convex programming. Finally, we generalize these results to allow for two network structures, where the opinion dynamics process and the measurement of disagreement become uncoupled, and determine how the adversary's power changes; for instance, this may arise when opinion dynamics are controlled an online community via social media, while disagreement is measured along "real-world" connections.
Preprints
- Virtues of Patience in Strategic Queuing Systems, with Éva Tardos.
In submission, 2020.
[Abstract] [PDF]
We consider the problem of selfish agents in discrete-time queuing systems, where competitive queues try to get their packets served. In this model, a queue gets to send a packet each step to one of the servers, which will attempt to serve the oldest arriving packet, and unprocessed packets are returned to each queue. We model this as a repeated game where queues compete for the capacity of the servers, but where the state of the game evolves as the length of each queue varies, resulting in a highly dependent random process. In classical work for learning in repeated games, the learners evaluate the outcome of their strategy in each step---in our context, this means that queues estimate their success probability at each server. Earlier work by the authors [in EC'20]
shows that with no-regret learners the system needs twice the capacity as would be required in the coordinated setting to ensure queue lengths remain stable, despite the selfish behavior of the queues. In this paper, we demonstrate that this myopic way of evaluating outcomes is suboptimal: if more patient queues choose strategies that selfishly maximize their long-run success rate, stability can be ensured with just $\frac{e}{e-1}\approx 1.58$ times extra capacity, strictly better than what is possible assuming the no-regret property.
As these systems induce highly dependent random processes, our analysis draws heavily on techniques from the theory of stochastic processes to establish various game-theoretic properties of these systems. Though these systems are random even under any
fixed stationary policies by the queues, we show using careful probabilistic arguments that surprisingly, under such fixed policies, these systems have essentially deterministic and explicit asymptotic behavior. We show that the growth rate of a set can be written as the ratio of a submodular and modular function, and
use the resulting explicit description to show that the subsets of queues with largest growth rate is closed under union and non-disjoint intersections, which we use in turn to prove the claimed sharp bicriteria result for the equilibria of the resulting system. Our equilibrium analysis relies on a novel deformation argument towards a more analyzable
solution that is quite different from classical price of anarchy bounds. While the intermediate points in this deformation will not be Nash, the structure will ensure the relevant constraints and incentives similarly hold to establish monotonicity along this continuous path.
- Fractional Pseudorandom Generators from Any Fourier Level, with Eshan Chattopadhyay, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty.
In submission, 2020.
[Abstract] [PDF]
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [CHHL18, CHLT19] that exploit $L_1$ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the $k$-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with $k$. This interpolates previous works, which either require Fourier bounds on all levels [CHHL18], or has polynomial dependence on the error parameter in the seed length [CHLT19], and thus answers an open question in [CHLT19]. As an example, we show that for polynomial error, Fourier bounds on the first $O(\log n)$ levels is sufficient to recover the seed length in [CHHL], which requires bounds on the entire tail.
We obtain our results by an alternate analysis of fractional PRGs using Taylor's theorem and bounding the degree-$k$ Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the level-k unsigned Fourier sum, which is potentially a much smaller quantity than the $L_1$ notion in previous works. By generalizing a connection established in [CHHLZ20], we give a new reduction from constructing PRGs to proving correlation bounds.
Finally, using these improvements we show how to obtain a PRG for $\mathbb{F}_2$ polynomials with seed length close to the state-of-the-art construction due to Viola [Vio08].