Optimal Sequential Resource Sharing and Exchange in Multi-Agent Systems
Mar 03, 2014
from 09:00 AM to 12:00 PM
|Where||Engr. IV Bldg, Maxwell Room 57-124|
|Contact Name||Yuanzhang Xiao|
|Add event to calendar||
Advisor: Prof. Mihaela van der Schaar
Central to the design of many engineering systems and social networks is to solve the underlying resource sharing and exchange problems, in which multiple decentralized agents make sequential decisions over time to optimize some long-term performance metrics. It is challenging for the decentralized agents to make optimal sequential decisions because of the complicated coupling among the agents and across time. In this dissertation, we mainly focus on three important classes of multi-agent sequential resource sharing and exchange problems and derive optimal solutions to them.
First, we study multi-agent resource sharing problems in which self-interested agents have imperfect monitoring of the resource usage and inflict strong negative externality (i.e. strong interference and congestion) among each other. Despite of the imperfect monitoring, the strong negative externality, and the self-interested agents, we propose an optimal, distributed, easy-to-implement resource sharing policy that achieves Pareto optimal outcomes at the equilibrium. A key feature of the optimal resource sharing policy is that it is non-stationary, namely it makes decisions based on the history of past (imperfect) monitoring of the resource usages. The applications of our proposed design in wireless spectrum sharing problems enable us to triple the spectrum efficiency and achieve up to 90% energy saving, compared to state-of-the-art (stationary) spectrum sharing policies.
Second, we study multi-agent resource exchange problems, in which self-interested, anonymous agents exchange services (e.g. task solving in crowdsourcing platforms, files in peer-to-peer networks, answers in question-and-answer forums). Due to the anonymity of the agents and the lack of fixed partners, free-riding is prevalent, and can be addressed by rating protocols. We propose the first rating protocol that can achieve the social optimum at the equilibrium under imperfect monitoring of the service quality. A key feature of the optimal rating protocol is again that it is non-stationary, namely it recommends good behaviors based on the history of past rating distributions of the agents.
Finally, we study multi-agent resource sharing problems, in which each agent has an independently and stochastically changing state (whose transition may depend on the agent's action), and the agents' actions are coupled through resource sharing constraints. We propose distributed resource sharing policies that achieve the social optimum, and apply the proposed policies to demand-side management in smart grids, and joint resource allocation and packet scheduling in wireless video transmissions. The proposed policies demonstrate significant performance gains over existing myopic policies that do not take into account the state dynamics and the policies based on Lyapunov optimization that were proposed for single-agent problems.
Yuanzhang Xiao is a Ph.D candidate in the Electrical Engineering Department at UCLA, working with Prof. Mihaela van der Schaar. He received B.S and M.S. degrees from Department of Electrical Engineering at Tsinghua University. He received the dissertation year fellowship in 2013-2014. His research interests are multi-agent sequential resource sharing and exchange problems, repeated and stochastic games, with applications in wireless communications, smart grids, and social networks.