Bart de Keijzer

AAAI Conference 2026 Conference Paper

Breaking Barriers, Finding Boundaries: Not Obviously Manipulable Budget-Feasible Mechanism Design

• Bart De Keijzer
• Guido Schäfer
• Artem Tsikiridis
• Carmine Ventre

Strategyproofness has been the holy grail in mechanism design for decades, providing strong incentive compatibility guarantees under the assumption of perfectly rational agents. However, this assumption is questionable when agents exhibit bounded rationality. Moreover, strategyproofness often imposes strong impossibility results that prevent mechanisms from surpassing certain approximation barriers. We study this tension in budget-feasible mechanism design, where a designer wants to procure services of maximum value from agents subject to a budget constraint. Here, strategyproofness imposes approximation barriers of 2.41 and 2 for deterministic and randomized mechanisms, respectively. We investigate how much we can potentially gain under bounded rationality. We adopt the weaker notion of not obviously manipulable (NOM), which only prevents "obvious" strategic deviations. We fully resolve the achievable approximation guarantees under NOM: We derive a deterministic 2-approximate NOM mechanism under the general class of monotone subadditive valuations. We also show that this bound is tight (even for additive valuations). Additionally, we provide a simple randomized NOM mechanism that is approximately optimal. These results demonstrate a clear separation between strategyproof and NOM mechanisms. Our mechanisms use Golden Tickets and Wooden Spoons as natural design primitives, arising from our characterization of NOM mechanisms.

AAAI Conference 2026 Conference Paper

On the Approximation Ratio of Optimal Fixed-Price Mechanisms for Single and Multi-Unit Bilateral Trade

• Giordano Giambartolomei
• Bart De Keijzer

Multi-unit bilateral trade refers to the setting, where there is a buyer and a seller, who holds a finite number of units of an indivisible item. An automated mechanism has to decide how many units are transferred from the seller to the buyer and the corresponding payment from the buyer to the seller. The buyer and the seller have both either increasing or increasing submodular valuation functions in the number of units in possession. The (single-unit) bilateral trade problem arises as a particular case. We study the problem of social welfare maximisation by establishing the fraction (approximation ratio) of the optimal social welfare that a fixed-price mechanism can recover. Fixed-price mechanisms, understood as per-unit price in the multi-unit setting, have been characterised as the only truthful, individually rational and strongly budget balanced mechanisms. We narrow the gap on the approximation ratio of optimal fixed-price mechanisms for bilateral trade, which has been shown to lie between 0.72 and 0.7381. We show that it must lie between 0.7292 and 0.73805, which leads to improved bounds on the approximation ratio of optimal fixed-price mechanisms for multi-unit bilateral trade. In particular, we show that multi-unit bilateral trade is at least as hard as single-unit bilateral trade, and obtain several hardness results for different numbers of units.

AAAI Conference 2025 Conference Paper

Asymptotic Extinction in Large Coordination Games

• Desmond Chan
• Bart De Keijzer
• Tobias Galla
• Stefanos Leonardos
• Carmine Ventre

We study the exploration-exploitation trade-off for large multiplayer coordination games where players strategise via Q-Learning, a common learning framework in multi-agent reinforcement learning. Q-Learning is known to have two shortcomings, namely non-convergence and potential equilibrium selection problems, when there are multiple fixed points, called Quantal Response Equilibria (QRE). Furthermore, whilst QRE have full support for finite games, it is not clear how Q-Learning behaves as the game becomes large. In this paper, we characterise the critical exploration rate that guarantees convergence to a unique fixed point, addressing the two shortcomings above. Using a generating-functional method, we show that this rate increases with the number of players and the alignment of their payoffs. For many-player coordination games with perfectly aligned payoffs, this exploration rate is roughly twice that of p-player zero-sum games. As for large games, we provide a structural result for QRE, which suggests that as the game size increases, Q-Learning converges to a QRE near the boundary of the simplex of the action space, a phenomenon we term asymptotic extinction, where a constant fraction of the actions are played with zero probability at a rate o(1/N) for an N -action game.

ECAI Conference 2025 Conference Paper

Optimal Candidate Positioning in Multi-Issue Elections

• Colin Cleveland
• Bart de Keijzer
• Maria Polukarov

We study strategic candidate positioning in multidimensional spatial-voting elections. Voters and candidates are represented as points in Rd and each voter supports the candidate that is closest under a distance induced by an ℓp-norm. We prove that computing an optimal location for a new candidate is NP-hard already against a single opponent, whereas for a constant number of issues the problem is tractable: an O(nd + 1) hyperplane-enumeration algorithm and an O(n log n) radial-sweep routine for d = 2 solve the task exactly. We further derive the first approximation guarantees for the general multi-candidate case and show how our geometric approach extends seamlessly to positional scoring rules such as k-approval and Borda. These results clarify the algorithmic landscape of multi-dimensional spatial elections and provide practically implementable tools for campaign strategy.

AAMAS Conference 2024 Conference Paper

Reducing Systemic Risk in Financial Networks through Donations

• Jinyun Tong
• Bart De Keijzer
• Carmine Ventre

We examine the extent to which rescue strategies within a banking system can reduce systemic risk. We focus on donations from solvent banks to banks in distress, which can in principle reduce losses and prevent default cascades. We build an agent-based model to simulate the ensuing strategic game on a randomly generated financial network, where nodes represent banks and edges represent interbank liabilities. Each bank independently decides whether to rescue (and whom) to maximise their payoffs. We analyse the rescue strategies adopted by the banks at equilibrium, using empirical game-theoretic analysis. Our results show that donations can indeed reduce systemic risk when the equilibrium strategy profile is adopted. Individual donations can benefit multiple banks in the network. Our results also indicate that lower default costs and small-variance liabilities tend to decrease the incentives to donate. We furthermore examine the impact of the banks’ rationality on the effects of rescue, finding that banks behaving rationally use their funds for rescues more efficiently than banks that behave irrationally.

ECAI Conference 2024 Conference Paper

Reducing Systemic Risk in Financial Networks through Donations

• Jinyun Tong
• Bart de Keijzer
• Carmine Ventre

We examine the extent to which rescue strategies within a banking system can reduce systemic risk. We focus on donations from solvent banks to banks in distress, which can in principle reduce losses and prevent default cascades. We build an agent-based model to simulate the ensuing strategic game on a randomly generated financial network, where nodes represent banks and edges represent inter-bank liabilities. Each bank independently decides whether to rescue (and whom) to maximise their payoffs. We analyse the rescue strategies adopted by the banks at equilibrium, using empirical game-theoretic analysis. Our results show that donations can indeed reduce systemic risk when the equilibrium strategy profile is adopted. Individual donations can benefit multiple banks in the network. Our results also indicate that lower default costs and small-variance liabilities tend to decrease the incentives to donate. We furthermore examine the impact of the banks’ rationality on the effects of rescue, finding that banks behaving rationally use their funds for rescues more efficiently than banks that behave irrationally.

ECAI Conference 2024 Conference Paper

Selfishly Cancelling Debts Can Reduce Systemic Risk

• Jinyun Tong
• Bart de Keijzer
• Carmine Ventre

The exposure of banks to systemic risk in financial networks usually requires large bailouts of taxpayer money with long-lasting and damaging societal consequences. We examine whether the banking network can reduce systemic risk from within by selfishly cancelling the debts of banks in distress. This operation can in principle reduce losses and prevent default cascades. We define an abstract model to simulate the ensuing strategic game on randomly generated financial networks, where each systemically important bank independently decides how likely it is to cancel some debts of insolvent banks. We compute the equilibrium of the induced empirical game with the empirical game-theoretic analysis and analyse its efficiency by measuring the price of anarchy. Our results show that selfish debt cancellation can reduce systemic risk when adopting the equilibrium strategy profile. However, our results also indicate that the efficiency of the equilibrium can be low and relatively few banks cancel debts at equilibrium, and we explain the reason for this through analysis of the banks’ incentives and game dynamics.

AAMAS Conference 2024 Conference Paper

Willy Wonka Mechanisms

• Thomas Archbold
• Bart De Keijzer
• Carmine Ventre

Bounded rationality in mechanism design aims to ensure incentivecompatibility for agents who are cognitively limited. These agents lack the contingent reasoning skills that traditional mechanism design assumes, and depending on how these cognitive limitations are modelled this alters the class of incentive-compatible mechanisms. In this work we design mechanisms without any “obvious” manipulations for several auction settings that aim to either maximise revenue or minimise the compensation paid to the agents. A mechanism without obvious manipulations is said to be not obviously manipulable (NOM), and assumes agents act truthfully as long as the maximum and minimum utilities from doing so are no worse than the maximum and minimum utilities from lying, with the extremes taken over all possible actions of the other agents. We exploit the definition of NOM by introducing the concept of golden tickets and wooden spoons, which designate bid profiles ensuring the mechanism’s incentive-compatibility for each agent. We then characterise these “Willy Wonka” mechanisms, and by carefully choosing the golden tickets and wooden spoons we use this to design revenue-maximising auctions and frugal procurement auctions.

TCS Journal 2023 Journal Article

Financial networks with singleton liability priorities

• Stavros D. Ioannidis
• Bart De Keijzer
• Carmine Ventre

AAMAS Conference 2023 Conference Paper

Non-Obvious Manipulability for Single-Parameter Agents and Bilateral Trade

• Thomas Archbold
• Bart De Keijzer
• Carmine Ventre

A recent line of work in mechanism design has focused on guaranteeing incentive compatibility for agents without contingent reasoning skills: obviously strategyproof mechanisms [22] guarantee that it is “obvious” for these imperfectly rational agents to behave honestly, whereas non-obviously manipulable (NOM) mechanisms [28] take a more optimistic view and ensure that these agents will only misbehave when it is “obvious” for them to do so. Technically, obviousness requires comparing certain extrema (defined over the actions of the other agents) of an agent’s utilities for honest behaviour against dishonest behaviour. We present a technique for designing NOM mechanisms in settings where monetary transfers are allowed based on cycle monotonicity, which allows us to disentangle the specification of the mechanism’s allocation from the payments. By leveraging this framework, we completely characterise both allocation and payment functions of NOM mechanisms for single-parameter agents. We then look at the classical setting of bilateral trade and study how much subsidy, if any, is needed to guarantee NOM, efficiency, and individual rationality. We prove a stark dichotomy: no finite subsidy suffices if agents look only at best-case extremes, whereas no subsidy at all is required when agents focus on worst-case extremes. We conclude the paper by characterising the NOM mechanisms that require no subsidies whilst satisfying individual rationality.

IJCAI Conference 2023 Conference Paper

Non-Obvious Manipulability in Extensive-Form Mechanisms: The Revelation Principle for Single-Parameter Agents

• Thomas Archbold
• Bart De Keijzer
• Carmine Ventre

Recent work in algorithmic mechanism design focuses on designing mechanisms for agents with bounded rationality, modifying the constraints that must be satisfied in order to achieve incentive compatibility. Starting with Li's strengthening of strategyproofness, obvious strategyproofness (OSP) requires truthtelling to be "obvious" over dishonesty, roughly meaning that the worst outcome from truthful actions must be no worse than the best outcome for dishonest ones. A celebrated result for dominant-strategy incentive-compatible mechanisms that allows us to restrict attention to direct mechanisms, known as the revelation principle, does not hold for OSP: the implementation details matter for the obvious incentive properties of the mechanism. Studying agent strategies in real-life mechanisms, Troyan and Morrill introduce a relaxation of strategyproofness known as non-obvious manipulability, which only requires comparing certain extrema of the agents' utility functions in order for a mechanism to be incentive-compatible. Specifically a mechanism is not obviously manipulable (NOM) if the best and worst outcomes when acting truthfully are no worse than the best and worst outcomes when acting dishonestly. In this work we first extend the cycle monotonicity framework for direct-revelation NOM mechanism design to indirect mechanisms. We then apply this to two settings, single-parameter agents and mechanisms for two agents in which one has a two-value domain, and show that under these models the revelation principle holds: direct mechanisms are just as powerful as indirect ones.

AAAI Conference 2019 Conference Paper

Multi-Unit Bilateral Trade

• Matthias Gerstgrasser
• Paul W. Goldberg
• Bart De Keijzer
• Philip Lazos
• Alexander Skopalik

We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular. Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1−e) approximation mechanism, matching the best known bounds for the single-item setting.

IJCAI Conference 2018 Conference Paper

Facility Reallocation on the Line

• Bart De Keijzer
• Dominik Wojtczak

We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between stages based on the locations reported by n agents. The aim of the reallocation mechanism is to minimize the social cost, i. e. , the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility. We also study this problem both in the offline setting and online setting. In the offline case the mechanism has full knowledge of the agent locations in all future stages, and in the online setting the mechanism does not know these future locations and must decide the location of the facility on a stage-per-stage basis. For both cases, we derive the optimal mechanism, where for the online setting we show that its competitive ratio is (n+2)/(n+1). As neither of these mechanisms turns out to be strategyproof, we propose another strategyproof mechanism which has a competitive ratio of (n+3)/(n+1) for odd n and (n+4)/n for even n, which we conjecture to be the best possible. We also consider a generalization with multiple facilities and weighted agents, for which we show that the optimum can be computed in polynomial time for a fixed number of facilities.

SODA Conference 2016 Conference Paper

Approximately Efficient Double Auctions with Strong Budget Balance

• Riccardo Colini-Baldeschi
• Bart de Keijzer
• Stefano Leonardi 0001
• Stefano Turchetta

Mechanism design for one-sided markets is an area of extensive research in economics and, since more than a decade, in computer science as well. Two-sided markets, on the other hand, have not received the same attention despite the numerous applications to web advertisement, stock exchange, and frequency spectrum allocation. This work studies double auctions, in which unit-demand buyers and unit-supply sellers act strategically. An ideal goal in double auction design is to maximize the social welfare of buyers and sellers with individually rational (IR), incentive compatible (IC) and strongly budget-balanced (SBB ) mechanisms. The first two properties are standard. SBB requires that the payments charged to the buyers are entirely handed to the sellers. This property is crucial in all the contexts that do not allow the auctioneer retaining a share of buyers' payments or subsidizing the market. Unfortunately, this goal is known to be unachievable even for the special case of bilateral trade, where there is only one buyer and one seller. Therefore, in subsequent papers, meaningful trade-offs between these requirements have been investigated. Our main contribution is the first IR, IC and SBB mechanism that provides an O (1)-approximation to the optimal social welfare. This result holds for any number of buyers and sellers with arbitrary, independent distributions. Moreover, our result continues to hold when there is an additional matroid constraint on the sets of buyers who may get allocated an item. To prove our main result, we devise an extension of sequential posted price mechanisms to two-sided markets. In addition to this, we improve the best-known approximation bounds for the bilateral trade problem.

MFCS Conference 2016 Conference Paper

The Ground-Set-Cost Budgeted Maximum Coverage Problem

• Irving van Heuven van Staereling
• Bart de Keijzer
• Guido Schäfer

We study the following natural variant of the budgeted maximum coverage problem: We are given a budget B and a hypergraph G = (V, E), where each vertex has a non-negative cost and a non-negative profit. The goal is to select a set of hyperedges T subseteq E such that the total cost of the vertices covered by T is at most B and the total profit of all covered vertices is maximized. Besides being a natural generalization of the well-studied maximum coverage problem, our motivation for investigating this problem originates from its application in the context of bid optimization in sponsored search auctions, such as Google AdWords. It is easily seen that this problem is strictly harder than budgeted max coverage, which means that the problem is (1-1/e)-inapproximable. The difference of our problem to the budgeted maximum coverage problem is that the costs are associated with the covered vertices instead of the selected hyperedges. As it turns out, this difference refutes the applicability of standard greedy approaches which are used to obtain constant factor approximation algorithms for several other variants of the maximum coverage problem. Our main results are as follows: - We obtain a (1 - 1/sqrt(e))/2-approximation algorithm for graphs. - We derive a fully polynomial-time approximation scheme (FPTAS) if the incidence graph of the hypergraph is a forest (i. e. , the hypergraph is Berge-acyclic). We also extend this result to incidence graphs with a fixed-size feedback hyperedge node set. - We give a (1-epsilon)/(2d^2)-approximation algorithm for every epsilon > 0, where d is the maximum degree of a vertex in the hypergraph.

AAAI Conference 2012 Conference Paper

Housing Markets with Indifferences: A Tale of Two Mechanisms

• Haris Aziz
• Bart De Keijzer

The (Shapley-Scarf) housing market is a well-studied and fundamental model of an exchange economy. Each agent owns a single house and the goal is to reallocate the houses to the agents in a mutually beneficial and stable manner. Recently, Alcalde-Unzu and Molis (2011) and Jaramillo and Manjunath (2011) independently examined housing markets in which agents can express indifferences among houses. They proposed two important families of mechanisms, known as TTAS and TCR respectively. We formulate a family of mechanisms which not only includes TTAS and TCR but also satisfies many desirable properties of both families. As a corollary, we show that TCR is strict core selecting (if the strict core is non-empty). Finally, we settle an open question regarding the computational complexity of the TTAS mechanism. Our study also raises a number of interesting research questions.

AAMAS Conference 2011 Conference Paper

Complexity of Coalition Structure Generation

• Haris Aziz
• Bart De Keijzer

We revisit the coalition structure generation problem in which the goal is to partition the players into exhaustive and disjoint coalitions so as to maximize the social welfare. One of our key results is a general polynomial-time algorithm to solve the problem for all monotonic coalitional games provided that player types are known and the number of player types is bounded by a constant. As a corollary, we obtain a polynomial-time algorithm to compute an optimal partition for weighted voting games with a constant number of weight values and for coalitional skill games with a constant number of skills. We also consider well-studied and well-motivated coalitional games defined compactly on combinatorial domains. For these games, we characterize the complexity of computing an optimal coalition structure by presenting polynomial-time algorithms, approximation algorithms, or NP-hardness and inapproximability lower bounds.

AAMAS Conference 2010 Conference Paper

Enumeration and exact design of weighted voting games

• Bart De Keijzer
• Tomas Klos
• Yingqian Zhang

In many multiagent settings, situations arise in which agentsmust collectively make decisions while not every agent issupposed to have an equal amount of influence in the outcome of such a decision. Weighted voting games are oftenused to deal with these situations. The amount of influence that an agent has in a weighted voting game can bemeasured by means of various power indices. This paper studies the problem of finding a weighted voting game in which the distribution of the influence amongthe agents is as close as possible to a given target value. We propose a method to exactly solve this problem. Thismethod relies on a new efficient procedure for enumeratingweighted voting games of a fixed number of agents. The enumeration algorithm we propose works by exploiting the properties of a specific partial order over the class ofweighted voting games. The algorithm enumerates weightedvoting games of a fixed number of agents in time exponentialin the number of agents, and polynomial in the number ofgames output. As a consequence we obtain an exact anytimealgorithm for designing weighted voting games.