Frugality ratios and improved truthful mechanisms for vertex cover

Details Frugality ratios and improved truthful mechanisms for vertex cover Frugality ratios and improved truthful mechanisms for vertex cover

2006-06-09

arxiv.org/abs/cs/0606044v4

Computer Science

Computer Science and Game Theory

26 pages, 5 figures (minor revision of the previous version)

Scientific paper

In {\em set-system auctions}, there are several overlapping teams of agents, and a task that can be completed by any of these teams. The buyer's goal is to hire a team and pay as little as possible. Recently, Karlin, Kempe and Tamir introduced a new definition of {\em frugality ratio} for this setting. Informally, the frugality ratio is the ratio of the total payment of a mechanism to perceived fair cost. In this paper, we study this together with alternative notions of fair cost, and how the resulting frugality ratios relate to each other for various kinds of set systems. We propose a new truthful polynomial-time auction for the vertex cover problem (where the feasible sets correspond to the vertex covers of a given graph), based on the {\em local ratio} algorithm of Bar-Yehuda and Even. The mechanism guarantees to find a winning set whose cost is at most twice the optimal. In this situation, even though it is NP-hard to find a lowest-cost feasible set, we show that {\em local optimality} of a solution can be used to derive frugality bounds that are within a constant factor of best possible. To prove this result, we use our alternative notions of frugality via a bootstrapping technique, which may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Frugality ratios and improved truthful mechanisms for vertex cover 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 Frugality ratios and improved truthful mechanisms for vertex cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Frugality ratios and improved truthful mechanisms for vertex cover will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-543470