1,721,019 research outputs found
Metastability of the Logit Dynamics for Asymptotically Well-Behaved Potential Games
Full text linkConvergence rate and stability of a solution concept are classically measured in terms of “even- tually” and “forever”, respectively. In the wake of recent computational criticisms to this approach, we study whether these time frames 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 pro- files). 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, that might be of indepen- dent interest, and a number of involved technical contributions
Election Control in Social Networks via Edge Addition or Removal
No full textWe 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)
Obvious strategyproofness needs monitoring for good approximations (extended abstract)
Full text linkObvious 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 [10]. However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching [3]. We here deepen the study of the limitations of OSP mechanisms by look-ing 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 signifificant cost. How-ever, rather surprisingly, we prove that OSP mechanisms can return opti-mal solutions when they use monitoring|a mechanism design paradigm that introduces a mild level of scrutiny on agents' declarations [9]
A Mechanism Design Approach to Measure Awareness
Full text linkIn 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
Probabilistic Verification for Obviously Strategyproof Mechanisms
Full text linkObviously 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 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
On the Impact of Social Media Recommendations on Opinion Consensus
No full textWe consider a discrete opinion formation problem in a setting where agents are influenced by both information diffused by their social relations and from recommendations received directly from the social media manager. We study how the “strength” of the influence of the social media and the homophily ratio affect the probability of the agents of reaching a consensus and how they can determine the type of consensus reached. In a simple 2-symmetric block model we prove that agents converge either to a consensus or to a persistent disagreement. In particular, we show that when the homophily ratio is large, the social media has a very low capacity of determining the outcome of the opinion dynamics. On the other hand, when the homophily ratio is low, the social media influence can have an important role on the dynamics, either by making harder to reach a consensus or inducing it on extreme opinions. Finally, in order to extend our analysis to more general and realistic settings we give some experimental evidences that our results still hold on general networks
Obvious strategyproofness needs monitoring for good approximations
No full textObvious 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)
Robustness in Discrete Preference Games
No full textIn a discrete preference game, each agent is equipped with an internal belief and declares her preference from a discrete set of alternatives. The payoff of an agent depends on whether the declared preference agrees with the belief of the agent and on the coordination with the preferences declared by the neighbors of the agent in the underlying social network. These games have been used to model the formation of opinions and the adoption of innovations in social networks.
Recently, researchers have obtained bounds on the Price of Anarchy and on the Price of Stability of discrete preference games and they have studied to which extent the winning preference reached via best-response dynamics disagrees with the majority of beliefs. In this work, we investigate the robustness of these results to variants of the model. Our starting point is the observation that bounds on the Price of Anarchy and Stability can be very dependent on the way the quality of an equilibrium is measured. On the other side, results about the disagreement between majority at equilibria and majority among beliefs continue to hold even if we consider different classes of dynamics, such as no-worse-response dynamics, best response with multiple players updating at the same time, or with weighted neighbors
Contrasting the Spread of Misinformation in Online Social Networks
Full text linkThe emergence of online social networks has revolutionized the way people seek and share information. Nowadays, popular online social sites as Twitter, Facebook and Google+ are among the major news sources as well as the most effective channels for viral marketing. However, these networks also became the most effective channel for spreading misinformation, accidentally or maliciously. The widespread diffusion of inaccurate information or fake news can lead to undesirable and severe consequences, such as widespread panic, libelous campaigns and conspiracies. In order to guarantee the trustworthiness of online social networks it is a crucial challenge to find effective strategies to contrast the spread of the misinformation in the network.
In this paper we concentrate our attention on two problems related to the diffusion of misinformation in social networks: identify the misinformation sources and limit its diffusion in the network. We consider a social network where some nodes have already been infected from misinformation. We first provide an heuristics to recognize the set of most probable sources of the infection. Then, we provide an heuristics to place a few monitors in some network nodes in order to control information diffused by the suspected nodes and block misinformation they injected in the network before it reaches a large part of the network. To verify the quality and efficiency of our suggested solutions, we conduct experiments on several real-world networks. Empirical results indicate that our heuristics are among the most effective known in literature
- …
