In their seminal work on systemic risk in financial markets, Eisenberg and Noe proposed and studied a model with @math firms embedded into a network of debt relations. We analyze this model from a game-theoretic point of view. Every firm is a rational agent in a directed graph that has an incentive to allocate payments in order to clear as much of its debt as possible. Each edge is weighted and describes a liability between the firms. We consider several variants of the game that differ in the permissible payment strategies. We study the existence and computational complexity of pure Nash and strong equilibria, and we provide bounds on the (strong) prices of anarchy and stability for a natural notion of social welfare. Our results highlight the power of financial regulation -- if payments of insolvent firms can be centrally assigned, a socially optimal strong equilibrium can be found in polynomial time. In contrast, worst-case strong equilibria can be a factor of @math away from optimal, and, in general, computing a best response is an NP-hard problem. For less permissible sets of strategies, we show that pure equilibria might not exist, and deciding their existence as well as computing them if they exist constitute NP-hard problems.
On a more technical level, our game-theoretic approach is related to a number of existing game-theoretic models based on flows in networks. In cooperative game theory, there are several notions of flow games based on a directed flow network. Existing variants include games, where edges are players @cite_2 @cite_8 @cite_22 @cite_0 @cite_7 @cite_20 , or each player owns a source-sink pair @cite_1 @cite_12 . The total value of a coalition @math is the profit from a maximum (multi-commodity) flow that can be routed through the network if only the players in @math are present. There is a rich set of results on structural characterizations and computability of solutions in the core, as well as other solution concepts for cooperative games. In contrast to our work, these games are non-strategic. Instead, here we consider each player as a single node with a strategic decision about flow allocation.
@cite_22 @cite_7 @cite_8 @cite_1 @cite_0 @cite_2 @cite_12 @cite_20
2028847614 2064699170 2125537511 2076900408 2034600319 2005690414
A class of characteristic function games arising from maximum flow problems is introduced and is shown to coincide with the class of totally balanced games. The proof relies on the max flow-min cut theorem of Ford and Fulkerson and on the observation that the class of totally balanced games is the span of the additive games with the minimum operation. A class of multiperson mathematical optimization problems is considered and is shown to generate cooperative games with nonempty cores. The class includes, but is not restricted to, numerous versions of network flow problems. It was shown by Owen that for games generated by linear programming optimization problems, optimal dual solutions correspond to points in the core. We identify a special class of network flow problems for which the converse is true, i.e., every point in the core corresponds to an optimal dual solution. If the Internet is the next great subject for Theoretical Computer Science to model and illuminate mathematically, then Game Theory, and Mathematical Economics more generally, are likely to prove useful tools. In this talk I survey some opportunities and challenges in this important frontier. A cooperative game in characteristic-function form is obtained by allowing a number of individuals to esercise partial control over the constraints of a (generally nonlinear) mathematical programming problem, either directly or through committee voting. Conditions are imposed on the functions defining the programming problem and the control system which suffice to make the game totally balanced. This assures a nonempty core and hence a stable allocation of the full value of the programming problem among the controlling palyers. In the linear case the core is closely related to the solutions of the dual problem. Applications are made to a variety of economic models, including the transferable utility trading economies of Shapley and Shubik and a multishipper one-commodity transshipment model with convex cost functions and concave revenue functions. Dropping the assumption of transferable utility leads to a class of controlled multiobjective or ‘Pareto programming’ problems, which again yield totally balanced games. In citepapa, Papadimitriou formalized the notion of routing stability in BGP as the following coalitional game theoretic problem: Given a network with a multicommodity flow satisfying node capacity and demand constraints, the payoff of a node is the total flow originated or terminated at it. A payoff allocation is in the core if and only if there is no subset of nodes that can increase their payoff by seceding from the network. We answer one of the open problems in citepapa by proving that for any network, the core is non-empty in both the transferable (where the nodes can compensate each other with side payments) and the non-transferable case. In the transferable case we show that such an allocation can be computed in polynomial time. We also generalize this result to the case where a strictly concave utility function is associated with each commodity. Preference aggregation is used in a variety of multiagent applications, and as a result, voting theory has become an important topic in multiagent system research. However, power indices (which reflect how much "real power" a voter has in a weighted voting system) have received relatively little attention, although they have long been studied in political science and economics. We consider a particular multiagent domain, a threshold network flow game. Agents control the edges of a graph; a coalition wins if it can send a flow that exceeds a given threshold from a source vertex to a target vertex. The relative power of each edge agent reflects its significance in enabling such a flow, and in real-world networks could be used, for example, to allocate resources for maintaining parts of the network. We examine the computational complexity of calculating two prominent power indices, the Banzhaf index and the Shapley-Shubik index, in this network flow domain. We also consider the complexity of calculating the core in this domain. The core can be used to allocate, in a stable manner, the gains of the coalition that is established. We show that calculating the Shapley-Shubik index in this network flow domain is NP-hard, and that calculating the Banzhaf index is #P-complete. Despite these negative results, we show that for some restricted network flow domains there exists a polynomial algorithm for calculating agents' Banzhaf power indices. We also show that computing the core in this game can be performed in polynomial time.