קולוקוויום: Colloquium: It's Just a Game: Designing Distributed Multiagent Protocols by Ilai Bistritz
Electrical Engineering Colloquium
Speaker: Dr. Ilai Bistritz
Title: It's Just a Game: Designing Distributed Multiagent Protocols
Abstract
Automation relegates many decision-making processes from humans to machines. In recent years, automation is powered by machine learning, which enables trained machines to achieve expert-level performance in some tasks. Many of these tasks require humans to interact (e.g., driving, delivery, construction), so automating them will result in interacting machines where the decisions of one machine affect others. As game theory predicts, this interaction can lead to a globally inefficient equilibrium. However, machines follow programmatic objectives and protocols that, unlike humans, are not limited by selfish interests, but by information and resources. This modern paradigm calls for new tools to design efficient multiagent protocols.
We will first highlight the major design challenges and then discuss the distributed energy allocation problem as a concrete example. We formulate this problem as a game and study the performance of best-response dynamics (BRD) as a distributed algorithm that the sources run to allocate energy to consumers. We show that "bad networks" exist where BRD suffers from poor performance. However, empirically, these bad networks are rare. Drawing inspiration from this empirical finding, we analyze BRD as a random process in a random game. We show that, with high probability, BRD is asymptotically optimal (in the size of the network). Applying our “random games approach” broadly may reveal that BRD is efficient more often than the worst-case overly pessimistic approach would suggest. This is an encouraging finding since BRD requires little to no coordination between the agents.
Light refreshments will be served before the lecture
This colloquium is not counted toward seminar credit.
ההרצאה לא מזכה בקרדיט שמיעת סמינרים.