Graphical Congestion Games

We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem.     

Stackelberg Strategies for Atomic Congestion Games

We investigate the effectiveness of Stackelberg strategies for atomic congestion games with unsplittable demands. In our setting, only a fraction of the players are selfish, while the rest are willing to follow a predetermined strategy. A Stackelberg strategy assigns the coordinated players to appropriately selected strategies trying to minimize the performance degradation due to the selfish players. We consider two orthogonal cases, namely congestion games with affine latency functions and arbitrary strategies, and congestion games on parallel links with arbitrary non-decreasing latency functions. We restrict our attention to pure Nash equilibria and derive strong upper and lower bounds on the pure Price of Anarchy (PoA) under different Stackelberg strategies.     

Selfish Load Balancing and Atomic Congestion Games

We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server from a permissible set. Each client has a unit-length job and selfishly wants to minimize its own latency (job completion time). A server's latency is inversely proportional to its speed, but it grows linearly with (or, more generally, as the pth power of) the number of clients matched to it. This interaction is naturally modeled as an atomic congestion game, which we call selfish load balancing. We analyze the Nash equilibria of this game and prove nearly tight bounds on the price of anarchy (worst-case ratio between a Nash solution and the social optimum). In particular, for linear latency functions, we show that if the server speeds are relatively bounded and the number of clients is large compared with the number of servers, then every Nash assignment approaches social optimum. Without any assumptions on the number of clients, servers, and server speeds, the price of anarchy is at most 2.5. If all servers have the same speed, then the price of anarchy further improves to We also exhibit a lower bound of 2.01. Our proof techniques can also be adapted for the coordinated load balancing problem under L₂ norm, where it slightly improves the best previously known upper bound on the competitive ratio of a simple greedy scheme.     

ACK报文拥塞对网络性能影响的研究

为了提高网络性能和安全、设计更有效地队列拥塞控制算法,通过研究现有的一些主动队列拥塞控制算法发现:大多数的拥塞控制算法的实现是基于队列长度或平均队列长度,这使得算法在提高网络整体性能上具有局限性。本文在现有的网络队列拥塞控制算法的基础上,将ACK信息确认报文传输状态引入到队列拥塞控制算法研究的系统中,通过仿真实验发现:ACK数据报文的传输状态在很大程度上影响着网络的吞吐量、数据包的传输延迟等。     

Handling Communication Restrictions and Team Formation in Congestion Games

There are many domains in which a multi-agent system needs to maximize a “system utility” function which rates the performance of the entire system, while subject to communication restrictions among the agents. Such communication restrictions make it difficult for agents that take actions to optimize their own “private” utilities to also help optimize the system utility. In this article we show how previously introduced utilities that promote coordination among agents can be modified to be effective in domains with communication restrictions. The modified utilities provide performance improvements of up to 75 over previously used utilities in congestion games (i.e., games where the system utility depends solely on the number of agents choosing a particular action). In addition, we show that in the presence of severe communication restrictions, team formation for the purpose of information sharing among agents leads to an additional 25 improvement in system utility. Finally, we show that agents’ private utilities and team sizes can be manipulated to form the best compromise between how “aligned” an agent’s utility is with the system utility and how easily an agent can learn that utility.     

A System for Weighted Max-Min Congestion Control in MPLS Networks

This paper introduces a framework to support explicit rate congestion control for best-effort service in MPLS networks. We devise the two basic mechanisms required, namely, a signaling component to convey explicit-rate congestion control information and associated algorithm for calculating explicit fair rates. The proposed signaling component uses Resource Reservation Protocol (RSVP) in a novel way to convey explicit rate congestion control information. An algorithm to calculate Weight Proportional Max-Min (WPMM) fair rates appropriate for MPLS networks is introduced. Simulations are presented that show the effectiveness of the RSVP explicit rate signaling method when combined with the proposed max-min fair rate algorithm.     

Self-Fulfilling Signal of an Endogenous State in Network Congestion Games

We consider the problem of coordination via signaling in network congestion games to improve social welfare deteriorated by incomplete information about traffic flow. Traditional studies on signaling, which focus on exogenous factors of congestion and ignore congestion externalities, fail to discuss the oscillations of traffic flow. To address this gap, we formulate a problem of designing a coordination signal on endogenous information about traffic flow and introduce a self-fulfilling characteristic of a signal that guarantees an outcome flow consistent with the signal itself without causing the unwanted oscillation. An instance of the self-fulfilling signal is shown in the case of a Gaussian signal distribution. In addition, we show simple numerical examples. The results reveal how a self-fulfilling signal suppresses the oscillation and simultaneously improves social welfare through improved network efficiency.     

大时延对拥塞控制系统性能的影响及补偿方法

针对大时延对计算机网络拥塞控制系统性能的影响,设计了一种基于Smith预估器的拥塞控制算法,并将其推广到多条链路的情况;该算法实现简单,适合计算机控制系统实现,在大时延网络中具有实际应用价值#仿真结果表明,该算法动态响应快,能够有效克服大时延对系统性能的不利影响,大大抑制了队列的不稳定振荡,提高了链路利用率。     

Serious Games: Broadening Games Impact Beyond Entertainment

Computer and videogames for many years has been an island of technology and design innovation largely left to itself as it morphed from a cottage business into a global media and software industry. While there have been pockets of derivative activity related to games and game technology only in the last half-dozen years has there been a real movement toward exploiting this industry in many new and exciting ways. Today the general use of games and game technologies for purposes beyond entertainment is collectively referred to as serious games. The Serious Games Initiative was formed in 2002 and since its inception has been among a number of critical efforts that has helped open up the world and many disciplines to the ideas and innovations that may be sourced from the commercial, independent, and academic game fields. This has been a person-by-person, project-by-project effort that not only has informed us about the potential of games but also in how you merge innovation and innovators from one discipline with those in another. In this talk we will explore the total gamut of the serious games field identifying past the obvious how games and game technologies are being applied to problems in a wide array of areas including healthcare, productivity, visualization, science, and of course training and education. Once a proper definition of serious games is established the talk will focus on the current state of the field as it relates to research and infrastructure issues that are needed to make the difference between seeing serious games take hold as a major new practice or having it devolve into another trend of the moment lost to history.     

社会道德风险在计算机网络中的影响

随着信息技术的发展,计算机网络在人们生活中的应用越来越广泛,但是随着计算机网络的逐渐普及和应用,社会道德风险逐渐体现出来.本文对于社会道德风险在计算机网络中的影响作了简要的分析.     

The Impact of Geographic Distance on Online Social Interactions

Online social networking services entice millions of users to spend hours every day interacting with each other. The focus of this work is to explain the effect that geographic distance has on online social interactions and, simultaneously, to understand the interplay between the social characteristics of friendship ties and their spatial properties. We analyze data from a large-scale online social network, Tuenti, with about 10 million active users: our sample includes user profiles, user home locations and online social interactions among Tuenti members. Our findings support the idea that spatial distance constraints whom users interact with, but not the intensity of their social interactions. Furthermore, friendship ties belonging to denser connected groups tend to arise at shorter spatial distances than social ties established between members belonging to different groups. Finally, we show that our findings mostly do not depend on the age of the users, although younger users seem to be slightly more constrained to shorter geographic distances. Augmenting social structure with geographic information adds a new dimension to social network analysis and a large number of theoretical investigations and practical applications can be pursued for online social systems, with many promising outcomes. As the amount of available location-based data is increasing, our findings and results open the door to future possibilities: researchers would benefit from these insights when studying online social services, while developers should be aware of these additional possibilities when building systems and applications related to online social platforms.     

基于加权LeaderRank的用户社交网络排序算法

针对加权LeaderRank算法存在的权值均分、主题漂移等问题,提出一种用户社交网络排序算法。结合GloVe模型、余弦相似度计算方法和牛顿冷却定律,通过引入链入链出因子、主题相关度因子和时间衰减度因子,改善加权LeaderRank算法的不足。实验结果表明,与加权LeaderRank算法相比,该算法的精确率、点击率和NDCG值分别提高7.80%、6.73%和4.75%,可有效提高排序质量。     

社交关系在基于模型社会化推荐系统中的影响

目前社会化推荐系统方面的研究主要集中于构建性能更优的基于模型的推荐算法,然而模型算法中分解得到的隐式特征和社交信息的变化会给推荐性能带来不确定性。为了消除不确定性,探究了在基于模型的社会化推荐系统中社交关系的变化对推荐性能的影响。实验首先按比例移除关系网络中的连边或节点,再对推荐质量进行评估,结果表明,社交关系的数量增多将对推荐质量带来明显提升,同时关系网络中心节点对推荐质量的影响巨大。因此,在构建基于模型的社会化推荐系统的过程中应尽可能多地获取社交关系,并提升中心节点的关系在推荐中的权重,降低非中心节点(潜在噪声)的影响。     

Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy

We investigate the effect of linear independence in the strategies of congestion games on the convergence time of best improvement sequences and on the pure Price of Anarchy. In particular, we consider symmetric congestion games on extension-parallel networks, an interesting class of networks with linearly independent paths, and establish two remarkable properties previously known only for parallel-link games. We show that for arbitrary (non-negative and non-decreasing) latency functions, any best improvement sequence reaches a pure Nash equilibrium in at most as many steps as the number of players, and that for latency functions in class $\mathcal{D}$ , the pure Price of Anarchy is at most $\rho(\mathcal{D})$ , i.e. it is bounded by the Price of Anarchy for non-atomic congestion games. As a by-product of our analysis, we obtain that for symmetric network congestion games with latency functions in class $\mathcal{D}$ , the Price of Stability is at most $\rho(\mathcal{D})$ .     

Cultural Entrepreneurship: The Impact of Social Networking on Success

Because of the complex structures characteristic of the arts sector and creative industries, it is often thought that external network ties of leading managers are critical to the success of their cultural enterprises. Based on research into entrepreneurship and promoters' activity, this study examines the influence of social network relationships on the success of cultural establishments in Germany. The regression analysis of data from 121 private arts and culture ventures presented here clearly shows that founders as well as managers can overcome numerous barriers through their engagement and activity in social networks, and thereby exercise to a significant degree a positive influence on establishing their enterprise. As expected, this effect is even stronger in cases of low sponsorship of cultural activities on the part of cities and communities. Contrary to expectations, the positive effect of intensive networking activities is not increased by a high intensity of competition; it is worth noting that the effect is strongest in situations of low competitive pressure. The results of this study demonstrate that successful networking expertise, as postulated by research into promoters' activity, is of great importance for overcoming significant barriers in the cultural sector, but that its effectiveness also has limits.     

The Impact of Interaction and Social Learning on Aggregate Expectations

We examine the effect of information sharing within small world networks. Agents receive a signal correlated with the state of the world (SoW) which is adjusted following discussions with neighbours. If one agent in the network, referred to as an expert, does not engage in social learning (that is they always follow their own signal) then all agents learn the SoW. It is found that volatility in the mean level of expectations varies with changes in the number of experts and the network structure. A trade-off emerges between the level of volatility and the speed at which agents learn of changes to the SoW. A second finding is that certain network structures lead to information cascades.      

Constrained Games: The Impact of the Attitude to Adversary's Constraints

We consider properties of constrained games, where the strategy set available to a player depends on the choice of strategies made by other players. We show that the utilities of each player associated with that player's own performance and constraints are not sufficient to model a constrained game and to define equilibria; for the latter, one also needs to model how a player values the fact that other players meet their constraints. We study three different approaches to other players' constraints, and show that they exhibit completely different equilibrium behaviors. Further, we study a general class of stochastic games with partial information, and focus on the case where the players are indifferent to whether the constraints of other players hold.