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

A multiobjective approach based on artificial bee colony for the static routing and wavelength assignment problem

Nowadays, the most promising technology for designing optical networks is the wavelength division multiplexing. This technique divides the huge bandwidth of an optical fiber link into different wavelengths, providing different available channels per link. However, a problem comes up when it is necessary to interconnect a set of traffic demands. This problem is known as routing and wavelength assignment problem, and due to its complexity (NP-hard problem) it is very suitable for being solved using evolutionary computation. The selected heuristics is the artificial bee colony algorithm, an heuristics based on the behavior of honeybee foraging for nectar. Therefore, we have applied multiobjective optimization to solve the static routing and wavelength assignment problem, and adapted this algorithm to the multiobjective context. New results have been obtained that significantly improve those published in previous researches.     

Service oriented evolutionary algorithms

This work presents a service oriented architecture for evolutionary algorithms, and an implementation of this architecture using a specific technology (called OSGiLiath). Service oriented architecture is a computational paradigm where users interact using services to increase the integration between systems. The presented abstract architecture is formed by loosely coupled, highly configurable and language-independent services. As an example of an implementation of this architecture, a complete process development using a specific service oriented technology is explained. With this implementation, less effort than classical development in integration, distribution mechanisms and execution time management has been attained. In addition, steps, ideas, advantages and disadvantages, and guidelines to create service oriented evolutionary algorithms are presented. Using existing software, or from scratch, researchers can create services to increase the interoperability in this area.     

Design with shape grammars and reinforcement learning

Shape grammars are a powerful and appealing formalism for automatic shape generation in computer-based design systems. This paper presents a proposal complementing the generative power of shape grammars with reinforcement learning techniques. We use simple (naive) shape grammars capable of generating a large variety of different designs. In order to generate those designs that comply with given design requirements, the grammar is subject to a process of machine learning using reinforcement learning techniques. Based on this method, we have developed a system for architectural design, aimed at generating two-dimensional layout schemes of single-family housing units. Using relatively simple grammar rules, we learn to generate schemes that satisfy a set of requirements stated in a design guideline. Obtained results are presented and discussed.     

Elimination and accumulation of polycyclic aromatic hydrocarbons in urban stormwater wet detention ponds

The concentrations of polycyclic aromatic hydrocarbons (PAHS) in water and sediments of seven wet detention ponds receiving urban stormwater were investigated. The ponds comprised traditional wet detention ponds with a permanent wet volume and a storage volume as well as ponds that were expanded with sand filters and other means to improve the removal of micropollutants. The concentrations of sigmaPAH in the sediments varied between 6 +/- 5 and 2,222 +/- 603 ng g(-1) dry weight (mean +/- standard deviation), and were highest in the ponds with lower pond volume per catchment area and did not clearly reflect different activities in the catchments. In general, the concentrations of PAHS in the sediments decreased from inlet to outlet, especially in the systems with good conditions for sedimentation such as systems with flow perpendicular sand dikes and extensive submerged vegetation. High molecular weight PAHs were predominant in the sediments indicating the pyrogenic origin of the PAHS. There was no correlation between PAH species concentrations in water or sediments and their hydrophobicity (log K(ow)). PAH concentrations in water fluctuated in response to intensity and frequency of rain events, whereas concentrations in the sediments integrated the pollutant load over time. Pond systems expanded with sand filters and other technologies to enhance removal of micropollutants consistently had concentrations of PAHS in the effluents below the detection level.     

Effect of thermal alkaline pretreatment on the anaerobic digestion of wasted activated sludge

The effect of alkaline pretreatment of waste-activated sludge, using two models to study the sequential hydrolysis rates of suspended (Sanders' surface model) and dissolved (Goel's saturation model) solids, on the mesophilic and thermophilic anaerobic digestion rate is evaluated. The pretreatment, which reduces the size of the solids, increases the reaction rate by increasing the surface area and the specific surface hydrolysis constant (K(SBK)); at thermophilic conditions from 0.45 x 10(-3) kg m(-2) d(-1) for the fresh sludge to 0.74 x 10(-3) kg m(-2) d(-1) for the pretreated sludge and at mesophilic conditions these values are 0.28 x 10(-3) kg m(-2) d(-1) and 0.47 x 10(-3) kg m(-2) d(-1) confirming the usefulness of a pretreatment for solids reduction. But for soluble solids, the thermoalkaline pretreatment decreases the reaction rates by inducing a competitive inhibition on the thermophilic anaerobic digestion rate while in the mesophilic range, a non-competitive inhibition is observed. A mathematical simulation of the consecutive reactions, suspended solids to dissolved solids and to methane in staged anaerobic thermophilic-mesophilic digestion, shows that with 4% suspended solids concentration it is better not to use a thermoalkaline pretreatment because overall solids reduction and total methane production are not as good as without pretreatment.     

P distribution in different sediment fraction of a constructed wetland

The aim of this work was to study the accumulation and fractionation of P in the inlet and outlet sediment of a constructed wetland for the wastewater treatment of a metallurgic plant in Argentina. It was important to predict whether P could be released into the water again by changing environmental conditions or retained over time. P-fractionation was performed using a sequential extraction method. Sediment cores were sliced at depths of: 0-3; 3-7 and 7-10 cm. Sediment showed high pH values and anoxic conditions. In the inlet area, P was principally bound to the carbonate fraction, whereas in the outlet area, it was mainly bound in the residual fraction. This behavior was justified by the effluent composition, which is rich in Ca2+ and Fe3+ and presents high values of pH and conductivity. These conditions favor CaCO3 and Fe(OOH)n precipitation and the subsequent sorption of P to their surface. The sediment active layer involved in the exchange reactions was the superficial one (0-3 cm). The wetland is highly efficient in P retention. P was retained by sediment in fractions that will not release it to the water while chemical and environmental conditions of the system are maintained.     

Influence of hydraulic retention time on UASB post-treatment with UF membranes

A pilot UASB reactor coupled with an external ultrafiltration (UF) membrane was operated under three different hydraulic retention times (HRT) for domestic wastewater treatment. The aim was to assess the HRT influence on system performance and fouling. The highest concentrations of COD, total solids, extracellular polymeric substances (EPS) and soluble microbial products (SMP) in UASB effluent and permeate were found when the UASB reactor was operated under the lowest HRT studied (4 hours); although the fulfillment of Mexican Standard for wastewater reclamation was not compromised. This fact could be attributed to the higher shear stress forces inside the UASB reactor when it was operated at low HRT, which promoted the release of biopolymeric substances in its effluent. Besides, the fouling propensity in the UASB effluent was worsened with HRT reduction, by increasing the fouling rate and the specific cake resistance. Based on these results, it is recommended to avoid operating the UASB reactor at low HRTs (less than 4 hours) in order to control SMP and EPS fouling potential. The results presented also suggest that HRT reduction has a detrimental effect on performance and fouling.     

Mechanical resistance properties of gravel used in subsurface flow constructed wetlands: implications for clogging

Gravel constitutes the filter medium in subsurface flow constructed wetlands (SSF CWs) and its porosity and hydraulic conductivity decrease over time (clogging), limiting the lifespan of the systems. Using gravel of poor quality accelerates clogging in wetlands. In this study, gravel samples from six different wetland systems were compared with regards to their mineral composition and mechanical resistance properties. Results showed that both mineralogy and texture are related to mechanical resistance. Accordingly, gravel with high content of quartz (> 80%) showed a lower percentage of broken particles (0.18-1.03%) than those with lower content of quartz (2.42-4.56% media broken). Although granite is formed by high durability minerals, its non-uniform texture results in a lower resistance to abrasion (ca. 10% less resistance than calcareous gravel). Therefore, it is recommended to use gravels composed mainly of quartz or, when it is not available, limestone gravels (rounded and uniform) are recommended instead. The resistance to abrasion (LAA test) seems to be a good indicator to determine the mechanical properties of gravels used in CWs. It is recommended to use gravels with LAA below 30% in order to avoid a rapid clogging due to gravel crumbling and subsequent mineral solids accumulation.     

Estimating the Economic Value of Landscape Losses Due to Flooding by Hydropower Plants in the Chilean Patagonia

This paper presents a contingent valuation study concerning landscape impacts generated by the construction of one dam (Baker 1) of the HIDROAYSEN hydropower project located in the Chilean Patagonia. A survey was used to collect information about citizens’ opinions towards the hydropower project in four major cities in Chile. Specifically, a One-and-One-Half-Bound (OOHB) willingness to pay eliciting format was applied to capture citizens’ WTP. The economic loss, associated to the landscape impacts for people living in urban areas of the country, is found to be approximately US$ 205 million, which is nearly 28% of the total investment. Our results also show that the cities’ distance from the dam affects citizens’ willingness to pay.