Game theory has been widely used for modeling strategic behaviors in networked multiagent systems. However, the context within which these strategic behaviors take place has received limited attention. We present a model of strategic behavior in networks that incorporates the behavioral context. We focus on the contextual aspects of congressional voting. A senator's decision to vote yea or nay on a bill comes as a result of their ideologies, agendas, and their interactions with other senators. One salient model in political science is the ideal point model , which assigns each senator and each bill a number on the real line of political spectrum. These points then allow for prediction of future voting behavior. We extend the classical ideal point model with network-structured interactions among senators. In contrast to the ideal point model's prediction of individual voting behavior, we predict joint voting behaviors in a game-theoretic fashion. Our model also includes the characteristics of a bill. This allows it to outperform previous models that solely focus on the networked interactions among senators with no bill-specific parameters. We focus on two fundamental questions: learning the model using real-world data and computing stable outcomes of the model in order to predict joint voting behaviors. We demonstrate the effectiveness of our model through experiments using data from the 114th U.S. Congress.

We provide the first fully polynomial time approximation scheme (FPTAS) for computing an approximate mixed-strategy Nash equilibrium in graphical multi-hypermatrix games (GMhGs), which are generalizations of normal-form games, graphical games, graphical polymatrix games, and hypergraphical games. Computing an exact mixed-strategy Nash equilibria in graphical polymatrix games is PPAD complete and thus generally believed to be intractable. In contrast, to the best of our knowledge, we are the first to establish an FPTAS for tree polymatrix games as well as tree graphical games when the number of actions is bounded by a constant. As a corollary, we give a quasi-polynomial time approximation scheme (quasi-PTAS) when the number of actions is bounded by a logarithm of the number of players.

We propose influence games, a new class of graphical games, as a model of the behavior of large but finite networked populations. Grounded in non-cooperative game theory, we introduce a new approach to the study of influence in networks that captures the strategic aspects of complex interactions in the network. We study computational problems on influence games, including the identification of the most influential nodes. We characterize the computational complexity of various problems in influence games, propose several heuristics for the hard cases, and design approximation algorithms, with provable guarantees, for the most influential nodes problem.

We explore the art gallery problem for the special case that the domain (gallery) P is an m-polyomino, a polyform whose cells are m unit squares. We study the combinatorics of guarding polyominoes in terms of the parameter m, in contrast with the traditional parameter n, the number of vertices of P; in particular, we show that floor((m+1)/3) point guards are always sufficient and sometimes necessary to cover an m-polyomino. When m d 3n/4 - 4, the point guard sufficiency condition yields a strictly lower guard number than floor(n/4), given by the art gallery theorem for orthogonal polygons. When pixels behave themselves like guards (pixel guards), we prove that floor(3m/11) + 1 guards are sufficient and sometimes necessary to cover an m-polyomino. We also study the algorithmic complexity of computing optimal guard sets for polyominoes. We prove that determining the guard number of a given m-polyomino is NP-hard. We provide polynomial-time algorithms to solve exactly some special cases in which the polyomino is "thin".