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.

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.

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.

We consider general resource assignment games involvingselfish users/agentsin which users compete for resources and try to be assigned to those which maximize their own benefits (e.g., try to route their traffic through links which minimize the latency of their own traffic). We propose and study amechanism designapproach in which an allocation mechanism assigns users to resources and charges the users for using the resources so as to induce each user totruthfullyreport a private piece of information he/she holds (e.g., how much traffic he/she needs to transmit). This information is crucial for computing optimal (or close to optimal) allocations and an agent could misreport his/her information to induce the underlying allocation algorithm to output a solution which he/she likes more (e.g., which assigns better resources to him/her). For our resource allocation problems, we give analgorithmic characterizationof the solutions for which truth-telling is a Nash equilibrium. A natural application of these results is to a scheduling/routing problem which is the mechanism design counterpart of the selfish routing game of Koutsoupias and Papadimitriou [1999]: Each selfish user wants to route a piece of unsplittable traffic using one ofmlinks of different speeds so as to minimize his/herownlatency. Our mechanism design counterpart can be seen as the problem of schedulingselfish jobson parallel related machines and is the dual of the problem of scheduling (unselfish) jobs on parallelselfish machinesstudied by Archer and Tardos [2001]. Koutsoupias and Papadimitriou studied an “anarchic” scenario in which each user chooses his/her own link, and this may produce Nash equilibria of cost Ω(logm/log logm) times the optimum. Our mechanism design counterpart is a possible way of reducing the effect of selfish behavior via suitable incentives to the agents (i.e., taxes for using the links). We indeed show that in the resulting game, it is possible to guarantee an approximation factor of 8 for any number of links/machines (this solution also works for online settings). However, it remains impossible to guarantee arbitrarily good approximate solutions, even for 2 links/machines and even if the allocation algorithm is allowed superpolynomial time. This result shows that our scheduling problem with selfish jobs is more difficult than the scheduling problem with selfish machines by Archer and Tardos (which admits exact solutions). We also study some generalizations of this basic problem.

We present an experiment relative to the use of Bluetooth wireless technology to provide network support for midlet applications accessing Web services. We refer to the most common architecture used to invoke Web services, where a client and a server exchange SOAP messages using HTTP as the transport protocol. To the best of our knowledge, there is no implemented support for executing a HTTP POST operation over a Bluetooth channel. Therefore, to guarantee the independence of the application from the type of communication channel used, in this paper, we deal with the problem of designing a framework allowing a Java application programmer to directly interface Web services from a mobile device using a Bluetooth connection. This paper presents a proof of concept of how Bluetooth technology can be used to design, develop, and deploy Web services-based applications. According to our experiments, programming interfaces like Blue Cove and kSOAP, despite being still under development, are mature enough to be used as the underlying technologies for Web services invocation over Bluetooth in a real world application

The number of online commercial transactions involving small amount of money is more and more increasing. For these transactions, different payment mechanisms from traditional ones are needed in order to reduce the overall costs. To answer to the growing demand for micropayment technologies, several commercial companies have recently started offering micropayment services, which offer reduced costs per transactions. In this work we present the design and the implementation of a micropayment system relying on Web service technology to conclude commercial transactions. The proposed system enables clients to access the restricted resources offered by the merchants and to pay for the received service by invoking the Web services exposed by a Payment Service Provider, acting like an online bank.

We study the problem of assigning unsplittable traffic to a set of m links so to minimize the maximum link congestion (i.e., the makespan). We consider the case of selfish agents owning pieces of the traffic. In particular, we introduce a variant of the model by Koutsopias and Papadimitriou [1999] in which owners of the traffic cannot directly choose which link to use; instead, the assignment is performed by a scheduler. The agents can manipulate the scheduler by reporting falseinformation regarding the size of each piece of unsplittable traffic.We provide upper and ower bounds on the approximation achievable by mechanisms that induce a Nash equilibrium when all agents report their true values.For the case of each agent owning one job, our positive results for m identical links show the effectiveness of introducing such a scheduler since, in this case, (1+ε)-approximate solutions are guaranteed in polynomial time. In contrast, the result by Koutsopias and Papadimitriou [1999] shows that, without payments and allowing selfish routing, Nash equilibria yield (in the worst case) Ω(log m over log log m)-approximate solutions, even for unitary weighted traffic. When links have different speeds we prove lower and upper bounds on the approximation achievable by a mechanism inducing a Nash equilibrium.Similar approximability results for identical machines have been achieved by Feldman et al. [2003]. However these results do not hold in our setting because their model assumes that the algorithm is provided with the correct traffic weights. For the case of agents owning more than one job, we give mechanisms that achieve constant approximation and prove lower bounds on the approximation ratio that can be achieved by a mechanism.

In this paper, we study efficient strategies for mapping onto parallel memory systems complete trees that are accessed by fixed templates (like complete subtrees, paths, or any combinations their of). These mappings are evaluated with respect to the following criteria: (1) the largest number of data items that can be accessed in parallel without memory conflicts; (2) the number of memory conflicts that can occur when accessing templates of size equal to the number of available memory modules, thereby exploiting the full parallelism of the system; (3) the complexity of the memory addressing scheme, i.e., the cost of retrieving the module where a given data item is mapped. We show that there exist trade-offs between these three criteria and the performance of different mapping strategies depends on the emphasis given on each of these criteria. More specifically, we describe an algorithm for mapping complete binary trees of height H onto M memory modules and prove that it achieves the following performance results: (1) conflict-free access to complete subtrees of size K and paths of size N such that N + K - [log K] /spl les/ M; (2) at most 1 conflict in accessing complete subtrees and paths of size M; (3) O(K/M + c) conflicts when accessing a composite template of K nodes consisting of c disjoint subsets, each subset being a complete subtree, or a path or a set of consecutive nodes in a level of the tree.

In this paper we study strategies for mapping complete tree data structures, that are accessed by fixed templates, onto parallel memory systems. These mappings are evaluated with respect to the following three different criteria: (i) the number of memory conflicts that can occur in a parallel access to the data structure; (ii) the largest number of elements that can be accessed in parallel without memory conflicts; (iii) the complexity of the memory addressing scheme. We show that there exist trade-offs between these criteria. We describe an algorithm COLOR for mapping complete trees onto EA memory modules and prove that it achieves the following performance: (i) conflict-free access to complete subtrees of size K and paths of size N, for M/spl ges/N+K-[log K]; (ii) at most 1 conflict when accessing complete subtrees and paths of size M; (iii) O((K/M)+c) conflicts when accessing a composite template of K nodes consisting of c disjoint subsets, each being a complete subtree, a path or a set of consecutive nodes in a level of the tree.

In this paper we consider the Supercube, a new interconnection network derived from the hypercube. The Supercube, introduced by A. Sen (1989), has the same diameter and connectivity as a Hypercube but can be realized for any number of nodes, not only powers of 2. We study the Supercube's ability to execute parallel programs, using graph-embedding techniques. We show that complete binary trees and bidimensional meshes (with a side length power of 2) are spanning subgraphs of the Supercube. We then prove that the Supercube is Hamiltonian and, when the number of nodes is not a power of 2, it contains all cycles of length greater than 3 as subgraphs.>