Algorithmic Economics & Operations Research

Our research focuses on the analysis and optimization of economic processes in general. Our aim is to develop models, algorithms, and economic mechanisms for the improvement of social welfare.
Topics include the analysis and design of economic mechanisms with multiple decision makers (auctions, matching, voting, etc.), the design of algorithms to solve managerial resource allocation and scheduling problems, and the analysis of data in the context of predictive analytics. We analyze game-theoretical as well as algorithmic properties of economic mechanisms, and evaluate their performance in the lab and in the field.
Our work is rooted in combinatorial optimization, game theory, mechanism design, and social choice theory, but also requires tools and techniques from algorithm design and complexity theory. While these areas have been separate academic disciplines in the past, much recent research at the intersection of computer science, matematics, management science, and economics combines respective methods to design new types of economic mechanisms. Examples include new types of combinatorial auction mechanisms for the allocation of spectrum licenses or other private or public assets, new optimization techniques for kidney exchanges, and stable matching algorithms for course assignment at universities. All these examples consider computational aspects, as well as incentives and strategies of multiple decision makers to achieve globally optimal solutions. The cluster includes an outstanding combination of internationally recognized experts in algorithms, game theory, mechanism design, and experimental economics, who have contributed to theory, but also to a variety of important and challenging real-world problems.

Scientists

Graduate Program "Advanced Optimization in the Networked Economy" (AdONE)

A new Research Training Group approved by the DFG is the new Graduate Program “Advanced Optimization in the Networked Economy (AdONE)”. Due to an increasingly interconnected economy, multiple decision-makers are typically involved in resource control, and large data sets are available allowing for new optimization methods for the efficient use of resources. The Graduate Program conducts research in operations research and management science to develop models and processes that aim at the efficient use of resources through intelligent planning and control. Professors Susanne Albers and Martin Bichler are members of the new Graduate Program.

Exemplary Projects

Design of a Combinatorial Exchange for the Trade of Fishery Rights

The project is concerned with the design and development of software for allocation and pricing of fishery shares. The auction rules draw on mathematical programming techniques to solve underlying optimization problems. A formal analysis focuses on economic properties such as robustness against manipulation and fairness of the payment rules.

An Axiomatic and Computational Study of Probabilistic Social Choice

The goal of this project is to investigate the axiomatic properties of probabilistic social choice functions, i.e., functions that aggregate the preferences of individual agents to socially acceptable probabilistic outcomes. Probabilistic social choice is gaining increasing attention in economics and computer science and has many applications in special domains of interest such as random assignment and matching markets.

Auction Design for Procurement Markets with Economies of Scale and Scope

Design and development of a solver for the optimal selection of suppliers in markets with economies of scale and scope. Bids in such markets include various types of volume discounts. The project designed corresponding mathematical optimization problems, analyzed the computational complexity, and developed effective algorithms for allocation and pricing. The project won an HP Labs eAward.

Dynamic Resource Allocation in Cloud Data Centers

Design and development of algorithms for static and dynamic resource allocation in cloud data centers. The problems require solving very high-dimensional packing problems. We draw on mathematical programming and matrix approximation techniques, and show that allocation problems with hundreds of virtual machines can be solved to near-optimality. Initial results received the INFORMS Design Science Award.

Preference Over Sets in Coalition Formation and Strategic Voting

This project focusses on two related topics from computational social choice and algorithmic game theory: manipulability of voting rules and efficient coalition formation in hedonic games. We argue that, in both settings, lifting the resoluteness requirement is a promising way of achieving robustness against manipulability. Doing so requires a proper formal understanding of the different ways in which preferences over outcomes can be extended to preferences over sets of outcomes. Specifically, we plan to pursue four objectives in this context, namely (i) to investigate which non-resolute voting rules are strategyproof according to common types of preference extensions, (ii) to study the computational complexity of stable partitions in hedonic games, (iii) to construct non-resolute strategyproof mechanisms for reaching stable partitions, and (iv) to explore the applicability of generalized tournament solutions to hedonic games.

Poster