Envy, Multi Envy, and Revenue Maximization

Details Envy, Multi Envy, and Revenue Maximization Envy, Multi Envy, and Revenue Maximization

2009-09-24

arxiv.org/abs/0909.4569v1

Computer Science

Computer Science and Game Theory

Scientific paper

We study the envy free pricing problem faced by a seller who wishes to maximize revenue by setting prices for bundles of items. If there is an unlimited supply of items and agents are single minded then we show that finding the revenue maximizing envy free allocation/pricing can be solved in polynomial time by reducing it to an instance of weighted independent set on a perfect graph. We define an allocation/pricing as \textit{multi envy free} if no agent wishes to replace her allocation with the union of the allocations of some set of other agents and her price with the sum of their prices. We show that it is \textit{coNP}-hard to decide if a given allocation/pricing is multi envy free. We also show that revenue maximization multi envy free allocation/pricing is \textit{APX} hard. Furthermore, we give efficient algorithms and hardness results for various variants of the highway problem.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-325125