Carmine Ventre

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.

JAAMAS Journal 2026 Journal Article

Green disclosure policies and market dynamics: evidence from agent-based ESG models

• Lingxiao Zhao
• Maria Polukarov
• Carmine Ventre

Abstract Green disclosure policies aim to improve the transparency of corporate environmental practices and guide investors’ capital allocation. While existing studies mostly examine firm-level effects, their market-level implications in multi-agent systems remain insufficiently explored. This paper develops a dual-market dynamic ESG fund model, integrating agent-based simulation with empirical game-theoretic analysis, to study how upgrade costs, investor valuation preferences, and disclosure regimes jointly shape firms’ green transition incentives in the EU and China. The results show that both transition costs and valuation gaps strongly influence strategic upgrading behaviour and equilibrium outcomes: Strict disclosure sharpens differentiation but may suppress upgrading due to high costs; lax disclosure facilitates initial transitions by polluting firms; and hybrid disclosure, combining lax and strict phases, generates stronger incentives across different firm types. Cross-market comparison further indicates that the EU’s mature regulatory environment is better suited to strict disclosure, whereas China’s emerging market benefits more from a lax form to accelerate early-stage transitions. This study provides a reference for regulators in selecting appropriate disclosure forms at different levels of market maturity and offers methodological support for the sustainable development of green finance markets.

AAMAS Conference 2025 Conference Paper

Agent-Based Analysis of Green Disclosure Policies and Their Market-Wide Impact on Firm Behavior

• Lingxiao Zhao
• Maria Polukarov
• Carmine Ventre

Green disclosure policies are designed to help firms communicate their environmentally friendly practices to investors. While most research has focused on the effects of these policies at the individual firm level, their influence within a system of multiple firms remains largely unexamined. To address this gap, we develop an agent-based model to simulate market dynamics among firms with varying levels of environmental performance and strategic responses. Using Empirical Game-Theoretic Analysis, we investigate how the costs associated with becoming greener and investors’ valuation of these efforts shape equilibrium outcomes and the prevalence of green firms in the market. Our findings reveal that changes in the cost of green upgrades significantly influence firms’ strategic choices and alter the equilibrium behavior of the other firms. Additionally, we analyze the effects of different green disclosure policies and find that under more relaxed policies, firms are more willing to incur into higher upgrade costs. Furthermore, we propose a two-stage disclosure policy that incentivizes all types of firms to improve their green practices, leading to broader adoption of sustainable energy solutions across the market.

AAMAS Conference 2025 Conference Paper

Agent-based Modeling and Simulation of Ambiguity in Catastrophe Insurance Markets

• Yu Bi
• Lingxiao Zhao
• Jinyun Tong
• Zhe Feng
• Carmine Ventre

Pricing covers for catastrophes is challenging for insurers due to uncertainty in loss probabilities. This paper addresses this so-called ambiguity problem in competitive catastrophe insurance markets through three key approaches. First, it introduces ambiguity in premium pricing and capital holdings. Second, it develops an Agentbased Model simulator to mimic general insurance markets and the Lloyd’s market. Third, it applies Empirical Game-Theoretical Analysis to explore insurers’ ambiguity preferences in different markets. The study evaluates the effects of ambiguity by analyzing their impact on individual companies, differences between small and large companies, and overall market performance. Simulation results reveal that the simulator effectively captures underwriting cycles and insurers’ strategic shifts following catastrophes. In markets with equally sized insurers, competition mitigates the negative effects of ambiguity by stabilizing premiums and increasing the number of underwritten risks. In markets with varying-sized insurers, large insurers gain market power while small insurers adopt aggressive ambiguity strategies to compete. In contrast, Lloyd’s lead-follow mechanism encourages conservative ambiguity strategies and reduces bankruptcy.

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.

EUMAS Conference 2025 Conference Paper

Designing Resilient Markets: Agent-Based Insights into Flash Crashes

• Sriram Bharadwaj Rangarajan
• Carmine Ventre

ECAI Conference 2025 Conference Paper

From Competition to Centralization: The Oligopoly in Ethereum Block Building Auctions

• Fei Wu 0030
• Thomas Thiery
• Stefanos Leonardos
• Carmine Ventre

Block production on the Ethereum blockchain has adopted an auction-based mechanism known as Proposer-Builder Separation (PBS), where validators outsource block creation to builders competing in MEV-Boost auctions for Maximal Extractable Value (MEV) rewards. We employ empirical game-theoretic analysis based on simulations to examine how advantages in latency and MEV access shape builder strategic bidding and auction outcomes. We find that a small set of dominant builders leverage these advantages, consolidating power, reducing auction efficiency, and heightening centralization. Our results underscore the need for fair MEV distribution and sustained efforts to promote decentralization in Ethereum’s block building market.

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

Who gets the Maximal Extractable Value? A Dynamic Sharing Blockchain Mechanism

• Pedro Braga
• Georgios Chionas
• Piotr Krysta
• Stefanos Leonardos
• Georgios Piliouras
• Carmine Ventre

Maximal Extractable Value (MEV) has emerged as a new frontier in the design of blockchain systems. MEV refers to any excess value that a block producer can realize by manipulating the ordering of transactions. In this paper, we propose to make the MEV extraction rate part of the protocol design space. Our aim is to leverage this parameter to maintain a healthy balance between block producers (who need to be compensated for the service they provide) and users (who need to feel encouraged to transact). We design a dynamic mechanism which updates the MEV extraction rate with the goal of stabilizing it at a target value. We analyse the evolution of this dynamic mechanism under various market conditions and provide formal guarantees about its long-term performance. The main takeaway from our work is that the proposed system exhibits desirable behavior (near-optimal performance) even when it operates in out of equilibrium conditions that are often met in practice. Our work establishes, the first to our knowledge, dynamic framework for the integral problem of MEV sharing between extractors and users.

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.

AAMAS Conference 2023 Conference Paper

Error in the Euclidean Preference Model

• Luke Thorburn
• Maria Polukarov
• Carmine Ventre

Spatial models of preference, in the form of vector embeddings, are learned by many deep learning and multiagent systems, including recommender systems. Often these models are assumed to approximate a Euclidean structure, where an individual prefers alternatives positioned closer to their “ideal point”, as measured by the Euclidean metric. However, Bogomolnaia and Laslier [3] showed that there exist ordinal preference profiles that cannot be represented with this structure if the Euclidean space has two fewer dimensions than there are individuals or alternatives. We extend this result, showing that there are realistic situations in which almost all preference profiles cannot be represented with the Euclidean model, and derive a theoretical lower bound on the expected error when using the Euclidean model to approximate non-Euclidean preference profiles. Our results have implications for the interpretation and use of vector embeddings, because in some cases close approximation of arbitrary, true ordinal relationships can be expected only if the dimensionality of the embeddings is a substantial fraction of the number of entities represented.

IJCAI Conference 2023 Conference Paper

Error in the Euclidean Preference Model

• Luke Thorburn
• Maria Polukarov
• Carmine Ventre

Spatial models of preference, in the form of vector embeddings, are learned by many deep learning and multiagent systems, including recommender systems. Often these models are assumed to approximate a Euclidean structure, where an individual prefers alternatives positioned closer to their "ideal point", as measured by the Euclidean metric. However, previous work has shown there are ordinal preference profiles that cannot be represented with this structure if the Euclidean space has two fewer dimensions than there are individuals or alternatives. We extend this result, showing that there are situations in which almost all preference profiles cannot be represented with the Euclidean model, and derive a theoretical lower bound on the expected error when using the Euclidean model to approximate non-Euclidean preference profiles. Our results have implications for the interpretation and use of vector embeddings, because in some cases close approximation of arbitrary, true ordinal relationships can be expected only if the dimensionality of the embeddings is a substantial fraction of the number of entities represented.

AAMAS Conference 2023 Conference Paper

Explicit Payments for Obviously Strategyproof Mechanisms

• Diodato Ferraioli
• Carmine Ventre

The design of mechanisms where incentives are simple to understand for the agents has attracted a lot of attention recently. One particularly relevant concept in this direction has been Obvious Strategyproofness (OSP), a class of mechanisms that are so simple to be recognized as incentive compatible even by agents with a limited form of rationality. It is known that there exist payments that lead to an OSP mechanism whenever the algorithm they augment is either greedy or reverse greedy (a. k. a. , deferred acceptance). However, to date, their explicit definition is unknown. In this work we provide payments for OSP mechanisms based on greedy or reverse greedy algorithms. Interestingly, our results show an asymmetry between these two classes of algorithms: while for reverse greedy the usual strategyproof payments work well also for OSP, the payments for greedy algorithms may break individual rationality or budget balancedness. Thus, the designer needs to subsidize the market in order to simultaneously guarantee these properties and simple incentives. We apply this result to analyze the amount of subsidies needed by a well-known greedy algorithm for combinatorial auctions with single-minded bidders.

TCS Journal 2023 Journal Article

Financial networks with singleton liability priorities

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

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.

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.

AAMAS Conference 2022 Conference Paper

Irrational Behaviour and Globalisation

• Yuanzi Zhu
• Carmine Ventre

This paper seeks to predict globalisation using agent models and a combination of evolutionary game theory and irrational bias. In this paper, we use a new evolutionary process in the model, where we set several complex parameters and trade-offs to set the payoff matrix and its change in real-time. We define a new dynamic evolutionary process to ensure that each agent can choose its interests in the simulation of globalisation and also the model include irrational agents in the model to test the usefulness of the new dynamics against a control group without irrational agents.

AAMAS Conference 2022 Conference Paper

The Spoofing Resistance of Frequent Call Markets

• Buhong Liu
• Maria Polukarov
• Carmine Ventre
• Lingbo Li
• Leslie Kanthan
• Fan Wu
• Michail Basios

We study the effects of spoofing attacks on frequent call markets (FCMs). Spoofing—a strategic manipulation to mislead market participants by creating spurious limit orders—could harm the market efficiency and has been declared illegal in many countries. However, this practice is still very common, which inspired extensive research on measuring, detecting and curbing such manipulation in the popular market model of continuous double auctions (CDAs). In this paper, we extend this research to frequent call markets and use agent-based modelling to simulate spoofing in this context. Specifically, we apply empirical game-theoretic analysis (EGTA) to compute equilibria of agent-based markets, and demonstrate that while spoofing may be profitable in both market models, it has less impact on FCMs as opposed to CDAs. Finally, we explore several FCM mechanism designs to help to curb this type of market manipulation even further.

AAMAS Conference 2021 Conference Paper

Call Markets with Adaptive Clearing Intervals

• Buhong Liu
• Maria Polukarov
• Carmine Ventre
• Lingbo Li
• Leslie Kanthan

Trading mechanisms play a fundamental role in the health of financial markets. For example, it is believed that continuous double auctions constitute fertile soil for predatory behaviour and toxic order flows. To this end, frequent call markets have been proposed as an alternative design choice to address the latency arbitrage opportunities built in those markets. This paper studies the extent to which adaptive rules to define the length of the clearing intervals affect the performance of frequent call markets.

AAAI Conference 2021 Conference Paper

Efficient Truthful Scheduling and Resource Allocation through Monitoring

• Dimitris Fotakis
• Piotr Krysta
• Carmine Ventre

We study the power and limitations of the Vickrey-Clarke- Groves mechanism with monitoring (VCGmon ) for cost minimization problems with objective functions that are more general than the social cost. We identify a simple and natural sufficient condition for VCGmon to be truthful for general objectives. As a consequence, we obtain that for any cost minimization problem with non-decreasing objective µ, VCGmon is truthful, if the allocation is Maximal-in-Range and µ is 1-Lipschitz (e. g. , µ can be the Lp-norm of the agents’ costs, for any p ≥ 1 or p = ∞). We apply VCGmon to scheduling on restricted-related machines and obtain a polynomial-time truthful-in-expectation 2-approximate (resp. O(1)-approximate) mechanism for makespan (resp. Lp-norm) minimization. Moreover, applying VCGmon, we obtain polynomial-time truthful O(1)-approximate mechanisms for some fundamental bottleneck network optimization problems with single-parameter agents. On the negative side, we provide strong evidence that VCGmon could not lead to computationally efficient truthful mechanisms with reasonable approximation ratios for binary covering social cost minimization problems. However, we show that VCGmon results in computationally efficient approximately truthful mechanisms for binary covering problems.

AAMAS Conference 2019 Conference Paper

How to Get the Most from Goods Donated to Charities

• Christopher Culley
• Ji Qi
• Carmine Ventre

The charity sector is assuming a central role in many countries, due to a generalized increase in wealth inequalities and the restructuring of the welfare state. This market, however, exhibits inefficiencies. In this work, we empirically test the adoption of a centralized truthful allocation mechanism without money to charities bidding for donations. Our results show that it is indeed possible to improve the income of the sector by at least 50% on average. We further show how the application of proxy bidding allows to maintain a significant portion of the welfare improvements without the need of many bids. Our results pave the way for a novel and more profitable model of distribution of donated goods.

AAMAS Conference 2019 Conference Paper

Obvious Strategyproofness, Bounded Rationality and Approximation

• Diodato Ferraioli
• Carmine Ventre

Obvious strategyproofness (OSP) has recently emerged as the solution concept of interest to study incentive compatibility in presence of agents with a specific form of bounded rationality, i. e. , those who have no contingent reasoning skill whatsoever. We here want to study the relationship between the approximation guarantee of incentive-compatible mechanisms and the degree of rationality of the agents, intuitively measured in terms of the number of contingencies that they can handle in their reasoning. We weaken the definition of OSP to accommodate for cleverer agents and study the trade-off between approximation and agents’ rationality for the paradigmatic machine scheduling problem. We prove that, at least for the classical machine scheduling problem, “good” approximations are possible if and only if the agents’ rationality allows for a significant number of contingencies to be considered, thus showing that OSP is not too restrictive a notion of bounded rationality from the point of view of approximation.

AAMAS Conference 2019 Conference Paper

Obviously Strategyproof Mechanisms without Money for Scheduling

• Maria Kyropoulou
• Carmine Ventre

We consider the scheduling problem when no payments are allowed and the machines are bound by their declarations. We are interested in a stronger notion of truthfulness termed obvious strategyproofness (OSP) and explore its possibilities and its limitations. OSP formalizes the concept of truthfulness for agents/machines with a certain kind of bounded rationality, by making an agent’s incentives to act truthfully obvious in some sense: roughly speaking, the worst possible outcome after selecting her true type is at least as good as the best possible outcome after misreporting her type. Under the weaker constraint of truthfulness, Koutsoupias [2011] proves a tight approximation ratio of n+1 2 for one task. We wish to examine how this guarantee is affected by the strengthening of the incentive compatibility constraint. The main message of our work is that there is essentially no worsening of the approximation guarantee corresponding to the significant strengthening of the guarantee of incentive-compatibility from truthfulness to OSP. To achieve this, we introduce the notion of strict monitoring and prove that such a monitoring framework is essential, thus providing a complete picture of OSP with monitoring in the context of scheduling a task without money.

TCS Journal 2019 Journal Article

Social pressure in opinion dynamics

• Diodato Ferraioli
• Carmine Ventre

Motivated by privacy and security concerns in online social networks, we study the role of social pressure in opinion dynamics. These are dynamics, introduced in economics and sociology literature, that model the formation of opinions in a social network. We enrich some of the most classical opinion dynamics, by introducing the pressure, increasing with time, to reach an agreement. We prove that for clique social networks, the dynamics always converges to consensus if the social pressure is high enough. Moreover, we provide (tight) bounds on the speed of convergence; these bounds are polynomial in the number of nodes in the network provided that the pressure grows sufficiently fast. We finally look beyond cliques: we characterize the graphs for which consensus is guaranteed, and make some considerations on the computational complexity of checking whether a graph satisfies such a condition.

JAAMAS Journal 2019 Journal Article

Truthfulness on a budget: trading money for approximation through monitoring

• Paolo Serafino
• Carmine Ventre
• Angelina Vidali

Abstract Albeit a pervasive desideratum when computing in the presence of selfish agents, truthfulness typically imposes severe limitations to what can be implemented. The price of these limitations is typically paid either economically, in terms of the financial resources needed to enforce truthfulness, or algorithmically, in terms of restricting the set of implementable objective functions, which often leads to renouncing optimality and resorting to approximate allocations. In this paper, with regards to utilitarian problems, we ask two fundamental questions: (i) what is the minimum sufficient budget needed by optimal truthful mechanisms, and (ii) whether it is possible to sacrifice optimality in order to achieve truthfulness with a lower budget. To answer these questions, we connect two streams of work on mechanism design and look at monitoring—a paradigm wherein agents’ actual costs are bound to their declarations. In this setting, we prove that the social cost is always a sufficient budget, even for collusion-resistant mechanisms, and, under mild conditions, also a necessary budget for a large class of utilitarian problems that encompass set system problems. Furthermore, for two well-studied problems outside of this class, namely facility location and obnoxious facility location, we draw a novel picture about the relationship between (additive) approximation and frugality. While for optimal mechanisms we prove that the social cost is always a sufficient and necessary budget for both problems, for approximate mechanisms we do have a dichotomy: for the facility location problem (i. e. , agents want to be close to the facilities) we show that “good” approximations still need a budget equal to the social cost; on the contrary, for the obnoxious facility location problem (i. e. agents want to be as far away from the facilities as possible) we show that it is possible to trade approximation for frugality, thus obtaining truthfulness with a lower budget.

AAMAS Conference 2019 Conference Paper

Truthfulness on a Budget: Trading Money for Approximation through Monitoring

• Paolo Serafino
• Carmine Ventre
• Angelina Vidali

Albeit a pervasive desideratum when computing in the presence of selfish agents, truthfulness typically imposes severe limitations to what can be implemented. The price of these limitations is typically paid either economically, in terms of the financial resources needed to enforce truthfulness, or algorithmically, in terms of restricting the set of implementable objective functions, which often leads to renouncing optimality and resorting to approximate allocations. In this paper, with regards to utilitarian problems, we ask two fundamental questions: (i) what is the a minimum sufficient budget needed by optimal truthful mechanisms, and (ii) whether it is possible to sacrifice optimality in order to achieve truthfulness with a lower budget. To answer these questions, we connect two streams of work on mechanism design and look at monitoring – a paradigm wherein agents’ actual costs are bound to their declarations. In this setting, we prove that the social cost is always a sufficient budget, even for collusion-resistant mechanisms, and, under mild conditions, also a necessary budget for a large class of utilitarian problems that encompass set system problems. Furthermore, for facility location, a well-studied problem outside of this class, we draw a novel picture about the relationship between approximation and frugality.

IJCAI Conference 2018 Conference Paper

Probabilistic Verification for Obviously Strategyproof Mechanisms

• Diodato Ferraioli
• Carmine Ventre

Obviously strategyproof (OSP) mechanisms maintain the incentive compatibility of agents that are not fully rational. They have been object of a number of studies since their recent definition. A research agenda, initiated in [Ferraioli and Ventre, 2017], is to find a small set (possibly, the smallest) of conditions allowing to implement an OSP mechanism. To this aim, we define a model of probabilistic verification wherein agents are caught misbehaving with a certain probability, and show how OSP mechanisms can implement every social choice function at the cost of either imposing very large fines or verifying a linear number of agents.

AAMAS Conference 2018 Conference Paper

Probabilistic Verification for Obviously Strategyproof Mechanisms

• Diodato Ferraioli
• Carmine Ventre

Obviously strategyproof (OSP) mechanisms maintain the incentive compatibility of agents that are not fully rational. They have been object of a number of studies since their recent definition. We are motivated by the result showing that OSP mechanisms without money cannot return good approximations, even if the designer monitors the agents during the execution of the mechanism [10]. We ask whether there are different (harsher) forms of punishments and novel ways to exert control over the agents that can overcome this impossibility. We define a model of probabilistic verification wherein agents are caught misbehaving with a certain probability and show how OSP mechanisms without money can implement a given social choice function at the cost of either imposing very large fines for lying or verifying a linear number of agents.

JAIR Journal 2018 Journal Article

The Power of Verification for Greedy Mechanism Design

• Dimitris Fotakis
• Piotr Krysta
• Carmine Ventre

Greedy algorithms are known to provide, in polynomial time, near optimal approximation guarantees for Combinatorial Auctions (CAs) with multidimensional bidders. It is known that truthful greedy-like mechanisms for CAs with multi-minded bidders do not achieve good approximation guarantees. In this work, we seek a deeper understanding of greedy mechanism design and investigate under which general assumptions, we can have efficient and truthful greedy mechanisms for CAs. Towards this goal, we use the framework of priority algorithms and weak and strong verification, where the bidders are not allowed to overbid on their winning set or on any subset of this set, respectively. We provide a complete characterization of the power of weak verification showing that it is sufficient and necessary for any greedy fixed priority algorithm to become truthful with the use of money or not, depending on the ordering of the bids. Moreover, we show that strong verification is sufficient and necessary to obtain a 2-approximate truthful mechanism with money, based on a known greedy algorithm, for the problem of submodular CAs in finite bidding domains. Our proof is based on an interesting structural analysis of the strongly connected components of the declaration graph.

AAAI Conference 2017 Conference Paper

Obvious Strategyproofness Needs Monitoring for Good Approximations

• Diodato Ferraioli
• Carmine Ventre

Obvious strategyproofness (OSP) is an appealing concept as it allows to maintain incentive compatibility even in the presence of agents that are not fully rational, e. g. , those who struggle with contingent reasoning (Li 2015). However, it has been shown to impose some limitations, e. g. , no OSP mechanism can return a stable matching (Ashlagi and Gonczarowski 2015). We here deepen the study of the limitations of OSP mechanisms by looking at their approximation guarantees for basic optimization problems paradigmatic of the area, i. e. , machine scheduling and facility location. We prove a number of bounds on the approximation guarantee of OSP mechanisms, which show that OSP can come at a significant cost. However, rather surprisingly, we prove that OSP mechanisms can return optimal solutions when they use monitoring — a novel mechanism design paradigm that introduces a mild level of scrutiny on agents’ declarations (Kovács, Meyer, and Ventre 2015).

IJCAI Conference 2017 Conference Paper

Social Pressure in Opinion Games

• Diodato Ferraioli
• Carmine Ventre

Motivated by privacy and security concerns in online social networks, we study the role of social pressure in opinion games. These are games, important in economics and sociology, that model the formation of opinions in a social network. We enrich the definition of (noisy) best-response dynamics for opinion games by introducing the pressure, increasing with time, to reach an agreement. We prove that for clique social networks, the dynamics always converges to consensus (no matter the level of noise) if the social pressure is high enough. Moreover, we provide (tight) bounds on the speed of convergence; these bounds are polynomial in the number of players provided that the pressure grows sufficiently fast. We finally look beyond cliques: we characterize the graphs for which consensus is guaranteed, and make some considerations on the computational complexity of checking whether a graph satisfies such a condition.

TCS Journal 2016 Journal Article

Decentralized dynamics for finite opinion games

• Diodato Ferraioli
• Paul W. Goldberg
• Carmine Ventre

Game theory studies situations in which strategic players can modify the state of a given system, in the absence of a central authority. Solution concepts, such as Nash equilibrium, have been defined in order to predict the outcome of such situations. In multi-player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to decrease their own cost and the hope is that the system reaches an “equilibrium” quickly. We study these dynamics for the class of opinion games, recently introduced by Bindel et al. [10]. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio.

TCS Journal 2016 Journal Article

Heterogeneous facility location without money

• Paolo Serafino
• Carmine Ventre

The study of the facility location problem in the presence of self-interested agents has recently emerged as the benchmark problem in the research on mechanism design without money. In the setting studied in the literature so far, agents are single-parameter in that their type is a single number encoding their position on a real line. We here initiate a more realistic model for several real-life scenarios. Specifically, we propose and analyze heterogeneous facility location without money, a novel model wherein: (i) we have multiple heterogeneous (i. e. , serving different purposes) facilities, (ii) agents' locations are disclosed to the mechanism and (iii) agents bid for the set of facilities they are interested in (as opposed to bidding for their position on the network). We study the heterogeneous facility location problem under two different objective functions, namely: social cost (i. e. , sum of all agents' costs) and maximum cost. For either objective function, we study the approximation ratio of both deterministic and randomized truthful algorithms under the simplifying assumption that the underlying network topology is a line. For the social cost objective function, we devise an ( n − 1 ) -approximate deterministic truthful mechanism and prove a constant approximation lower bound. Furthermore, we devise an optimal and truthful (in expectation) randomized algorithm. As regards the maximum cost objective function, we propose a 3-approximate deterministic strategyproof algorithm, and prove a 3/2 approximation lower bound for deterministic strategyproof mechanisms. Furthermore, we propose a 3/2-approximate randomized strategyproof algorithm and prove a 4/3 approximation lower bound for randomized strategyproof algorithms.

ECAI Conference 2016 Conference Paper

Towards Better Models of Externalities in Sponsored Search Auctions

• Nicola Gatti 0001
• Marco Rocco
• Paolo Serafino
• Carmine Ventre

Sponsored Search Auctions (SSAs) arguably represent the problem at the intersection of computer science and economics with the deepest applications in real life. Within the realm of SSAs, the study of the effects that showing one ad has on the other ads, a. k. a. externalities in economics, is of utmost importance and has so far attracted the attention of much research. However, even the basic question of modeling the problem has so far escaped a definitive answer. The popular cascade model is arguably too idealized to really describe the phenomenon yet it allows a good comprehension of the problem. Other models, instead, describe the setting more adequately but are too complex to permit a satisfactory theoretical analysis. In this work, we attempt to get the best of both approaches: firstly, we define a number of general mathematical formulations for the problem in the attempt to have a rich description of externalities in SSAs and, secondly, prove a host of results drawing a nearly complete picture about the computational complexity of the problem. We complement these approximability results with some considerations about mechanism design in our context.

AAMAS Conference 2016 Conference Paper

What to Verify for Optimal Truthful Mechanisms without Money

• Diodato Ferraioli
• Paolo Serafino
• Carmine Ventre

AAAI Conference 2015 Conference Paper

A Mechanism Design Approach to Measure Awareness

• Diodato Ferraioli
• Carmine Ventre
• Gabor Aranyi

In this paper, we study protocols that allow to discern conscious and unconscious decisions of human beings; i. e. , protocols that measure awareness. Consciousness is a central research theme in Neuroscience and AI, which remains, to date, an obscure phenomenon of human brains. Our starting point is a recent experiment, called Post Decision Wagering (PDW) (Persaud, McLeod, and Cowey 2007), that attempts to align experimenters’ and subjects’ objectives by leveraging financial incentives. We note a similarity with mechanism design, a research area which aims at the design of protocols that reconcile often divergent objectives through incentivecompatibility. We look at the issue of measuring awareness from this perspective. We abstract the setting underlying the PDW experiment and identify three factors that could make it ineffective: rationality, risk attitude and bias of subjects. Using mechanism design tools, we study the barrier between possibility and impossibility of incentive compatibility with respect to the aforementioned characteristics of subjects. We complete this study by showing how to use our mechanisms to potentially get a better understanding of consciousness.

TCS Journal 2015 Journal Article

Combinatorial auctions with verification are tractable

• Piotr Krysta
• Carmine Ventre

We study mechanism design for social welfare maximization in combinatorial auctions with general bidders given by demand oracles. It is a major open problem in this setting to design a deterministic truthful auction which would provide the best possible approximation guarantee in polynomial time, even if bidders are double-minded (i. e. , they assign positive value to only two sets in their demand collection). On the other hand, there are known such randomized truthful auctions in this setting. In the general model of verification (i. e. , some kind of overbidding can be detected) we provide the first deterministic truthful auctions which indeed provide essentially the best possible approximation guarantees achievable by any polynomial-time algorithm even if the complete input data is known. This shows that deterministic truthful auctions have the same power as randomized ones if the bidders withdraw from unrealistic lies. Our truthful auctions are based on greedy algorithms and our approximation guarantee analyses employ linear programming duality based techniques. Finally, our truthfulness analyses are based on applications of the cycle-monotonicity technique which we show to surprisingly couple with the greedy approach.

JAIR Journal 2015 Journal Article

Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods

• Piotr Krysta
• Orestis Telelis
• Carmine Ventre

We design and analyze deterministic truthful approximation mechanisms for multi-unit Combinatorial Auctions involving only a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i.e., for more than one unit per distinct good. Our objective is to determine allocations of multisets that maximize the Social Welfare. Our main results are for multi-minded and submodular bidders. In the first setting each bidder has a positive value for being allocated one multiset from a prespecified demand set of alternatives. In the second setting each bidder is associated to a submodular valuation function that defines his value for the multiset he is allocated. For multi-minded bidders, we design a truthful FPTAS that fully optimizes the Social Welfare, while violating the supply constraints on goods within factor (1+e), for any fixed e>0 (i.e., the approximation applies to the constraints and not to the Social Welfare). This result is best possible, in that full optimization is impossible without violating the supply constraints. For submodular bidders, we obtain a PTAS that approximates the optimum Social Welfare within factor (1+e), for any fixed e>0, without violating the supply constraints. This result is best possible as well. Our allocation algorithms are Maximal-in-Range and yield truthful mechanisms, when paired with Vickrey-Clarke-Groves payments.

IJCAI Conference 2015 Conference Paper

Near-Optimal Approximation Mechanisms for Multi-Unit Combinatorial Auctions

• Piotr Krysta
• Orestis Telelis
• Carmine Ventre

We design and analyze deterministic truthful approximation mechanisms for multi-unit combinatorial auctions involving a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i. e. , for more than one unit per distinct good, that are expressed through their private valuation functions. Our objective is to determine allocations of multisets that maximize the Social Welfare approximately. Despite the recent theoretical advances on the design of truthful combinatorial auctions (for multiple distinct goods in unit supply) and multi-unit auctions (for multiple units of a single good), results for the combined setting are much scarcer. We elaborate on the main developments of [Krysta et al. , 2013], concerning bidders with multi-minded and submodular valuation functions, with an emphasis on the presentation of the relevant algorithmic techniques.

AAAI Conference 2015 Conference Paper

Truthful Mechanisms without Money for Non-Utilitarian Heterogeneous Facility Location

• Paolo Serafino
• Carmine Ventre

In this paper, we consider the facility location problem under a novel model recently proposed in the literature, which combines the no-money constraint (i. e. the impossibility to employ monetary transfers between the mechanism and the agents) with the presence of heterogeneous facilities, i. e. facilities serving different purposes. Agents thus have a significantly different cost model w. r. t. the classical model with homogeneous facilities studied in literature. We initiate the study of non-utilitarian optimization functions under this novel model. In particular, we consider the case where the optimization goal consists of minimizing the maximum connection cost of the agents. In this setting, we investigate both deterministic and randomized algorithms and derive both lower and upper bounds regarding the approximability of strategyproof mechanisms.

ECAI Conference 2014 Conference Paper

Heterogeneous Facility Location without Money on the Line

• Paolo Serafino
• Carmine Ventre

The study of facility location in the presence of self-interested agents has recently emerged as the benchmark problem in the research on mechanism design without money. Here we study the related problem of heterogeneous 2-facility location, that features more realistic assumptions such as: (i) multiple heterogeneous facilities have to be located, (ii) agents' locations are common knowledge and (iii) agents bid for the set of facilities they are interested in. We study the approximation ratio of both deterministic and randomized truthful algorithms when the underlying network is a line. We devise an (n− 1)-approximate deterministic truthful mechanism and prove a constant approximation lower bound. Furthermore, we devise an optimal and truthful (in expectation) randomized algorithm.

TCS Journal 2014 Journal Article

Truthful optimization using mechanisms with verification

• Carmine Ventre

We study the question of whether optimization problems can be solved exactly in the presence of economic constraints, such as truthfulness of selfish agents. In general, imposing these extra constraints makes it impossible to optimize, even in exponential time. To reconcile optimization and economic incentives we focus on so-called mechanisms with verification and show that, under this general mechanism design paradigm, it is indeed possible to optimize and to be truthful. Our truthful mechanisms minimize any cost function that is monotone nondecreasing in agentsʼ costs under the technical hypothesis that the possible declarations of the selfish agents belong to a finite set. Our results also extend to the multidimensional scenario of compound agents; in the case in which the single dimensions are one-parameter, we also show how to implement truthfully and efficiently classical (approximation) algorithms for cost functions that behave smoothly in the presence of input rounding. Our results are applied to a number of very general scheduling problems to obtain the first truthful mechanisms for them. Finally, the issue of designing mechanisms with verification for infinite domains is studied showing the limitations that the imposition of the Taxation Principle yields.

TCS Journal 2013 Journal Article

Ranking games that have competitiveness-based strategies

• Leslie Ann Goldberg
• Paul W. Goldberg
• Piotr Krysta
• Carmine Ventre

An extensive literature in economics and social science addresses contests, in which players compete to outperform each other on some measurable criterion, often referred to as a player’s score, or output. Players incur costs that are an increasing function of score, but receive prizes for obtaining higher score than their competitors. In this paper we study finite games that are discretized contests, and the problems of computing exact and approximate Nash equilibria. Our motivation is the worst-case hardness of Nash equilibrium computation, and the resulting interest in important classes of games that admit polynomial-time algorithms. For games that have a tie-breaking rule for players’ scores, we present a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and for multiple players, a characterization of Nash equilibria that shows an interesting parallel between these games and unrestricted 2-player games in normal form. When ties are allowed, via a reduction from these games to a subclass of anonymous games, we give approximation schemes for two special cases: constant-sized set of strategies, and constant number of players.

JAAMAS Journal 2010 Journal Article

A response to “Mechanism Design with Partial Verification and Revelation Principle”

• Vincenzo Auletta
• Paolo Penna
• Carmine Ventre

SODA Conference 2010 Conference Paper

Utilitarian Mechanism Design for Multi-Objective Optimization

• Fabrizio Grandoni 0001
• Piotr Krysta
• Stefano Leonardi 0001
• Carmine Ventre

JAAMAS Journal 2009 Journal Article

Alternatives to truthfulness are hard to recognize

• Vincenzo Auletta
• Paolo Penna
• Carmine Ventre

Abstract The central question in mechanism design is how to implement a given social choice function. One of the most studied concepts is that of truthful implementations in which truth-telling is always the best response of the players. The Revelation Principle says that one can focus on truthful implementations without loss of generality (if there is no truthful implementation then there is no implementation at all). Green and Laffont (Rev Econ Stud 53: 447–456, 1986) showed that, in the scenario in which players’ responses can be partially verified, the revelation principle holds only in some particular cases. When the Revelation Principle does not hold, non-truthful implementations become interesting since they might be the only way to implement a social choice function of interest. In this work we show that, although non-truthful implementations may exist, they are hard to find. Namely, it is NP-complete to decide if a given social choice function can be implemented in a non-truthful manner, or even if it can be implemented at all. This is in contrast to the fact that truthful implementability can be efficiently recognized, even when partial verification of the agents is allowed. Our results also show that there is no “simple” characterization of those social choice functions for which it is worth looking for non-truthful implementations.

TCS Journal 2009 Journal Article

Fast payment schemes for truthful mechanisms with verification

• Alessandro Ferrante
• Gennaro Parlato
• Francesco Sorrentino
• Carmine Ventre

In this paper we study optimization problems with verifiable one-parameter selfish agents introduced by Auletta et al. [V. Auletta, R. De Prisco, P. Penna, P. Persiano, The power of verification for one-parameter agents, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming, ICALP, in: LNCS, vol. 3142, 2004, pp. 171–182]. Our goal is to allocate load among the agents, provided that the secret data of each agent is a single positive real number: the cost they incur per unit load. In such a setting the payment is given after the load completion, therefore if a positive load is assigned to an agent, we are able to verify if the agent declared to be faster than she actually is. We design truthful mechanisms when the agents’ type sets are upper-bounded by a finite value. We provide a truthful mechanism that is c ⋅ ( 1 + ϵ ) -approximate if the underlying algorithm is c -approximate and weakly-monotone. Moreover, if type sets are also discrete, we provide a truthful mechanism preserving the approximation ratio of its algorithmic part. Our results improve the existing ones which provide truthful mechanisms dealing only with finite type sets and do not preserve the approximation ratio of the underlying algorithm. Finally, we give applications for our payment schemes. Firstly, we give a full characterization of the Q ∥ C max problem by using our techniques. Even if our payment schemes need upper-bounded type sets, every instance of Q ∥ C max can be “mapped” into an instance with upper-bounded type sets preserving the approximation ratio. In conclusion, we turn our attention to binary demand games. In particular, we show that the Minimum Radius Spanning Tree admits an exact truthful mechanism with verification achieving time (and space) complexity of the fastest centralized algorithm for it. This contrasts with a recent truthful mechanism for the same problem [G. Proietti, P. Widmayer, A truthful mechanism for the non-utilitarian minimum radius spanning tree problem, in: Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, ACM Press, 2005, pp. 195–202] which pays a linear factor with respect to the complexity of the fastest centralized algorithm. Such a result is extended to several binary demand games studied in literature.