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.