Cooperative network flow problem with pricing decisions and allocation of benefits: A game theory approach

Document Type : Research Paper


Industrial Engineering college, Islamic Azad university, South Tehran Branch


Several real problems in telecommunication, transportation, and distribution industries can be well analyzed by network flow models. In revenue management, pricing plays a primary role which increases the profit generated from a limited supply of assets. Pricing decision directly affects the amount of service or product demand. Hence, in traditional maximum flow problem, we assume that the demand of sink nodes depends on price of services or products of that nodes. We first develop a mathematical programming model for decision making of pricing by multiple owners in the maximum flow problem. Afterwards, coalitions between owners will be analyzed via different methods of cooperative game theory. A numerical example is given in order to show how these methods suggest appropriate assignments of extra revenue obtained from the cooperation among the owners. 


Main Subjects

Ahuja, R. K. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall.
Ahuja, R., Magnanti, T., & Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall.
Ahuja, Ravindra K.Magnanti; Thomas L.; Orlin, James B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall.
Altman, E., & Wynter, L. (2004). Equilibrium, games, and pricing in transportation and telecommunication networks. Networks and Spatial Economics, 4(1), 7-21.
Barron, E. N. (2013). Game Theory: An Introduction (2nd edition ed.). New York: John Wiley & Sons.
Bertsekas, D. (1998). Network Optimization - Continuous and Discrete Models. Athena Scientific.
Branzei, R., Dimitrov, D., & Tijs, S. (2008). Models in cooperative game theory (Vol. 556). Springer Science & Business Media.
Deng, S., & Yano, C. (2006). Joint production and pricing decisions with setup costs and capacity constraints. Manage. Sci., 52, 741-756.
Driessen, T. (1985). Contributions to the Theory of Cooperative Games: The τ-value and k-Convex Games. Ph.D. Thesis, U. of Nijmejen.
F´elegyh´azi, M., & Hubaux, J.-P. (2006). Game theory in wireless networks: tutorial. Technical Report LCA-REPORT-.
Fathabadi, H., & Ghiyasvand, M. (2007). A new algorithm for solving the feasibility problem of a network flow. Appl. Math. Comput., 192, 429-438.
Florian, M., & Klein, M. (1971). Deterministic production planning with concave costs and capacity constraints. Manage. Sci., 18, 12-20.
Ford, L. R., & Fulkerson, D. R. (1965). Maximal flow through a network. Canadian Journal of Mathematics , 399.
Geunes, J., Merzifonluo˘glu, Y., & Romeijn, H. (2008). Capacitated procurement planning with price-sensitive demand and general concave revenue functions. Eur. J. Oper. Res., 194(2), 390-405.
Geunes, J., Romeijn, H., & Taaffe, K. (2006). Requirements planning with dynamic pricing and order selection flexibility. Oper. Res., 54(2), 394-401.
Gilbert, S. (1999). Coordination of pricing and multi-period production for constant price goods. Eur. J. Oper. Res., 114(2), 330-337.
Glover, F., & Klingman, D. (1979). Network applications in industry and government. IIE Trans., 363-376.
Hafezalkotob, A., & Makui, A. (2015). Cooperative Maximum-Flow Problem under Uncertainty in Logistic Networks. Applied Mathematics and Computation(250), 5930604.
Hammons, T. (2001). Electricity Restructuring in Latin America Systems with Significant Hydro Generation. Rev. Energ. Ren: Power Engineering, 39-48.
Harris, T. E., & Ross, F. S. (1995). Fundamentals of a Method for Evaluating Rail Net Capacities. Research Memorandum.
Juan, A.; Faulin, J;, Pérez-Bernabeu, E.; Jozefowiez, N. (2014). Horizontal cooperation in vehicle routing problems with backhauling and environmental criteria. Procedia-Social and Behavioral Sciences, 111, 1133-1141.
Kunreuther, H., & Schrage, L. (1971). Optimal pricing and inventory decisions for non-seasonal items. Econometrica, 2, 193-205.
Kunreuther, H., & Schrage, L. (1973). Joint pricing and inventory decisions for constant priced items. Manage.Sci., 19, 732-738.
Lin, C.-C., & Hsieh, C.-C. (2012). A cooperative coalitional game in duopolistic supply-chain competition. Networks and Spatial Economics, 12(1), 129-146.
Lozano, A., Moreno, P., Adenso-Díaz, B., & Algaba, E. (2013). Cooperative game theory approach to allocating benefits of horizontal cooperation. Eur. J. Oper. Res., 229, 444-452.
Lozano, S., Moreno, P., Adenso-Díaz, B., & Algaba, E. (2013). Cooperative game theory approach to allocating benefits of horizontal cooperation. Eur. J. Oper. Res., 229(2), 444-452.
Mirás Calvo, M. S. (2006). TUGlab: A Cooperative Game Theory Toolbox. Retrieved (accessed 08.01.13, from abICM06.pdf
Palais, R. (1970). Critical point theory and the minimax principle. Proc. Sympos. Pure Math., 15, 185-212.
Pirani, S., & Yafimova, K. (2009). The Russo-Ukrainian gas dispute of January 2009: a comprehensive assessment. Oxford Institute for Energy Studies, 59.
Reyes, P. M. (2005, September). Logistics networks: A game theory application for solving the transshipment problem. Applied Mathematics and Computation, 168(2), 1419-1431.
Rockafellar, R. (1984). Network Flows and Monotropic Programming. John Wiley & Sons.
Roson, R., & Hubert, F. (2014). Bargaining Power and Value Sharing in Distribution Networks: A Cooperative Game Theory Approach. Networks and Spatial Economics, 1-17.
Saad, W. (2010). “Coalitional Game Theory for Distributed Cooperation in Next Generation Wireless Networks”, Ph.D. dissertation. University of Oslo.
Saad, W. (2010). Coalitional Game Theory for Distributed Cooperation in Next Generation Wireless Networks. Ph.D. dissertation, University of Oslo.
Saad, W., Han, Z., Debbah, M., Hjørungnes, A., & Basar, T. (2009). Coalitional game theory for communication networks. IEEE Signal Processing Mag., 26, 77-97.
Schintler, Laurie A;Gorman, Sean P;Reggiani, Aura;Patuelli, Roberto;Gillespie, Andy;Nijkamp, Peter;Rutherford, Jonathan. (2005). Complex network phenomena in telecommunication systems. Networks and Spatial Economics, 5(4), 351-370.
Schrijver, A. (2002). On the history of the transportation and maximum flow problem. Math Program(91), 437-445.
Scotti, M. (2012). Networks in Social Policy Problems. Cambridge University Press.
Sepehri, M. (2011). Cost and inventory benefits of cooperation in multi-period and multi-product supply. Scientica Iranica, 18(3), 731-741.
Shapley, L., & Shubik, M. (1972). The Assignment Game I: The Core. International Journal of Game Theory, 1, 111-130.
Sharkey, T. C. (2011). Network flow problems with pricing decisions. Optimization Letters, 5(1), 71-83.
Soyster, A. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res., 21, 1154-1157.
Szoplik, J. (2012). The Gas Transportation in a Pipeline Network. Advances in Natural Gas Technology.
Thomas, J. (1970). Price-production decisions with deterministic demand. Manage. Sci., 16(11), 747–750.
Van den Heuvel, W., & Wagelmans, A. (2006). A polynomial time algorithm for a deterministic joint pricing and inventory model. Eur. J. Oper. Res., 170(2), 463-480.
Winston, W. L. (2003). Operations Research: Applications and Algorithms, fourth ed. Cengage Learning.