Sunday, November 29, 2009

Budget Balanced Mechanism Design

On one fine day, in a lucky draw, I got 4 tickets for a movie show on Friday evening. Having lot of good friends, I was unable to choose 3 friends to take to the movie with me. I decided I should take those three friends who will have maximum enjoyment of the movie on that evening. However, all my friends are intelligent and rational, will report they will enjoy it most. So, I have to quantify somehow their enjoyment and get correct information about their enjoyment. I will say they have some valuations for the movie ticket. Now, as being student in game theory, I planned to use mechanism to illicit the true valuations. I will charge friends for the ticket in such a way that they will be willing to tell me their exact valuation for it. The sole purpose of charging friends is for getting some information, otherwise I am not interested in making any money. I decided I will redistribute the money collected among friends. Soon, I realised, Green-Laffont already proved that I can not design an mechanism which will allot these tickets to value it most, will illicit truth and net transfer in the money is zero. :(

This is really bad news. But have to do something. Okay. Let this ticket allotment is not budget balanced. But how much money I have to inject or I will be left with in the worst case. NO NO...what I am thinking, injecting money. Not at all, I am not going to pay to friends for them to tell me true information. So, I have to ensure that I am never going to pay from my pocket for allotting the free tickets.

So, now, in mechanism design terminology, my problem is to design an mechanism, in which the tickets are assigned to those who value it most, that is the outcome is allocatively efficient (AE). It is in best response for each agent to tell their true values, that is it is dominant strategy incentive compatible(DSIC). By being my friend and participating in mechanism nobody should get net utility to be negative, which means the mechanism is individually rational (IR) and I am not ending up paying for this mechanism, that is it is feasible (F).

Good, now I know what I want to do in terms of mechanism design. Research papers by Guo and Conitzer or by Moulin, are handy here. What did these two papers do?
(They do more than what I need, but I will describe only what I needed here.)

In these papers mainly they address the following problem:
p copies of an item are available to be distributed among n competing agents. (Objects being identical, this is referred to as homogeneous case.) As a social planner you are supposed to assign these objects to those p agents, (assuming unit demand, though the authors also work with multi unit demand, I won't talk about it here) who value it most. So, Goal is to design a mechanism that is DSIC, allocatively efficient (AE), individually rational (IR), feasible (F) for assigning p objects among n competing agents.

Now, as Groves theorem, we have to look for Groves mechanism if we need AE+DSIC. Clearly we have to use Groves payments scheme after choosing p top most bidders. The classical VCG mechanism will charge every agent (p+1)-highest bid by allotting the objects to p highest bidders.
So, we will be left will be p*(p+1)st bid. This is VCG surplus in the system. Way back in 1979, Maskin, (Noble Laureate 2007) suggested to redistribute this surplus among participating agents in such a way that other game theoretic properties are preserved. That is agents receive rebate from the mechanism. So we have to design rebate functions for n agents. In the papers by Moulin and also by Guo and Conitzer, they design rebate functions which minimizes the budget imbalance (or maximizes the fraction of the money received from VCG mechanism that gets redistributed with the proposed rebate functions) on worst case analysis. They also prove that no other mechanism can perform better than these mechanisms on the worst case analysis. And the both the mechanisms (that is, rebate functions) are identical, though they start with slightly different formulation. These nice rebate functions are linear functions of the bids of the remaining agents.

Now, what if, I had received 4 movie tickets in lucky draw which are for 4 different movies?
I will keep the one of that is most interesting for me and distribute remaining three among my friends who value them most. However, now I cannot use Moulin's or Guo's paper. Each friend may be valuing different movies in different fashion. So, now they will submit different bids for different movies. In short they will be submitting 3 real numbers to me. What will happen if there are p different objects, (that is heterogeneous objects), n agents each competing for one out of these p objects? I again started reading these two papers. I realised ohh, their rebate functions are linear in terms of bids of remaining agents. Let me also start with the similar rebate functions. Then I realised that on worst case analysis, if I have to preserve IR+AE+DSIC+F, no linear rebate function will be able to guarantee me non-zero fraction of the VCG surplus to be distributed back.

Then I started immediately conjecturing that no mechanism will be good. (Too fast to jump to conclusion, which eventually was wrong). Then soon I realised that, as opposed to homogeneous objects case, here the VCG surplus received is not linear function of the bids received. So linear functions anyway would not do well. Can there be any non-linear function which will do well. Then I just used functions from Cavello's paper or Bailey's paper applied in the heterogeneous objects case. I could prove that when there are sufficiently large number of agents, the scheme will definitely redistribute non-zero fraction OF VCG surplus. Can it be worst case optimal? Unlikely.

Then, I thought already for homogeneous case, we have optimal rebate functions. Homogeneous case is special case of heterogeneous case. That is rebate functions in my case have larger domain than homogeneous case. Can I use some kind of function extension so that if I use the new rebate functions, for homogeneous objects case the new rebate functions match with Moulin's rebate functions? Yes, I could some how rewrite the original functions in such a manner that I can use them now as well it is worst case optimal when objects are identical. However, I could not show TR+F. (They are designed in such a way that AE+DSIC are preserved). Then I did ample number of simulations and found that on the generated instances, our mechanism is IR+F and worst case optimal. The proofs are still illusive.

The other directions from impossibility of linear rebate functions guaranteeing non-zero fraction XXXX (do not want to re write whole thing, I am sure you got it what I meant here),
resitrct the domain of valuations. Suppose, the valuations of the objects are different but correlated. Like say first objects is more favourable than second one and so on. Further more this co-relation is such that, for each agent, we can derive valuations for all the objects from just a single real number. Now, the problem is simple. Though it looks like Guo's problem, it is more general than their paper. However, now private information being single dimensional, I could design an optimal mechanism in this context using approach that of Guo.

If you want to know more about mechanism design, vast literature is avaialbe on internet. (However, being rational/selfish) I would definitely recommend our tutorials on mechanism design:
Foundations of mechanism design: A tutorial Part 1-Key concepts and classical results
( or )
Foundations of mechanism design: A tutorial Part 2-Advanced concepts and results
( or

For redistribution mechanisms for heterogeneous objects: (Here you can get Moulin's paper or Guo's paper in references)
Redistribution of VCG Payments in Assignment of Heterogeneous Objects

For impossibility of linear rebate functions and linear rebate functions in co-related domains:
Redistribution Mechanisms for Assignment of Heterogeneous Objects

Chalo then,
Bye for now, Royal Sujit has to sign off...

Sujit Gujar
Research Student,
Indian Institute of Science, Bangalore.


  1. Though title is budget balanced, one cannot acheive budget balanced provided mechanism is AE+DSIC. So mechanism tries to reduce budget imbalance.

  2. I felt its too long. Its not "illicit", its "elicit".