In this work, we consider the design of Non-Obviously Manipulable (NOM) mechanisms, mechanisms that bounded rational agents may fail to recognize as manipulable, for two relevant classes of succinctly representable Hedonic Games: Additively Separable and Fractional Hedonic Games. In these classes, agents have cardinal scores towards other agents, and their preferences over coalitions are determined by aggregating such scores. This aggregation results in a utility function for each agent, which enables the evaluation of outcomes via the utilitarian social welfare. We first prove that, when scores can be arbitrary, every optimal mechanism is NOM; moreover, when scores are limited in a continuous interval, an optimal mechanism that is NOM exists. Given the hardness of computing optimal outcomes in these settings, we turn our attention to efficient and NOM mechanisms. To this aim, we first prove a characterization of NOM mechanisms that simplifies the class of mechanisms of interest. Then, we design a NOM mechanism returning approximations that asymptotically match the best-known approximation achievable in polynomial time. Finally, we focus on discrete scores, where the compatibility of NOM with optimality depends on the specific values. Therefore, we initiate a systematic analysis to identify which discrete values support this compatibility and which do not.

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.

Most economic reports suggest that almost half of the market value unlocked by artificial intelligence (AI) by the next decade (about 9 trillion USD per year) will be in marketing&sales. In particular, AI will allow the optimization of more and more intricate economic settings in which multiple different activities can be automated jointly. A relatively recent example is that one of ad auctions in which similar products or services are displayed together with their price, thus merging advertising and pricing in a unique website. This is the case, e.g., of Google Hotel Ads and TripAdvisor. More precisely, as in a classical ad auction, the ranking of the ads depends on the advertisers' bids, while, differently from classical ad auctions, the price is displayed together with the ad, so as to provide a direct comparison among the prices and thus dramatically affect the behavior of the users. This paper investigates how displaying prices and ads together conditions the properties of the main economic mechanisms such as VCG and GSP. Initially, we focus on the direct-revelation mechanism, showing that prices are chosen by the mechanisms once given the advertisers' reports. We also provide an efficient algorithm to compute the optimal allocation given the private information reported by the advertisers. Then, with both VCG and GSP payments, we show the inefficiency in terms of Price of Anarchy (PoA) and Stability (PoS) over the social welfare and mechanism's revenue when the advertisers choose the prices. The main results show that, with both VCG and GSP, PoS over the revenue may be unbounded even with two slots, while PoA over the social welfare may be as large as the number of slots. Finally, we show that, under some assumptions, simple modifications to VCG and GSP allow us to obtain a better PoS over the revenue.

Modeling how agents form their opinions is of paramount importance for designing marketing and electoral campaigns. In this work, we present a new framework for opinion formation which generalizes the well-known Friedkin-Johnsen model by incorporating three important features: (i) social group membership, that limits the amount of influence that people not belonging to the same group may lead on a given agent; (ii) both attraction among friends, and repulsion among enemies; (iii) different strengths of influence lead from different people on a given agent, even if the social relationships among them are the same. We show that, despite its generality, our model always admits a pure Nash equilibrium which, under opportune mild conditions, is even unique. Next, we analyze the performances of these equilibria with respect to a social objective function defined as a convex combination, parametrized by a value λ∈[0,1], of the costs yielded by the untruthfulness of the declared opinions and the total cost of social pressure. We prove bounds on both the price of anarchy and the price of stability which show that, for not-too-extreme values of λ, performance at equilibrium are very close to optimal ones. For instance, in several interesting scenarios, the prices of anarchy and stability are both equal to max{2λ,1-λ}/min{2λ,1-λ} which never exceeds 2 for λ∈[1/5,1/2].

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 focus on the election manipulation problem through social influence, where a manipulator exploits a social network to make her most preferred candidate win an election. Influence is due to information in favor of and/or against one or multiple candidates, sent by seeds and spreading through the network according to the independent cascade model. We provide a comprehensive theoretical study of the election control problem, investigating two forms of manipulations: seeding to buy influencers given a social network and removing or adding edges in the social network given the set of the seeds and the information sent. In particular, we study a wide range of cases distinguishing in the number of candidates or the kind of information spread over the network. Our main result shows that the election manipulation problem is not affordable in the worst-case, even when one accepts to get an approximation of the optimal margin of victory, except for the case of seeding when the number of hard-to-manipulate voters is not too large, and the number of uncertain voters is not too small, where we say that a voter that does not vote for the manipulator's candidate is hard-to-manipulate if there is no way to make her vote for this candidate, and uncertain otherwise. We also provide some results showing the hardness of the problems in special cases. More precisely, in the case of seeding, we show that the manipulation is hard even if the graph is a line and that a large class of algorithms, including most of the approaches recently adopted for social-influence problems (e.g., greedy, degree centrality, PageRank, VoteRank), fails to compute a bounded approximation even on elementary networks, such as undirected graphs with every node having a degree at most two or directed trees. In the case of edge removal or addition, our hardness results also apply to election manipulation when the manipulator has an unlimited budget, being allowed to remove or add an arbitrary number of edges, and to the basic case of social influence maximization/minimization in the restricted case of finite budget. Interestingly, our hardness results for seeding and edge removal/addition still hold in a re-optimization variant, where the manipulator already knows an optimal solution to the problem and computes a new solution once a local modification occurs, e.g., the removal/addition of a single edge.

We focus on the scenario in which messages pro and/or against one or multiple candidates are spread through a social network in order to affect the votes of the receivers. Several results are known in the literature when the manipulator can make seeding by buying influencers. In this paper, instead, we assume the set of influencers and their messages to be given, and we ask whether a manipulator (e.g., the platform) can alter the outcome of the election by adding or removing edges in the social network. We study a wide range of cases distinguishing for the number of candidates or for the kind of messages spread over the network. We provide a positive result, showing that, except for trivial cases, manipulation is not affordable, the optimization problem being hard even if the manipulator has an unlimited budget (i.e., he can add or remove as many edges as desired). Furthermore, we prove that our hardness results still hold in a reoptimization variant, where the manipulator already knows an optimal solution to the problem and needs to compute a new solution once a local modification occurs (e.g., in bandit scenarios where estimations related to random variables change over time).

The social proof marketing strategy assumes that the marketer provides a novel product for free to some users of a social network and then promptly recommends the product to other users, by informing them that a number of their friends are already using it. In this paper we study this popular marketing strategy in scenarios where the new product enters in markets where two old products are already competing. We show that if customers tend to adopt the product that is the most popular one (over the three alternative products) among their friends, then this marketing strategy allows to maximize the diffusion of the new product only on a narrow class of networks. Moreover, even if we focus on this narrow class of networks, computing the best order of the recommendations is computationally intractable. Instead, if customers are less prone to change their mind, that is, if they are willing to adopt some product only when an absolute majority of their friends has already agreed on it, then the marketing strategy always works well and, furthermore, an optimal order of recommendations can be computed in polynomial time.

Security Games have been widely adopted to model scenarios in which one player, the Defender, has to decide how to deploy her resources to minimize the loss that can be caused by an attack performed by another player, the Attacker, aiming at maximizing such loss. In the present paper, we focus on scenarios in which the Defender has lexicographic-like preferences on the targets, being primarily interested in defending the integrity of a subset of the targets and, only secondarily, to reduce the amount of the other damaged targets. Our central motivation for studying this problem comes from the need to reduce the impact of malicious flows in networks, that can be either physical, like cities, or virtual, e.g., social networks. In this work, we introduce a new class of security games to model these scenarios, characterizing it and proving the NP-hardness of computing a leader-follower equilibrium, which is the most appropriate solution concept for this setting. To compute such an equilibrium, we then provide an exact exponential-time algorithm, capable of exploiting the topological properties of the network. Finally, we show that, with opportune optimizations, this algorithm can work efficiently even on network of 10000 nodes.

Online social networks are nowadays one of the most effective and widespread tools used to share information. In addition to being employed by individuals for communicating with friends and acquaintances, and by brands for marketing and customer service purposes, they constitute a primary source of daily news for a significant number of users. Unfortunately, besides legit news, social networks also allow to effectively spread inaccurate or even entirely fabricated ones. Also due to sensationalist claims, misinformation can spread from the original sources to a large number of users in a very short time, with negative consequences that, in extreme cases, can even put at risk public safety or health. In this work we discuss and propose methods to limit the spread of misinformation over online social networks. The issue is split in two separate sub-problems. We first aim to identify the most probable sources of the misinformation among the subset of users that have been reached by it. In the second step, assuming to know the misinformation sources, we want to locate a minimum number of monitors (that is, entities able to identify and block false information) in the network in order to prevent that the misinformation campaign reaches some “critical” nodes while maintaining low the number of nodes exposed to the infection. For each of the two issues, we provide both heuristics and mixed integer programming formulations. To verify the quality and efficiency of our suggested solutions, we conduct experiments on several real-world networks. The results of this extensive experimental phase validate our heuristics as effective tools to contrast the spread of misinformation in online social networks. Regarding the source identification step, our approach showed success rates above 80% in most of the considered settings, and above 60% in almost all of them. With respect to the second issue, our heuristic proved to be able to obtain solutions that exceeded (in terms of number of required monitors) the ones obtained through our MILP-based approach of more than 20% in only few test scenarios. Our heuristics for both problems also proved to outperform significantly some previously proposed algorithms.

Friedkin and Johnsen (1990) modeled opinion formation in social networks as a dynamic process which evolves in rounds: at each round each agent updates her expressed opinion to a weighted average of her innate belief and the opinions expressed in the previous round by her social neighbors. The stubbornness level of an agent represents the tendency of the agent to express an opinion close to her innate belief. Motivated by the observation that innate beliefs, stubbornness levels and even social relations can co-evolve together with the expressed opinions, we present a new model of opinion formation where the dynamics runs in a co-evolving environment. We assume that agents’ stubbornness and social relations can vary arbitrarily, while their innate beliefs slowly change as a function of the opinions they expressed in the past. We prove that, in our model, the opinion formation dynamics converges to a consensus if reasonable conditions on the structure of the social relationships and on how the personal beliefs can change are satisfied. Moreover, we discuss how this result applies in several simpler (but realistic) settings.

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.

Opinion diffusion is studied on social graphs where agents hold binary opinions and where social pressure leads them to conform to the opinion manifested by their neighbors. Within this setting, questions related to whether a minority/majority can spread the opinion it supports to all the other agents are considered.It is shown that, no matter of the graph given at hand, there always exists a group formed by a half of the agents that can annihilate the opposite opinion. Instead, the influence power of minorities depends on certain features of the underlying graphs, which are NP-hard to be identified. Deciding whether the two opinions can coexist in some stable configuration is NP-hard, too.

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.

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.

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.

We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted price mechanisms are conceptually simple mechanisms that work by proposing a “take-it-or-leave-it” offer to each buyer. We apply sequential posted price mechanisms to single-parameter multi-unit settings in which each buyer demands only one item and the mechanism can assign the service to at most k of the buyers. For standard sequential posted price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the case of a continuous valuation distribution when various standard assumptions hold simultaneously. In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted price mechanism is proportional to the ratio of the highest and lowest possible valuation. We prove that for two simple generalizations of these mechanisms, a better revenue performance can be achieved: if the sequential posted price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then a $$\varOmega (1/\max \{1,d\})$$ fraction of the optimal revenue can be extracted, where d denotes the “degree of dependence” of the valuations, ranging from complete independence ( $$d=0$$ ) to arbitrary dependence ( $$d = n-1$$ ). When we generalize the sequential posted price mechanisms further, such that the mechanism has the ability to make a take-it-or-leave-it offer to the i-th buyer that depends on the valuations of all buyers except i, we prove that a constant fraction $$(2 - \sqrt{e})/4 \approx 0.088$$ of the optimal revenue can be always extracted.

It is often observed that agents tend to imitate the behavior of their neighbors in a social network. This imitating behavior might lead to the strategic decision of adopting a public behavior that differs from what the agent believes is the right one and this can subvert the behavior of the population as a whole. In this paper, we consider the case in which agents express preferences over two alternatives and model social pressure with the majority dynamics: at each step an agent is selected and its preference is replaced by the majority of the preferences of her neighbors. In case of a tie, the agent does not change her current preference. A profile of the agents’ preferences is stable if the each agent’s preference coincides with the preference of at least half of the neighbors (thus, the system is in equilibrium). We ask whether there are network topologies that are robust to social pressure. That is, we ask whether there are graphs in which the majority of preferences in an initial profile $${\mathbf {s}}$$ always coincides with the majority of the preference in all stable profiles reachable from $${\mathbf {s}}$$ . We completely characterize the graphs with this robustness property by showing that this is possible only if the graph has no edge or is a clique or very close to a clique. In other words, except for this handful of graphs, every graph admits at least one initial profile of preferences in which the majority dynamics can subvert the initial majority. We also show that deciding whether a graph admits a minority that becomes majority is NP-hard when the minority size is at most 1 / 4-th of the social network size.

Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g., exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. In several cases it happens that on a time-scale shorter than mixing time the chain is “quasi-stationary”, meaning that it stays close to some small set of the state space, while in a time-scale multiple of the mixing time it jumps from one quasi-stationary configuration to another; this phenomenon is usually called “metastability”. In this paper we give a quantitative definition of “metastable probability distributions” for a Markov chain and we study the metastability of the Logit dynamics for some classes of coordination games. In particular, we study no-risk-dominant coordination games on the clique (which is equivalent to the well-known Glauber dynamics for the Ising model) and coordination games on a ring (both the risk-dominant and no-risk-dominant case). We also describe a simple “artificial” game that highlights the distinctive features of our metastability notion based on distributions.

We present the first general bounds on the mixing time of logit dynamics for wide classes of strategic games. The logit dynamics describes the behaviour of a complex system whose individual components act "selfishly" and keep responding according to some partial ("noisy") knowledge of the system. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that, for potential games, the mixing time is upper and lower bounded by an "exponential" in the inverse of the noise and in the maximum potential difference. Instead, for games with dominant strategies, the mixing time cannot grow arbitrarily with the inverse of the noise. Finally, we refine our analysis for a subclass of potential games called "graphical" coordination games and we give evidence that the mixing time strongly depends on the structure of the underlying graph. Games in this class have been previously studied in Physics and, more recently, in Computer Science in the context of diffusion of new technologies.