We define solution concepts appropriate for computationally bounded players playing a fixed finite game. To do so, we need to define what it means for a computational game, which is a sequence of games that get larger in some appropriate sense, to represent a single finite underlying extensive-form game. Roughly speaking, we require all the games in the sequence to have essentially the same structure as the underlying game, except that two histories that are indistinguishable (i.e., in the same information set) in the underlying game may correspond to histories that are only computationally indistinguishable in the computational game. We define a computational version of both Nash equilibrium and sequential equilibrium for computational games, and show that every Nash (resp., sequential) equilibrium in the underlying game corresponds to a computational Nash (resp., sequential) equilibrium in the computational game. One advantage of our approach is that if a cryptographic protocol represents an abstract game, then we can analyze its strategic behavior in the abstract game, and thus separate the cryptographic analysis of the protocol from the strategic analysis.

The Adaptive Seeding problem is an algorithmic challenge motivated by influence maximization in social networks: One seeks to select among certain accessible nodes in a network, and then select, adaptively, among neighbors of those nodes as they become accessible in order to maximize a global objective function. More generally, adaptive seeding is a stochastic optimization framework where the choices in the first stage affect the realizations in the second stage, over which we aim to optimize. Our main result is a (1 – 1/e)2-approximation for the adaptive seeding problem for any monotone submodular function. While adaptive policies are often approximated via non-adaptive policies, our algorithm is based on a novel method we call locally-adaptive policies. These policies combine a non-adaptive global structure, with local adaptive optimizations. This method enables the (1–1/e)2-approximation for general monotone submodular functions and circumvents some of the impossibilities associated with non-adaptive policies. We also introduce a fundamental problem in submodular optimization that may be of independent interest: given a ground set of elements where every element appears with some small probability, find a set of expected size at most k that has the highest expected value over the realization of the elements. We show a surprising result: there are classes of monotone submodular functions (including coverage) that can be approximated almost optimally as the probability vanishes. For general monotone submodular functions we show via a reduction from Planted-Clique that approximations for this problem are not likely to be obtainable. This optimization problem is an important tool for adaptive seeding via non-adaptive policies, and its hardness motivates the introduction of locally-adaptive policies we use in the main result.

Adapting Seeding is a key algorithmic challenge of influence maximization in social networks. One seeks to select among certain available nodes in a network, and then, adaptively, among neighbors of those nodes as they become available, in order to maximize influence in the overall network. Despite recent strong approximation results [Seeman and Singer 2013; Badanidiyuru et al. 2015], very little is known about the problem when nodes can take on different activation costs. Surprisingly, designing adaptive seeding algorithms that can appropriately incentivize users with heterogeneous activation costs introduces fundamental challenges that do not exist in the simplified version of the problem.

We study the problem of computing an ε-Nash equilibrium in repeated games. Earlier work by Borgs et al. [2010] suggests that this problem is intractable. We show that if we make a slight change to their model---modeling the players as polynomial-time Turing machines that maintain state (rather than stateless polynomial-time Turing machines)---and make some standard cryptographic hardness assumptions (the existence of public key encryption), the problem can actually be solved in polynomial time.

The algorithmic challenge of maximizing information diffusion through word-of-mouth processes in social networks has been heavily studied in the past decade. While there has been immense progress and an impressive arsenal of techniques has been developed, the algorithmic frameworks make idealized assumptions regarding access to the network that can often result in poor performance of state-of-the-art techniques. In this paper we introduce a new framework which we call Adaptive Seeding. The framework is a two-stage stochastic optimization model designed to leverage the potential that typically lies in neighboring nodes of arbitrary samples of social networks. Our main result is an algorithm which provides a constant factor approximation to the optimal adaptive policy for any influence function in the Triggering model.

We show that by modeling people as bounded finite automata, we can capture at a qualitative level the behavior observed in experiments. We consider a decision problem with incomplete information and a dynamically changing world, which can be viewed as an abstraction of many real-world settings. We provide a simple strategy for a finite automaton in this setting, and show that it does quite well, both through theoretical analysis and simulation. We show that, if the probability of nature changing state goes to 0 and the number of states in the automaton increases, then this strategy performs optimally (as well as if it were omniscient and knew when nature was making its state changes). Thus, although simple, the strategy is a sensible strategy for a resource-bounded agent to use. Moreover, at a qualitative level, the strategy does exactly what people have been observed to do in experiments.

Coordination is a challenging everyday task; just think of the last time you organized a party or a meeting involving several people. As a growing part of our social and professional life goes online, an opportunity for an improved coordination process arises. Recently, Gupta et al. proposed entangled queries as a declarative abstraction for data-driven coordination, where the difficulty of the coordination task is shifted from the user to the database. Unfortunately, evaluating entangled queries is very hard, and thus previous work considered only a restricted class of queries that satisfy safety (the coordination partners are fixed) and uniqueness (all queries need to be satisfied). In this paper we significantly extend the class of feasible entangled queries beyond uniqueness and safety. First, we show that we can simply drop uniqueness and still efficiently evaluate a set of safe entangled queries. Second, we show that as long as all users coordinate on the same set of attributes, we can give an efficient algorithm for coordination even if the set of queries does not satisfy safety. In an experimental evaluation we show that our algorithms are feasible for a wide spectrum of coordination scenarios.