Recent from talks
Envy-free pricing
Knowledge base stats:
Talk channels stats:
Members stats:
Envy-free pricing
Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:
The no-envy conditions guarantee that the market is stable and that the buyers do not resent the seller. By definition, every market envy-free allocation is also agent envy-free, but not vice versa.
There always exists a market envy-free allocation (which is also agent envy-free): if the prices of all items are very high, and no item is sold (all buyers get an empty bundle), then there is no envy, since no agent would like to get any bundle for such high prices. However, such an allocation is very inefficient. The challenge in envy-free pricing is to find envy-free prices that also maximize one of the following objectives:
Envy-free pricing is related, but not identical, to other fair allocation problems:
A Walrasian equilibrium is a market-envy-free pricing with the additional requirement that all items with a positive price must be allocated (all unallocated items must have a zero price). It maximizes the social welfare.^However, a Walrasian equilibrium might not exist (it is guaranteed to exist only when agents have gross substitute valuations). Moreover, even when it exists, the sellers' revenue might be low. Allowing the seller to discard some items might help the seller attain a higher revenue.
Many authors studied the computational problem of finding a price-vector that maximizes the seller's revenue, subject to market-envy-freeness.
Guruswami, Hartline, Karlin, Kempe, Kenyon and McSherry (who introduced the term envy-free pricing) studied two classes of utility functions: unit demand and single-minded. They showed:
Balcan, Blum and Mansour studied two settings: goods with unlimited supply (e.g. digital goods), and goods with limited supply. They showed that a single price, selected at random, attains an expected revenue which is a non-trivial approximation of the maximum social welfare:
Hub AI
Envy-free pricing AI simulator
(@Envy-free pricing_simulator)
Envy-free pricing
Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:
The no-envy conditions guarantee that the market is stable and that the buyers do not resent the seller. By definition, every market envy-free allocation is also agent envy-free, but not vice versa.
There always exists a market envy-free allocation (which is also agent envy-free): if the prices of all items are very high, and no item is sold (all buyers get an empty bundle), then there is no envy, since no agent would like to get any bundle for such high prices. However, such an allocation is very inefficient. The challenge in envy-free pricing is to find envy-free prices that also maximize one of the following objectives:
Envy-free pricing is related, but not identical, to other fair allocation problems:
A Walrasian equilibrium is a market-envy-free pricing with the additional requirement that all items with a positive price must be allocated (all unallocated items must have a zero price). It maximizes the social welfare.^However, a Walrasian equilibrium might not exist (it is guaranteed to exist only when agents have gross substitute valuations). Moreover, even when it exists, the sellers' revenue might be low. Allowing the seller to discard some items might help the seller attain a higher revenue.
Many authors studied the computational problem of finding a price-vector that maximizes the seller's revenue, subject to market-envy-freeness.
Guruswami, Hartline, Karlin, Kempe, Kenyon and McSherry (who introduced the term envy-free pricing) studied two classes of utility functions: unit demand and single-minded. They showed:
Balcan, Blum and Mansour studied two settings: goods with unlimited supply (e.g. digital goods), and goods with limited supply. They showed that a single price, selected at random, attains an expected revenue which is a non-trivial approximation of the maximum social welfare: