Undominated Groves Mechanisms

Details Undominated Groves Mechanisms Undominated Groves Mechanisms

2012-03-08

arxiv.org/abs/1203.1809v1

Computer Science

Computer Science and Game Theory

42 pages

Scientific paper

The family of Groves mechanisms, which includes the well-known VCG mechanism (also known as the Clarke mechanism), is a family of efficient and strategy-proof mechanisms. Unfortunately, the Groves mechanisms are generally not budget balanced. That is, under such mechanisms, payments may flow into or out of the system of the agents, resulting in deficits or reduced utilities for the agents. We consider the following problem: within the family of Groves mechanisms, we want to identify mechanisms that give the agents the highest utilities, under the constraint that these mechanisms must never incur deficits. We adopt a prior-free approach. We introduce two general measures for comparing mechanisms in prior-free settings. We say that a non-deficit Groves mechanism $M$ {\em individually dominates} another non-deficit Groves mechanism $M'$ if for every type profile, every agent's utility under $M$ is no less than that under $M'$, and this holds with strict inequality for at least one type profile and one agent. We say that a non-deficit Groves mechanism $M$ {\em collectively dominates} another non-deficit Groves mechanism $M'$ if for every type profile, the agents' total utility (social welfare) under $M$ is no less than that under $M'$, and this holds with strict inequality for at least one type profile. The above definitions induce two partial orders on non-deficit Groves mechanisms. We study the maximal elements corresponding to these two partial orders, which we call the {\em individually undominated} mechanisms and the {\em collectively undominated} mechanisms, respectively.

Affiliated with

Also associated with

No associations

Rating

Undominated Groves Mechanisms 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 Undominated Groves Mechanisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Undominated Groves Mechanisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-17453