University of Southampton

Computational Economics

Computational economics is a core part of the AIC research agenda and applies game-theoretic and market-based economic principles to the design and understanding of multi-agent systems. Research areas include algorithmic game theory, coalition formation, mechanism design, automated negotiation, social choice, and agent-based computational economics. Applications include sponsored search, cloud computing, the smart grid, e-business, and disaster management.

Our research in computational economics focuses on the following areas.

Algorithmic game theory is a new and exciting area of research on the intersection of economics and theoretical computer science. Its results have found applications in a wide range of real life domains, such as international affairs, coalition formation in parliament, multi-robot coordination, job scheduling, auction design, peer-to-peer file sharing, and, most notably, the internet. Algorithmic game theory combines the ideas and techniques from game theory and algorithm design, with the aim of developing appropriate algorithms for strategic environments, where multiple self-interested agents interact. In addition to the strategic considerations analysed in classical game theory, algorithmic game theory considers whether and how the theoretical solution concepts, such as Nash equilibrium, can be applied in practice. In particular, it involves determining the feasibility of certain approaches by considering their computational complexity, as well as designing approximate algorithms when computing optimal solutions is intractable. The aim is then to design computationally tractable algorithms which have good approximation ratios, and at the same time maintain their economic properties. 

Coalition formation  is also concerned with strategic environments, and focuses on situations where groups of self-interested agents come together to achieve a set of joint goals. Such situations arise in various domains, from political lobbies and customs unions, to production cartels and multi-agent systems.  Example applications in multi-agent systems include disaster response, where different stakeholders need to share their resources to achieve various tasks such as saving civilians; sensor networks  where different sensors need to work together to achieve missions such as tracking targets; and group buying networks where groups of agents form a coalition to take advantage of quantity discounts. Key challenges in this area include the computation of optimal coalitions, which takes maximum advantage of the synergies between agents, as well as computing stable coalitions whereby no group of agents has an incentive to deviate and form their own coalition. 

Social choice addresses a central problem in multi-agent systems and is concerned with how groups of agents with different interests arrive at a collective decision, such as deciding which subset of tasks to execute, a joint plan of action, or a specific allocation of resources. Social choice considers the mechanisms, such as voting, by which disparate agents can reconcile their differences. In particular, given that agents may have incentives to vote strategically and hide their real interests, much of the research involves exploring different mechanisms for minimising or even eliminating such manipulations.

Mechanism design studies the design of incentives in order to build systems where individual agents, be they humans or software agents, would act in a way that satisfies the goals of the system as a whole. A prime example is the allocation of tasks and resources through auctions, where the system goal is to allocate the tasks to those agents who are most able to execute them, or to allocate the resources to those who value them the most. Unlike cooperative systems where techniques such as decentralised optimisation can be used to perform such allocations, mechanism design applies to systems which consist of different stakeholders, and where agents may have conflicting goals and preferences. The aim is to make these agents, through appropriate rewards and penalties such as monetary payments or reputation values, to act in a way that is consistent with the global goals of the system. For instance, in the auction example, it is important to incentivise the agents to be truthful about their capabilities and preferences such that appropriate allocations can be made. Furthermore, unlike social choice, where the decisions are global and affect all of the agents, mechanism design considers local decisions that affect individual agents.

Automated negotiation studies computational approaches to resolve conflicts between two or more agents by means of negotiation. Such situations arise, for example, when software agents need to agree on an the exchange of resources, the scheduling of appointments, and other situations where agents have conflicts of interest. Negotiation typically involves an iterative process whereby agents exchange offers and counter offers. The advantage of using machines to automate this process is that the computer can negotiate much more effectively in a number of ways. Specifically, automated negotiation allows for a large number of offers to be exchanged in a short period of time, the offers can be of a complex nature (consisting of not just the price, but include many other factors such as quality of service, duration, and other terms and conditions), negotiation can occur concurrently between a number of agents, and overall negotiation time can be significantly reduced.

Agent-based computational economics is concerned with reproducing system-wide phenomena from the real world, such as financial bubbles and crashes, using relatively simple agents, where the complexity arises through the interaction among the agents. The aim is to find the fundamental features that could explain the observed phenomena, and how changes in system variables, such as government policy and market structure, could affect the outcome of a system. This is mostly achieved through computational simulations.