Budget Feasible Mechanism Design via Random Sampling

Details Budget Feasible Mechanism Design via Random Sampling Budget Feasible Mechanism Design via Random Sampling

2011-07-15

arxiv.org/abs/1107.2994v2

Computer Science

Computer Science and Game Theory

Updated version please refer to http://arxiv.org/abs/1203.4455

Scientific paper

Budget feasible mechanism considers algorithmic mechanism design questions where there is a budget constraint on the total payment of the mechanism. An important question in the field is that under which valuation domains there exist budget feasible mechanisms that admit `small' approximations (compared to a socially optimal solution). Singer \cite{PS10} showed that additive and submodular functions admit a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer \cite{DPS11} gave an $O(\log^2n)$ approximation mechanism for subadditive functions and remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive function." In this paper, we give the first attempt to this question. We give a polynomial time $O(\frac{\log n}{\log\log n})$ sub-logarithmic approximation ratio mechanism for subadditive functions, improving the best known ratio $O(\log^2 n)$. Further, we connect budget feasible mechanism design to the concept of approximate core in cooperative game theory, and show that there is a mechanism for subadditive functions whose approximation is, via a characterization of the integrality gap of a linear program, linear to the largest value to which an approximate core exists. Our result implies in particular that the class of XOS functions, which is a superclass of submodular functions, admits a constant approximation mechanism. We believe that our work could be a solid step towards solving the above fundamental problem eventually, and possibly, with an affirmative answer.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-225954