Computer Science – Computer Science and Game Theory
Scientific paper
2010-03-27
Computer Science
Computer Science and Game Theory
Scientific paper
We study mechanisms for an allocation of goods among agents, where agents have no incentive to lie about their true values (incentive compatible) and for which no agent will seek to exchange outcomes with another (envy-free). Mechanisms satisfying each requirement separately have been studied extensively, but there are few results on mechanisms achieving both. We are interested in those allocations for which there exist payments such that the resulting mechanism is simultaneously incentive compatible and envy-free. Cyclic monotonicity is a characterization of incentive compatible allocations, local efficiency is a characterization for envy-free allocations. We combine the above to give a characterization for allocations which are both incentive compatible and envy free. We show that even for allocations that allow payments leading to incentive compatible mechanisms, and other payments leading to envy free mechanisms, there may not exist any payments for which the mechanism is simultaneously incentive compatible and envy-free. The characterization that we give lets us compute the set of Pareto-optimal mechanisms that trade off envy freeness for incentive compatibility.
Cohen Edith
Feldman Michal
Fiat Amos
Kaplan Haim
Olonetsky Svetlana
No associations
LandOfFree
On the Interplay between Incentive Compatibility and Envy Freeness 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 On the Interplay between Incentive Compatibility and Envy Freeness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Interplay between Incentive Compatibility and Envy Freeness will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-127514