TY - GEN
T1 - Envy-free pricing in multi-item markets
AU - Chen, Ning
AU - Deng, Xiaotie
PY - 2010
Y1 - 2010
N2 - In this paper, we study the revenue maximization envy-free pricing in multi-item markets: there are m items and n potential buyers where each buyer is interested in acquiring one item. The goal is to determine allocations (a matching between buyers and items) and prices of all items to maximize the total revenue given that all buyers are envy-free. We give a polynomial time algorithm to compute a revenue maximization envy-free pricing when every buyer evaluates at most two items a positive valuation, by reducing it to an instance of weighted independent set in a perfect graph and applying the Strong Perfect Graph Theorem. We complement our result by showing that the problem becomes NP-hard if some buyers are interested in at least three items. Next we extend the model to allow buyers to demand a subset of consecutive items, motivated from TV advertising where advertisers are interested in different consecutive slots with different valuations and lengths. We show that the revenue maximization envy-free pricing in this setting can be computed in polynomial time. © 2010 Springer-Verlag Berlin Heidelberg.
AB - In this paper, we study the revenue maximization envy-free pricing in multi-item markets: there are m items and n potential buyers where each buyer is interested in acquiring one item. The goal is to determine allocations (a matching between buyers and items) and prices of all items to maximize the total revenue given that all buyers are envy-free. We give a polynomial time algorithm to compute a revenue maximization envy-free pricing when every buyer evaluates at most two items a positive valuation, by reducing it to an instance of weighted independent set in a perfect graph and applying the Strong Perfect Graph Theorem. We complement our result by showing that the problem becomes NP-hard if some buyers are interested in at least three items. Next we extend the model to allow buyers to demand a subset of consecutive items, motivated from TV advertising where advertisers are interested in different consecutive slots with different valuations and lengths. We show that the revenue maximization envy-free pricing in this setting can be computed in polynomial time. © 2010 Springer-Verlag Berlin Heidelberg.
UR - https://www.scopus.com/pages/publications/77955325776
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-77955325776&origin=recordpage
U2 - 10.1007/978-3-642-14162-1_35
DO - 10.1007/978-3-642-14162-1_35
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3642141617
SN - 9783642141614
VL - 6199 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 418
EP - 429
BT - Automata, Languages and Programming
PB - Springer Verlag
T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010
Y2 - 6 July 2010 through 10 July 2010
ER -