## Tesi etd-04302019-134743 |

Thesis type

Tesi di dottorato di ricerca

Author

FABIANI, FILIPPO

URN

etd-04302019-134743

Title

Potential game-theoretic control of complex multi-agent systems

Settore scientifico disciplinare

ING-INF/04

Corso di studi

INGEGNERIA DELL'INFORMAZIONE

Supervisors

**tutor**Prof. Caiti, Andrea

Parole chiave

- Algorithmic game theory
- Complex systems
- Multi-agent systems
- Potential game theory

Data inizio appello

09/05/2019;

Consultabilità

Parziale

Data di rilascio

09/05/2089

Riassunto analitico

The world around us is strongly conditioned by the interactions among its constituent systems, which may intrinsically conceal the germs of conflict or, in contrast, may reveal mutual collaboration, either voluntary or unexpected.

A peculiar characteristic of modern society is, in fact, the wide dissemination of large-scale systems with a complex network structure, involving interacting, possibly selfish entities.

In this context, the role played by game theory promises to be key, since it offers a general framework to describe, analyze and, in the end, control loosely coupled systems characterized by individual interests.

Under the lens of potential game theory, this thesis investigates several control challenges posed to the system-and-control community within the complex sciences domain. As a particular subclass of games, potential games directly inherit the pivotal concept of ``stable states''. An equilibrium solution, indeed, represents a suitable compromise that embraces individual interests while respecting the constraints imposed by the interactions. Moreover, potential games offer some kind of additional degree of freedom, since they intrinsically include the possibility to seek an equilibrium of the game by means of an ``unconscious'' cooperation among egoistic entities.

The strong connection between the equilibrium solution of a potential game and the classical multi-agent optimization theory paves the way to the synthesis of scalable and distributed algorithms that exploit the structure of the game to compute an equilibrium solution. Along this direction, we extend the literature on the topic by envisioning an interplay dynamics among the players of the original potential game and some ``fictitious'' agents introduced by constraints. Specifically, the players set the value of their local decision variable, while the fictitious agents are in charge of ensuring that the constraints are asymptotically fulfilled, imposing penalties if they are not met.

In some cases, the potential function characterizing a game can have a physical interpretation. With this regard, we show an intriguing affinity between two ways of modeling and control a set of constrained, double-integrator agents: the energetic, port-Hamiltonian framework and a potential game. By enforcing distance-based constraints among agents by means of pairs of spring-damper (passive elements), the overall network exhibits symmetries across the decision variables of each agent: two connected agents showing the same deviation in term of strategies reflect in exactly the same amount of deviation on the respective objective functions. This is crucial to prove the existence of an exact potential game associated to the related control problem. Since the passive elements are purely design parameters and result in a distributed, gradient-based controller, it is possible to shape the transient behaviour of the players and, ideally, the reached equilibrium of the associated game.

Finally, potential game theory offers several tools to get over intrinsic technical obstacles as, for example, the presence of mixed-integer decision variables in hybrid systems. The players, indeed, can exploit local interactions to iteratively update their decisions towards a minimum of the potential function, which corresponds to an equilibrium of the game. Remarkably, this procedure does not require any particular technical assumption and hence holds in general. Thus, we propose best-response based, distributed algorithms to solve a potential game with mixed-integer decision variables, extending the referred literature on typical iterative schemes (e.g., Gauss-Seidel algorithm) and leaving some questions unanswered on the possibility to study open- and closed-loop games.

A peculiar characteristic of modern society is, in fact, the wide dissemination of large-scale systems with a complex network structure, involving interacting, possibly selfish entities.

In this context, the role played by game theory promises to be key, since it offers a general framework to describe, analyze and, in the end, control loosely coupled systems characterized by individual interests.

Under the lens of potential game theory, this thesis investigates several control challenges posed to the system-and-control community within the complex sciences domain. As a particular subclass of games, potential games directly inherit the pivotal concept of ``stable states''. An equilibrium solution, indeed, represents a suitable compromise that embraces individual interests while respecting the constraints imposed by the interactions. Moreover, potential games offer some kind of additional degree of freedom, since they intrinsically include the possibility to seek an equilibrium of the game by means of an ``unconscious'' cooperation among egoistic entities.

The strong connection between the equilibrium solution of a potential game and the classical multi-agent optimization theory paves the way to the synthesis of scalable and distributed algorithms that exploit the structure of the game to compute an equilibrium solution. Along this direction, we extend the literature on the topic by envisioning an interplay dynamics among the players of the original potential game and some ``fictitious'' agents introduced by constraints. Specifically, the players set the value of their local decision variable, while the fictitious agents are in charge of ensuring that the constraints are asymptotically fulfilled, imposing penalties if they are not met.

In some cases, the potential function characterizing a game can have a physical interpretation. With this regard, we show an intriguing affinity between two ways of modeling and control a set of constrained, double-integrator agents: the energetic, port-Hamiltonian framework and a potential game. By enforcing distance-based constraints among agents by means of pairs of spring-damper (passive elements), the overall network exhibits symmetries across the decision variables of each agent: two connected agents showing the same deviation in term of strategies reflect in exactly the same amount of deviation on the respective objective functions. This is crucial to prove the existence of an exact potential game associated to the related control problem. Since the passive elements are purely design parameters and result in a distributed, gradient-based controller, it is possible to shape the transient behaviour of the players and, ideally, the reached equilibrium of the associated game.

Finally, potential game theory offers several tools to get over intrinsic technical obstacles as, for example, the presence of mixed-integer decision variables in hybrid systems. The players, indeed, can exploit local interactions to iteratively update their decisions towards a minimum of the potential function, which corresponds to an equilibrium of the game. Remarkably, this procedure does not require any particular technical assumption and hence holds in general. Thus, we propose best-response based, distributed algorithms to solve a potential game with mixed-integer decision variables, extending the referred literature on typical iterative schemes (e.g., Gauss-Seidel algorithm) and leaving some questions unanswered on the possibility to study open- and closed-loop games.

File

Nome file | Dimensione |
---|---|

2 file non consultabili su richiesta dell'autore. |