Author name cluster

Carme Àlvarez

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

TCS Journal 2024 Journal Article

The diameter of sum basic equilibria games

Aida Abiad
Carme Àlvarez
Arnau Messegué

We study the sum basic network creation game introduced in 2010 by Alon, Demaine, Hajiaghai and Leighton. In this game, an undirected and unweighted graph G is said to be a sum basic equilibrium if and only if, for every edge uv and any vertex v ′ in G, swapping edge uv with edge u v ′ does not decrease the total sum of the distances from u to all the other vertices. This concept lies at the heart of the network creation games, where the central problem is to understand the structure of the resulting equilibrium graphs, and in particular, how well they globally minimize the diameter. In this sense, in 2013 Alon et al. showed an upper bound of 2 O ( log ⁡ n ) on the diameter of sum basic equilibria, and they also proved that if a sum basic equilibrium graph is a tree, then it has diameter at most 2. In this paper, we prove that the upper bound of 2 also holds for bipartite graphs and even for some non-bipartite classes like block graphs and cactus graphs.

Details DOI

TCS Journal 2016 Journal Article

Celebrity games

Carme Àlvarez
Maria J. Blesa
Amalia Duch
Arnau Messegué
Maria Serna

We introduce Celebrity games, a new model of network creation games. In this model players have weights (W being the sum of all the player's weights) and there is a critical distance β as well as a link cost α. The cost incurred by a player depends on the cost of establishing links to other players and on the sum of the weights of those players that remain farther than the critical distance. Intuitively, the aim of any player is to be relatively close (at a distance less than β) from the rest of players, mainly of those having high weights. The main features of celebrity games are that: computing the best response of a player is NP-hard if β > 1 and polynomial time solvable otherwise; they always have a pure Nash equilibrium; the family of celebrity games having a connected Nash equilibrium is characterized (the so called star celebrity games) and bounds on the diameter of the resulting equilibrium graphs are given; a special case of star celebrity games shares its set of Nash equilibrium profiles with the MaxBD games with uniform bounded distance β introduced in Bilò et al. [6]. Moreover, we analyze the Price of Anarchy (PoA) and of Stability (PoS) of celebrity games and give several bounds. These are that: for non-star celebrity games PoA = PoS = m a x { 1, W / α }; for star celebrity games PoS = 1 and PoA = O ( m i n { n / β, W α } ) but if the Nash Equilibrium is a tree then the PoA is O ( 1 ); finally, when β = 1 the PoA is at most 2. The upper bounds on the PoA are complemented with some lower bounds for β = 2.

Details DOI

TCS Journal 2011 Journal Article

The robustness of stability under link and node failures

Carme Àlvarez
Maria Blesa
Maria Serna

In the area of communication systems, stability refers to the property of keeping the amount of traffic in the system always bounded over time. Different communication system models have been proposed in order to capture the unpredictable behavior of some users and applications. Among those proposed models the adversarial queueing theory (aqt) model turned out to be the most adequate to analyze an unpredictable network. Until now, most of the research done in this field did not consider the possibility of the adversary producing failures on the network structure. The adversarial models proposed in this work incorporate the possibility of dealing with node and link failures provoked by the adversary. Such failures produce temporal disruptions of the connectivity of the system and increase the collisions of packets in the intermediate hosts of the network, and thus the average traffic load. Under such a scenario, the network is required to be equipped with some mechanism for dealing with those collisions. In addition to proposing adversarial models for faulty systems we study the relation between the robustness of the stability of the system and the management of the queues affected by the failures. When the adversary produces link or node failures the queues associated to the corresponding links can be affected in many different ways depending on whether they can receive or serve packets, or rather that they cannot. In most of the cases, protocols and networks containing very simple topologies, which were known to be universally stable in the aqt model, turn out to be unstable under some of the newly proposed adversarial models. This shows that universal stability of networks is not a robust property in the presence of failures.

Details DOI

STOC Conference 2010 Conference Paper

The HOM problem is decidable

Guillem Godoy
Omer Giménez
Lander Ramos
Carme Àlvarez

We provide an algorithm that, given a tree homomorphism H and a regular tree language L represented by a tree automaton, determines whether H(L) is regular. This settles a question that has been open for a long time.

Details

TCS Journal 2008 Journal Article

High level communication functionalities for wireless sensor networks

Carme Àlvarez
Josep Díaz
Jordi Petit
José Rolim
Maria Serna

In this paper we show how to establish a reliable and efficient high level communication system in a randomly deployed network of sensors equipped with directional antennas. This high level communication system enables the programming of the sensor network using high level communication functionalities without the burden of taking care of their physical capacities (low range, unidirectional links, single frequency, presence of collisions, etc.). The high level communication functionalities we offer include point-to-point communication, point-to-area communication, and one-to-all communication. The basic idea to implement this system is to simulate a virtual network that emerges from the ad-hoc network using self-organization, self-discovery and collaborative methods. We also analyse the efficiency, scalability and robustness of the proposed protocols.

Details DOI

TCS Journal 2007 Journal Article

Communication tree problems

Carme Àlvarez
Rafel Cases
Josep Díaz
Jordi Petit
Maria Serna

In this paper, we deal with the problem of constructing optimal communication trees satisfying given communication requirements. We consider two constant degree tree communication models and several cost measures. First, we analyze whether a tree selected at random provides a good randomized approximation algorithm, and we show that such a construction fails for some of the measures. Secondly, we provide approximation algorithms for the case in which the communication requirements are given by a random graph in two different random models, namely the classical G n, p and random geometric graphs. Finally, we conclude with some open problems.

Details DOI

MFCS Conference 2005 Conference Paper

Pure Nash Equilibria in Games with a Large Number of Actions

Carme Àlvarez
Joaquim Gabarró
Maria J. Serna

Abstract We study the computational complexity of deciding the existence of a Pure Nash Equilibrium in multi-player strategic games. We address two fundamental questions: how can we represent a game? and how can we represent a game with polynomial pay-off functions? Our results show that the computational complexity of deciding the existence of a pure Nash equilibrium in a strategic game depends on two parameters: the number of players and the size of the sets of strategies. In particular we show that deciding the existence of a Nash equilibrium in a strategic game is NP -complete when the number of players is large and the number of strategies for each player is constant, while the problem is Σ \(^{p}_{\rm 2}\) -complete when the number of players is a constant and the size of the sets of strategies is exponential (with respect to the length of the strategies).

Details

MFCS Conference 2003 Conference Paper

Adversarial Models for Priority-Based Networks

Carme Àlvarez
Maria J. Blesa
Josep Díaz
Antonio Fernández 0001
Maria J. Serna

Abstract We propose several variations of the adversarial queueing model to cope with packets that can have different priorities, the priority and variable priority models, and link failures, the failure and reliable models. We address stability issues in the proposed adversarial models. We show that the set of universally stable networks in the adversarial model remains the same in the four introduced models. From the point of view of queueing policies we show that several queueing policies that are universally stable in the adversarial model remain so in the priority, failure and reliable models. However, we show that lis, a universally stable queueing policy in the adversarial model, is not universally stable in any of the other models, and that no greedy queueing policy is universally stable in the variable priority model. Finally we analyze the problem of deciding stability of a given network under a fixed protocol. We provide a characterization of the networks that are stable under fifo and lis in the failure model. This characterization allows us to show that deciding network stability under fifo and lis in the proposed models can be solved in polynomial time.

Details

TCS Journal 1995 Journal Article

On adaptive DLOGTIME and POLYLOGTIME reductions

Carme Àlvarez
Birgit Jenner

We investigate properties of the relativized AC and NC hierarchies in their DLOGTIME-, respectively, ALOGTIME-uniform setting and show that these hierarchies can be characterized in terms of adaptive reducibility in deterministic (poly)logarithmic time, i. e. in time O(log n) i for i ⩾ 0. Using this characterization, we substantially generalize various previous results concerning the structure of the two hierarchies.

Details DOI