Take Action

Home | Faculty & Research Overview | Research

Research Details

Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks, Informs journal of computing


The inequity aversion pricing problem aims to maximize revenue while providing prices to people connected in a social network such that connected people receive prices that are not too different. This problem is known to be NP-hard even when the number of prices offered is three. This paper provides an extended graph formulation for the problem whose LP-relaxation is shown to be very strong. We show that the extended graph relaxation is integral on a network without any cycle. We develop extended cycle inequalities and show that the extended cycle inequalities cut off all the fractional extreme points of the extended graph relaxation on a cycle. We generalize cycle inequalities to zero half cuts performing a Chvátal–Gomory procedure on a cycle. Computational experiments show that the extended graph relaxation results in an integer solution for most problem instances with very small gaps (less than 3%) from optimality for the remaining instances. The addition of zero half cuts reduces the integrality gap significantly on the few difficult instances.




Sunil Chopra, Sangho Shim, H. Park

Date Published



Chopra, Sunil, Sangho Shim, and H. Park. 2022. Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks. Informs journal of computing.(3): 1327-1344.


Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more


Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.


Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more