IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i3p1327-1344.html
   My bibliography  Save this article

Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks

Author

Listed:
  • Sunil Chopra

    (Kellogg School of Management, Northwestern University, Evanston, Illinois 60208)

  • Hyunwoo Park

    (Graduate School of Data Science, Seoul National University, Seoul 08826, Republic of Korea)

  • Sangho Shim

    (School of Engineering, Mathematics and Science, Robert Morris University, Moon Township, Pennsylvania 15108)

Abstract

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. Summary of Contribution: 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 paper provides an extended graph formulation of this practical revenue management problem whose LP-relaxation is shown to be very strong. The authors show that the extended graph relaxation is integral on a network without any cycle. They develop extended cycle inequalities and generalize them to zero-half cuts. Computational experiments show that the extended graph formulation results in an integer solution or a very small integrality gap. For difficult instances, the addition of zero half cuts significantly reduces the integrality gap.

Suggested Citation

  • Sunil Chopra & Hyunwoo Park & Sangho Shim, 2022. "Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1327-1344, May.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:3:p:1327-1344
    DOI: 10.1287/ijoc.2021.1148
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1148
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2021.1148?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Ernst Fehr & Klaus M. Schmidt, 1999. "A Theory of Fairness, Competition, and Cooperation," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 114(3), pages 817-868.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Agnes Bäker & Werner Güth & Kerstin Pull & Manfred Stadler, 2012. "On the Context-Dependency of Inequality Aversion - Experimental Evidence and a Stylized Model -," Jena Economics Research Papers 2012-023, Friedrich-Schiller-University Jena.
    2. Mengyuan Zhou, 2022. "Does the Source of Inheritance Matter in Bequest Attitudes? Evidence from Japan," Journal of Family and Economic Issues, Springer, vol. 43(4), pages 867-887, December.
    3. Engelhardt, Sebastian v. & Freytag, Andreas, 2013. "Institutions, culture, and open source," Journal of Economic Behavior & Organization, Elsevier, vol. 95(C), pages 90-110.
    4. David J. Cooper & Krista Saral & Marie Claire Villeval, 2021. "Why Join a Team?," Management Science, INFORMS, vol. 67(11), pages 6980-6997, November.
    5. Ellingsen, Tore & Johannesson, Magnus, 2009. "Time is not money," Journal of Economic Behavior & Organization, Elsevier, vol. 72(1), pages 96-102, October.
    6. Becchetti, Leonardo & Degli Antoni, Giacomo & Ottone, Stefania & Solferino, Nazaria, 2013. "Allocation criteria under task performance: The gendered preference for protection," Journal of Behavioral and Experimental Economics (formerly The Journal of Socio-Economics), Elsevier, vol. 45(C), pages 96-111.
    7. Mujcic, Redzo & Frijters, Paul, 2013. "Still Not Allowed on the Bus: It Matters If You're Black or White!," IZA Discussion Papers 7300, Institute of Labor Economics (IZA).
    8. Christian Thöni, 2014. "Inequality aversion and antisocial punishment," Theory and Decision, Springer, vol. 76(4), pages 529-545, April.
    9. Mononen, Lasse, 2024. "Dynamically Consistent Intergenerational Welfare," Center for Mathematical Economics Working Papers 687, Center for Mathematical Economics, Bielefeld University.
    10. Yukihiko Funaki & Emmanuel Sol & Marc Willinger, 2021. "Equal division among the few: an experiment about a coalition formation game," CEE-M Working Papers hal-03227388, CEE-M, Universtiy of Montpellier, CNRS, INRA, Montpellier SupAgro.
    11. Anne Corcos & Yorgos Rizopoulos, 2011. "Is prosocial behavior egocentric? The “invisible hand” of emotions," Post-Print halshs-01968213, HAL.
    12. Burks, Stephen V. & Carpenter, Jeffrey P. & Verhoogen, Eric, 2003. "Playing both roles in the trust game," Journal of Economic Behavior & Organization, Elsevier, vol. 51(2), pages 195-216, June.
    13. Gonzalo Olcina & Vicente Calabuig, 2015. "Coordinated Punishment and the Evolution of Cooperation," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 17(2), pages 147-173, April.
    14. Engelmann, Dirk, 2012. "How not to extend models of inequality aversion," Journal of Economic Behavior & Organization, Elsevier, vol. 81(2), pages 599-605.
    15. Adrian Bruhin & Ernst Fehr & Daniel Schunk, 2019. "The many Faces of Human Sociality: Uncovering the Distribution and Stability of Social Preferences," Journal of the European Economic Association, European Economic Association, vol. 17(4), pages 1025-1069.
    16. Friedrich Heinemann & Martin Kocher, 2013. "Tax compliance under tax regime changes," International Tax and Public Finance, Springer;International Institute of Public Finance, vol. 20(2), pages 225-246, April.
    17. Benito Arruñada & Marcos Casarin & Francesca Pancotto, 2012. "Are Self-regarding Subjects More Rational?," Working Papers 611, Barcelona School of Economics.
    18. Vollmer Uwe, 2004. "Streissler, E.W. (Hrsg.), Studien zur Entwicklung der ökonomischen Theorie XIX," Journal of Economics and Statistics (Jahrbuecher fuer Nationaloekonomie und Statistik), De Gruyter, vol. 224(6), pages 758-759, December.
    19. Emin Karagözoğlu & Elif Tosun, 2022. "Endogenous Game Choice and Giving Behavior in Distribution Games," Games, MDPI, vol. 13(6), pages 1-32, November.
    20. Amrei Lahno & Marta Serra-Garcia, 2015. "Peer effects in risk taking: Envy or conformity?," Journal of Risk and Uncertainty, Springer, vol. 50(1), pages 73-95, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:3:p:1327-1344. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.