IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v253y2017i1d10.1007_s10479-016-2320-3.html
   My bibliography  Save this article

Method of Digraphs for Multi-dimensional Screening

Author

Listed:
  • Sergey Kokovin

    (National Research University Higher School of Economics, Russian Federation
    Novosibirsk State University)

  • Babu Nahata

    (University of Louisville)

Abstract

We study a general model of multi-dimensional screening for discrete types of consumers without the single-crossing condition or any other essential restrictions. Such generality motivates us to introduce graph theory into optimization by treating each combination of active constraints as a digraph. Our relaxation of the constraints (a slackness parameter) excludes bunching and cycles among the constraints. Then, the only possible solution structures are rivers, which are acyclic rooted digraphs, and the Lagrange multipliers can be used to characterize the solutions. Relying on these propositions, we propose and justify an optimization algorithm. In the experiments, its branch-and-bound version with a good starting plan shows fewer iterations than a complete search among all rivers.

Suggested Citation

  • Sergey Kokovin & Babu Nahata, 2017. "Method of Digraphs for Multi-dimensional Screening," Annals of Operations Research, Springer, vol. 253(1), pages 431-451, June.
    • Handle: RePEc:spr:annopr:v:253:y:2017:i:1:d:10.1007_s10479-016-2320-3
    DOI: 10.1007/s10479-016-2320-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-016-2320-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-016-2320-3?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Andersson, Tommy, 2008. "Efficiency properties of non-linear pricing schedules without the single-crossing condition," Economics Letters, Elsevier, vol. 99(2), pages 364-366, May.
    2. Brito, Dagobert L, et al, 1990. "Pareto Efficient Tax Structures," Oxford Economic Papers, Oxford University Press, vol. 42(1), pages 61-77, January.
    3. Jean-Charles Rochet & Philippe Chone, 1998. "Ironing, Sweeping, and Multidimensional Screening," Econometrica, Econometric Society, vol. 66(4), pages 783-826, July.
    4. Rachel R. Chen & Esther Gal-Or & Paolo Roma, 2014. "Opaque Distribution Channels for Competing Service Providers: Posted Price vs. Name-Your-Own-Price Mechanisms," Operations Research, INFORMS, vol. 62(4), pages 733-750, August.
    5. Babu Nahata & Serguei Kokovin & Evgeny Zhelobodko, 2003. "Self-Selection Under Non-Ordered Valuations: Type-Splitting, Envy-Cycles, Rationing And Efficiency," General Economics and Teaching 0307001, University Library of Munich, Germany.
    6. Kokovin, S. & Nahata, B. & Zhelobodko, E., 2011. "All Solution Graphs in Multidimensional Screening," Journal of the New Economic Association, New Economic Association, issue 11, pages 10-38.
    7. Araujo, Aloisio & Moreira, Humberto, 2010. "Adverse selection problems without the Spence-Mirrlees condition," Journal of Economic Theory, Elsevier, vol. 145(3), pages 1113-1141, May.
    8. Kokovin, Sergey & Nahata, Babu & Zhelobodko, Evgeny, 2010. "Multidimensional screening under nonlinear costs: Limits of standard approach," Economics Letters, Elsevier, vol. 107(2), pages 263-265, May.
    9. Blundell,Richard & Newey,Whitney K. & Persson,Torsten (ed.), 2006. "Advances in Economics and Econometrics," Cambridge Books, Cambridge University Press, number 9780521871525.
    10. Mark Armstrong & Robert Porter (ed.), 2007. "Handbook of Industrial Organization," Handbook of Industrial Organization, Elsevier, edition 1, volume 3, number 1.
    11. Blundell,Richard & Newey,Whitney K. & Persson,Torsten (ed.), 2006. "Advances in Economics and Econometrics," Cambridge Books, Cambridge University Press, number 9780521692083.
    12. Kokovin, Sergey & Nahata, Babu & Zhelobodko, Evgeny, 2013. "Dupuit conjecture for constrained screening: Overall distortion and type-partitioning," Economics Letters, Elsevier, vol. 118(3), pages 439-441.
    13. Guesnerie, Roger & Seade, Jesus, 1982. "Nonlinear pricing in a finite economy," Journal of Public Economics, Elsevier, vol. 17(2), pages 157-179, March.
    14. Bonatti, Alessandro, 2011. "Brand-specific tastes for quality," International Journal of Industrial Organization, Elsevier, vol. 29(5), pages 562-575, September.
    15. Jullien, Bruno, 2000. "Participation Constraints in Adverse Selection Models," Journal of Economic Theory, Elsevier, vol. 93(1), pages 1-47, July.
    16. Stole, Lars A., 2007. "Price Discrimination and Competition," Handbook of Industrial Organization, in: Mark Armstrong & Robert Porter (ed.), Handbook of Industrial Organization, edition 1, volume 3, chapter 34, pages 2221-2299, Elsevier.
    17. Hugh Everett, 1963. "Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources," Operations Research, INFORMS, vol. 11(3), pages 399-417, June.
    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. Sergey Kokovin & Babu Nahata & Evgeny Zhelobodko, 2014. "Distortion in Screening and Spatial Preferences," HSE Working papers WP BRP 83/EC/2014, National Research University Higher School of Economics.
    2. Kokovin, S. & Nahata, B. & Zhelobodko, E., 2011. "All Solution Graphs in Multidimensional Screening," Journal of the New Economic Association, New Economic Association, issue 11, pages 10-38.
    3. Kimmo Berg, 2013. "Complexity of solution structures in nonlinear pricing," Annals of Operations Research, Springer, vol. 206(1), pages 23-37, July.
    4. Kimmo Berg & Harri Ehtamo, 2012. "Continuous learning methods in two-buyer pricing problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 75(3), pages 287-304, June.
    5. Thomas D. Jeitschko & Yeonjei Jung & Jaesoo Kim, 2017. "Bundling and joint marketing by rival firms," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 26(3), pages 571-589, September.
    6. Helfrich, Magdalena & Herweg, Fabian, 2016. "Fighting collusion by permitting price discrimination," Economics Letters, Elsevier, vol. 145(C), pages 148-151.
    7. Alexei Alexandrov & Özlem Bedre-Defolie, 2014. "The Equivalence of Bundling and Advance Sales," Marketing Science, INFORMS, vol. 33(2), pages 259-272, March.
    8. Bhattacharyya, Aditi & Kutlu, Levent & Sickles, Robin C., 2018. "Pricing Inputs and Outputs: Market prices versus shadow prices, market power, and welfare analysis," Working Papers 18-009, Rice University, Department of Economics.
    9. Rodrigo Montes & Wilfried Sand-Zantman & Tommaso Valletti, 2019. "The Value of Personal Information in Online Markets with Endogenous Privacy," Management Science, INFORMS, vol. 65(3), pages 1342-1362, March.
    10. Vincent Conitzer & Curtis R. Taylor & Liad Wagman, 2012. "Hide and Seek: Costly Consumer Privacy in a Market with Repeat Purchases," Marketing Science, INFORMS, vol. 31(2), pages 277-292, March.
    11. Devin Garcia & Levent Kutlu & Robin C. Sickles, 2022. "Market Structures in Production Economics," Springer Books, in: Subhash C. Ray & Robert G. Chambers & Subal C. Kumbhakar (ed.), Handbook of Production Economics, chapter 13, pages 537-574, Springer.
    12. Kokovin, Sergey & Nahata, Babu & Zhelobodko, Evgeny, 2010. "Multidimensional screening under nonlinear costs: Limits of standard approach," Economics Letters, Elsevier, vol. 107(2), pages 263-265, May.
    13. Stephen Davies, Catherine Waddams Price, and Chris M. Wilson, 2014. "Nonlinear Pricing and Tariff Differentiation: Evidence from the British Electricity Market," The Energy Journal, International Association for Energy Economics, vol. 0(Number 1).
    14. Pishchulov, Grigory & Richter, Knut, 2016. "Optimal contract design in the joint economic lot size problem with multi-dimensional asymmetric information," European Journal of Operational Research, Elsevier, vol. 253(3), pages 711-733.
    15. Dobson, Paul W. & Waterson, Michael, 2008. "Chain-Store Competition: Customized vs. Uniform Pricing," Economic Research Papers 269789, University of Warwick - Department of Economics.
    16. Aryal, Gaurab & Gabrielli, Maria F., 2020. "An empirical analysis of competitive nonlinear pricing," International Journal of Industrial Organization, Elsevier, vol. 68(C).
    17. Takanori Adachi & Noriaki Matsushima, 2014. "The Welfare Effects Of Third-Degree Price Discrimination In A Differentiated Oligopoly," Economic Inquiry, Western Economic Association International, vol. 52(3), pages 1231-1244, July.
    18. Sang Won Kim & Marcelo Olivares & Gabriel Y. Weintraub, 2014. "Measuring the Performance of Large-Scale Combinatorial Auctions: A Structural Estimation Approach," Management Science, INFORMS, vol. 60(5), pages 1180-1201, May.
    19. Bouckaert, J.M.C. & Degryse, H.A., 2006. "Opt In versus Opt Out : A Free-Entry Analysis of Privacy Policies," Other publications TiSEM 17393c5d-1ed2-47ec-bc96-9, Tilburg University, School of Economics and Management.
    20. Maruyama, Masayoshi & Minamikawa, Kazumitsu, 2009. "Vertical integration, bundled discounts and welfare," Information Economics and Policy, Elsevier, vol. 21(1), pages 62-71, 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:spr:annopr:v:253:y:2017:i:1:d:10.1007_s10479-016-2320-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.