Data-driven algorithms for multi-agent optimization and games
Multi-agent optimization and game theory constitute fundamental frameworks for modelling a plethora of engineering problems. In some systems, agents cooperate to optimize a collective cost, thus giving rise to multi-agent optimization programs. In other cases, agents act as selfish entities wishing...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2022
|
| Subjects: |
| _version_ | 1817933157099372544 |
|---|---|
| author | Pantazis, G |
| author_facet | Pantazis, G |
| author_sort | Pantazis, G |
| collection | OXFORD |
| description | Multi-agent optimization and game theory constitute fundamental frameworks for
modelling a plethora of engineering problems. In some systems, agents cooperate to
optimize a collective cost, thus giving rise to multi-agent optimization programs. In
other cases, agents act as selfish entities wishing to minimize their own individual
cost subject to local or global constraints. To model such behaviour, non-cooperative
game theory is required. Finally, agents though selfish can opt towards the formation
of coalitions such that they receive a higher payoff. Such systems are studied under
the lenses of cooperative game theory.
One of the most crucial challenges in such problems is finding solutions that are
robust against the effects of uncertainty. Uncertainty represents our lack of knowledge
about how the underlying system behaves and usually originates from unmodelled
dynamics or external factors. Its significance is apparent in modern applications such
as the electric vehicle charging problem, the optimal power flow problem with power
generation from renewable energy sources, transportation and social networks.
Following a data-driven approach, this thesis builds a theoretical framework for the
provision of robustness certificates for solutions to multi-agent optimization problems
and non-cooperative games with an arbitrary cost function and uncertainty in the
constraints. The theoretical tools developed allow the provision of collective certificates
for sets (and subsets) of solutions that do not necessarily need to be optimal. Focusing
on the class of aggregative games, agents’ deviations from an equilibrium solution and
uncertain constraints are considered. A data-driven equilibrium seeking algorithm is
then proposed such that tunable collective guarantees can be provided for all possible
feasible deviations from the equilibrium.
Shifting our attention towards a particular class of optimization programs with
uncertain cost, prevalent in practical applications, we provide probabilistic guarantees
for the randomized optimizer that do not depend on the number of agents but only on
the size of the decision vector of each agent. As such, the probabilistic guarantees
provided are scalable as the number of agents increases.
Finally, a data-driven theoretical framework is established for multi-agent cooperative
games with uncertain value functions. Collective stability guarantees for the
entire core set, a fundamental concept in cooperative game theory, are provided based
on data from the value functions in a probably approximately correct learning fashion.
The case where the core can be empty is considered and a methodology to accompany
allocations in a relaxed core with stability certificates is proposed. |
| first_indexed | 2024-03-07T07:33:15Z |
| format | Thesis |
| id | oxford-uuid:5228d17c-b847-4142-8a6f-e1639b259274 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:49:20Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | oxford-uuid:5228d17c-b847-4142-8a6f-e1639b2592742024-12-08T12:35:38ZData-driven algorithms for multi-agent optimization and gamesThesishttp://purl.org/coar/resource_type/c_db06uuid:5228d17c-b847-4142-8a6f-e1639b259274Multi-agent systemsScenario approachStatistical learningEnglishHyrax Deposit2022Pantazis, GMulti-agent optimization and game theory constitute fundamental frameworks for modelling a plethora of engineering problems. In some systems, agents cooperate to optimize a collective cost, thus giving rise to multi-agent optimization programs. In other cases, agents act as selfish entities wishing to minimize their own individual cost subject to local or global constraints. To model such behaviour, non-cooperative game theory is required. Finally, agents though selfish can opt towards the formation of coalitions such that they receive a higher payoff. Such systems are studied under the lenses of cooperative game theory. One of the most crucial challenges in such problems is finding solutions that are robust against the effects of uncertainty. Uncertainty represents our lack of knowledge about how the underlying system behaves and usually originates from unmodelled dynamics or external factors. Its significance is apparent in modern applications such as the electric vehicle charging problem, the optimal power flow problem with power generation from renewable energy sources, transportation and social networks. Following a data-driven approach, this thesis builds a theoretical framework for the provision of robustness certificates for solutions to multi-agent optimization problems and non-cooperative games with an arbitrary cost function and uncertainty in the constraints. The theoretical tools developed allow the provision of collective certificates for sets (and subsets) of solutions that do not necessarily need to be optimal. Focusing on the class of aggregative games, agents’ deviations from an equilibrium solution and uncertain constraints are considered. A data-driven equilibrium seeking algorithm is then proposed such that tunable collective guarantees can be provided for all possible feasible deviations from the equilibrium. Shifting our attention towards a particular class of optimization programs with uncertain cost, prevalent in practical applications, we provide probabilistic guarantees for the randomized optimizer that do not depend on the number of agents but only on the size of the decision vector of each agent. As such, the probabilistic guarantees provided are scalable as the number of agents increases. Finally, a data-driven theoretical framework is established for multi-agent cooperative games with uncertain value functions. Collective stability guarantees for the entire core set, a fundamental concept in cooperative game theory, are provided based on data from the value functions in a probably approximately correct learning fashion. The case where the core can be empty is considered and a methodology to accompany allocations in a relaxed core with stability certificates is proposed. |
| spellingShingle | Multi-agent systems Scenario approach Statistical learning Pantazis, G Data-driven algorithms for multi-agent optimization and games |
| title | Data-driven algorithms for multi-agent optimization and games |
| title_full | Data-driven algorithms for multi-agent optimization and games |
| title_fullStr | Data-driven algorithms for multi-agent optimization and games |
| title_full_unstemmed | Data-driven algorithms for multi-agent optimization and games |
| title_short | Data-driven algorithms for multi-agent optimization and games |
| title_sort | data driven algorithms for multi agent optimization and games |
| topic | Multi-agent systems Scenario approach Statistical learning |
| work_keys_str_mv | AT pantazisg datadrivenalgorithmsformultiagentoptimizationandgames |