JECCO UK 2026

University of Glasgow

Stability is crucial in matching markets, yet in many real-world settings — from hospital residency allocations to roommate assignments — full stability is either impossible to achieve or can come at the cost of leaving many agents unmatched. When stability cannot be achieved, algorithmicists and market designers face a critical question: how should instability be measured and distributed among participants? Existing approaches to "almost-stable" matchings focus on aggregate measures, minimising either the total number of blocking pairs or the count of agents involved in blocking pairs. However, such aggregate objectives can result in concentrated instability on a few individual agents, raising concerns about fairness and incentives to deviate.

We introduce a fairness-oriented approach to approximate stability based on the minimax principle: we seek matchings that minimise the maximum number of blocking pairs any agent finds themselves in. Equivalently, we minimise the maximum number of agents that anyone has justified envy towards. This distributional objective protects the worst-off agents from bearing a disproportionate amount of instability. We characterise the computational complexity of this notion across fundamental matching settings, uncover surprisingly strong intractability results, provide efficient algorithms for special cases, and discuss the approximability of these problems. Our results map the algorithmic landscape and reveal fundamental trade-offs between distributional guarantees on justified envy and computational feasibility in matching market design.

https://arxiv.org/pdf/2601.14195

University of Southampton

School choice mechanisms have increased school segregation across municipalities worldwide, with urban geography and proximity-based admissions priorities restricting disadvantaged families' feasible choices. Quota-based approaches for reducing segregation face computational intractability and can produce Pareto inferior outcomes. Existing research suggests transportation significantly influences school selection decisions. We propose a stable, student-optimal matching mechanism that incorporates transportation directly into the allocation process, enabling eligible students from disadvantaged areas to access expanded choice sets. Our mechanism extends deferred acceptance by allowing route-eligible students to rank route-school tuples (contracts) alongside individual schools, with these students receiving priority equivalent to local students at served schools. We prove that our mechanism terminates, produces stable matchings, and returns the student-optimal stable matching when the student-oriented version is executed. Preliminary experiments demonstrate lower dissimilarity indices compared to standard deferred acceptance, suggesting potential for reducing proximity-induced segregation while maintaining desirable matching properties.

Technical University of Munich

Combinatorial markets provide a general framework for trading indivisible goods in bundles. Building on the market settings of Bikhchandani and Ostroy [2002] and Bichler and Waldherr [2017], we extend these models by introducing explicit side payments, allowing restricted transfer of utility among subsets of agents, and capturing different forms of financial collusion. Although this extension results in a large number of seemingly distinct market settings, we establish a systematic classification of their expressive power. Most notably, we show that higher-order market settings (i.e., those with more personalized prices and less clearinghouse power) are essentially equivalent in terms of market properties when side payments are permitted between buyers. An analogous collapse occurs for the third- and higher-order settings when side payments are permitted between sellers. In contrast, we identify a fundamental structural separation between the second- and third-order settings. To analyze stability in these environments, we generalize the classical concepts of stability with and without transferable utility (TU and NTU) to a partition-based notion of restricted transferability (the T-core). We relate stable outcomes across different settings to appropriate stability notions, identify market instances in which partially transferable utility yields a better (or any) stable outcome, and show that under personalized pricing, all stability notions collapse to NTU-stability.

King's College London

Economic models adopted by trading agents do not merely analyse markets, but actively shape them. This effect, known as performativity, arises when strategies follow established economic theories, resulting in a collective alteration of market dynamics by creating self-fulfilling prophecies. Although discussed in the literature on economic sociology, this deeply rooted phenomenon lacks mathematical formulation in financial markets. Our paper closes this gap by studying performativity in the context of market making in financial markets, by breaking down the canonical separation of diffusion processes between the description of the market environment and the agents’ models. We do that by embedding the models in the process itself, creating a closed feedback loop, demonstrating how prices change towards greater conformity to the prevailing financial models used in the market. In this framework, we show with closed-form solutions how an agent should best respond to the current dominant strategies of other agents in the market and effectively exploit them while maintaining competitive actions and superior performance. We further prove that there is a performative stable state, where agents do not have an incentive in finding new strategies to which they deviate. Our work emphasises performativity as a naturally emerging phenomenon in markets.

https://arxiv.org/pdf/2508.04344

University of Edinburgh

In this talk, we explore the short- and long-term stability of backed stablecoins offering constant mint and redeem prices to all agents. We refer to such designs as price window-based, since the mint and redeem prices constrain the stablecoin's market equilibrium. We show that, without secondary stabilization mechanisms, price window designs cannot achieve both short- and long-term stability unless they are backed by already-stable reserves. In particular, the mechanism faces a tradeoff: either risk eventual reserve depletion through persistent arbitrage by a speculator, or widen the distance between mint and redeem prices enough to disincentivize arbitrage. In the latter case, however, the market price of the stablecoin inherits the volatility of its backing asset, with fluctuations that can be proportional to the backing asset's own volatility.

https://arxiv.org/abs/2602.15981

Universitat de Barcelona

We provide new axiomatizations for three values for games with a hierarchical structure that are introduced in Álvarez-Mozos et al. (2017). The axiomatizations are comparable in the sense that, besides three standard axioms and three other axioms satisfied by all of them, from a set of four additional and distinguishing axioms, each satisfies a different combination of two of them. We also show that the Shapley value satisfies the remaining reasonable combination of two distinguishing axioms. However, the Shapley value does not satisfy all of the common axioms. Finally, we complete the comparable axiomatization by introducing a new value that satisfies the three common axioms as well as the final combination of two distinguishing axioms.

Joint work with Mikel Álvarez-Mozos and René van den Brink.

Royal Holloway University of London

In standard fair division models, we assume that all agents are selfish. However, in many scenarios, division of resources has a direct impact on the whole group or even society. Therefore, we study fair allocations of indivisible items that, at the same time, maximize social impact. In this model, each agent is associated with two additive functions that define their value and social impact for each item. The goal is to allocate items so that the social impact is maximized while maintaining some fairness criterion. We reveal that the complexity of the problem heavily depends on whether the agents are socially aware, i.e., they take into consideration the social impact functions. For socially unaware agents, we prove that the problem is NP-hard for a variety of fairness notions, and that it is tractable only for very restricted cases, e.g., if, for every agent, the valuation equals social impact and it is binary. On the other hand, social awareness allows for fair allocations that maximize social impact, and such allocations can be computed in polynomial time. Interestingly, the problem becomes again intractable as soon as the definition of social awareness is relaxed.

https://arxiv.org/abs/2511.08160

University of Edinburgh

Fair division of indivisible goods has been a focus of recent work in the CS-Econ community. The prominent solution concept of envy free allocations up to any good (EFX) has been shown to exist (in the case of additive valuations) for up to 3 agents. However even the existence problem remains open for 4 or more agents. We introduce a mixed integer linear programming (MILP) formulation for the problem, and demonstrate its performance on larger test instances using both synthetically generated and real world instances.

Supervised by Sergio Garcia and Akshay Gupte.

University of Oxford

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. We study strategic behaviour in online round-robin as an extensive-form game with perfect information. Although it is known from prior work that computing Subgame Perfect Nash Equilibria (SPNE) is hard when the number of agents is unbounded, the case of a constant number of agents with additive utilities has remained a challenging open problem. In this work, we make progress on this question by showing intractability for more general utility functions. Namely, we show that if there are just two agents, one with an additive and the other with a submodular utility function, computing an SPNE is PSPACE-complete. Even if we consider only a slight generalisation of additive utilities, namely OXS utilities, computing an SPNE remains NP-hard for a small number of agents. Finally, we show that for additive utility functions, there are fairness guarantees at equilibrium allocations: proportionality up to one good in general and envy freeness up to one good for two agents.

University of Oxford

We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central fairness notion is envy-freeness up to any good (EFX), which requires that any envy toward another agent vanishes after the removal of any single good from the latter’s bundle. The existence of EFX allocations is considered a major open problem in fair division, and has so far been established only in limited settings. Christodoulou et al. [2023] proved the existence of EFX allocations for graphical valuations. In this setting, agents correspond to the nodes of an underlying graph, goods correspond to edges, and each good has positive value only for the endpoints of the corresponding edge. Their proof crucially relies on the restriction that the graph is simple, meaning that for any pair of agents, there is at most one good that has value for both agents. For multigraph valuations, where multiple goods may be valued by the same pair of agents, only partial results are known. Amanatidis et al. [2024] and Kaviani et al. [2025] obtained 2/3 and √2/2 approximations of EFX, respectively; Kaviani et al. [2024] established existence under restricted additive valuations; and Afshinmehr et al. [2025a] proved existence under the assumption that the shortest cycle containing non-parallel edges has length at least 4. In this paper, we resolve this open problem by proving the existence of EFX allocations for multigraph instances under cancelable valuations, a strict superclass of additive valuation functions. Our proof is algorithmic and computes such allocations in polynomial time when the valuation functions are additive, and in pseudo-polynomial time when they are cancelable. This work contributes to the small number of EFX existence results that apply to an arbitrary number of agents.

Technical University of Munich

We explore the concept of finite stochastic games, where a principal must incentivize agents to conduct tasks. We look at the situation from a

1) We study the problem of optimal contract design in a single-principal-multi-agent setting where a principal must incentivize a group of agents to participate in a collective task. The principal offers a reward-sharing scheme that distributes the realized outcome stemming from a value oracle, which is a function of the agents' contribution via participation. We employ a linear contract appropriate for crowdsourcing, with structure which allows incentivization to take place on a fixed cost basis. We examine the, complexity of the optimization under modular, submodular, and XOS value oracles. Further, motivated by crowdsourcing settings where agents need to be incentivized according to a measure of their ability in contribution to a collective task, we introduce a new class of value oracle known as asymptotic ranked ordered gain function (ARGF), presenting a special kind of value oracle that is not always XOS (nor always submodular), but crucially takes into account the competencies of each agent in a collective task.

2) We look at finite games, where a single principal may need to incentivize a collection of no-regret learning (NRL) agents, who are learning independently. The principal is able to apply a payoff modification/payment function/payoff morphism to the native payoff function to incentivize/steer/manipulate agents into a desired equilibrium. This work investigates the problem of agent manipulation towards a desired equilibrium (that they may not naturally converge to under NRL dynamics). Intuitively, this consequently costs a budget. Therefore, we ask how to minimize the budget expenditure given our knowledge of the geometry of the loss/reward function, the probability distribution(s) of the strategies, the initial conditions of the agents, and learning behaviour of agents (better if invariant)? We aim to tie the aspects of inverse game (RL) design to incremental strategic manipulation (which currently lacks a principled approach and generality).

University of Liverpool

Abstract to be added.

INRIA Paris

Standard methods for aligning large language models with human preferences learn from pairwise comparisons among sampled candidate responses and regularize toward a reference policy. Despite their effectiveness, the effects of sampling and reference choices are poorly understood theoretically. We investigate these effects through Identity Preference Optimization, a widely used preference alignment framework and show that proper instance-dependent sampling can yield stronger ranking guarantees, while skewed on-policy sampling can induce excessive concentration under structured preferences. We then analyze iterative alignment dynamics in which the learned policy feeds back into future sampling and reference policies, reflecting a common practice of model-generated preference data. We prove that these dynamics can exhibit persistent oscillations or entropy collapse for certain parameter choices, and characterize regimes that guarantee stability. Our theoretical insights extend to Direct Preference Optimization, indicating the phenomena we captured are common to a broader class of preference-alignment methods. Experiments on real-world preference data validate our findings.

https://arxiv.org/abs/2602.12180

University of Edinburgh

We study the complexity of computing Bayes-Nash equilibria in single-item first-price auctions. We present the first efficient algorithms for the problem, when the bidders' values for the item are independently drawn from the same continuous distribution, under both established variants of continuous and finite bidding sets. More precisely, we design polynomial-time algorithms for the white-box model, where the distribution is provided directly as part of the input, and query-efficient algorithms for the black-box model, where the distribution is accessed via oracle calls. Our results settle the computational complexity of the problem for bidders with i.i.d. values.

Boston University

We study the budget-feasible procurement problem, in which a buyer seeks to procure goods or services from strategic sellers with private costs under a hard budget constraint. Most prior work on this problem has focused on maximizing the buyer’s total value; in this talk, we instead consider objectives such as buyer utility (value minus payments) and welfare (value minus production costs). For welfare, we present a simple mechanism that achieves a constant-factor approximation in the prior-free worst-case setting. For utility, we show that prior-free guarantees are impossible, even with a single seller, motivating a Bayesian approach in which the buyer has distributional information about sellers’ costs. In that setting, we characterize a utility-optimal mechanism that satisfies the budget constraint in expectation, and then show how to modify it to satisfy the budget ex post, for every cost realization, while retaining near-optimal utility guarantees.

Aristotle University of Thessaloniki & Archimedes

We study non-atomic congestion games on parallel-link networks with polynomial latencies. We investigate the power of machine-learned predictions in the design of coordination mechanisms aimed at minimizing the impact of selfishness. Our main results demonstrate that enhancing coordination mechanisms with simple advice on the input rate can optimize the social cost whenever the advice is accurate (consistency), while only incurring minimal losses even when the predictions are arbitrarily inaccurate (bounded robustness). Moreover, we provide a full characterization of consistent mechanisms, and show that our proposed mechanism is optimal with respect to robustness. We further explore the notion of error-tolerance within this context.

https://arxiv.org/abs/2507.07915

Joint work with George Christodoulou, Alkmini Sgouritsa, and Ioannis Vlachos.

University of Edinburgh

We study delegated voting in a setting where each voter has binary approval preferences over a subset of projects. A fixed number of delegates coordinate and advertise their approval preferences, and a voter is attracted when a delegate agrees with the voter on a sufficient fraction of the projects. In this setting, we study the problem of constructing delegates that maximize the number of attracted voters. We show that this problem is computationally hard in most scenarios, that even optimal delegates may attract only a small fraction of voters, and that efficient algorithms exist under specific conditions.

University of Warwick

Recently, in the social choice literature, much attention has been given to the question of avoiding underrepresentation in approval-based multi-winner voting. In our work, we explore the largely overlooked complementary question of avoiding overrepresentation. This has not been explored systematically, despite being a desirable property with concrete applications. Intuitively, overrepresentation happens when a group determines a disproportionately large part of the committee, thereby exceeding the group's quota. We formulate a strong and appealing axiom for avoiding overrepresentation, called justifiable upper quota (JUQ). We consider several voting rules that output a committee satisfying JUQ, and analyse the compatibility of the axiom with established proportionality notions such as EJR+.

University of Birmingham

Gerrymandering is the process of altering the boundaries of a district to manipulate the results of an election by favoring a particular candidate. A natural way of thinking about Gerrymandering would be to consider voters and ballot boxes as points on the plane ℝ² with district boundaries being manipulated over the plane and the distance between voters and ballot boxes is measured using the ℓ₂ norm.

In their paper, Lewenberg et al. [AAMAS 2017] proved that the Gerrymandering problem with the plurality rule is NP-complete, even when the number of candidates is four. This was further extended by Eiben et al. [AAAI 2020] who proved that for any number of candidates at least 2, the Gerrymandering problem with the plurality rule is W[1]-hard parameterized by k + n.

We further extend this problem by adding a fairness restriction on the difference between the number of voters between any two districts and prove that the Balanced-Gerrymandering problem with the plurality rule is W[1]-hard parameterized by k for any balance b ∈ ℤ⁺. Moreover, under the Exponential Time Hypothesis (ETH), for any computable function f, there is no f(k) · n^o(√k) time algorithm for this problem.

University of Oxford

Imagine yourself on a self-driving car, programmed to make tough moral decisions under extreme circumstances. Or perhaps, you are a citizen dependent on the foundations of a healthy democracy. Society constantly has to determine the boundaries of what it deems acceptable, from legislative decisions to the guardrails governing autonomous systems. Given individuals' attitudes toward options, which options should receive societal consent? Our quest stands on three principles: sufficient support, minority protection, and dominance by decisively better options.

In this talk, we will explore the aggregation of consent preferences via the three principles, presenting the challenges and recent breakthroughs associated with balancing the tussle between minority protection and majority support.