Artículos con la etiqueta ‘Computer Science and Game Theory (cs.GT)’

Inequity aversion and the evolution of cooperation

Por • 26 feb, 2014 • Category: sociologia

Evolution of cooperation is a widely studied problem in biology, social science, economics, and artificial intelligence. Most of the existing approaches that explain cooperation rely on some notion of direct or indirect reciprocity. These reciprocity based models assume agents recognize their partner and know their previous interactions, which requires advanced cognitive abilities. In this paper we are interested in developing a model that produces cooperation without requiring any explicit memory of previous game plays. Our model is based on the notion of, a concept introduced within behavioral economics, whereby individuals care about payoff equality in outcomes.



How to Gamble Against All Odds

Por • 21 nov, 2013 • Category: Ambiente

We compare the prediction power of betting strategies (aka martingales) whose wagers take values in different sets of reals. A martingale whose wagers take values in a set A is called an A -martingale. A set of reals B anticipates a set A , if for every A -martingale there is a countable set of B -martingales, such that on every binary sequence on which the A -martingale gains an infinite amount at least one of the B -martingales gains an infinite amount, too. We show that for a wide class of pairs of sets A and B , B anticipates A if and only if A is a subset of the closure of rB , for some r>0 , e.g., when B is well ordered (has no left-accumulation points). Our results answer a question posed by Chalcraft et al. (2012).



Power indices of influence games and new centrality measures for social networks

Por • 4 jul, 2013 • Category: sociologia

Influence games provide tools to measure the importance of the actors of a social network by means of classic power indices and provide a framework to consider new centrality criteria. In this paper we consider two of the most classical power indices, i.e., Banzhaf and Shapley-Shubik indices, as centrality measures for social networks in influence games. Although there is some work related to specific scenarios of game-theoretic networks, here we use such indices as centrality measures in any social network where the spread of influence phenomenon can be applied. Further, we define new centrality measures such as satisfaction and effort that, as far as we know, have not been considered so far. We also perform a comparison of the proposed measures with other three classic centrality measures, degree, closeness and betweenness, considering three social networks. We show that in some cases our measurements provide centrality hierarchies similar to those of other measures, while in other cases provide different hierarchies.



Selection and Influence in Cultural Dynamics

Por • 6 may, 2013 • Category: sociologia

One of the fundamental principles driving diversity or homogeneity in domains such as cultural differentiation, political affiliation, and product adoption is the tension between two forces: influence (the tendency of people to become similar to others they interact with) and selection (the tendency to be affected most by the behavior of others who are already similar). Influence tends to promote homogeneity within a society, while selection frequently causes fragmentation. When both forces are in effect simultaneously, it becomes an interesting question to analyze which societal outcomes should be expected.



How hard is it to control an election by breaking ties?

Por • 29 abr, 2013 • Category: sociologia

We study the computational complexity of the problem of controlling the result of an election by breaking ties. When the chair is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round elections like STV, we prove that it can be NP-hard for the chair to compute how to break ties to ensure a given result. Our results contain several surprises. For example, whilst it is NP-hard to compute a manipulating vote for a multi-round rule like Nanson, it is polynomial for the chair to control the result by breaking ties. As a second example, it can be NP-hard to control an election by breaking ties even with a simple two-stage voting rule.



Paradoxes in Social Networks with Multiple Products

Por • 4 feb, 2013 • Category: Opinion

Recently, we introduced in arXiv:1105.2434 a model for product adoption in social networks with multiple products, where the agents, influenced by their neighbours, can adopt one out of several alternatives. We identify and analyze here four types of paradoxes that can arise in these networks. To this end, we use social network games that we recently introduced in arXiv:1211.5938. These paradoxes shed light on possible inefficiencies arising when one modifies the sets of products available to the agents forming a social network. One of the paradoxes corresponds to the well-known Braess paradox in congestion games and shows that by adding more choices to a node, the network may end up in a situation that is (weakly) worse for everybody.



A Game-Theoretic Model Motivated by the DARPA Network Challenge

Por • 12 may, 2012 • Category: sociologia

In this paper we propose a game-theoretic model to analyze events similar to the 2009 \emph{DARPA Network Challenge}, which was organized by the Defense Advanced Research Projects Agency (DARPA) for exploring the roles that the Internet and social networks play in incentivizing wide-area collaborations. The challenge was to form a group that would be the first to find the locations of ten moored weather balloons across the United States. We consider a model in which $N$ people are located in the space with a fixed coverage volume around each person’s geographical location, and these people can join together to form groups. A balloon is placed in the space and a group wins if it is the first one to report the location of the balloon. A larger team has a higher probability of finding the balloon, but the prize money is divided equally among the team members and hence there is a competing tension to keep teams as small as possible. We analyze this model under a natural set of utilities, and under the assumption that the players are \emph{risk averse}.