Samson Lasaulce Tania Jimenez - NETWORK GAMES, CONTROL, AND OPTIMIZATION: proceedings of netgcoop 2016

NETWORK GAMES, CONTROL, AND OPTIMIZATION: proceedings of netgcoop 2016 — read online for free the complete book (whole text) full work

Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "NETWORK GAMES, CONTROL, AND OPTIMIZATION: proceedings of netgcoop 2016" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

1234567...75

Springer International Publishing AG 2017

Samson Lasaulce , Tania Jimenez and Eilon Solan (eds.) Network Games, Control, and Optimization Static & Dynamic Game Theory: Foundations & Applications 10.1007/978-3-319-51034-7_1

Finite Improvement Property in a Stochastic Game Arising in Competition over Popularity in Social Networks

Eitan Altman 1, 2

(1)

Universit Cte dAzur, INRIA, Sophia Antipolis, France

(2)

LINCS, Paris, France

(3)

Indian Institute of Technology, Guwahati, India

(4)

CERI/LIA, University of Avignon, Avignon, France

Eitan Altman (Corresponding author)

Email:

Atulya Jain

Email:

Yezekael Hayel

Email:

Abstract

This paper is a follow-up of (Eitan Altman, Dynamic Games and Applications, Springer Verlag, Vol. 3, No. 2 (2013) 313323). It considers the same stochastic game that describes competition through advertisement over the popularity of their content. We show that the equilibrium may or may not be unique, depending on the systems parameters. We further identify structural properties of the equilibria. In particular, we show that a finite improvement property holds on the best response pure policies which implies the existence of pure equilibria. We further show that all pure equilibria are fully ordered in the performance they provide to the players and we propose a procedure to obtain the best equilibrium.

Keywords

Social networks Stochastic games Non-uniqueness of equilibria Finite improvement property (FIP)

Introduction

In [] are (1) a set of coupled dynamic programming is formulated so that for each state, a solution (fixed point) in the set of mixed actions for the dynamic programming defines a stationary randomized equilibrium policy. (2) If the utilities that are linear in the state then the state in this stochastic game can be aggregated and is simply the number of destinations m that have received a content from some source, no matter which. (3) Moreover, under this condition, the cost to go in the dynamic programming becomes independent of the actions of the players. The latter only influences the immediate utility of the players. (4) Hence the solution is obtained by solving M independent matrix games. (5) The equilibrium is shown to be of a threshold type if the utility is linear in the actions. (6) Similar results are then obtained for the case in which the players have no state information.

This paper is a follow-up of [] showing that the stochastic game can be decomposed into a finite number of matrix games each determining the stationary equilibria policy of the players in a different state in the original game. We provide an example in which for some state, this gives rise to a coordination matrix game and thus has two pure equilibria and a mixed one. We show that there is a total order on all pure policies according to their performance. In particular, we show that there exists a pure equilibrium which dominates all other equilibria and we provide an iterative procedure to compute it within a finite number of steps. This is shown to imply the Finite Improvement Property (FIP).

The structure of the paper is as follows. We begin with a quick definition of the problem and an overview of the stochastic game formulation from [. It also provides some structural results on the equilibria. The paper ends with a concluding section.

Stochastic Game Model and Statement of the Problem

We begin by recalling the stochastic game model from []. There are N competing contents. There are M potential common destinations. We assume that a destination wishes to acquire one of these contents and will purchase the one at the first possible opportunity. We assume that once the destination has a content then it is not interested in other content.

We assume that opportunities for purchasing a content i arrive at destination m according to a Poisson process with parameter i starting at time t =0. Hence if at time t =0 destination m wishes to purchase the content i , it will have to wait for some exponentially distributed time with parameter i .

The value of i may differ from one content to another. The difference is partly due to the fact that different contents may have different popularity.

We assume that the owner of a content n can accelerate the propagation speed of the propagation of the content by accelerating i e.g. through some advertisement effort which increases the popularity of the content.

2.1 Markov Game Formulation

We next present the mathematical formulation of this Markov game after uniformization and after aggregating the state space. The uniformization allows us to obtain the discrete time game from the original continuous time game by considering a Markov game embedded at the jumps of some Poisson process whose rate is given by . Details are given in [].

• State Space. We consider a finite state space . We say that the system is in state m if the total number of destinations that have already some content (no matter which is its origin) equals m .
• Action Space. The set A i of actions available to the owner of content type i contains the two actions a and . a A i is the amount of acceleration of i . We assume a =1 and . Let A be the product action space of A i , i =1, N .
• Transition probabilities.

  

  (1)
• Policies. A pure stationary policy for player i is a map from X to A i . Let ( A i ) be the set of probability measures over A i . A mixed stationary policy is a map from X to ( A i ). Choose some horizon T . A Markov policy for player i is a measurable function w i that assigns for each t [0, T ] and each state x a mixed action w t i ( x ). For a given initial state x and a given Markov policy w , there exists a unique probability measure P x w which defines the state and action random processes X ( t ), A ( t ). Multi-policies are defined as vectors of policies, one for each player.
• The immediate utility. The utility for player i is the difference between the dissemination utility and the advertisement cost (disutility). The total accumulated (over time) dissemination utility for player i till time t is given by the total expected number of contents originating from source i at the various destinations till time t . Hence the instantaneous dissemination utility for player i at time t if the state is x and an action a is taken by the players is given by

  

  The advertisement cost for player i at time n if it uses a is some increasing function c i ( a ) of a .
• Utility of player i : Player i wishes to maximize its total expected utility till absorption at state M . The process is thus an absorbing MDP [, Chap 7].

Next page

1234567...75

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

Similar books «NETWORK GAMES, CONTROL, AND OPTIMIZATION: proceedings of netgcoop 2016»

Look at similar books to NETWORK GAMES, CONTROL, AND OPTIMIZATION: proceedings of netgcoop 2016. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.

Shaul Bar

The Samson Story: Love, Seduction, Betrayal, Violence, Riddles, Myth

Shawn Hoffman

Samson: A Savior Will Rise

Bernabé Dorronsoro

Optimization and Learning: 4th International Conference, OLA 2021, Catania, Italy, June 21-23, 2021, Proceedings

Anita Khosla

Renewable Energy Optimization, Planning and Control: Proceedings of ICRTE 2021

Hisao Ishibuchi

Evolutionary Multi-Criterion Optimization: 11th International Conference, EMO 2021, Shenzhen, China, March 28–31, 2021, Proceedings

Vladimir Mazalov

Networking Games: Network Forming Games and Games on Networks

Tania Blackmore

Community Palliative Care and COVID-19

Sinan Melih Nigdeli

Proceedings of 6th International Conference on Harmony Search, Soft Computing and Applications: ICHSA 2020, Istanbul

Tania Kaczynski

Who Am I?

Jiménez-Losada

Models for cooperative games with fuzzy relations among the agents: fuzzy communication, proximity relation and fuzzy permission

Bertsch Valentin

Advances in Energy System Optimization Proceedings of the first International Symposium on Energy System Optimization

Rufus Isaacs

Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization

Discussion, reviews of the book NETWORK GAMES, CONTROL, AND OPTIMIZATION: proceedings of netgcoop 2016 and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.