Computation in Games and Networks

点击翻译按钮获取中文摘要

The aim of this proposal is to provide quantitative analyses of decision making, where decision makers may be single authorities, such as a network operator attempting to minimize traffic congestion, or participants in multi-agent systems such as auctions or social networks. In practice all decision makers are computationally bounded. Thus, for multi-agent systems, we need to know how computational considerations affect game-play; despite its widespread applicability and importance, there is currently little understanding with respect to this question. Furthermore, an agent's choice of action may be heavily influenced by mechanistic restrictions within the system, for example, the actual pricing mechanism used within a market or the actual routing protocol used within a network. Consequently, this proposal focuses on the implications of computational and mechanistic constraints on decision making, with a particular emphasis on applications related to networks. Thus, at a high level, we are interested in the following type of question. Can we build a cheap but functionally effective network? Can we design a market mechanism that leads to high social welfare? What are the dynamics and quality of outcomes produced by specific game-playing strategies (in particular, strategies that agents actually use rather than those prescribed by theoretical behavioural assumptions)? What are the effects of an intervention into a system? Clearly, to model and answer such questions we require tools from a wide range of areas. Towards this end, we utilize techniques from algorithm design and analysis, optimization, game theory, behavioural economics, graph theory, and causal inference.