Back to search

National Technical University of Athens (NTUA)

Natural and efficient dynamics through convex optimization

Abstract

dc:description

The subject of this thesis is the use of convex optimization techniques to study the dynamic behavior of the agents’ strategies and the Price of Anarchy in opinion formation games, as well as to design efficient algorithms in computational problems related to opinion selection in time-changing environments. More specifically, the contribution of the thesis is the following:Extension and generalization of the previous results concerning the convergence properties and the Anarchy Price in opinion formation games based on the Friedkin-Johnsen model. These extensions are carried out in two main directions. In the first direction, a generalization of the opinion formation games is examined in which the influences among the agents can be negative (some agents' opinions can be repulsive to others). It turns out that even in this case, the Anarchy Price is upper bounded by a constant independent on the number of the agents participating in the game. At the same time, it turns out that the best response dynamics converge to Nash equilibrium even in cases where the agents admit limited information about the other agents' strategies. In the second direction, we consider a random-payoff variant of the opinion formation games in which the disagreement cost of each agent is a random variable depending on the agent’ s random meetings. The goal of each agent is to appropriately select an opinion (strategy) that minimizes her expected disagreement cost. We present results concerning the convergence rate of the opinions to Nash equilibrium when all agents update their opinion according to the Follow the Leader algorithm. We also present lower bounds on the convergence rate of any update rule that ensures no-regret.We examine two generalizations of the Hegselmann-Krause model. In the first generalization, we consider an undirected graph in which the nodes represent the agents and the edges represent the social relationships among them. At each round, the agents update their opinions to the average of the opinions of their neighbors that are sufficiently close to their own opinion. The model proposed by Hegselmann and Krause is a special case of the above model, when any two agents are socially connected. We prove that that for any graph topology, the agents' opinions are stabilized after a finite number of rounds. In the second extension that we examine, each agent randomly selects a small subset of the other agents and updates her opinion to the average the opinions of the randomly-met agents that are close to her own opinion. We show that even in this case the system converges to a stable point with high probability.We present a polynomial time algorithm for the k-facility reallocation problem. This problem was proposed as a generalization of the classical k-median optimization problem, where the positions of the requests lie on the real line but may change over time. Our algorithm is based on rounding an optimal fractional solution of an appropriate linear program and runs in strongly polynomial time. Our result is a significant improvement over the previous known algorithm, which was exponential in the parameter k.

Degree

thesis:*
Grantor dc:publisher
National Technical University of Athens (NTUA)
Year dc:date
2019

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Skoulakis, Efstratios-Panteleimon
  • Σκουλάκης, Ευστράτιος-Παντελεήμων

Subjects

dc:subject × 6

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/46365

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Skoulakis, Efstratios-Panteleimon; Σκουλάκης, Ευστράτιος-Παντελεήμων. Natural and efficient dynamics through convex optimization. National Technical University of Athens (NTUA), 2019. http://hdl.handle.net/10442/hedi/46365