Distributed Control and Game Design: From Strategic Agents to Programmable Machines
dc.contributor.author
Paccagnan, Dario
dc.contributor.supervisor
Lygeros, John
dc.contributor.supervisor
Krause, Andreas
dc.contributor.supervisor
Marden, Jason R.
dc.date.accessioned
2020-01-20T07:47:00Z
dc.date.available
2019-01-10T15:28:39Z
dc.date.available
2019-01-11T09:39:52Z
dc.date.available
2019-01-18T08:52:10Z
dc.date.available
2019-01-18T09:46:35Z
dc.date.available
2019-01-18T09:49:28Z
dc.date.available
2019-01-18T10:20:07Z
dc.date.available
2020-01-20T07:47:00Z
dc.date.issued
2018-12
dc.identifier.isbn
978-3-906916-47-7
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/314981
dc.identifier.doi
10.3929/ethz-b-000314981
dc.description.abstract
Large scale systems are forecasted to greatly impact our future lives thanks to their wide ranging applications including cooperative robotics, mobility on demand, resource and task allocation, supply chain management, and many more. While technological developments have paved the way for the realization of such futuristic systems, we have a limited grasp on how to coordinate the behavior of their individual components to achieve the desired global objective. With the objective of advancing our understanding, this thesis focus on the analysis and coordination of large scale systems without the need of a centralized authority. At a high level, we distinguish these systems depending on wether they are composed of cooperative or non-cooperative subsystems. In regard to the first class, a key challenge is the design of local decision rules for the individual components to guarantee that the collective behavior is desirable with respect to a global objective. Non-cooperative systems, on the other hand, require a more careful thinking in that the designer needs to take into account the self-interested nature of the agents. In both cases, the need for distributed protocols stems from the observation that centralized decision making is prohibited due to the scale and privacy requirement associated with typical systems. In the first part of this thesis, we focus on the coordination of a large number of non-cooperative agents. More specifically, we consider strategic decision making problems where each agent's objective is a function of the aggregate behavior of the population. Examples are ubiquitous and include social and traffic networks, demand-response markets, vaccination campaigns, to name just a few. We present two cohesive contributions. First, we compare the performance of an equilibrium allocation with that of an optimal allocation, that is an allocation where a common welfare function is maximized. We propose conditions under which all Nash equilibrium allocations are efficient, i.e., are desirable from a macroscopic standpoint. In the journey towards this goal, we prove a novel result bounding the distance between the strategies at a Nash and at a Wardrop equilibrium that might be of independent interest. Second, we show how to derive scalable algorithms that guide agents towards an equilibrium allocation, i.e., a stable configuration where no agent has any incentive to deviate. When the corresponding equilibria are efficient, these algorithms attain the global objective and respect the agents' selfish nature. In the second part of this thesis, we focus on the coordination of cooperative agents. We consider large-scale resource allocation problems, where a number of agents need to be allocated to a set of resources, with the goal of jointly maximizing a given submodular or supermodular set function. Applications include sensor allocation problems, distributed caching, data summarization, and many more. Since this class of problems is computationally intractable, we aim at deriving tractable algorithms for attaining approximate solutions, ideally with the best possible approximation ratio. We approach the problem from a game-theoretic perspective and ask the following question: how should we design agents' utilities so that any equilibrium configuration recovers a large fraction of the optimum welfare? In order to answer this question, we introduce a novel framework providing a tight expression for the worst-case performance (price of anarchy) as a function of the chosen utilities. Leveraging this result, we show how to design utility functions so as to optimize the price of anarchy by means of a tractable linear program. The upshot of our contribution is the design of algorithms that are distributed, efficient, and whose performance is certified to be on par or better than that of existing (and centralized) schemes.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
Multiagent Systems
en_US
dc.subject
Game Theory
en_US
dc.subject
Combinatorial Optimization
en_US
dc.subject
Algorithms
en_US
dc.title
Distributed Control and Game Design: From Strategic Agents to Programmable Machines
en_US
dc.type
Doctoral Thesis
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.size
203 p.
en_US
ethz.code.ddc
DDC - DDC::6 - Technology, medicine and applied sciences::621.3 - Electric engineering
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
ethz.identifier.diss
25597
en_US
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02650 - Institut für Automatik / Automatic Control Laboratory::03751 - Lygeros, John / Lygeros, John
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02650 - Institut für Automatik / Automatic Control Laboratory::03751 - Lygeros, John / Lygeros, John
en_US
ethz.date.deposited
2019-01-10T15:28:42Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.date.embargoend
2020-01-18
ethz.rosetta.installDate
2019-01-18T09:46:43Z
ethz.rosetta.lastUpdated
2023-02-06T18:12:16Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Distributed%20Control%20and%20Game%20Design:%20From%20Strategic%20Agents%20to%20Programmable%20Machines&rft.date=2018-12&rft.au=Paccagnan,%20Dario&rft.isbn=978-3-906916-47-7&rft.genre=unknown&rft.btitle=Distributed%20Control%20and%20Game%20Design:%20From%20Strategic%20Agents%20to%20Programmable%20Machines
Files in this item
Publication type
-
Doctoral Thesis [30085]