Mechanism Design for Risk Averse Sellers

Details Mechanism Design for Risk Averse Sellers Mechanism Design for Risk Averse Sellers

2011-07-24

arxiv.org/abs/1107.4722v2

Computer Science

Computer Science and Game Theory

Scientific paper

We design efficient algorithms to compute truthful mechanisms for risk-averse sellers, in Bayesian single-parameter and multi-parameter settings. We model risk aversion by a concave utility function, where the the seller maximizes its expected utility. Much earlier work on Bayesian mechanism design has focused on maximizing expected revenue, and no succinct characterization of expected utility maximizing mechanism is known even for multi-unit auctions. We design a poly-time algorithm for multi-unit auctions, to compute a randomized sequential posted pricing mechanism (SPM) that for any $\eps > 0$, yields a $(1-1/e-\eps)$-approximation to the expected utility of an optimal mechanism. In comparison, the best known approximation factor using SPM is $(1-1/e)$ even for the expected revenue objective (linear utility). Our result is based on a clever application of a correlation gap bound, along with {\em splitting} and {\em merging} of random variables to redistribute probability mass across buyers. This allows us to reduce the problem to checking feasibility of a set of $2^{\poly(1/\epsilon)}$ distinct configurations, each of which corresponds to a linear covering program. A feasible solution to the program gives us the distribution on prices for each buyer to use in the randomized SPM. We check the feasibility of each configuration and pick the best mechanism. Our technique extend to the multi-parameter setting with unit demand buyers, and we design a poly-time algorithm to compute a $\frac{(1-1/e)}{6.75}- \eps > 0.63/6.75$-approximation. In comparison, the best known guarantee of an efficient mechanism to maximize expected revenue in unit-demand setting is 1/4. We believe that our techniques will be useful in handling risk aversion in other stochastic optimization problems.

Affiliated with

Also associated with

No associations

Rating

Mechanism Design for Risk Averse Sellers 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 Mechanism Design for Risk Averse Sellers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism Design for Risk Averse Sellers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-76430