Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions

Details Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions

2010-08-10

arxiv.org/abs/1008.1616v1

Computer Science

Computer Science and Game Theory

16 pages

Scientific paper

We design algorithms for computing approximately revenue-maximizing {\em sequential posted-pricing mechanisms (SPM)} in $K$-unit auctions, in a standard Bayesian model. A seller has $K$ copies of an item to sell, and there are $n$ buyers, each interested in only one copy, who have some value for the item. The seller must post a price for each buyer, the buyers arrive in a sequence enforced by the seller, and a buyer buys the item if its value exceeds the price posted to it. The seller does not know the values of the buyers, but have Bayesian information about them. An SPM specifies the ordering of buyers and the posted prices, and may be {\em adaptive} or {\em non-adaptive} in its behavior. The goal is to design SPM in polynomial time to maximize expected revenue. We compare against the expected revenue of optimal SPM, and provide a polynomial time approximation scheme (PTAS) for both non-adaptive and adaptive SPMs. This is achieved by two algorithms: an efficient algorithm that gives a $(1-\frac{1}{\sqrt{2\pi K}})$-approximation (and hence a PTAS for sufficiently large $K$), and another that is a PTAS for constant $K$. The first algorithm yields a non-adaptive SPM that yields its approximation guarantees against an optimal adaptive SPM -- this implies that the {\em adaptivity gap} in SPMs vanishes as $K$ becomes larger.

Affiliated with

Also associated with

No associations

Rating

Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Schemes for Sequential Posted Pricing in Multi-Unit Auctions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-582710