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 α.     

Examining the dimensionality of genuine multipartite entanglement

Entanglement in high-dimensional many-body systems plays an increasingly vital role in the foundations and applications of quantum physics. In the present paper, we introduce a theoretical concept which allows to categorize multipartite states by the number of degrees of freedom being entangled. In this regard, we derive computable and experimentally friendly criteria for arbitrary multipartite qudit systems that enable to examine in how many degrees of freedom a mixed state is genuine multipartite entangled.     

Privacy-enhanced architecture for smart metering

The recent deployment of smart grids promises to bring numerous advantages in terms of energy consumption reduction in both homes and businesses. A more transparent and instantaneous measurement of electricity consumption through smart meters utilization leads to an enhancement in the ability of monitoring, controlling and predicting energy usage. Nevertheless, it also has associated drawbacks related to the privacy of customers, since such management might reveal their personal habits, which electrical appliances they are using at each moment, whether they are at home or not, etc. In this work, we present a privacy-enhanced architecture for smart metering aimed at tackling this threat by means of encrypting individual measurements while allowing the electricity supplier to access the aggregation of the corresponding decrypted values.     

Figure-ground separation by cue integration

This letter presents an improved cue integration approach to reliably separate coherent moving objects from their background scene in video sequences. The proposed method uses a probabilistic framework to unify bottom-up and top-down cues in a parallel, "democratic" fashion. The algorithm makes use of a modified Bayes rule where each pixel's posterior probabilities of figure or ground layer assignment are derived from likelihood models of three bottom-up cues and a prior model provided by a top-down cue. Each cue is treated as independent evidence for figure-ground separation. They compete with and complement each other dynamically by adjusting relative weights from frame to frame according to cue quality measured against the overall integration. At the same time, the likelihood or prior models of individual cues adapt toward the integrated result. These mechanisms enable the system to organize under the influence of visual scene structure without manual intervention. A novel contribution here is the incorporation of a top-down cue. It improves the system's robustness and accuracy and helps handle difficult and ambiguous situations, such as abrupt lighting changes or occlusion among multiple objects. Results on various video sequences are demonstrated and discussed. (Video demos are available at http://organic.usc.edu:8376/ approximately tangx/neco/index.html .).     

Rapid convergence to feature layer correspondences

We describe a neural network able to rapidly establish correspondence between neural feature layers. Each of the network's two layers consists of interconnected cortical columns, and each column consists of inhibitorily coupled subpopulations of excitatory neurons. The dynamics of the system builds on a dynamic model of a single column, which is consistent with recent experimental findings. The network realizes dynamic links between its layers with the help of specialized columns that evaluate similarities between the activity distributions of local feature cell populations, are subject to a topology constraint, and can gate the transfer of feature information between the neural layers. The system can robustly be applied to natural images, and correspondences are found in time intervals estimated to be smaller than 100 ms in physiological terms.     

METIS-II: low resource machine translation

METIS-II was an EU-FET MT project running from October 2004 to September 2007, which aimed at translating free text input without resorting to parallel corpora. The idea was to use “basic” linguistic tools and representations and to link them with patterns and statistics from the monolingual target-language corpus. The METIS-II project has four partners, translating from their “home” languages Greek, Dutch, German, and Spanish into English. The paper outlines the basic ideas of the project, their implementation, the resources used, and the results obtained. It also gives examples of how METIS-II has continued beyond its lifetime and the original scope of the project. On the basis of the results and experiences obtained, we believe that the approach is promising and offers the potential for development in various directions.     

Capillary-driven pumping for passive degassing and fuel supply in direct methanol fuel cells

In this paper we present a new concept of creating and using capillary pressure gradients for passive degassing and passive methanol supply in direct methanol fuel cells (DMFCs). An anode flow field consisting of parallel tapered channels structures is applied to achieve the passive supply mechanism. The flow is propelled by the surface forces of deformed CO₂ bubbles, generated as a reaction product during DMFC operation. This work focuses on studying the influence of channel geometry and surface properties on the capillary-induced liquid flow rates at various bubbly gas flow rates. Besides the aspect ratios and opening angles of the tapered channels, the static contact angle as well as the effect of contact angle hysteresis has been identified to significantly influence the liquid flow rates induced by capillary forces at the bubble menisci. Applying the novel concept, we show that the liquid flow rates are up to thirteen times higher than the methanol oxidation reaction on the anode requires. Experimental results are presented that demonstrate the continuous passive operation of a DMFC for more than 15 h.     

Quality management in service ecosystems

Service-oriented architectures and Web services mature and have become more widely accepted and used by industry. This growing adoption increased the demands for new ways of using Web service technology. Users start re-combining and mediating other providers’ services in ways that have not been anticipated by their original provider. Within organisations and cross-organisational communities, discoverable services are organised in repositories providing convenient access to adaptable end-to-end business processes. This idea is captured in the term Service Ecosystem. This paper addresses the question of how quality management can be performed in such service ecosystems. Service quality management is a key challenge when services are composed of a dynamic set of heterogeneous sub-services from different service providers. This paper contributes to this important area by developing a reference model of quality management in service ecosystems. We illustrate the application of the reference model in an exploratory case study. With this case study, we show how the reference model helps to derive requirements for the implementation and support of quality management in an exemplary service ecosystem in public administration.