PaperlayerView exact revision on arXiv

Source-linked AI summary

Competitive Charging Station Pricing for Plug-in Electric Vehicles

Wei Yuan, Jianwei Huang, Ying Jun Zhang

arXiv:1511.07907v2cs.GTeess.SYmath.OC

TL;DR

The paper addresses how competing charging stations should price service while PEVs choose among stations using price, distance, and waiting time. It models these interactions as a two-stage Stackelberg game, characterizes the resulting equilibria, and provides a low-complexity algorithm for computing them.

  • Problem

    The central problem is jointly determining PEV station selection and competing charging-station prices in a coupled charging market.

  • Method

    The paper uses a two-stage multi-leader-multi-follower Stackelberg game with stations pricing first and PEVs selecting stations second.

  • Results

    The paper proves a unique station-selection equilibrium under fixed prices and characterizes sufficient conditions for pricing-equilibrium existence and uniqueness.

  • Takeaways & Limitations

    A low-complexity, provably convergent algorithm computes the pricing equilibrium and the game’s subgame perfect equilibrium.

Abstract

from arXiv · show

This paper considers the problem of charging station pricing and plug-in electric vehicles (PEVs) station selection. When a PEV needs to be charged, it selects a charging station by considering the charging prices, waiting times, and travel distances. Each charging station optimizes its charging price based on the prediction of the PEVs' charging station selection decisions and the other station's pricing decision, in order to maximize its profit. To obtain insights of such a highly coupled system, we consider a one-dimensional system with two competing charging stations and Poisson arriving PEVs. We propose a multi-leader-multi-follower Stackelberg game model, in which the charging stations (leaders) announce their charging prices in Stage I, and the PEVs (followers) make their charging station selections in Stage II. We show that there always exists a unique charging station selection equilibrium in Stage II, and such equilibrium depends on the charging stations' service capacities and the price difference between them. We then characterize the sufficient conditions for the existence and uniqueness of the pricing equilibrium in Stage I. We also develop a low complexity algorithm that efficiently computes the pricing equilibrium and the subgame perfect equilibrium of the two-stage Stackelberg game.

I. INTRODUCTION

The paper studies coupled pricing and station-selection decisions in a two-station PEV charging market, where prices, distance, waiting time, and station interactions shape equilibrium outcomes. It formulates this setting as a two-stage Stackelberg game and develops equilibrium analyses and a computational algorithm.

  • Motivation: Competitive charging pricing is increasingly practical as multiple operators set service-inclusive prices while PEV owners compare nearby stations.Operators maximize revenue subject to government rules, while owners trade off charging price and distance.
  • Research Questions: The paper asks how PEVs should select stations using prices, travel distances, and expected waiting times, and how stations should price against competitors’ responses.These decisions are tightly coupled across PEVs, stations, and market sides.
  • Game Model: Charging stations announce prices simultaneously, after which dynamically arriving PEVs select stations asynchronously in a multi-leader-multi-follower Stackelberg game.The model uses two competing stations in a stylized one-dimensional system.
  • Model: The model jointly captures heterogeneous service capabilities, asymmetric station locations, and PEV waiting time before charging service.This distinguishes it from existing station-selection models that omit waiting time.
  • Analysis: Under fixed prices, the station-selection equilibrium is unique and can have five types depending on prices and service capacities.The five types comprise three pure-strategy and two mixed-strategy equilibria.
  • Analysis: The paper characterizes sufficient conditions for pricing-equilibrium existence and uniqueness and proposes a provably convergent low-complexity computation algorithm.The algorithm may not require explicit information exchange between charging stations.

A. PEV Station Selection Game in Stage II

Stage II models PEV station selection as a population game in which each vehicle compares travel, charging, and waiting costs under shared station conditions. Arrival rates and queueing assumptions determine the waiting-time component of each vehicle’s payoff.

  • Game Definition: PEVs are the players, and each chooses station 1 or 2 based on its location.The strategy is the station choice s_n(x).
  • Game Definition: A PEV’s payoff is the negative of its total travel, waiting-time, and charging costs.The game evaluates station choices through these three cost components.
  • Traveling Cost: Traveling cost is proportional to the distance between the PEV’s location and its selected station.With no traffic jam, distance determines traveling delay and l_n,s_n = |x − x_s_n|.
  • Charging Cost: All PEVs are assumed to have identical charging demand, so charging cost depends on the selected station’s price.The charging cost is k_p d p_s_n.
  • Waiting Time: Waiting time is estimated with an M/G/k queue using station service parameters and the PEV arrival rate.The model assumes low penetration makes finite waiting-room events unlikely and uses queueing theory for estimation.
  • Waiting Time: If station i attracts PEVs from a total location-set length |A_i|, its arrival rate is |A_i|λ.The model assumes a baseline arrival rate λ from a unit line segment.

B. Charging Station Pricing Game in Stage I

The paper models charging-station competition as a two-stage game in which stations set prices and PEVs select stations in response. Stage-II equilibria depend on price differences and service capacities, with at most five equilibrium types.

  • Charging stations are the players, and each station chooses its charging price as its strategy.
  • Station payoffs combine charging-service revenue with fixed and operational costs, while demand depends on both stations’ prices.
  • The analysis derives the subgame-perfect equilibrium by solving PEV station selection in Stage II before station pricing in Stage I.
  • The model focuses on the meaningful case k1µ1 + k2µ2 > 2Lλ, because otherwise the two stations’ total capacity cannot serve all arriving PEVs.
  • Service capacities are classified as FULL, HIGH, MIDDLE, or LOW, producing nine system scenarios, although LOW-LOW and MIDDLE-LOW are unstable.
  • Stage II has at most five PEV-selection equilibria—three pure-strategy and two mixed-strategy equilibria—determined by price differences and system scenario.

A. The FULL-FULL Scenario

In the FULL-FULL scenario, both stations can serve all PEVs, and the unique selection equilibrium changes as the price difference crosses defined thresholds. Outcomes range from spatially separated pure strategies to mixed strategies and dominant-station equilibria.

  • In the FULL-FULL scenario, all five types of PEV-selection equilibria can emerge under different prices.
  • Pure-strategy NE with an indifference point: A pure-strategy equilibrium exists when the price difference lies between threshold values, yielding a unique indifference point x∗.
  • Pure-strategy NE with an indifference point: At this equilibrium, PEVs on opposite sides of x∗ select different stations, dividing the one-dimensional system into two continuous service segments.
  • Pure-strategy NE with an indifference point: As p1 −p2 increases, x∗ moves toward x1 and station 2 attracts more PEVs; at a threshold, x∗ reaches x1.
  • Mixed-strategy NE: Between threshold regions, some PEVs mix between stations, with probabilities chosen so their station payoffs are equal.
  • Mixed-strategy NE: At critical thresholds, all PEVs select one dominant station, and further price changes leave the selection outcome unchanged.

3) Pure-strategy NE with a dominant station:

The dominant-station pure-strategy outcome occurs when price differences reach critical thresholds, but limited capacity can prevent such equilibria in lower-capacity scenarios.

  • Pure-strategy NE with a dominant station: As p1 −p2 reaches θL2 or θR2, all PEVs select station 1 or station 2, respectively.
  • Pure-strategy NE with a dominant station: Beyond those critical thresholds, further decreasing station 1’s price or increasing station 2’s price leaves the selection outcome unchanged.
  • Pure-strategy NE with a dominant station: The PSSG always has a unique Nash equilibrium in the FULL-FULL analysis.
  • HIGH-HIGH: In HIGH-HIGH, neither station can serve all PEVs, so only the three equilibria shown in Fig. 3(a)–(c) can occur.
  • HIGH-HIGH: In HIGH-HIGH, the equilibrium varies across price-difference regions, including an indifference-point outcome and mixed-strategy outcomes.
  • HIGH-HIGH: The HIGH-HIGH mixed-strategy cases are represented by station-selection probabilities over regions near the competing station.

2) MIDDLE-MIDDLE:

In the MIDDLE-MIDDLE scenario, limited station capacities eliminate several possible PEV selection equilibria, leaving one equilibrium type. The analysis then derives station demand, best responses, and sufficient conditions for a unique pricing equilibrium.

  • 2) MIDDLE-MIDDLE:: Limited station capacities prevent the equilibria shown in Fig. 3 (b)–(e), leaving only one NE type in the MIDDLE-MIDDLE scenario.The surviving equilibrium is characterized in Theorem 5, which states that the indifference point is unique.
  • 2) MIDDLE-MIDDLE:: The equilibrium-analysis method extends to other scenarios and is summarized in Table I.The authors also state that the analysis applies to more general systems described in Appendices D and E.
  • V. CHARGING STATION PRICING GAME IN STAGE I: Given the PEV selection equilibrium, the authors derive charging-station demand and define each station’s best response as the price maximizing its payoff.For station 1, demand is derived from the price difference Δp = p1 − p2; the best response is denoted B_i(p_j).
  • V. CHARGING STATION PRICING GAME IN STAGE I: A pricing equilibrium occurs when both stations’ prices are mutual best responses, yielding the Nash equilibrium of the charging-station pricing game.This Stage I equilibrium, combined with the Stage II equilibrium, leads to the subgame perfect equilibrium of the two-stage game.
  • V. CHARGING STATION PRICING GAME IN STAGE I: Theorem 6 gives sufficient conditions for a pure-strategy pricing equilibrium: best responses must increase with the competitor’s price, while best price offsets decrease strictly.The equilibrium lies in a region [a, b] when these conditions hold, and the pure-strategy equilibrium is unique when additional stated conditions are satisfied.
  • V. CHARGING STATION PRICING GAME IN STAGE I: Uniqueness cannot be established from payoff convexity alone, because even convex games may lack a unique Nash equilibrium.This motivates the explicit best-response conditions used in Theorem 6.
  • V. CHARGING STATION PRICING GAME IN STAGE I: The best price offset measures a station’s pricing advantage relative to its competitor, and its decrease implies that price gaps narrow as the competitor’s price rises.The authors note that conditions 2 and 3 are satisfied in most simulations, while condition 1 is not always easy to satisfy.

VI. COMPUTING THE EQUILIBRIUM

Because a closed-form pricing equilibrium is difficult to characterize, the paper develops DSSA, a low-complexity iterative method that searches for equilibrium prices and converges to the game’s SPE.

  • Algorithm motivation: DSSA addresses the challenge that the pricing equilibrium lacks an easily obtainable closed-form characterization.The paper therefore focuses on computing the equilibrium algorithmically.
  • Directional search: Proposition 1 uses Θ_i(p_i)=B_i(B_j(p_i))−p_i to determine whether a current price is above or below the equilibrium price.Θ_i(p_i)<0 when p_i exceeds p_i*, enabling directional search.
  • Directional search: DSSA iteratively updates the search direction and step size while searching p_i* within [p_min,p_max].A sign change in consecutive Θ evaluations indicates that the search has crossed the equilibrium and triggers a direction change with a smaller step size.
  • Implementation: Each charging station can execute DSSA independently without synchronization or explicit information exchange when system parameters and feasible price bounds are public.Each station computes its Θ_i function locally.
  • Convergence: DSSA converges Q-linearly to a subgame-perfect equilibrium of the Stackelberg game.The algorithm uses the stopping and update rules specified in Algorithm 1.

VII. NUMERICAL RESULTS

Numerical results verify the charging-station selection equilibrium across service-capacity scenarios and show how price differences affect station choices. They also illustrate the predicted indifference points and selection probabilities.

  • FULL-FULL scenario: A larger price difference p1 − p2 moves the indifference point from x2 toward x1 and sends more PEVs to station 2.This matches Theorem 1 in the FULL-FULL scenario.
  • FULL-FULL scenario: When p1 − p2 lies between the threshold ranges, PEVs on [−L, x2] select station 1, while those on [x2, L] mix between both stations.The mixing probability is ω1 for station 1 and 1−ω1 for station 2.
  • HIGH-HIGH scenario: Neither station’s selection probability continuously spans [0, 1] in the HIGH-HIGH scenario because neither station can serve all PEVs.The result is consistent with Theorem 4.
  • MIDDLE-MIDDLE scenario: The indifference point lies in (−2, 4) in the MIDDLE-MIDDLE scenario, matching the interval predicted by Theorem 5.The scenario uses µ1 = 7 and µ2 = 6.
  • HIGH-LOW scenario: In the HIGH-LOW scenario, ω1 remains in (0.2, 0.6), so station 1 attracts some PEVs even when station 2 has much lower capacity and the price difference reaches 3.The reported range corresponds to the capacity-based bounds.

B. Pricing Equilibrium of CSPG

The numerical pricing experiments illustrate best-response behavior, equilibrium prices, and DSSA convergence. Across the tested scenarios, the best-response intersections identify Nash equilibria and DSSA reaches them quickly.

  • Best responses: The best price offset decreases with the competitor’s price, while both charging stations’ best-response curves increase.This is shown for the FULL-FULL scenario with µ1 = 16, µ2 = 14 and pi ∈ [0.25, 0.3].
  • Best responses: (0.269, 0.282) is the Nash equilibrium obtained from the intersection of the best-response curves.The price interval is (pmin, pmax) = (0.25, 0.3).
  • Equilibrium prices: (0.26, 0.27) is the Nash equilibrium when (pmin, pmax) = (0.2, 0.27), where positive best price offsets incentivize both stations to raise prices.The resulting equilibrium is high because candidate prices are relatively low and pmax is small.
  • Equilibrium prices: Changing station 2’s location from x2 = 5 to x2 = 9 reverses which station has the higher equilibrium price because the farther station needs a smaller price to attract PEVs.The comparison uses the equilibria shown in Figs. 11 and 13.
  • DSSA convergence: DSSA converges to the Nash equilibria within 25 iterations in all tested scenarios.The algorithm terminates as B1(B2(p1)) − p1 approaches zero under the stated convergence criterion.

APPENDIX A PROOF OF THEOREM 1

The proof establishes uniqueness of the charging-station selection equilibrium by showing that the relevant equilibrium equation has a unique solution and that the induced strategies leave no profitable unilateral deviations.

  • Indifference-point equilibrium: The proof reduces the indifference-point characterization to finding a root of f(x) = 0.The function incorporates price, queueing, and distance terms.
  • Indifference-point equilibrium: A root exists in (x1, x2) because f(x1) < 0 and f(x2) > 0, while strict monotonic increase makes the root unique.This establishes uniqueness of the indifference point.
  • Equilibrium verification: Given the strategy profile defined by the indifference point, PEVs on its left prefer station 1 and those on its right prefer station 2.The payoff comparisons show that no PEV has an incentive to switch unilaterally.
  • Uniqueness: The proof rules out alternative pure or mixed equilibria, completing the uniqueness argument for the selection equilibrium.The argument uses contradiction for alternative pure strategies and states that the mixed-strategy case is analogous.
  • Mixed-selection equilibrium: For the mixed-selection case, f(ω) is strictly increasing and has exactly one solution ω ∈ [0, 1].The solution cannot fall below 0 or exceed 1.

B. Nash equilibrium

The appendix verifies Nash equilibria for PEV station-selection strategies across spatial and price-difference cases. It establishes that the identified equilibria are unique.

  • PEVs to the right of station 1 prefer station 2 and have no unilateral incentive to deviate.
  • The mixed strategy (ω1, 1 −ω1) prevents PEV m from benefiting through unilateral deviation.
  • The strategy profile in (6) is a Nash equilibrium, and the equilibrium is unique.
  • When selecting station 2 is always better, every PEV chooses station 2, yielding the unique Nash equilibrium.

APPENDIX D EXTENSION FOR MULTIPLE CHARGING STATIONS

The extension examines station-selection equilibria with multiple stations and spatial dimensions, then proves existence and uniqueness of pure-strategy pricing equilibria under the stated response mappings.

  • Multiple charging stations: With three one-dimensional stations, two indifference points can divide PEV choices among stations 1, 2, and 3.At one point stations 1 and 2 are equivalent, while at the other stations 2 and 3 are equivalent.
  • Two-dimensional extension: For two homogeneous stations in two dimensions, the indifference boundary is a line through the midpoint, separating PEV choices between the stations.
  • Two-dimensional extension: Asymmetrical stations produce a nonlinear indifference curve determined by travel distance, queueing delay, and price costs.The curve separates the service regions of the two stations.
  • Pricing equilibrium: A fixed-point argument establishes existence of a pure-strategy Nash equilibrium for the pricing responses.
  • Pricing equilibrium: A contradiction argument proves that the pure-strategy pricing Nash equilibrium is unique.

APPENDIX G PROOF OF PROPOSITION 1

The appendix analyzes the DSSA iterative algorithm around the pricing equilibrium. It shows that the update mapping contracts the distance to equilibrium and therefore converges Q-linearly.

  • Proof cases: The proof considers pricing iterates below or above the equilibrium, with the second case analyzed similarly.
  • Algorithm mapping: DSSA is represented as an iterative mapping P1(τ + 1) = T(P1(τ)) around the equilibrium.
  • Convergence: The mapping shortens the distance between each candidate solution and the equilibrium.
  • Convergence: A constant γ satisfying 0 ≤γ < 1 makes T a pseudocontraction mapping.
  • Convergence: DSSA converges to p∗1, and the convergence is Q-linear.
Loading 1511.07907v2…