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.

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.

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

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

We 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.

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.

Abstract. We consider the scheduling problem when no payments are allowed and the machines are bound by their declarations. We are interested in a notion of incentive compatibility, stronger than the (standard) strategy-proofness, termed obviously strategy-proof (OSP), and explore its possibilities and limitations. OSP formalizes the concept of strategy-proofness 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 providing information about her true type is at least as good as the best possible outcome after misreporting information about her type. Under the weaker constraint of strategyroofness, Koutsoupias [ Theoret. Comput. Syst., 54 (2014), pp. 375–387] proves a tight approximation ratio of [Formula: see text] for the makespan for one task, under the monitoring paradigm. 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 strategy-proofness to OSP, as long as the mechanism designer can implement a particular notion of monitoring. To achieve this, we introduce the notion of max-monitoring and prove that weaker monitoring frameworks do not suffice, thus providing a complete picture of OSP with monitoring in the context of scheduling a task without money.

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.

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.

The Ethereum block-building process has changed significantly since the emergence of Proposer-Builder Separation. Validators access blocks through a marketplace, where block builders bid for the right to construct the block and earn MEV (Maximal Extractable Value) rewards in an on-chain competition, known as the MEV-boost auction. While more than 90% of blocks are currently built via MEV-Boost, tradeoffs between builders’ strategic behaviors and auction design remain poorly understood. In this paper we address this gap. We introduce a game-theoretic model for MEV-Boost auctions and use simulations to study different builders’ bidding strategies observed in practice. We study various strategic interactions and auction setups and evaluate how the interplay between critical elements such as access to MEV opportunities and improved connectivity to relays impact bidding performance. Our results demonstrate the importance of latency on the effectiveness of builders’ strategies and the overall auction outcome from the proposer’s perspective.

Political scientists distinguish between polarization (loosely, people moving further apart along a single dimension) and sorting (an increase in the probabilistic dependence between multiple dimensions of individual difference). Among other harms, sorting can increase the risk of conflict escalation by reinforcing us-and-them group identities and reducing the prevalence of cross-cutting affiliations. In this paper, we (i) review normative arguments for high or low sortedness, (ii) summarize the mechanisms by which sortedness can change, and (iii) show that under a simple model of social media recommender-driven preference change, personalized engagement-based ranking creates a systematic tendency towards sorting, while ranking by diverse engagement (sometimes called “bridging-based ranking”) mitigates this tendency. We conclude by considering the implications for those conducting systemic risk assessments of very large online platforms under the EU Digital Services Act.

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.

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.

The design of algorithms or protocols that are able to align the goals of the planner with the selfish interests of the agents involved in these protocols is of paramount importance in almost every decentralized setting (such as, computer networks, markets, etc.) as shown by the rich literature in Mechanism Design. Recently, huge interest has been devoted to the design of mechanisms for imperfectly rational agents, i.e., mechanisms for which agents are able to easily grasp that there is no action different from following the protocol that would satisfy their interests better. This work has culminated in the definition of Obviously Strategyproof (OSP) Mechanisms, that have been shown to capture the incentives of agents without contingent reasoning skills.

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

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

Abstract 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 two paradigmatic problems: machine scheduling and facility location. We prove that, for both problems, “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.

The realization that selfish interests need to be accounted for in the design of algorithms has produced many interesting and valuable contributions in computer science under the general umbrella of algorithmic mechanism design. Our work stems from the observation that selfishness is different from rationality; agents will attempt to strategize whenever they perceive it to be convenient. Recent work in economics has focused on a particular notion of imperfect rationality, namely absence of contingent reasoning skills, and defined obvious strategyproofness (OSP) as a way to deal with the selfishness of these agents. However, it is not clear to date what algorithmic approaches ought to be used for OSP. In this article, we rather surprisingly show that, for binary allocation problems, OSP is fully captured by a natural combination of two well-known and extensively studied algorithmic techniques: forward and reverse greedy. We call two-way greedy this underdeveloped algorithmic design paradigm. We are then able to import a host of known approximation bounds obtained through greedy algorithms to OSP and strengthen the strategic properties of this family of algorithms. Finally, we begin exploring the full power of two-way greedy (and, in turns, OSP) in the context of set systems.

Abstract 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, i.e., those who struggle with contingent reasoning (Li in Am Econ Rev 107(11):3257–3287, 2017). However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching (Ashlagi and Gonczarowski in J Econ Theory 177:405–425, 2018). 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 et al. in WINE 9470:398–412, 2015).

We consider the setting of combinatorial auctions when the agents are single-minded and have no contingent reasoning skills. We are interested in mechanisms that provide the right incentives to these imperfectly rational agents, and therefore focus our attention to obviously strategyproof (OSP) mechanisms. These mechanisms require that at each point during the execution where an agent is queried to communicate information, it should be "obvious" for the agent what strategy to adopt in order to maximise her utility. In this paper we study the potential of OSP mechanisms with respect to the approximability of the optimal social welfare. We consider two cases depending on whether the desired bundles of the agents are known or unknown to the mechanism. For the case of known-bundle single-minded agents we show that OSP can actually be as powerful as (plain) strategyproofness (SP). In particular, we show that we can implement the very same algorithm used for SP to achieve a √m-approximation of the optimal social welfare with an OSP mechanism, m being the total number of items. Restricting our attention to declaration domains with two values, we provide a 2-approximate OSP mechanism, and prove that this approximation bound is tight. We also present a randomised mechanism that is universally OSP and achieves a finite approximation of the optimal social welfare for the case of arbitrary size finite domains. This mechanism also provides a bounded approximation ratio when the valuations lie in a bounded interval (even if the declaration domain is infinitely large). For the case of unknown-bundle single-minded agents, we show how we can achieve an approximation ratio equal to the size of the largest desired set, in an OSP way. We remark this is the first known application of OSP to multi-dimensional settings, i.e., settings where agents have to declare more than one parameter. Our results paint a rather positive picture regarding the power of OSP mechanisms in this context, particularly for known-bundle single-minded agents. All our results are constructive, and even though some known strategyproof algorithms are used, implementing them in an OSP way is a non-trivial task.

Catering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms and approximation algorithms. Obviously strategyproof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the "right" definition rather than on the construction of these mechanisms. We here give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines. By extending the well-known cycle monotonicity technique, we are able to concentrate on the algorithmic component of OSP mechanisms and provide some novel paradigms for their design.

Convergence rate and stability of a solution concept are classically measured in terms of “eventually” and “forever,” respectively. In the wake of recent computational criticisms to this approach, we study whether these timeframes can be updated to have states computed “quickly” and stable for “long enough”. Logit dynamics allows irrationality in players’ behavior and may take time exponential in the number of players n to converge to a stable state (i.e., a certain distribution over pure strategy profiles). We prove that every potential game, for which the behavior of the logit dynamics is not chaotic as n increases, admits distributions stable for a super-polynomial number of steps in n no matter the players’ irrationality and the starting profile of the dynamics. The convergence rate to these metastable distributions is polynomial in n when the players are not too rational. Our proofs build upon the new concept of partitioned Markov chains , which might be of independent interest, and a number of involved technical contributions.

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 [Ferraioli and Ventre, AAAI 2017]. 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.

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.

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.

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 (Kovacs, Meyer, and Ventre 2015).

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.

Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in combinatorial auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of k -minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.

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.

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 incentive-compatibility. 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.

In this paper, we consider the facility location problem un- der 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 strate- gyproof mechanisms.

Novel algorithmic ideas for big data have not been accompanied by advances in the way central memory is allocated to concurrently running programs. Commonly, RAM is poorly managed since the programs’ trade offs between speed of execution and RAM consumption are ignored. This trade off is, however, well known to the programmers. We adopt mechanism design tools to truthfully elicit this (multidimensional) information with the aim of designing more clever RAM allocation algorithms. We introduce a novel paradigm wherein programs are bound to overbidding declarations of their running times. We show the limitations of this paradigm in the absence of transfers and prove how to leverage waiting times, as a currency, to obtain optimal money burning mechanisms for the makespan. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

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.

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.

In a classic optimization problem, the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In the case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multiobjective optimization problems. In this setting we are given a main objective function and a set of secondary objectives which are modeled via budget constraints. Multiobjective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely, approximate Pareto sets and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto sets, we devise truthful deterministic and randomized multicriteria fully polynomial-time approximation schemes (FPTASs) for multiobjective optimization problems whose exact version admits a pseudopolynomial-time algorithm, as, for instance, the multibudgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching, and matroid intersection. Our construction also applies to multidimensional knapsack and multiunit combinatorial auctions. Our FPTASs compute a $(1+\varepsilon)$-approximate solution violating each budget constraint by a factor $(1+\varepsilon)$. When feasible solutions induce an independence system, i.e., when subsets of feasible solutions are feasible as well, we present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint, where one wants to compute a minimum cost spanning tree whose length is at most a given value $L$. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time). This result can be derandomized in the case of integral lengths. All the mentioned results match the best known approximation ratios, which are, however, obtained by nontruthful algorithms.

Abstract In Stackelberg pricing a leader sets prices for items to maximize revenue from a follower purchasing a feasible subset of items. We consider computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but who apply publicly known algorithms to determine the items to purchase. This corresponds to general multidimensional pricing when customers cannot optimize their valuation functions efficiently but still aim to act rationally to the best of their ability. We consider two versions of this novel type of pricing problem. In the MIn‐KNAPSACK variant items are weighted objects and the follower seeks to purchase a min‐cost selection of objects of some bounded weight. When he uses a greedy 2‐approximation algorithm, we provide a polynomial‐time (2+ε) ‐approximation algorithm for the leader's revenue maximization problem based on so‐called near‐uniform price assignments. We also prove the problem to be strongly NP‐hard. In the SET‐COVER variant items are subsets of some ground set which the follower seeks to cover. When he uses a standard primal‐dual approach, we prove that exact revenue maximization is possible in polynomial time when elements have frequency 2 (VERTEX‐COVER variant). This stands in sharp contrast to APX‐hardness for the problem with elements of frequency 3. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

This paper studies - from the perspective of efficient computation - a type of competition that is widespread throughout the plant and animal kingdoms, higher education, politics and artificial contests. In this setting, an agent gains utility from his relative performance (on some measurable criterion) against other agents, as opposed to his absolute performance. We model this situation using ranking games in which each strategy corresponds to a level of competitiveness, and incurs an upfront cost that is higher for more competitive strategies. We study the Nash equilibria of these games, and polynomial-time algorithms for computing them. For games in which there is no tie between agents' levels of competitiveness we give a polynomial-time algorithm for computing an exact equilibrium in the 2-player case, and 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 polynomial-time approximation schemes for two special cases: constant-sized set of strategies, and constant number of players. The latter result is improved to a fully polynomial-time approximation scheme when the constant number of players only compete to win the game, i.e. to be ranked first.

In a classic optimization problem the complete input data is known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multi-objective optimization problems, where we are given the main objective function, and a set of secondary objectives which are modeled via budget constraints. Multi-objective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting, goals. Our main contribution is showing that two of the main tools for the design of approximation algorithms for multi-objective optimization problems, namely approximate Pareto curves and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto curves, we devise truthful FPTASs for multi-objective optimization problems whose exact version admits a pseudo-polynomial-time algorithm, as for instance the multi-budgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching, and matroid intersection. Our technique applies also to multi-dimensional knapsack and multi-unit combinatorial auctions. Our FPTASs compute a (1 + ε)-approximate solution violating each budget constraint by a factor (1 + ε). For a relevant sub-class of the mentioned problems we also present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest elements in the optimum solution. Finally we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and a random perturbation step (ensuring low expected running time in a way similar to the smoothed analysis of algorithms). All the mentioned results match the best known approximation ratios, which however are obtained by non-truthful algorithms.

We present the first general positive result on the construction of collusion-resistant mechanisms, that is, mechanisms that guarantee dominant strategies even when agents can form arbitrary coalitions and exchange compensations (sometimes referred to as transferable utilities or side payments). This is a much stronger solution concept as compared to truthful or even group-strategyproof mechanisms, and only impossibility results were known for this type of mechanisms in the "classical" model.