Wednesday, December 09, 2009

(Quasi) Proportional Mechanisms

Say you have a slot and multiple bids b_i's. We can assign it proportional to the bids, b_i/sum_i b_i. In a nice paper, Johari and Tsitsiklis showed that even in presence of strategic bidders, the total utility to the bidders is no worse than 3/4 of the maximum possible utility for proportional allocation. Interestingly, not much is known about analyses of revenue from such mechanisms. Uri Nadav visited for summer and studied quasi-proportional allocations where the slot is assigned proportional to f(b_i)/sum_i f(b_i), for some f. These allocations turn out to have interesting revenue properties (even without resorting to reserve prices like optimal revenue auctions do, and without prior knowledge of value distributions). Based on prior work of Uri, we could also prove the existence of unique Nash equilibria of such allocations. The paper is here. I was sorta surprised these mechanisms have not been characterized totally by now because they seem so basic, but our paper also leaves open a few analyses.



Anonymous Dimitris said...

Tsitsiklis, not Tsitkilis :))))

12:06 PM  
Anonymous Anonymous said...

Sorry, corrected. As an aside, search engines and iPhones are definitely training me to be less spelling-conscious at their sites, but beyond cut-and-paste, I have to be careful typing out of habit everywhere!

-- Metoo.

2:53 AM  

Post a Comment

<< Home