The paper Incentive Compatible Budget Elicitation in Multi-unit Auctions by Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia has recently been uploaded to the arXiv.

The basic model that they study is the auction of a single infinitely divisible good among bidders with budget limits. In the model each bidder has a private value and private budget . The utility of when allocated units of the infinitely divisible good and charged is assumed to be but only if the *budget is not exceeded*, . If then the utility is assumed to be negative infinity.

The twist in this model is the budget limit which takes us out of the quasi-linear model usually assumed in auction theory. In particular VCG mechanisms are no longer incentive compatible. A previous paper by Shahar Dobziniski, Ron Lavi, and myself shows that indeed there is no (anonymous) incentive compatible mechanism that produces Pareto-optimal allocations. This paper shows that there is such a *randomized* mechanism.

The paper starts with the mechanism that was previously shown to be incentive compatible in the special case that the budgets are *public knowledge* (an adaptive version of Ausubel’s auction). The heart of the proof lies in an analysis showing that the only way a bidder can gain by mis-reporting his budget is by over-reporting; under-reporting is never profitable. This requires quite a delicate analysis (which I didn’t fully read yet) but once this characterization is known, an incenive compatible randomized mechanism follows immediately: run the original mechanism, and instead of asking a bidder to pay , ask him to pay with probability . The expected payments have not changed so under-reporting is still not profitable, and this randomized payment makes over-reporting result in a postive probability of getting negative infinite utility and thus is certainly not profitable.

### Like this:

Like Loading...

Read Full Post »