Author name cluster

Maria J. Blesa

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.

3 papers

2 author rows

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

MFCS Conference 2005 Conference Paper

Adversarial Queueing Model for Continuous Network Dynamics

Maria J. Blesa
Daniel Calzada
Antonio Fernández 0001
Luis López 0003
Andrés L. Martínez
Agustín Santos
Maria J. Serna

Abstract In this paper we start the study of generalizing the Adversarial Queueing Theory aqt model towards a continuous scenario in which the usually assumed synchronicity of the evolution is not required anymore. We consider a model, named continuous AQT ( caqt ), in which packets can have arbitrary lengths, and the network links may have different speeds (or bandwidths) and propagation delays. We show that, in such a general model, having bounded queues implies bounded end-to-end packet delays and vice versa. From the network point of view, we show that networks with directed acyclic topologies are universally stable, i. e. , stable independently of the protocols and the traffic patterns used in it, and that this even holds for traffic patterns that make links to be fully loaded. Concerning packet scheduling protocols, we show that the well-known lis, sis, ftg and nfs protocols remain universally stable in our model. We also show that the caqt model is strictly stronger than the aqt model by presenting scheduling policies that are unstable under the former while they are universally stable under the latter.

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