Optimization and Multiobjective Control of Time-Discrete Systems: Dynamic Networks and Multilayered Structures

Optimization and Multiobjective Control of Time-Discrete Systems: Dynamic Networks and Multilayered Structures

by Dmitrii Lozovanu

Paperback(Softcover reprint of hardcover 1st ed. 2009)

$139.99
Choose Expedited Shipping at checkout for guaranteed delivery by Friday, February 28
MARKETPLACE
2 New & Used Starting at $134.77

Overview

The study of discrete structures and networks becomes more and more important in decision theory. A relevant topic in modern control theory reflecting this fact is concerned with multiobjective control problems and dynamical games. The monograph presents recent developments and applications in the field of multiobjective control of time-discrete systems with a finite set of states. The dynamics of such systems is described by a directed graph in which each vertex corresponds to a dynamic state and the edges correspond to transitions of the system moving from one state to another. This characterization allows us to formulate the considered control models on special dynamic networks. Suitable algorithms are derived exploiting multilayered structures. Game theoretical properties are characterized. A multlilayered game on a network can be used to model a certain trading procedure of emission certificates within Kyoto process. Optimal economic behavior and equilibria can be determined.

Product Details

ISBN-13: 9783642098680
Publisher: Springer Berlin Heidelberg
Publication date: 11/19/2010
Edition description: Softcover reprint of hardcover 1st ed. 2009
Pages: 285
Product dimensions: 6.10(w) x 9.25(h) x 0.03(d)

Table of Contents

1 Multi-Objective Control of Time-Discrete Systems and Dynamic Games on Networks 1

1.1 Problem Formulation 1

1.1.1 Single-Objective Discrete Control Problem 2

1.1.2 Multi-Objective Control Based on the Concept of Non-cooperative Games: Nash Equilibria 4

1.1.3 Hierarchical Control and Stackelberg's Optimization Principle 7

1.1.4 Multi-Objective Control Based on the Concept of Cooperative Games: Pareto Optima 8

1.1.5 Stationary and Non-Stationary Control of Time-Discrete Systems 10

1.2 Multi-Objective Control of Time-Discrete Systems with Infinite Time Horizon 10

1.3 Alternate Players' Control Condition and Nash Equilibria for Dynamic Games in Positional Form 11

1.4 Algorithms for Solving Single-Objective Control Problems on Networks 15

1.4.1 Dynamic Programming Algorithms for Solving Optimal Control Problems on Networks 15

1.4.2 An Extension of Dijkstra's Algorithm for Optimal Control Problems with a Free Number of Stages 18

1.5 Multi-Objective Control and Non-Cooperative Games on Dynamic Networks 22

1.5.1 The Problem of Determining the Optimal Stationary Strategies in a Dynamic c-Game 22

1.5.2 The Problem of Determining the Optimal Non-Stationary Strategies in a Dynamic c-Game 25

1.6 Main Results for Dynamic c-Games with Constant Costs of the Edges and Determining Optimal Stationary Strategies of the Players 26

1.7 Computational Complexity of the Problem of Determining Optimal Stationary Strategies in a Dynamic c-Game 45

1.8 Determining the Optimal Stationary Strategies for a Dynamic c-Game with Non-Constant Cost Functions on the Edges 45

1.9 Determining Nash Equilibria for Non-Stationary Dynamic c-Game 53

1.9.1 Time-Expanded Networks forNon-Stationary Dynamic c-Game and Their Main Properties 53

1.9.2 Determining Nash Equilibria 55

1.10 Application of the Dynamic c-Game for Studying and Solving Multi-Objective Control Problems 57

1.11 Multi-Objective Control and Cooperative Games on Dynamic Networks 58

1.11.1 Stationary Strategies on Networks and Pareto Solutions 58

1.11.2 A Pareto Solution for the Problem with Non-Stationary Strategies on Networks 59

1.12 Determining Pareto Solutions for Multi-Objective Control Problems on Networks 60

1.12.1 Determining Pareto Stationary Strategies 60

1.12.2 Pareto Solution for the Non-Stationary Case of the Problem 65

1.12.3 Computational Complexity of the Stationary Case of the Problem and an Algorithm for its Solving on Acyclic Networks 65

1.13 Determining Pareto Optima for Multi-Objective Control Problems 66

1.14 Determining a Stackelberg Solution for Hierarchical Control Problems 67

1.14.1 A Stackelberg Solution for Static Games 68

1.14.2 Hierarchical Control on Networks and Determining Stackelberg Stationary Strategies 69

1.14.3 An Algorithm for Determining Stackelberg Stationary Strategies on Acyclic Networks 73

1.14.4 An Algorithm for Solving Hierarchical Control Problems 78

2 Max-Min Control Problems and Solving Zero-Sum Games on Networks 81

2.1 Discrete Control and Finite Antagonistic Dynamic Games 81

2.2 Max-Min Control Problem with Infinite Time Horizon 82

2.3 Zero-Sum Games on Networks and a Polynomial Time Algorithm for Max-Min Paths Problems 83

2.3.1 Problem Formulation 84

2.3.2 An Algorithm for Solving the Problem on Acyclic Networks 86

2.3.3 Main Results for the Problem on an Arbitrary Network 88

2.3.4 A Polynomial Time Algorithm for Determining Optimal Strategies of the Players in a Dynamic c-Game 90

2.3.5 A Pseudo-Polynomial Time Algorithm for Solving a Dynamic c-Game 95

2.4 A Polynomial Time Algorithm for Solving Acyclic l-Games on Networks 101

2.4.1 Problem Formulation 101

2.4.2 Main Properties of Optimal Strategies in Acyclic l-Games 102

2.4.3 A Polynomial Time Algorithm for Finding the Value and the Optimal Strategies in an Acyclic l-Game 103

2.5 Cyclic Games: Algorithms for Finding the Value and the Optimal Strategies of the Players 105

2.5.1 Problem Formulation and Main Properties 106

2.5.2 Determining the Best Response of the First Player for a Fixed Strategy of the Second Player 107

2.5.3 Some Preliminary Results 110

2.5.4 The Reduction of Cyclic Games to Ergodic Games 111

2.5.5 A Polynomial Time Algorithm for Solving Ergodic Zero-Value Cyclic Games 111

2.5.6 A Polynomial Time Algorithm for Solving Cyclic Games Based on the Reduction to Acyclic l-Games 113

2.5.7 An Approach for Solving Cyclic Games Based on a Dichotomy Method and Solving Dynamic c-Games 116

2.6 Cyclic Games with Random States' Transitions of the Dynamical System 117

2.7 A Nash Equilibria Condition for Cyclic Games with p Players 118

2.8 Determining Pareto Optima for Cyclic Games with p Players 122

3 Extension and Generalization of Discrete Control Problems and Algorithmic Approaches for its Solving 125

3.1 Discrete Control Problems with Varying Time of States' Transitions of the Dynamical System 125

3.1.1 The Single-Objective Control Problem with Varying Time of States' Transitions of the Dynamical System 126

3.1.2 An Algorithm for Solving a Single-Objective Control Problem with Varying Time of States' Transitions of the Dynamical System 127

3.1.3 The Discrete Control Problem with Cost Functions of System's Passages that Depend on the Transition-Time of States' Transitions 132

3.2 The Control Problem on a Network with Transition-Time Functions on the Edges 133

3.2.1 Problem Formulation 133

3.2.2 An Algorithm for Solving the Problem on a Network with Transition-Time Functions on the Edges 134

3.3 Multi-Objective Control of Time-Discrete Systems with Varying Time of States' Transitions 141

3.3.1 Multi-Objective Discrete Control with Varying Time of States' Transitions of Dynamical Systems 141

3.3.2 A Dynamic c-Game on Networks with Transition-Time Functions on the Edges 146

3.3.3 Remark on Determining Pareto Optima for the Multi-Objective Control Problem with Varying Time of States' Transitions 149

3.4 An Algorithm for Solving the Discrete Optimal Control Problem with Infinite Time Horizon and Varying Time of the States' Transitions 150

3.4.1 Problem Formulation and Some Preliminary Results 150

3.4.2 An Algorithm for Determining an Optimal Stationary Control for Dynamical Systems with Infinite Time Horizon 152

3.5 A General Approach for Algorithmic Solutions of Discrete Optimal Control Problems and its Game-Theoretic Extension 154

3.5.1 A General Optimal Control Model 154

3.5.2 An Algorithm for Determining an Optimal Solution of the Problem with Fixed Starting and Final States 156

3.5.3 The Discrete Optimal Control Problem on a Network 159

3.5.4 The Game-Theoretic Control Model with p Players 160

3.5.5 The Game-Theoretic Control Problem on Networks and an Algorithm for its Solving 161

3.5.6 Multi-Criteria Discrete Control Problems: Pareto Optima 169

3.6 Pareto-Nash Equilibria for Multi-Objective Games 171

3.6.1 Problem Formulation 172

3.6.2 Main Results 173

3.6.3 Discrete and Matrix Multi-Objective Games 177

3.6.4 Some Comments on and Interpretations of Multi-Objective Games 179

3.6.5 Determining a Pareto-Stackelberg Solution for Multi-Objective Games 179

4 Discrete Control and Optimal Dynamic Flow Problems on Networks 181

4.1 Single-Commodity Dynamic Flow Problems and the Time-Expanded Network Method for Their Solving 181

4.1.1 The Minimum Cost Dynamic Flow Problem 182

4.1.2 The Main Results 183

4.1.3 The Dynamic Model with Flow Storage at Nodes 186

4.1.4 The Dynamic Model with Flow Storage at Nodes and Integral Constant Demand-Supply Functions 188

4.1.5 The Algorithm 189

4.1.6 Constructing the Time-Expanded Network and its Size 190

4.1.7 Approaches for Solving the Minimum Cost Flow Problem with Different Types of Cost Functions on the Edges 200

4.1.8 Determining the Minimum Cost Flows in Dynamic Networks with Transition Time Functions that Depend on Flow and Time 208

4.1.9 An Algorithm for Solving the Maximum Dynamic Flow Problem 212

4.2 Multi-Commodity Dynamic Flow Problems and Algorithms for their Solving 214

4.2.1 The Minimum Cost Multi-Commodity Dynamic Flow Problem 214

4.2.2 The Main Results 216

4.2.3 The Algorithm 220

4.2.4 Examples 220

4.2.5 The Dynamic Multi-Commodity Minimum Cost Flow Problem with Transition Time Functions that Depend on Flows and on Time 224

4.2.6 Generalizations 229

4.2.7 An Algorithm for Solving the Maximum Dynamic Multi-Commodity Flow Problem 229

4.3 The Game-Theoretic Approach for Dynamic Flow Problems on Networks 231

5 Applications and Related Topics 233

5.1 Analysis and Control of Time-Discrete Systems: Resource Planning - The TEM Model 233

5.1.1 Motivation 234

5.1.2 The Basic Model 234

5.1.3 Control Theoretic Part 237

5.1.4 Problem of Fixed Point Controllability and Null-Controllability 238

5.1.5 Optimal Investment Parameter 240

5.1.6 A Game-Theoretic Extension - Relation to Multilayered Decision Problems 244

5.2 Algorithmic Solutions for an Emission Reduction Game: The Kyoto Game 250

5.2.1 The Core in the TEM Model 250

5.2.2 A Second Cooperative Treatment of the TEM Model 259

5.2.3 Comments 268

5.3 An Emission Reduction Process - The MILAN Model 269

5.3.1 MILAN: Multilayered Games on Networks The General Kyoto Game as a Multi-Step Process 269

5.3.2 Sequencing and Dynamic Programming 271

5.3.3 Generalizations of the Feasible Decision Sets: Optimal Solutions on k-Layered Graphs 274

Conclusion 275

References 277

Index 283

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews