NDLI: Optimal Envy-Free Pricing with Metric Substitutability

Please wait, while we are loading the content...

Optimal Envy-Free Pricing with Metric Substitutability

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Chen, Ning Vassilvitskii, Sergei Ghosh, Arpita
Copyright Year	2011
Abstract	We study the unit-demand envy-free pricing problem faced by a profit-maximizing seller with unlimited supply when there is metric substitutability among the itemsconsumer i's value for item j is $v_i-c_{i,j}$, and the substitution costs, $\{c_{i,j}\}$, form a metric. Our model is motivated by the observation that sellers often sell the same product at different prices in different locations, and rational consumers optimize the tradeoff between prices and substitution costs. While the general envy-free pricing problem is hard to approximate, we show that the problem of maximizing revenue with metric substitutability among items can be solved exactly in polynomial time. We do this by first showing that in any optimal price vector, the set of nodes that pay exactly their value uniquely determines which nodes buy an item and what price they pay, and therefore the revenue. We transform the problem of finding an optimal set of such nodes to an instance of weighted independent set on a perfect graph which can be solved in polynomial time by the strong perfect graph theorem, proving the result. We then analyze the computational tractability of various extensions to our model. We begin with relaxing the metric substitutability requirement and show that when the substitution costs do not form a metric, even if a $(1+\epsilon)$-approximate triangle inequality holds, the problem becomes NP-hard. Thus the triangle inequality characterizes the threshold at which the problem goes from tractable to hard. We then relax assumptions on the supply and demand. We consider restricting supplies to a subset of locations, or the amount of supplies, or allowing buyers to demand more than one unit. In all cases, the problem becomes NP-hard. In addition, the multiunit demand case illustrates an interesting paradoxical nonmonotonicity: The optimal revenue the seller can extract can actually decrease when consumers' demands increase. We show the revenue maximization problem with multiunit demand is APX-hard even for the simplest valuations with equal marginal values for all items up to the demand constraint, and demands of at most 3.
Starting Page	623
Ending Page	645
Page Count	23
File Format	PDF
ISSN	00975397
DOI	10.1137/080740970
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3 (Special Section on Foundations of Computer Science)
Volume Number	40
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2011-05-26
Access Restriction	Subscribed
Subject Keyword	strong perfect graph theorem General envy-free pricing Price theory and market structure algorithm
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in