Data-driven algorithms for multi-agent optimization and games - Pantazis, G (2022)
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.