Reductions are the fundamental tool of computational complexity. They allow classification of computational problems into families (somewhat resembling those in biology), with problems in the same class sharing common features (in particular NP-complete problems being isomorphic versions of a single problem, if we believe that the Berman-Hartmanis conjecture [6] holds). A significant concern in the literature on complexity-theoretic reductions is to make the theory of reductions more predictive. This means that we should aim to better connect the structural properties of the two problems that the given reduction is connecting. For instance the notion of pasimonious reduction attempts to preserve the total number of solutions between instances.

We study the power of (competitive) algorithms with predictions in a multiagent setting. To this extent we introduce a multiagent version of the ski-rental problem. In this problem agents can collaborate by pooling resources to get a group license for some asset. If the license price is not met agents have to rent the asset individually for the day at a unit price. Otherwise the license becomes available forever to everyone at no extra cost. Our main contribution is a best-response analysis of a single-agent competitive algorithm that assumes perfect knowledge of other agents' actions (but no knowledge of its own renting time). We then analyze the setting when agents have a predictor for their own active time, yielding a tradeoff between robustness and consistency. We investigate the effect of using such a predictor in an equilibrium, as well as the new equilibria formed in this way.

The theory of algorithms with predictions [1, 2, 3] is, without a doubt, one of the most exciting recent research directions in algorithmics: when supplemented by a (correct) predictor, often based on machine learning, the newly-developed algorithms are capable of outcompeting their worst-case classical counterparts. A desirable feature of such algorithms is, of course, to perform comparably to the (worst-case) algorithms when the predictors are really bad. This requirement often results [2] in tradeoffs between two measures of algorithm performance, robustness and consistency. A significant amount of subsequent research has followed, summarized by the algorithms with predictions webpage [3]. Recently, the idea of augmenting algorithms by predictions has been adapted to the game-theoretic setting of mechanism design [4, 5, 6, 7]: indeed, strategyproof mechanisms often yield solutions that are only approximately optimal [8]. On the other hand, if the designer has access to a predictor for the desired outcome it could conceivably take advantage of this information by creating mechanisms that lead to an improved approximation ratio, compared to their existing (worst-case) counterparts. Tradeoffs between robustness and consistency similar to the ones from [2] apply to this setting as well.

We investigate Kantian equilibria in finite normal form games, a class of non-Nashian, morally motivated courses of action that was recently proposed in the economics literature. We highlight a number of problems with such equilibria, including computational intractability, a high price of miscoordination, and problematic extension to general normal form games. We give such a generalization based on concept of program equilibria, and point out that that a practically relevant generalization may not exist. To remedy this we propose some general, intuitive, computationally tractable, other-regarding equilibria that are special cases Kantian equilibria, as well as a class of courses of action that interpolates between purely self-regarding and Kantian behavior.

We advocate the development of a discipline of interacting with and extracting information from models, both mathematical (e.g. game-theoretic ones) and computational (e.g. agent-based models). We outline some directions for the development of a such a discipline: - the development of logical frameworks for the systematic formal specification of stylized facts and social mechanisms in (mathematical and computational) social science. Such frameworks would bring to attention new issues, such as phase transitions, i.e. dramatical changes in the validity of the stylized facts beyond some critical values in parameter space. We argue that such statements are useful for those logical frameworks describing properties of ABM. - the adaptation of tools from the theory of reactive systems (such as bisimulation) to obtain practically relevant notions of two systems "having the same behavior". - the systematic development of an adversarial theory of model perturbations, that investigates the robustness of conclusions derived from models of social behavior to variations in several features of the social dynamics. These may include: activation order, the underlying social network, individual agent behavior.

We investigate Kantian equilibria in finite normal form games, a class of non-Nashian, morally motivated courses of action that was recently proposed in the economics literature. We highlight a number of problems with such equilibria, including computational intractability, a high price of miscoordination, and expensive/problematic extension to general normal form games. We point out that such a proper generalization will likely involve the concept of program equilibrium. Finally we propose some general, intuitive, computationally tractable, other-regarding equilibria related to Kantian equilibria, as well as a class of courses of action that interpolates between purely self-regarding and Kantian behavior.

We study strategic network formation games in which agents attempt to form (costly) links in order to maximize their network centrality. Our model derives from Jackson and Wolinsky's symmetric connection model, but allows for heterogeneity in agent utilities by replacing decay centrality (implicit in the Jackson-Wolinsky model) by a variety of classical centrality and game-theoretic measures of centrality. We are primarily interested in characterizing the asymptotically pairwise stable networks, i.e. those networks that are pairwise stable for all sufficiently small, positive edge costs. We uncover a rich typology of stability: - we give an axiomatic approach to network centrality that allows us to predict the stable network for a rich set of combination of centrality utility functions, yielding stable networks with features reminiscent of structural properties such as "core periphery" and "rich club" networks. - We show that a simple variation on the model renders it universal, i.e. every network may be a stable network. - We also show that often we can infer a significant amount about agent utilities from the structure of stable networks.

It's Not Whom You Know, It's What You (or Your Friends) Can Do: Succint Coalitional Frameworks for Network Centralities. September 25, 2019 Abstract We investigate the representation of game-theoretic measures of network centrality using a framework that blends a social network representation with the succint formalism of cooperative skill games. We discuss the expressiveness of the new framework and highlight some of its advantages, including a fixed-parameter tractability result for computing centrality measures under such representations. As an application we introduce new network centrality measures that capture the extent to which neighbors of a certain node can help it complete relevant tasks. 1 Introduction Measures of network centrality have a long and rich history in the social sciences [1] and Artificial Intelligence. Such measures have proved useful for a variety of tasks, such as identifying spreading nodes [2] and gatekeepers for information dissemination [3], advertising ...

We investigate the manipulation of power indices in TU-cooperative games by stimulating (subject to a budget constraint) changes in the propensity of other players to participate to the game. We display several algorithms that show that the problem is often tractable for so-called network centrality games and influence attribution games, as well as an example when optimal manipulation is intractable, even though computing power indices is feasible.