The Price of Anarchy in Network Creation Games Is (Mostly) Constant

We study the price of anarchy and the structure of equilibria in network creation games. A network creation game is played by n players {1,2,…,n}, each identified with a vertex of a graph (network), where the strategy of player i, i=1,…,n, is to build some edges adjacent to i. The cost of building an edge is α>0, a fixed parameter of the game. The goal of every player is to minimize its creation cost plus its usage cost. The creation cost of player i is α times the number of built edges. In the SumGame variant, the usage cost of player i is the sum of distances from i to every node of the resulting graph. In the MaxGame variant, the usage cost is the eccentricity of i in the resulting graph of the game. In this paper we improve previously known bounds on the price of anarchy of the game (of both variants) for various ranges of α, and give new insights into the structure of equilibria for various values of α. The two main results of the paper show that for α>273?n all equilibria in SumGame are trees and thus the price of anarchy is constant, and that for α>129 all equilibria in MaxGame are trees and the price of anarchy is constant. For SumGame this answers (almost completely) one of the fundamental open problems in the field—is price of anarchy of the network creation game constant for all values of α?—in an affirmative way, up to a tiny range of α.     

Braess’s Paradox for Flows over Time

We study the properties of Braess’s paradox in the context of the model of congestion games with flow over time introduced by Koch and Skutella. We compare them to the well known properties of Braess’s paradox for Wardrop’s model of games with static flows. We show that there are networks which do not admit Braess’s paradox in Wardrop’s model, but which admit it in the model with flow over time. Moreover, there is a topology that admits a much more severe Braess’s ratio for this model. Further, despite its symmetry for games with static flow, we show that Braess’s paradox is not symmetric for flows over time. We illustrate that there are network topologies which exhibit Braess’s paradox, but for which the transpose does not. Finally, we conjecture a necessary and sufficient condition of existence of Braess’s paradox in a network, and prove the condition of existence of the paradox either in the network or in its transpose.     

Tensor Clustering for Rendering Many‐Light Animations

Rendering animations of scenes with deformable objects, camera motion, and complex illumination, including indirect lighting and arbitrary shading, is a long‐standing challenge. Prior work has shown that complex lighting can be accurately approximated by a large collection of point lights. In this formulation, rendering of animation sequences becomes the problem of efficiently shading many surface samples from many lights across several frames. This paper presents a tensor formulation of the animated many‐light problem, where each element of the tensor expresses the contribution of one light to one pixel in one frame. We sparsely sample rows and columns of the tensor, and introduce a clustering algorithm to select a small number of representative lights to efficiently approximate the animation. Our algorithm achieves efficiency by reusing representatives across frames, while minimizing temporal flicker. We demonstrate our algorithm in a variety of scenes that include deformable objects, complex illumination and arbitrary shading and show that a surprisingly small number of representative lights is sufficient for high quality rendering. We believe out algorithm will find practical use in applications that require fast previews of complex animation.     

An integral system‐ergonomic approach for IT‐based process management in complex work environments by example of manufacturing and health care

Recent trends in manufacturing and health care move these two work systems closer together from a system ergonomics point of view. Individual treatment of products, especially patients, by specialists in a distributed environment demand information technology (IT)‐based support suitable for complex systems. IT‐based support of processes in complex systems is difficult due to the lack of standard processes. IT support also means to rethink processes to use efficiency potentials. Close cooperation of users and software developers is needed to increase the ergonomic quality of the system. Therefore, suitable tools are needed: UML is available as the standard industry modeling language, Zope/Plone as the quasi‐standard for content management systems, SimPy as an object‐oriented simulation tool for event‐triggered processes, and ACT‐R as a powerful cognitive architecture for simulation of human information processes. The integration of these tools enables system‐ergonomic support of processes in the complex work system as well as of the development and deployment process. It is the base of an integral system‐ergonomic approach for IT‐based process management. Knowledge gained during process analysis either enters models or leads to the extension and adaptation of the tool chain. The models serve as basis for discussion among system ergonomists, programmers, and specialists from the work system. Further, they are understood by simulation and process support tools. Transcoding efforts between humans with different professional backgrounds and machines are reduced, and the flexibility demanded by complex systems is met. © 2008 Wiley Periodicals, Inc.     

A case study comparing defect profiles of a reused framework and of applications reusing it

The benefits of software reuse have been studied for many years. Several previous studies have observed that reused software has a lower defect density than newly built software. However, few studies have investigated empirically the reasons for this phenomenon. To date, we have only the common sense observation that as software is reused over time, the fixed defects will accumulate and will result in high-quality software. This paper reports on an industrial case study in a large Norwegian Oil and Gas company, involving a reused Java class framework and two applications that use that framework. We analyzed all trouble reports from the use of the framework and the applications according to the Orthogonal Defect Classification (ODC), followed by a qualitative Root Cause Analysis (RCA). The results reveal that the framework has a much lower defect density in total than one application and a slightly higher defect density than the other. In addition, the defect densities of the most severe defects of the reused framework are similar to those of the applications that are reusing it. The results of the ODC and RCA analyses reveal that systematic reuse (i.e. clearly defined and stable requirements, better design, hesitance to change, and solid testing) lead to lower defect densities of the functional-type defects in the reused framework than in applications that are reusing it. However, the different “nature” of the framework and the applications (e.g. interaction with other software, number and complexity of business logic, and functionality of the software) may confound the causal relationship between systematic reuse and the lower defect density of the reused software. Using the results of the study as a basis, we present an improved overall cause–effect model between systematic reuse and lower defect density that will facilitate further studies and implementations of software reuse.

Attuning speech-enabled interfaces to user and context for inclusive design: technology, methodology and practice

This paper presents a methodology to apply speech technology for compensating sensory, motor, cognitive and affective usage difficulties. It distinguishes (1) an analysis of accessibility and technological issues for the identification of context-dependent user needs and corresponding opportunities to include speech in multimodal user interfaces, and (2) an iterative generate-and-test process to refine the interface prototype and its design rationale. Best practices show that such inclusion of speech technology, although still imperfect in itself, can enhance both the functional and affective information and communication technology-experiences of specific user groups, such as persons with reading difficulties, hearing-impaired, intellectually disabled, children and older adults.

Study on the electrical conductivity and morphology of porous polypyrrole layers prepared electrochemically in the presence of pyridinium chlorochromate

The electrical conductivity and morphology of thick (up to 3 mm) porous polypyrrole (PPy) layers produced electrochemically from pyrrole in acetonitrile (ACN) solutions have been studied. The electrical conductivity of pressed porous layers ranges from 1 to 10 Scm^–1, which is about one order of magnitude less than that in films which were prepared under similar conditions but without PnClCr. Analysis of the temperature dependence of conductivity has confirmed the major role of hopping in relation to tunnelling in charge transport inside the PPy layers even at lower temperatures. Scanning electron microscopy (SEM) showed a globular structure, which is different from the usual cauliflower-like structure of PPy films prepared without any oxidizing agent. Globular particles of about 1–3 m diameter have been found under a thin smooth crust on the electrode side of the sample. Globular particles form linked chain-like or larger round formations poorly filling the space. Closely packed fibrils of about 20 nm diameter and over 100 nm in length were found inside the aggregates.     

A variable-precision square root implementation for field programmable gate arrays

Applications requiring variable-precision arithmetic often rely on software implementations because custom hardware is either unavailable or too costly to build. By using the flexibility of the Xilinx XC4010 field programmable gate arrays, we present a hardware implementation of square root that is easily tailored to any desired precision. Our design consists of three types of modules: a control logic module, a data path module to extend the precision in 4-bit increments, and an interface module to span multiple chips. Our data path design avoids the common problem of large fan-out delay in the critical path. Cycle time is independent of precision, and operation latency can be independent of interchip communication delays.Notation S_j square root digit of weight 2^–j - S _j {–1, 0, 1} - S[j] computed square root value as of stepj - S _j ^s sign bit in the representation ofS _j in sign and magnitude form - S _j ^m magnitude bit in the representation ofS _j in sign and magnitude form - w[j] residual at stepj in two's complement carry-save representation - a sum vector in the carry-save representation of 2w[j] - b carry vector in the carry-save representation of 2w[j] - a _i bit of weight 2^–i in the sum vector,a - b_i bit of weight 2^–i in the carry vector,b - T[j]=–S[j – 1]s_j – s _j ² 2^–(j+1) T _i bit of weight 2^–i inT