Vladimir Mazalov - Networking Games: Network Forming Games and Games on Networks

First edition

Vladimir V. Mazalov

Julia V. Chirkova

Russian Academy of Sciences, Karelia, Petrozavodsk, Russian Federation

Academic Press is an imprint of Elsevier

125 London Wall, London EC2Y 5AS, United Kingdom

525 B Street, Suite 1650, San Diego, CA 92101, United States

50 Hampshire Street, 5th Floor, Cambridge, MA 02139, United States

The Boulevard, Langford Lane, Kidlington, Oxford OX5 1GB, United Kingdom

Copyright 2019 Elsevier Inc. All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher's permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.

This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).

Notices

Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.

Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.

To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library

ISBN: 978-0-12-816551-5

For information on all Academic Press publications visit our website at https://www.elsevier.com/books-and-journals

Publisher: Candice Janco

Acquisition Editor: Scott J. Bentley

Editorial Project Manager: Michael Lutz

Production Project Manager: Paul Prasad Chandramohan

Designer: Matthew Limbert

Typeset by VTeX

The book is dedicated to game-theoretic models in communication and information networks. This research field forms a modern direction of game theory, which originated with the appearance of new technologies such as the Internet, mobile communications, distributed and cloud computing, social networks, etc. A basic knowledge of mathematical analysis, algebra, and probability theory is a necessary prerequisite for reading.

The book is addressed to under- and postgraduates and to experts in the field of operations research, information technology, and modeling of social systems and processes.

Some of the problems considered remain unsolved and can be the subject of independent research. As a matter of fact, our primary goal is to stimulate further investigations for interested readers. The list of references at the end of the book will guide them through relevant publications.

For many years, the authors have been enjoying the opportunity to discuss the derived results with Russian colleagues L.A. Petrosyan, V.V. Zakharov, N.V. Zenkevich, A.Yu. Garnaev, A.A. Sedakov (St. Petersburg State University), A.A. Vasin (Moscow State University), D.A. Novikov (Trapeznikov Institute of Control Sciences, Russian Academy of Sciences), and A.B. Zhizhchenko (Steklov Mathematical Institute, Russian Academy of Sciences) and with foreign colleagues M. Sakaguchi (Osaka University), B. Monin (University of Paderborn), K.E. Avrachenkov (INRIA Sophia Antipolis), A.V. Gurtov (Linkping University), and A.S. Lukyanenko (Aalto University, Helsinki). They all have our deep and sincere appreciation. We also express gratitude to colleagues A.N. Rettieva, A.Yu. Kondratjev, N.N. Nikitina, B.T. Tsynguev, and A.V. Shchiptsova from Institute of Applied Mathematical Research (Karelian Research Center, Russian Academy of Sciences) for helpful remarks. Finally, we thank A.Yu. Mazurov (Alekseev Nizhny Novgorod State Technical University) for his thorough translation, permanent feedback, and positive contribution to the English version of the book.

Results presented in this work were obtained in the IAMR KarRS RAS and supported by the Russian Foundation for Basic Research (project nos. 16-51-55006, 16-01-00183), the Russian Science Foundation (project no. 17-11-01079) and by the Shandong Province of China Double-Hundred Talent Plan (no. WST2017009).

Network games, or games on networks, are games defined over graphs. This branch of game theory originated with the appearance of new information technologies, in the first place the Internet, mobile communications, distributed and cloud computing, and social networks. All users of a network are linked by (information and communication) channels, which leads to different problems such as the choice of data routes or channels, the definition of signal levels and quality, the establishment of links to neighbor nodes, and others. For example, in routing games the players choose data channels of limited capacity. As a result, jamming occurs in networks, causing interesting effects and even paradoxes such as the well-known Braess paradox.

Network games can be divided into two classes, namely, (1) network formation games in which the players establish links to each other based on personal interests and (2) games on formed networks. In addition, there exists a combined two-stage setting of such games where a network is formed at the first stage and the agents located at different nodes of this network play with each other at the second stage.

The recent years have been remarkable for a technological breakthrough in the analysis of the virtual information world. In terms of game theory, all participants of the Internet and mobile communication networks are interacting players who receive and transmit information by appropriate data channels. Each player pursues individual interests, acquiring some information or complicating this process. The players need high-capacity channels, and the channel distribution problem arises naturally in the case of numerous players. Game-theoretic methods are of assistance here.

Owing to the development of the Internet, information transmission techniques were changed accordingly, and new decision-making systems were designed. Novel approaches were suggested in the field of artificial intelligence, resource allocation, computational resource optimization, and the number of such approaches is still rapidly growing. The global control of the Internet turns out to be impossible. We may speak about distributed control of the network where each user manages his traffic to maximize his utility or the amount of information or to minimize delays. In this context, we mention a series of problems such as optimal routing, equilibrium design in global large-scale networks, the existence of pure strategy equilibria, resource allocation, negotiations in networks, energy balance control and its efficiency in wireless networks, multiagent systems, learning capabilities of agents, and decision support in telecommunication networks. The same class of problems includes boosting the performance of multiprocessor computers. These problems can be solved using noncooperative game theory methods.