Financial networks raise a significant computational challenge in identifying insolvent firms and evaluating their exposure to systemic risk. This task, known as the clearing problem, is computationally tractable when dealing with simple debt contracts. However under the presence of certain derivatives called credit default swaps (CDSes) the clearing problem is $\textsf{FIXP}$-complete. Existing techniques only show $\textsf{PPAD}$-hardness for finding an $ε$-solution for the clearing problem with CDSes within an unspecified small range for $ε$. We present significant progress in both facets of the clearing problem: (i) intractability of approximate solutions; (ii) algorithms and heuristics for computable solutions. Leveraging $\textsf{Pure-Circuit}$ (FOCS'22), we provide the first explicit inapproximability bound for the clearing problem involving CDSes. Our primal contribution is a reduction from $\textsf{Pure-Circuit}$ which establishes that finding approximate solutions is $\textsf{PPAD}$-hard within a range of roughly 5%. To alleviate the complexity of the clearing problem, we identify two meaningful restrictions of the class of financial networks motivated by regulations: (i) the presence of a central clearing authority; and (ii) the restriction to covered CDSes. We provide the following results: (i.) The $\textsf{PPAD}$-hardness of approximation persists when central clearing authorities are introduced; (ii.) An optimisation-based method for solving the clearing problem with central clearing authorities; (iii.) A polynomial-time algorithm when the two restrictions hold simultaneously.

Financial networks model a set of financial institutions (firms) interconnected by obligations. Recent work has introduced to this model a class of obligations called credit default swaps , a well-known type of financial derivative. The main computational challenge for such systems is known as the clearing problem . This problem involves the task of determining insolvent firms and quantifying their exposure to systemic risk. The technical term used to describe this exposure is the clearing recovery rate . In essence, the clearing problem involves computing the clearing recovery rates of all financial institutions in a given network. We address the clearing problem in financial networks containing simple debt contracts and credit default swaps. Our work builds on the model proposed by Schuldenzucker et al. 2016, 2017 and 2020 who analysed the complexity of the \(\epsilon\) -weak (almost)-approximation version of the problem. In this paper, we study the complexity of the problem from the point of view of exact computation, approximation strength and numerically irrational solutions. Our main result establishes FIXP -completeness for the exact computation version of the problem. Consequently, we infer FIXP \({}_{a}\) -completeness for finding a strongly (or ‘near’) approximate solution as a direct consequence of our main result, while we legitimise the significance of the strong approximation variant through an observation that weakly approximate solutions may ‘severely’ misrepresent the actual financial state of an institution. Finally, we study the structural properties required for irrationality, and we identify necessary conditions for numerically irrational solutions to emerge: The presence of certain types of cycles in a financial network forces the recovery rates to take the form of roots of second- or higher-degree polynomials. In the absence of a large subclass of such cycles, we study the complexity of finding an exact solution, which we show to be a problem close to, albeit outside of, PPAD .

We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate the remaining items. Given the known NP-hardness of the problem, we investigate whether—and under which conditions—one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem, which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items; (b) lower bounds that exclude the generalization of these positive results to more general settings. We conclude by showing that—unlike when computing allocations from scratch—the non-algorithmic question of whether more relaxed EFX allocations exist can be completely resolved in the extension setting.

In the recently introduced model of fair partitioning of friends, there is a set of agents located on the vertices of an underlying graph that indicates the friendships between the agents. The task is to partition the graph into k balanced-sized groups, keeping in mind that the value of an agent for a group is equal to the number of edges they have in that group. The goal is to construct partitions that are "fair", i.e., no agent would like to replace an agent in a different group. We generalize the standard model by considering utilities for the agents that are beyond binary and additive. Having this as our foundation, our contribution is threefold: (a) we adapt several fairness notions that have been developed in the fair division literature to our setting; (b) we give several existence guarantees supported by polynomial-time algorithms; (c) we initiate the study of the computational (and parameterized) complexity of the model and provide an almost complete landscape of the (in)tractability frontier for our fairness concepts.

Financial networks model debt obligations between economic firms. Computational and game-theoretic analyses of these networks have been recent focus of the literature. The main computational challenge in this context is the clearing problem, a fixed point search problem that essentially determines insolvent firms and their exposure to systemic risk, technically known as recovery rates. When Credit Default Swaps, a derivative connected to the 2008 financial crisis, are factored into the obligations, the clearing problem becomes more complex. Specifically, whenever insolvent firms pay their debts proportionally to their recovery rates, computing a weakly approximate solution was shown by Schuldenzucker et al. (2017) to be PPAD-complete. Additionally, Ioannidis et al. (2022) showed that computing a strongly approximate solution in the same framework is FIXP-complete. This paper addresses the computational complexity of the clearing problem in financial networks with derivatives, whenever payment priorities among creditors are applied. This practically relevant model has only been studied from a game-theoretic standpoint. We explicitly study the clearing problem whenever the firms pay according to a singleton liability priority list and prove that it is FIXP-complete. Finally, we provide a number of NP-hardness results for the computation of priority lists that optimise specific objectives of importance in the domain.

Financial networks model a set of financial institutions (firms) interconnected by obligations. Recent work has introduced to this model a class of obligations called credit default swaps, a certain kind of financial derivatives. The main computational challenge for such systems is known as the clearing problem, which is to determine which firms are in default and to compute their exposure to systemic risk, technically known as their recovery rates. It is known that the recovery rates form the set of fixed points of a simple function, and that these fixed points can be irrational. Furthermore, Schuldenzucker et al. (2016) have shown that finding a weakly (or "almost") approximate (rational) fixed point is PPAD-complete. We further study the clearing problem from the point of view of irrationality and approximation strength. Firstly, we observe that weakly approximate solutions may misrepresent the actual financial state of an institution. On this basis, we study the complexity of finding a strongly (or "near") approximate solution, and show FIXP-completeness. We then study the structural properties required for irrationality, and we give necessary conditions for irrational solutions to emerge: The presence of certain types of cycles in a financial network forces the recovery rates to take the form of roots of non-linear polynomials. In the absence of a large subclass of such cycles, we study the complexity of finding an exact fixed point, which we show to be a problem close to, albeit outside of, PPAD.

Fair division has emerged as a very hot topic in EconCS research, and envy-freeness is among the most compelling fairness concepts. An allocation of indivisible items to agents is envy-free if no agent prefers the bundle of any other agent to his own in terms of value. As envy-freeness is rarely a feasible goal, there is a recent focus on relaxations of its definition. An approach in this direction is to complement allocations with payments (or subsidies) to the agents. A feasible goal then is to achieve envy-freeness in terms of the total value an agent gets from the allocation and the subsidies. We consider the natural optimization problem of computing allocations that are envy-freeable using the minimum amount of subsidies. As the problem is NP-hard, we focus on the design of approximation algorithms. On the positive side, we present an algorithm which, for a constant number of agents, approximates the minimum amount of subsidies within any required accuracy, at the expense of a graceful increase in the running time. On the negative side, we show that, for a superconstant number of agents, the problem of minimizing subsidies for envy-freeness is not only hard to compute exactly (as a folklore argument shows) but also, more importantly, hard to approximate.