The algorithmic decision theory group at Data61 (ADT@Data61) works in two rapidly developing areas at the intersection of mathematical social science and computer science — algorithmic game theory and computational social choice.
These fields focus on a two-way exchange of ideas: how can we apply ideas from computer science, such as algorithms and complexity theory, to aspects of mathematical social sciences? Likewise, how can we incorporate results and ideas from mathematical social sciences, such as market design and preferences, and use the results in computer science and artificial intelligence?
The ADT group considers many fundamental questions that arise when self-interested agents interact in mutliagent environments. Our broad goal is to develop the theory, tools, and techniques to analyse rational behaviour and to propose mechanisms to aggregate possibly conflicting preferences in areas like resource allocation, voting, and auctions.
Everyone wants the best piece of cake, or the first pick when selecting your side for Oz tag, but we all cannot have it. Often people need to split objects, be they people, food, or landing slots at an airport, between a large group of people. As these allocation tasks become more complicated, with more variables and actors, we need to use algorithmic ideas from computer science to help scale up many of the mechanisms designed in mathematical social sciences.
We investigate many aspects of resource allocation — for many different stakeholders. We are currently involved with helping FoodBank Local design mechanisms to support fair, just in time delivery of food donations to multiple shelters throughout Australia. Our expertise lies both in designing mechanisms and evaluating axiomatic and strategic aspects of allocating divisible and indivisible goods, resources, or chores in both centralised and decentralised settings. These algorithms have applications in diverse fields such as scheduling, matching markets, and security.
Occasionally, countries come together to make a group decision about who will be in charge. However, much more often we must decide where to go for dinner with our friends; search and recommendation engines compute the best restaurant to visit or the most relevant webpage for your query thousands of times per second. The idea of making a decision from a large set of alternatives is similar, but the scale is radically different.
Our group has expertise in several research areas related to voting, including performing axiomatic analysis of voting protocols; developing languages and frameworks to express preferences; designing algorithms to identify structure in preference profiles; and leveraging our preference library PrefLib as a platform and library for handling preferences in computational social choice. We apply these tools and techniques to the broader computer science fields of recommender systems, data mining, and machine learning.
Students typically have preferences over the schools they want to attend. At the same time, schools often have preferences over the students they want to accept. Somehow we have to match students to schools, residents to hospitals, or kidneys to patients. The algorithms and techniques used must be fair; take into account the preferences and constraints of the agents; and return results in a reasonable amount of time.
The members of ADT have experience in both modelling matching markets and developing algorithms for clearing matching markets in both one-sided and two-sided settings.
When deciding how to deliver goods to multiple locations, or what parts of a power grid to upgrade, it is often better for agents to work together. The cost of a new grid can be split over all the houses that will receive benefit from it; and just like car pooling, stores can benefit if delivery companies pool their deliveries to achieve lower costs.
Using aspects of cooperative game theory, the ADT group is creating better models and algorithms for cost and profit allocation in logistics and transport settings. The results in these areas can be used by our commercial partners to save money and go greener in their efforts to serve the customers in Australia and across the world.
This short educational video presents the fundamental topics in algorithmic decision theory. It was awarded the “Most Educational Video” prize at the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013).