Skip to main content
Log in

Infrastructure topology optimization under competition through cross-entropy

  • Special Issue Paper
  • Published:
Journal of the Operational Research Society

Abstract

In this article, we study a two-level non-cooperative game between providers acting on the same geographic area. Each provider has the opportunity to set up a network of stations so as to capture as many consumers as possible. Its deployment being costly, the provider has to optimize both the number of settled stations as well as their locations. In the first level each provider optimizes independently his infrastructure topology while in the second level they price dynamically the access to their network of stations. The consumers’ choices depend on the perception (in terms of price, congestion and distances to the nearest stations) that they have of the service proposed by each provider. Each providers' market share is then obtained as the solution of a fixed point equation since the congestion level is supposed to depend on the market share of the provider, which increases with the number of consumers choosing the same provider. We prove that the two-stage game admits a unique equilibrium in price at any time instant. An algorithm based on the cross-entropy method is proposed to optimize the providers' infrastructure topology and it is tested on numerical examples providing economic interpretations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4

Notes

  1. It is assumed that online informations regarding the total number of EV drivers wishing to reload, prices, congestion levels and distance to stations are publicly accessible both for the EVs, through electronic technologies like smart phones for instance, and for the service providers.

  2. The analytical results obtained in this article can be extended to the case where we choose another density such as normal, truncated exponential, of gamma type, khi-deux, etc. However, under such density assumptions, it might not be possible to derive the analytical expressions of the service providers’ market shares and a numerical approach should be envisaged.

  3. Case 2 can be solved similarly by reversing the role played by both service providers.

  4. In economics, the total market share that is, the sum of the rival providers’ market share is also called penetration or market coverage rate (Laffont and Tirole, 2001).

  5. The discount factor is supposed identical for both providers. It means that both of them has the same risk aversion level for the future (Ross, 1983; Yildizoglu, 2011). The introduction of a discount factor is classical in (stochastic) dynamic programming and repeated game theory where the players consider their long-term utilities and have uncertainties on the future. However, extensions where it differs between the rival providers could be considered in a companion paper more devoted to simulation results.

References

  • Albareda-Sambola M, Fernandez E, Hinojosa Y and Puerto J (2009). The multi-period incremental service facility location problem. Computers and Operations Research 36 (5): 1356–1375.

    Article  Google Scholar 

  • Balmer O (2002). Species lists in ecology and conservation: Abundances matter. Conservation Biology 16 (4): 1160–1161.

    Article  Google Scholar 

  • Barth D, Cohen J, Echabbi L and Le Cadre H (2011). Coalition stability under QoS based-market segmentation. In: Krishnamurthy V (ed.) Proceedings 2nd International ICST conference on Game Theory for Networks. Shangai, China, 16–18 April.

  • Bernard A, Haurie A, Vielle M and Viguier L (2008). A two-level dynamic game of carbon emissions trading between Russia, China, and Annex B countries. Journal of Economic Dynamics and Control 32 (6): 1830–1856.

    Article  Google Scholar 

  • Borndörfer R, Omont B, Sagnol G and Swarat E (2012). A Stackelberg game to optimize the distribution of controls in transportation networks. In: Vasilakos A and Chlamtac I (eds.) Proceedings 3rd International ICST Conference on Game Theory for Networks. Vancouver, Canada, 24–26 May.

  • Chevallier J (2007). A differential game of intertemporal emissions trading with market power, EconomiX. Working Papers, University of Paris West-Nanterre la défense.

  • Chocteau V, Drake D, Kleindorfer PR, Orsato RJ and Roset A (2011). Collaborative innovation for sustainable fleet operations: The electric vehicle adoption decision. INSEAD. Working Paper.

  • De Boer P-T, Kroese DP, Mannor S and Rubinstein RY (2002). A tutorial on the cross-entropy method, Annals of Operations Research 134 (1): 19–67.

    Article  Google Scholar 

  • Dürr C and Nguyen KT (2007). Nash equilibria in Voronoï games on graphs. In: Fiat AE (ed.) Proceedings European Symposium on Algorithms (ESA). Israel, 8–10 October.

  • Gosh D (2003). Neighborhood search heuristics for the uncapacitated facility location problem. European Journal of Operational Research 150 (1): 150–162.

    Article  Google Scholar 

  • Hammersley JM and Handscomb DC (1964). Monte-Carlo Methods. Methuen & Co Ltd: London.

    Book  Google Scholar 

  • Hu TC and Shing MT (2002). Combinatorial Algorithms, 2nd edn. Dover Publications: USA.

    Google Scholar 

  • Laffont J-J and Tirole J (2001). Competition in Telecommunications. Collection Munich Lectures in Economics, MIT Press: USA.

    Google Scholar 

  • Le Cadre H and Bouhtou M (2010). An interconnection game between mobile network operators: Hidden information forecasting using expert advice fusion. Computer Networks: The International Journal of Computer and Telecommunications Networking (COMNET) 54 (17): 2913–2942.

  • Le Cadre H, Barth D and Pouyllau H (2011a). QoS commitment between vertically integrated autonomous systems. European Journal of Operational Research (EJOR) 214 (3): 627–643.

  • Le Cadre H, Potarusov R and Auliac C (2011b). Energy demand prediction: A partial information game approach. In: Van Mierlo J and Vergels F (eds). Proceedings European Electric Vehicle Congress (EEVC). Brussels, Belgium, 26–28 October.

  • McDonald J (2008). Adaptative intelligent power systems: Active distribution networks. Energy Policy 36 (12): 4346–4351.

    Article  Google Scholar 

  • McFadden D (1986). The choice theory approach to market research. Marketing Science 5 (4): 275–297.

    Article  Google Scholar 

  • McGill JI and Van Ryzin GJ (1999). Revenue management: Research overview and prospects. Transportation Science 33 (2): 233–256.

    Article  Google Scholar 

  • Minvielle P, Tantar E, Tantar A and Berisset P (2011). Sparse antenna array optimization with the cross-entropy method. IEEE Transactions on Antennas and Propagation 59 (8): 2862–2871.

    Article  Google Scholar 

  • Myerson R (2004). Game Theory, Analysis of Conflict. 6th edn. Harvard University Press: USA.

    Google Scholar 

  • Nora D (2009). The Green Gold Pioneers. Grasset & Fasquelle Editions: France.

  • Osborne MJ and Pitchik C (1987). Equilibrium in hotelling's model of spatial competition. Econometrica 55: 911–922.

    Article  Google Scholar 

  • Ozdaglar A (2008). Networks’ challenge: Where game theory meets network optimization. Tutorial In: Kschischang F (ed.) Proceedings International Symposium on Information Theory. Toronto, Canada, 6–11 July.

  • Pohjola O-P and Kilkky K (2007). Value-based methodology to analyze communication services. Netnomics 8 (1–2): 135–151.

    Article  Google Scholar 

  • Reese J (2006). Solution methods for solving p-median problem: An annotated bibliography. Networks 48 (3): 125–142.

    Article  Google Scholar 

  • Rubinstein R and Kroese DP (2004). The Cross-entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning. Springer-Verlag: USA.

    Book  Google Scholar 

  • Ross SM (1983). Introduction to Stochastic Dynamic Programming. Academic Press: USA.

    Google Scholar 

  • Saad W, Han Z, Debbah M, Hjorrungnes A and Basar T (2009). Coalitional game theory for communication networks: A tutorial. IEEE Signal Processing Magazine. Special Issue on Game Theory 26 (5): 77–97.

    Article  Google Scholar 

  • Simchi-Levy D, Kaminsky P and Simchi-Levy E (2008). Designing and Managing the Supply Chain, 3rd edn. McGraw-Hill: USA.

    Google Scholar 

  • Simonin C, Le Cadre J-P and Dambreville F (2007). The cross-entropy method for solving a variety of hierarchical search selection problems. In: Asselin A (ed.) Proceedings 10th International Conference on Information Fusion. Quebec, Canada, 9–12 July.

  • Thang NK (2010). On randomized strategy-proof mechanisms without payment for facility location games. In: Mahdian M, Mehta A, Saberi A, Shoham Y and Ye Y (eds.) Proceedings Workshop on Internet and Network Economics (WINE). Stanford, USA, 13–16 December.

  • Wade NS, Taylor PC, Lang PD and Jones PR (2010). Evaluating the benefits of an electrical energy storage sytem in a future smart grid. Energy Policy 38 (11): 7180–7188.

    Article  Google Scholar 

  • Yildizoglu M (2011). Introduction to Game Theory, 2nd edn. Dunod: France.

    Google Scholar 

Download references

Acknowledgements

The author thanks anonymous reviewers for their comments.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to H Le Cadre.

Appendix

Appendix

Proof of Lemma 1

  • As stated above, EV driver l is indifferent between S1 and S2 if, and only if, c l (1, t)=c l (2, t)⇔β l =/(ϕ(θ2(t), I2)−ϕ(θ1(t), I1)) Identically, EV driver l is indifferent between S k and no reload if, and only if, c l (k, t)=cmaxβ l = /(ϕ(θ k (t), I k )) for any k=1, 2. □

Proof of Proposition 2

  • To determine which provider is preferred at the left or at the right of the indifference bound B1, 2(t), it is important to determine the relative order between q1(t) and q2(t). Let consider an arbitrar EV driver l.

    Suppose for instance that q2(t)<q1(t) then c l (1, t)<c l (2, t) that is, provider S1 is preferred over provider S2 if, and only if, β l <B1, 2(t). This case is denoted Case 1.

    But, if q1(t)<q2(t) then c l (1, t)<c l (2, t) that is, provider S1 is preferred over provider S2 if, and only if, B1, 2(t)<β l . This case is denoted Case 2.

    Depending on the EV drivers’ congestion sensitivity coefficient position on interval [0;1], it is possible to determine the providers’ market shares since the EV drivers’ sensitivity coefficient is supposed to be distributed according to the uniform density on the interval [0;1] by the assumption described in Section 2. We obtain the following market shares:

    • In Case 1, θ2(t)=1−B1, 2(t), θ1(t)=B1, 2(t)−B1, 0(t).

    • In Case 2, θ1(t)=1−B1, 2(t), θ2(t)=B1, 2(t)−B2, 0(t).

    Informally, it is possible to interpret the EV drivers choices with the following arguments: When the EV drivers congestion sensitivity coefficient approaches 1, they choose the provider offering the smallest congestion level. When their sensitivity coefficient takes intermediate values, they might be less sensitive to the congestion than to the price. As a result, in this case, they accept to reload in the stations of the service provider having the highest congestion level. Finally, when their sensitivity coefficient approaches 0, the EV drivers are rather insensitive to the congestion that is, they are not so eager to reload and can delay it. □

Proof of Lemma 3

  • By assumption, the congestion level in S2's charge stations is smaller that in S1's ones since we have supposed that q2(t)<q1(t). At time instant t, provider S2 is always preferred over provider S1 by any EV driver l if, and only if, since β l (q1(t)−q2(t))>0 by assumption. □

Proof of Lemma 5

  • Differentiating ψ(.) once with respect to θ1(t), we obtain: + By absurd reasoning, we assume that ψ′(θ1(t))<0. This is equivalent with the following inequality: + Multyplying each side of the inequality by the term (θ1(t)−i1)2θ1(t), we infer: θ14(t)−2i1θ13(t)+θ12(t) >0. This inequality should be true for any θ1(t)∈[0;1]. But at the boundary θ1(t)=0 we obtain −i1>0, which contradicts the definition of i1 given in Section 3.1. Therefore, ψ′(.) is positive over interval [0;1] meaning that function ψ(.) is increasing other this interval. As a by product, the intersection of function ψ(.) with the line of equation θ2(t)=xθ1(t) is unique. □

Proof of Lemma 6

  • Differentiating ψ(.) twice with respect to θ1(t), we obtain:

    From this, we infer that ψ(.) cannot be convex provided it is continuous by assumption. Reducing ψ″(.) to the same denominator θ13(t)(θ1(t)−i1)3, we obtain ψ″(.)<0⇔ +θ1(t)(3θ1(t) 2i1)+2κ12<0. This is a polynomial of order 3 in θ1(t). The constant coefficient is positive whereas the coefficient of the higest order term () is negative. Indeed, if it were non-negative, provider S1 would not have any clients. Besides, the polynomial derivative is negative in zero meaning that the polynomial is decreasing in the neighbourhood of zero. As a result, if the polynomial admits three real roots, there are necessarily non-negative. The polynomial admits a unique minimum and a unique maximum. A sufficient condition to guaranteeing that +θ1(t)(3θ1(t)−2i1)+2i12<0 is to impose that the game parameters are chosen so that the polynomial minimum is greater than 1. But, the polynomial minimum is reached in / Finally, this value is smaller than 1 if, and only if,  □

Proof of Proposition 7

  • ψ(.) being increasing (cf. Lemma 5), System (3,1) admits a solution if, and only if the couple of allocations (θ1(t), θ2(t)) belongs to the constraint space . Formally, it means that the following inequalities should be simultaneously checked:

    Constraint (15) gives us . Depending on the sign of θ1(t)−i1, two cases appear. Either θ1(t)<i1 that is, there is no congestion in provider S1's stations, or θ1(t)≥i1 that is, congestion occurs. It is easy to check that if θ1(t)<i1, the second constraint is checked if, and only if, If θ1(t)⩾i1; the second constraint is checked if, and only if, Constraint (16) is equivalent with + To simplify the expression, we need to multiply it by (θ1(t)−i1)θ1(t). The two cases cited above already hold.

    Besides, we note that P1(0)=−1<0 and that since by assumption q2(t)<q1(t) therefore and needs to be greater than since otherwise no EV driver would choose S1 as provider. These remarks imply in turn that if polynomial P1(.) admits three real roots, they are all non-negative.

    In case where θ1(t)>i1, we need to determine the θ1(t) so that P1(θ1(t))⩾0 whereas in case where θ1(t)⩽i1, we need to determine the θ1(t) so that P1(θ1(t))⩽0. This is easily performed by comparing the positions of θ1(t) and those of polynomial P1(.)'s roots.

    Constraint (17) is equivalent with + To simplilfiy this inequality, we need to multiply it by (θ1(t)−i1)θ1(t).

    Proceeding as above, we observe that P2(0)=−1 and that . As cited in Constraint (16) study, two cases should be distinguished. If θ1(t)>i1, we need to determine the θ1(t) so that P2(θ1(t))⩽0 whereas in case where θ1(t)⩽i1, we need to determine the θ1(t) so that P2(θ1(t))⩾0. This is performed by comparing the position of θ1(t) and those of polynomial P2(.)'s roots.

    Depending on whether congestion occurs, the admissible area for the couple of allocations are summarized in Proposition 7 statement.

    If the whole market is captured then θ1(t)+θ2(t)=1⇔θ1(t)+ψ(θ1(t))==0. Since at equilibrium p1(t)=p E (t)+(1+θ1(t)) we infer that when the whole market is captured.

    If only a fraction x≠1 of the market is captured, solving θ1(t)+θ2(t)=x is equivalent to solve a second order polynomial equation in θ1(t): +

    The constant coefficient being non-negative and the polynomial increasing to infinity both when θ1(t) → +∞ and θ1(t) → −∞, we infer that if the polynomial admits real roots they are non-negative. Therefore, under the assumption that the parameters i1, i2 have been chosen so that the second-order polynomial admits real roots, we conclude that the unique allocation for S1 coincides with the smallest root whose expression is recalled in Proposition 7 statement.

Proof of Proposition 8

  • Differentiating ψ(.) twice with respect to θ1(t), we obtain:

    To determine the sign of ψ″(.), two cases should be distinguished:

    • Suppose . In this case ψ″(θ1(t))<0 meaning that ψ(.) is concave. But

    Since ψ(.) is concave, ψ(.) cannot belong to the constraint space . Therefore, under this assumption on cmax, System (3,2) has no solution.

    Suppose . Provider S1's congestion level being positive, the opportunity cost associated to provider S1 is always greater than the maximum admissible opportunity cost. It implies that provider S1's market share vanishes that is, θ1(t)=0. By substitution in ψ(.) expression, we obtain provider S2's market share: . □

Proof of Proposition 9

  • By substitution of p1(t) expression in System (3), function ψ(.) takes the form:

    We want to express θ2(t) exclusively as a function of θ1(t). Therefore, we multiply the equation θ2(t)=ψ(θ1(t)) by θ1(t). Then, we need to solve a second-order polynomial equation in θ2(t): + Suppose that the parameter i1 is chosen so that the polynom's discrimant remains non-negative, then θ2(t) is obtained as the smallest or the largest root of the polynomial depending whether congestion occurs. The root analytical expressions are given in Proposition 9 statement. □

Rights and permissions

Reprints and permissions

About this article

Cite this article

Le Cadre, H. Infrastructure topology optimization under competition through cross-entropy. J Oper Res Soc 65, 824–841 (2014). https://doi.org/10.1057/jors.2012.96

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2012.96

Keywords

Navigation