Stackelberg Strategies and Collusion in Network Games with Splittable Flow

We study the impact of collusion in network games with splittable flow and focus on the well established price of anarchy as a measure of this impact. We first investigate symmetric load balancing games and show that the price of anarchy is at most m, where m denotes the number of coalitions. For general networks, we present an instance showing that the price of anarchy is unbounded, even in the case of two coalitions. If latencies are restricted to polynomials with nonnegative coefficients and bounded degree, we prove upper bounds on the price of anarchy for general networks, which improve upon the current best ones except for affine latencies.     

Efficiency of Atomic Splittable Selfish Routing with Polynomial Cost Functions

Previous works on the inefficiency of selfish routing have focused on the Wardropian traffic equilibria with an infinite number of infinitesimal players, each controlling a negligible fraction of the overall traffic, but only very limited pseudo-approximation results have been obtained for the atomic selfish routing game with a finite number of players. In this note we examine the price of anarchy of selfish routing with atomic Cournot–Nash players, each controlling a strictly positive splittable amount of flow. We obtain an upper bound of the inefficiency of equilibria with polynomial cost functions, and show that the bound is 1 or there is no efficiency loss when there is only one player, and the bound reduces to the result established in the literature when there are an infinite number of infinitesimal players.     

Weakly-Acyclic (Internet) Routing Games

Weakly-acyclic games—a superclass of potential games—capture distributed environments where simple, globally-asynchronous interactions between strategic agents are guaranteed to converge to an equilibrium. We explore the class of routing games introduced in Fabrikant and Papadimitriou (The Complexity of Game Dynamics: BGP Oscillations, Sink Equilibria, and Beyond, pp. 844–853, 2008) and in Levin et al. (Interdomain Routing and Games, pp. 57–66, 2008), which models important aspects of routing on the Internet. We show that, in interesting contexts, such routing games are weakly acyclic and, moreover, that pure Nash equilibria in such games can be found in a computationally efficient manner.     

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.     

一种支持SIMD指令的流水化可拆分乘加器结构

乘加器是媒体数字信号处理器的关键运算部件。该文结合32位数字信号处理器芯片MD32开发（“863”计划）实践，提出了一种流水化可拆分的乘加器硬件实现结构，通过对乘法操作的流水处理实现了200MHz工作频率下的单周期吞吐量指标，通过构造可拆分的数据通道实现了对SIMD乘法指令的支持，支持4个通道16位媒体数据的并行乘法，大大提升了处理器的媒体处理性能。文中对所提出的乘加器体系结构，给出了理论依据和实验结果，通过MD32的流片实现得到了物理验证。     

Approximation Schemes for Packing Splittable Items with Cardinality Constraints

We continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of n items must be packed into as few bins as possible. Items may be split, but each bin may contain at most?k (parts of) items, where k is some given parameter. Complicating the problem further is the fact that items may be larger than?1, which is the size of a bin. The problem is known to be strongly NP-hard for any fixed value of?k. We essentially close this problem by providing an efficient polynomial-time approximation scheme (EPTAS) for most of its versions. Namely, we present an efficient polynomial time approximation scheme for k=o(n). A?PTAS for k=Θ(n) does not exist unless P = NP. Additionally, we present dual approximation schemes for k=2 and for constant values of?k. Thus we show that for any ε>0, it is possible to pack the items into the optimal number of bins in polynomial time, if the algorithm may use bins of size 1+ε.     

On Multifold MDS and Perfect Codes That Are Not Splittable into Onefold Codes

The union of disjoint MDS (or perfect) codes with distance 2 (respectively, 3) is always an -fold MDS (perfect) code. The converse is shown to be incorrect. Moreover, if k is a multiple of 4 and n + 1 16 is a power of two, then a k/2-fold k-ary MDS code of length m 3 and an (n + 1)/8-fold perfect code of length n exist from which no MDS (perfect) code can be isolated.     

Collusion set detection using graph clustering

Many mal-practices in stock market trading—e.g., circular trading and price manipulation—use the modus operandi of collusion. Informally, a set of traders is a candidate collusion set when they have “heavy trading” among themselves, as compared to their trading with others. We formalize the problem of detection of collusion sets, if any, in the given trading database. We show that naïve approaches are inefficient for real-life situations. We adapt and apply two well-known graph clustering algorithms for this problem. We also propose a new graph clustering algorithm, specifically tailored for detecting collusion sets. A novel feature of our approach is the use of Dempster–Schafer theory of evidence to combine the candidate collusion sets detected by individual algorithms. Treating individual experiments as evidence, this approach allows us to quantify the confidence (or belief) in the candidate collusion sets. We present detailed simulation experiments to demonstrate effectiveness of the proposed algorithms.     

A Collusion Problem and Its Solution

Consider a group of colluders, each with certain knowledge such as the identity of some other colluders, some cryptographic keys, and some data, possibly multiply encrypted. Two colluders can combine their knowledge if their current knowledge satisfies certain conditions. Their cryptographic keys can help decrypt each other's encrypted data, expanding their knowledge and revealing more collusion opportunities, and the process of collusion continues. The question we address is whether it is possible for the colluders to uncover a target set of unencrypted data. In this paper we formulate the collusion problem and provide an algorithm that determines whether a collusion problem has a solution and, if so, computes one. A solution is a specific way by which the colluders can uncover the hidden information. The solution generated by our algorithm is generally not one that involves the minimum number of colluders. We show, however, that to find such a solution is NP-complete. Complex communications protocols employing cryptographic building blocks are being developed to transfer information among some users and hide from others. The algorithm presented here can be applied to determine whether and how a subset of protocol users can discover during or after the protocol's execution the information that is to be hidden from them.     

抗共谋攻击的视频水印方案

关于版权保护优化问题,视频水印普遍存在不能抗共谋攻击的问题.针对嵌入强度和抵抗攻击能力的不足,在分析共谋攻击的数学模型的基础上,提出了一种利用镜头分割的视频水印方案.首先利用累加直方图对视频进行镜头分割,再以镜头为单位嵌入水印.嵌入水印时,依据视频的特征及其DCT系数的关系确定嵌入域,提取嵌入域的局部运动特征,并对特征进行全局统计收敛,得到特征系数作为水印嵌入强度,采用扩频方法嵌入水印.实验结果表明,水印方案能抵抗各类共谋攻击,可为版权保护提供有效的方法.     

自适应路由算法优于确定性路由算法

在研究并行计算机系统的容错时。自适应路由算法是一个极为重要的研究课题．它是在网络结点出错时,算法通过可选择的路径进行路由．在每个结点具有独立的出错概率的模型下,研究Mesh网络上自适应路由算法和确定性路算法的性能．本文提出的技术使得我们能严格地推导出路由算法的成功的概率,从而能分析和比较算法的性能．研究结果表明自适应路由算法具有明显的优势：一方面确定性路算法需要全局错误信息而变得高效性,另一方面自适应路由算法对于结点出错和网络规模具有更好的健壮性而具有更高的成功概率．     

Robust MC-CDMA-Based Fingerprinting Against Time-Varying Collusion Attacks

The design of robust fingerprinting systems for traitor tracing against time-varying collusion attacks in protecting continuous media, such as audio and video, is investigated in this research. We first show that it can be formulated as a multiuser detection problem in a wireless communication system with a time-varying channel response. Being inspired by the multicarrier code-division multiaccess technique, we propose a fingerprinting system that consists of three modules: 1) codeword generation with a multicarrier approach, 2) colluder weight estimation (CWE), and 3) advanced message symbol detection. We construct embedding codes with code spreading followed by multicarrier modulation. For CWE, we show that the weight estimation is analogous to channel response estimation, which can be solved by inserting pilot signals in the embedded fingerprint. As to advanced message symbol detection, we replace the traditional correlation-based detector with the maximal ratio combining detector and the parallel interference cancellation multiuser detector. The superior performance of the proposed fingerprinting system in terms of number of users/identified colluders and the bit-error probability of symbol detection is demonstrated by representative audio and video examples.      

基于路由长度的多径路由协议

针对单径路由协议在高速Ad hoc网络中平均端到端时延和丢包率高的问题,在动态源路由协议的基础上,提出基于邻居节点变化率与路由长度的多径路由协议DSR_HD。利用HELLO消息获得一跳范围内可用邻居数,根据邻居数求得节点的邻居节点变化率。在路由发现过程中,采用路由距离与路由跳数相结合的方法计算路由长度,并选择邻居节点变化率和路由长度低的节点加入路由,从而提高路由的稳定性。仿真实验结果显示,DSR_HD协议可以有效减少数据分组传输的端到端时延及路由开销,提高分组成功投递率。     

游戏

在移动世界大会上,Rovio品牌大使Peter Vesterbacka透露了Rovio未来5年的发展方向。在以F2P为主的移动游戏市场,他们将仿效米老鼠和Kitty猫的品牌策略。     

Reliable Routing in Wireless Ad Hoc Networks: The Virtual Routing Protocol

A novel routing protocol for wireless, mobile ad hoc networks is presented. This protocol incorporates features that enhance routing reliability, defined as the ability to provide almost 100% packet delivery rate. The protocol is based on a virtual structure, unrelated to the physical network topology, where mobile nodes are connected by virtual links and are responsible for keeping physical routes to their neighbors in the virtual structure. Routes between pairs of mobiles are set up by using information to translate virtual paths discovered in the virtual structure. Route discovery and maintenance phases of the protocol are based on unicast messages travelling across virtual paths, with sporadic use of flooding protocol. Most flooding is executed in the background using low priority messages. The routing protocol has been evaluated and compared with the Dynamic Source Routing protocol and with the Zone Routing Protocol by means of simulation.

一种采用按需路由策略的MPRN路由协议

提出了一种采用按需路由发现策略的移动分组无线网路由协议。协议采用按需路由发现过程,动态更新路由信息和建立路由转发组。数据包在转发组成员间进行有限泛洪,使协议能够降低对带宽的占用及减少可能的大量路由更新信息的传播。