1,721,059 research outputs found
On nash equilibria in non-cooperative all-optical networks
Full text linkWe consider the problem of determining a routing in all-optical networks, in which some couples of nodes want to communicate. In particular, we study this problem from the point of view of a network provider that has to design suitable payment functions for non-cooperative agents, corresponding to the couples of nodes wishing to communicate. The network provider aims at inducing stable routings (i.e., routings corresponding to Nash equilibria) using a low number of wavelengths. We consider three different kinds of local knowledge that agents may exploit to compute their payments, leading to three corresponding information levels. Under complete information, the network provider can design a payment function, inducing the agents to reach a Nash equilibrium mirroring any desired routing. If the price to an agent is computed only as a function of the wavelengths used along connecting paths (minimal level) or edges (intermediate level), the most reasonable functions either do not admit Nash equilibria or admit very inefficient ones, i.e., with the largest possible price of anarchy. However, by suitably restricting the network topology, a constant price of anarchy for chains and rings and a logarithmic one for trees can be obtained under the minimal and intermediate levels, respectively
An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks
No full textStable outcomes in modified fractional hedonic games
Full text linkIn coalition formation games self-organized coalitions are created as a result of the strategic interactions of independent agents. In this paper we assume that for each couple of agents (i, j), weight wi,j= wj,i reflects how much agents i and j benefit from belonging to the same coalition. We consider the (symmetric) modified fractional hedonic game, that is a coalition formation game in which agents’ utilities are such that the total benefit of agent i belonging to a coalition (given by the sum of wi,j over all other agents j belonging to the same coalition) is averaged over all the other members of that coalition, i.e., excluding herself. Modified fractional hedonic games constitute a class of succinctly representable hedonic games. We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0–1 weights. In particular, we completely characterize the existence of the considered stable outcomes and show many tight or asymptotically tight results on the performance of these natural stable outcomes for modified fractional hedonic games, also highlighting the differences with respect to the model of fractional hedonic games, in which the total benefit of an agent in a coalition is averaged over all members of that coalition, i.e., including herself
Pareto Approximations for the Bicriteria Scheduling Problem
No full textIn this paper, we consider the online bicriteria version of the classical Graham’s scheduling problem in which two cost measures must
be simultaneously minimized.
We present a parametric family of online algorithms Fm ={Ak|1<=k<=m}, such that, for each fixed integer k, Ak is
((2m−k)/(m−k+1),(m+k−1)/k)
-
competitive. Then we prove that, for m = 2 and 3, the tradeoffs on the competitive ratios realized by the algorithms in Fm correspond
to the Pareto curve, that is they are all and only the optimal ones, while for m>3 they give an r-approximation of the Pareto curve with
r = 5/4 for m = 4, r = 6/5
for m = 5, r = 1.186 for m = 6 and so forth, with r always less than 1.295. Unfortunately, for m>3, obtaining
Pareto curves is not trivial, as they would yield optimal algorithms for the single criterion case in correspondence of the extremal tradeoffs.
However, the situation seems more promising for the intermediate cases. In fact, we prove that for 5 processors the tradeoff
(7/3,7/3) of
A3 ∈ F5 is optimal.
Finally, we extend our results to the general d-dimensional case with corresponding applications to the Vector Scheduling problem
- …
