JECCO UK 2025

Mathematicians invented it in the 1940s, game theorists, economists and political philosophers developed it from the 1950s, and computer scientists joined the crowd with new algorithmic and approximation methods at the beginning of this century. I will discuss how the two main concepts, Fair Share and No Envy, evolved with the emergence of the digital economy and the new transactions opportunities it offers. And speculate about some related directions of research.

We study a temporal voting model where voters have dynamic preferences over a set of public chores---projects that benefit society, but impose individual costs on those affected by their implementation. We investigate the computational complexity of optimizing utilitarian and egalitarian welfare. Our results show that while optimizing the former is computationally straightforward, minimizing the latter is computationally intractable, even in very restricted cases. Nevertheless, we identify several settings where this problem can be solved efficiently, either exactly or by an approximation algorithm. We also examine the effects of enforcing temporal fairness and its impact on social welfare, and analyze the competitive ratio of online algorithms. We then explore the strategic behavior of agents, providing insights into potential malfeasance in such decision-making environments. Finally, we discuss a range of fairness measures and their suitability for our setting.

The Social Ranking problem consists in determining a ranking over items' power or influence within their population, by measuring their interactions with the other items, based on ordinal preferences over groups they may form. Several methods have been introduced in the literature to determine such a ranking, based on a complete preorder over the coalitions. This input can in practice prove tedious to gather, however, as the number of coalitions to consider grows exponentially with the size of the population. For this reason, we consider a relaxed version of the Social Ranking problem, in which only a partial preorder is required as input, and there is therefore missing information about some coalitions.

We have investigated different contexts of missing information: firstly, we studied a context in which the missing information is available through queries, and proposed elicitation methods, targeting key coalitions to gather sufficient information in order to infer the ranking over items; then, we studied a context in which the missing coalitions are not subject to queries, but the preferences over coalitions are assumed to follow a given structure, and we observed the robustness of "classical" social ranking methods under varying numbers of missing coalitions. Finally, we consider a context in which the missing information is not subject to queries because the missing coalitions are unrealisable, and investigate the possibility of a second, complementary measure of interactions by considering that missing coalitions express incompatibilities between their components.

We study the computational complexity of problems that have at most one solution, namely unambiguous problems. We focus mainly on problems syntactically in $\Sigma_2^P$, typically of the form: "Does there {\em exist} an item that beats all others?" Motivated by questions in social choice and game theory, we study the existence of (1) a dominating strategy in a game, (2) a Condorcet winner, (3) a strongly popular partition in hedonic games, and (4) a winner (sink) in a tournament. We classify these problems, showing the first is $P^{NP}$-complete, the second and third are complete for a class we term $PCW$ (Polynomial Condorcet Winner), and the fourth for a class we term $PTW$ (Polynomial Tournament Winner). We define another unambiguous class $PMA$ (Polynomial Majority Argument), seemingly incomparable to $PTW$. We show that with randomization, $PCW$ and $PTW$ collapse to $P^{NP}$, and $PMA$ is contained in $P^{NP}$. Specifically, we prove: $P^{NP} \subseteq PCW \subseteq PTW \subseteq S_2P$, and $coNP \subseteq PMA \subseteq S_2P$ (and it is know that $S_2P\subseteq ZPP^{NP} \subseteq \Sigma_2^P \cap \Pi_2^P$).

Abstract: Imperfect-recall games, in which players may forget previously acquired information, have found many practical applications, ranging from game abstractions to team games and testing AI agents. In this paper, we quantify the utility gain by endowing a player with perfect recall, which we call the value of recall (VoR). While VoR can be unbounded in general, we parameterize it in terms of various game properties, namely the structure of chance nodes and the degree of absentmindedness (the number of successive times a player enters the same information set). Further, we identify several pathologies that arise with VoR, and show how to circumvent them. We also study the complexity of computing VoR, and how to optimally apportion partial recall. Finally, we connect VoR to other previously studied concepts in game theory, including the price of anarchy. We use that connection in conjunction with the celebrated smoothness framework to characterize VoR in a broad class of games.

Paper: https://arxiv.org/pdf/2412.19659 (AAAI 2025)

This talk will explore the conceptual and computational landscape of non-bipartite stable matching problems. I will begin with the classical one-to-one setting, where stable and unstable instances can be characterised via stable partitions. I will briefly present new results for this framework and review the tractability frontier of efficiently computable solutions - such as maximum and fractional stable matchings - as well as hard optimisation problems like optimal stable matchings, almost-stable matchings and restricted-agent deletions.

I will then turn to a capacitated generalisation of the problem model and introduce a new extension of stable partitions to this setting. This efficiently computable structure provides a tight characterisation of problem instances and has inherent connections and applications to the computation of alternative solution concepts, including near-feasible and almost-stable matchings, both of which are of high theoretical and practical interest. I will conclude by pointing to a conceptual gap between these two notions and outlining possible directions for resolving it.

Papers: https://arxiv.org/abs/2406.00437 (SAGT'24), https://arxiv.org/abs/2505.11456

We study a continuous-time, infinite-horizon dynamic bipartite matching problem. Suppliers arrive according to a Poisson process; while waiting, they may abandon the queue at a uniform rate. Customers on the other hand must be matched upon arrival. The objective is to minimize the expected long-term average cost subject to a throughput constraint on the total match rate.

Previous literature on dynamic matching focuses on "static" policies, where the matching decisions do not depend explicitly on the state of the supplier queues, achieving constant-factor approximations. By contrast, we design "adaptive'' policies, which leverage queue length information, and obtain near-optimal polynomial-time algorithms for several classes of instances.

First, we develop a bi-criteria fully polynomial-time approximation scheme for dynamic matching on networks with a constant number of queues—that computes a $(1-\varepsilon)$-approximation of the optimal policy in time polynomial in both the input size and $1/\varepsilon$. A key new technique is a hybrid LP relaxation, which combines static and state-dependent LP approximations of the queue dynamics, after a decomposition of the network. Networks with a constant number of queues are motivated by deceased organ donation schemes, where the supply types can be divided according to blood and tissue types.

The above algorithm, combined with a careful cell decomposition gives a polynomial-time approximation scheme for dynamic matching on Euclidean networks of fixed dimension. The Euclidean case is of interest in ride-hailing and spatial service platforms, where the goal is to fulfill as many trips as possible while minimizing driving distances.

Paper: https://arxiv.org/abs/2501.08775 (STOC'25)

We study the utilitarian distortion of social choice mechanisms under the recently proposed learning-augmented framework where some (possibly unreliable) predicted information about the preferences of the agents is given as input. In particular, we consider two fundamental social choice problems: single-winner voting and one-sided matching. In these settings, the ordinal preferences of the agents over the alternatives (either candidates or items) is known, and some prediction about their underlying cardinal values is also provided. The goal is to leverage the prediction to achieve improved distortion guarantees when it is accurate, while simultaneously still achieving reasonable worst-case bounds when it is not. This leads to the notions of consistency and robustness, and the quest to achieve the best possible tradeoffs between the two. We show tight tradeoffs between the consistency and robustness of ordinal mechanisms for single-winner voting and one-sided matching, for different levels of information provided by as prediction.

Paper: https://arxiv.org/abs/2502.06489 (EC 2025)

Stablecoins are cryptocurrencies whose value is pegged to some non-volatile currency like the US Dollar, and backed by some underlying reserves, which, depending on the design, can be either fiat currencies or cryptocurrencies themselves. In this work, we investigate the relationship between the stability of stablecoins and the price volatility of the reserves. To this end, we propose an appropriate theoretical model for studying the livelihood of stablecoin systems, and obtain both analytical and experimental results on how the reserves deplete as a function of their price volatility. At a more fine-grained level, our results relate the rate of depletion with the variance in the price distribution, as well as the potential for arbitrage opportunities, expressed via the patience and attitude towards risk of the agents involved in the system. Both our theoretical findings and our simulations suggest that, in the absence of other contingency measures, a stablecoin system operating on unstable reserves is not long-term sustainable.

Financial networks model a set of banks interconnected by monetary obligations. Recent work has introduced a class of obligations called Credit Default Swaps ("CDS"), a well-known type of financial derivative.

The main computational challenge in financial systems is 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.

It is established that the clearing problem is computationally tractable when dealing with simple debt contracts, while existing techniques show PPAD-hardness for finding a weak approximate \( \varepsilon \)-solution when CDSes are involved, within an unspecified small range for \( \varepsilon \).

This presentation addresses the clearing problem in financial networks containing simple debt contracts and credit default swaps and presents results on the following aspects of the problem:

• Exact Computation
• Approximation Strength
• Algorithms and Heuristics

Papers: here, here, and here.

We study a model of subscription-based platforms where users pay a fixed fee for unlimited access to content, and creators receive a share of the revenue. Existing approaches to detecting fraud predominantly rely on machine learning methods, engaging in an ongoing arms race with bad actors. We explore revenue division mechanisms that inherently disincentivize manipulation. We formalize three types of manipulation-resistance axioms and examine which existing rules satisfy these. We show that a mechanism widely used by streaming platforms, not only fails to prevent fraud, but also makes detecting manipulation computationally intractable. We also introduce a novelrule, ScaledUserProp, that satisfies all three manipulation-resistance axioms. Finally, experiments with both real-world and synthetic streaming data support ScaledUserProp as a fairer alternative compared to existing rules.

A multiselves equilibrium is a game-theoretic situation in which some or all of the players are assumed to be "like-minded" in the sense that they count on each other to use the same strategy. Multiselves equilibria lead to problems of designing of algorithms whose analysis assumes that multiple copies of the same algorithm will interact with each other. That, in turn, is a theme that arises in various other setting of algorithms and complexity theory, which I will touch on in the talk. I will mainly try to explain how they model absentmindedness in the context of decision theory, and the distinction between causal and evidential decision theory.

Stackelberg equilibria, as functions of the players' payoffs, can inversely reveal information about the players' incentives. In this paper, we study to what extent one can learn about the leader's incentives by actively querying the leader's optimal commitments against strategically designed followers. We show that, by using polynomially many queries and operations, one can learn a payoff function that is strategically equivalent to the leader's, in the sense that: 1) it preserves the leader's preference over almost all strategy profiles; and 2) it preserves the set of all possible (strong) Stackelberg equilibria the leader may engage in, considering all possible follower types. As an application, we show that the information acquired by our algorithm is sufficient for a follower to induce the best possible Stackelberg equilibrium by imitating a different follower type. To the best of our knowledge, we are the first to demonstrate that this is possible without knowing the leader's payoffs beforehand.

Joint work with: Xiaotie Deng (Peking University), Jiarui Gan (Uiversity of Oxford), and Yuhao Li (Columbia University)

Agents in social networks with threshold-based dynamics change opinions when influenced by sufficiently many peers. Existing literature typically assumes that the network structure and dynamics are fully known, which is often unrealistic. In this work, we ask how to learn a network structure from samples of the agents' synchronous opinion updates. Firstly, if the opinion dynamics follow a threshold rule where a fixed number of influencers prevent opinion change (e.g., unanimity and quasi-unanimity), we give an efficient PAC learning algorithm provided that the number of influencers per agent is bounded. Secondly, under standard computational complexity assumptions, we prove that if the opinion of agents follows the majority of their influencers, then there is no efficient PAC learning algorithm. We propose a polynomial-time heuristic that successfully learns consistent networks in over 97% of our simulations on random graphs, with no failures for some specified conditions on the numbers of agents and opinion diffusion examples.

We define a new procedure to nudge the selection of desirable outcomes in games played by algorithms. We consider the case where agents use a learning algorithm to play. The innovative feature is to introduce a correlation device: decision makers update the values assigned to each action given the past actions performance and a payoff irrelevant message. Messages, which can be either public or private, are correlated among players. The probability distribution over messages is either fixed or time-varying according to some welfare criterion. We ask the following questions: do algorithms learn desirable correlated equilibria? Does information improves welfare and fairness when algorithms compete? We give a partial answer to the above questions based on simulations.

Joint work with Mateus Hiro Nagata (HEC Paris)

Paper: preprint

We consider the computational complexity of computing Bayes-Nash equilibria in first-price auctions, where the bidders' values for the item are drawn from a general (possibly correlated) joint distribution. We show that when the values and the bidding space are discrete, determining the existence of a pure Bayes-Nash equilibrium is NP-hard. This is the first hardness result in the literature of the problem that does not rely on assumptions of subjectivity of the priors, or convoluted tie-breaking rules. We then present two main approaches for achieving positive results, via bid sparsification and via bid densification. The former is more combinatorial and is based on enumeration techniques, whereas the latter makes use of the continuous theory of the problem developed in the economics literature. Using these approaches, we develop polynomial-time approximation algorithms for computing equilibria in symmetric settings or settings with a fixed number of bidders, for different (discrete or continuous) variants of the auction.

Paper: https://arxiv.org/abs/2506.05322 (EC 2025)

We present the commonly used notions of fairness, in particular we examine cases based on the notion of envy-free up to one good (EF1). We provide ways how we can restore the fairness of allocations, when they lose the EF1 property. In addition, we examine the open questions that we can follow up on from this research.

We study the problem of fairly allocating a set of chores to a group of agents. The existence of envy-free up to any item (EFX) allocations is a long-standing open question for both goods and chores. We resolve this question by providing a negative answer for the latter, presenting a simple construction that admits no EFX solutions for allocating six items to three agents equipped with superadditive cost functions, thus proving a separation result between goods and bads. In fact, we uncover a deeper insight, showing that the instance has unbounded approximation ratio. Moreover, we show that deciding whether an EFX allocation exists is NP-complete. On the positive side, we establish the existence of EFX allocations under general monotone cost functions when the number of items is at most $n + 2$. We then shift our attention to additive cost functions. We employ a general framework in order to improve the approximation guarantees in the well-studied case of three additive agents, and provide several conditional approximation bounds that leverage ordinal information.

Joint work with Christodoulos Santorinaios.

Paper: https://arxiv.org/abs/2406.10752

Facility Location Problems are well studied in the literature of operational research. These involve selecting a set of facilities to open from a set of candidate locations. Customers are then allocated to facilities to satisfy their demand.

Classically both the choice of location and the customer allocation is completed by a central decision maker, and customers cannot choose among the open facilities. However customer preferences may not align with those of the decision maker. This talk shows how such preferences can be incorporated into integer linear programming formulations for the problem, enforcing stability with regard to these preferences. Variants including facility capacity and single source allocation are also discussed. Finally the effect of the Kendall-Tau distance between customer and locator preferences on runtime is investigated.

Reference: Pierre Hanjoul and Dominique Peeters. A facility location problem with clients' preference orderings. Regional Science and Urban Economics 17(3), 451-473, 1987.

Joint work with Sergio Garcia and Akshay Gupte.