Further Enquiries

School of Computer Science
Ingkarni Wardli Building
The University of Adelaide
SA 5005
AUSTRALIA
Email

Telephone: +61 8 8313 5586
Facsimile: +61 8 8313 4366

Algorithmic Game Theory

Coordinator: Dr Mingyu Guo

Computationally Feasible Automated Mechanism Design

Electronic markets such as Internet advertisement auctions are among the emerging driving forces for economic growth. Market mechanisms are also powerful tools for making social decisions. For example, it can help resolve conflict during the allocation of limited resources among competing parties. Computer scientists are interested in market design for two main reasons. First, the development of Internet has led to novel and influential electronic markets, accompanied by new computational challenges. Second, computational techniques enable us to design new market mechanisms that are more complex and larger in scale. More importantly, computational techniques enable the idea of automated mechanism design, which aims to design new market mechanisms in an automated fashion, instead of relying on manual effort.

Mechanism Design: Mechanism design deals with economic systems involving multiple agents. A mechanism is a set of rules that map the agents’ preferences to social decisions. For example, a school allocation mechanism maps the students’ preferences over schools to an assignment of students to schools. Sometimes, the decision also involves payments. For example, an Internet advertisement auction mechanism maps the advertisers’ preferences over different advertising slots to an arrangement of the advertisements, as well as some corresponding payments. Mechanism design studies how to design mechanism rules that optimize certain objective while enforcing certain constraints. Typical objectives include welfare maximization and revenue maximization. A typical constraint is that the mechanism should encourage truthful reporting. It should be noted that the mechanism makes decisions based on the agents’ reported preferences, so a manipulative agent may lie about his preference in order to reach a better social decision for himself, which may be bad for the others. A truthful mechanism ensures that under its rules, no agents can benefit by misreporting.

Automated Mechanism Design: Traditionally, economists have designed mechanisms manually. Automated mechanism design aims to automate the mechanism design process using computational techniques. The basic idea is to model the design process as a functional optimization problem. Essentially, if we express the agents’ preferences and the possible social decisions using numeric terms, then a mechanism is just a complex function whose domain and range are both multi-dimensional. The original idea of automated mechanism design is based on the following observation. If the number of possible reports from the agents is finite, then the functional optimization problem reduces to a linear/integer program, which can then be solved computationally. Unfortunately, albeit elegant, this approach only works for tiny problem instances, because the number of variables in the reduced model is exponential. Nevertheless, straightforward automated mechanism design is still valuable, because solutions to small problem instances may provide general insights.

Computationally Feasible Automated Mechanism Design: The basic idea of computationally feasible automated mechanism design is to avoid functional optimization by restricting attention to a parameterized family of candidate mechanisms. The candidate mechanisms are hand-picked to be truthful and feasible. As a result of the restriction, optimal mechanisms within the family can be solved via value optimization (we only need to tweak the parameters). In some occasions, mechanisms obtained by optimizing within the restricted family turn out to be globally optimal or close to global optimality.

The project aims to advance the theory and applications of computationally feasible automated mechanism design.

Selected Publications

  • Computationally Feasible Automated Mechanism Design: General Approach and Case Studies
    Mingyu Guo and Vincent Conitzer
    AAAI 2010 (new scientific and technical advances in research track)
  • Increasing VCG Revenue by Decreasing the Quality of Items
    Mingyu Guo, Argyrios Deligkas, and Rahul Savani
    AAAI 2014
  • Revenue Maximization via Hiding Item Attributes
    Mingyu Guo and Argyrios Deligkas
    IJCAI 2013
  • Undominated Groves Mechanisms
    Mingyu Guo, Evangelos Markakis, Krzysztof R. Apt, and Vincent Conitzer
    Journal of Artificial Intelligence Research, Volume 46, Page 129-163, January 2013
  • Worst-Case Optimal Redistribution of VCG Payments in Heterogeneous-Item Auctions with Unit Demand
    Mingyu Guo
    AAMAS 2012
  • VCG Redistribution with Gross Substitutes
    Mingyu Guo
    AAAI 2011
  • Optimal-in-Expectation Redistribution Mechanisms
    Mingyu Guo and Vincent Conitzer
    Artificial Intelligence, Volume 174, Issue 5-6, Pages 363-381, April 2010
  • Worst-Case Optimal Redistribution of VCG Payments in Multi-Unit Auctions
    Mingyu Guo and Vincent Conitzer
    Games and Economic Behavior, Volume 67, Issue 1, Page 69-98, September 2009

Social Choice

Solving Hard Control Problems in Voting Systems via Integer Programming

Sergey Polyakovskiy, Rudolf Berghammer, and Frank Neumann

We address various voting systems and types of control of elections and show how hard control problems can be modeled as integer programs. By means of the off-the-shelf solver Cplex we then demonstrate that the approach allows to treat the control of larger elections successfully. As a consequence, the hardness of a certain control problem is not a secure protection for the fraudulent falsification of outcomes of elections using this type of manipulation.

arXiv link