# Coalitional Game Theory in Power Systems: Applications, Challenges, and
Future Directions

Mukesh Gautam, _Graduate Student Member, IEEE_ , Mohammed Benidris, _Senior
Member, IEEE_ ,
Department of Electrical & Biomedical Engineering, University of Nevada, Reno,
Reno, NV 89557
(emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Game theory-based approaches have recently gained traction in a wide range of
applications, importantly in power and energy systems. With the onset of
cooperation as a new perspective for solving power system problems, as well as
the nature of power system problems, it is now necessary to seek appropriate
game theory-based tools that permit the investigation and analysis of the
behavior and relationships of various players in power system problems. In
this context, this paper performs a literature review on coalitional game
theory’s most recent advancements and applications in power and energy
systems. First, we provide a brief overview of the coalitional game theory’s
fundamental ideas, current theoretical advancements, and various solution
concepts. Second, we examine the recent applications in power and energy
systems. Finally, we explore the challenges, limitations, and future research
possibilities with applications in power and energy systems in the hopes of
furthering the literature by strengthening the applications of coalitional
game theory in power and energy systems.

###### Index Terms:

Coalitional game theory, energy systems, nucleolus, power systems, Shapley
value.

##  1 Introduction

Game theory-based approaches provide a set of mathematical tools to assess
complex interactions and rational behaviors of economic agents in a mutually
interactive setting [1]. Specifically, coalitional game theory-based
approaches have attracted considerable attention of power system researchers
because of their ability to uniquely assign payoff among players of the game
taking into account their marginal contributions [2]. Coalitional and non-
coalitional game theory-based methodologies have been extensively used in a
number of power system-related disciplines. Planning, economics, operations,
and control of the power system are some of these areas. Game theory-based
methods have been applied to determine the optimum dispatch strategies of
thermal power plants in [3], coordinate the charging of plug-in hybrid
electric vehicles in [4], and allocate the cost of transmission system losses
to market participants (customers and power generating companies) in [5].

The primary focus of coalitional game theory is the distribution of rewards
obtained from player collaboration. When members of a coalition work together
and take coordinated action, the collective wealth or value of the coalition
is frequently increased or decreased. Naturally, a fascinating and significant
issue that has drawn the attention of many mathematicians and scientists is
how to distribute the collective reward in an equitable and consistent way.
The total payment or incentive of a coalitional game is divided among the
players using various solution concepts such the Shapley value, the core, the
Nucleolus, and the Nash-bargaining solution.

Applications of coalitional game theoretic approaches in power and energy
systems have gained significant momentum in recent years due to their ability
to uniquely assign payoffs among players of the game taking into consideration
their marginal contributions. A coalitional game theory-based energy
management system has been proposed in [6] to facilitate power exchange of
microgrids connected with the main grid. In [7], a game theory-based strategy
for improving system reliability and reducing power loss in active
distribution networks and microgrids has been proposed, where the locational
marginal cost was computed at each bus, and each player in the game received
financial rewards when system reliability level was improved and the network
power losses were reduced. In [8], a coalitional game theory-based strategy
has been presented for involvement of distributed energy resources in the
distribution network to take part in secondary frequency regulation. To
determine the optimal locations and sizes of distributed energy resources in
distribution systems, a methodology based on coalitional game theory has been
presented in [9]. In [10], a multi-stage optimum planning of multi-microgrids
utilizing deep learning and coalitional game theory has been developed, where
a deep neural network was utilized for forecasting, and coalitional game
theory was used to determine optimal set points for the multi-microgrid. A
two-layer game model was developed in [11] to enhance the integrated energy
system, where an upper-level Stackelberg game model of the improved energy
network was firstly optimized and a cooperative game model for the users, the
supply system, and the integrated energy system was developed to carry out an
internal optimization. The viability of peer-to-peer (P2P) energy trading in a
grid-connected system with voltage limits has been investigated in [12], where
a local voltage control strategy that considers network constraints and
prompts prosumers to engage in energy trading has been proposed. Prosumers
participating in the P2P energy trading proposed in [12] could join a
coalition to discuss and determine the energy trading specifications,
including trading volumes and pricing, under a coalitional game-based
structure.

Authors of [13] have conducted a survey of coalitional game theory
applications focusing on expansion planning of power systems. Contrary to the
aforementioned paper, this paper presents a review of recent advancements and
applications of coalitional game theory in overall power and energy systems.
This paper starts by giving the basic introduction of coalitional games along
with various solution concepts including the core, Shapley value, nucleolus,
and Nash bargaining solutions. Then, the recent advancements of coalitional
game theory in both transmission and distribution systems are explained.
Moreover, the paper examines the applicability, challenges, and limitations of
coalitional game theory through a case study in a 33-node distribution system
considering the reserve allocation problem in active distribution systems.

The remainder of the paper is organized as follows: Section 2 present an
introduction to coalitional game theory along with various solution concepts;
Section 3 presents various applications of coalitional game theory in power
and energy systems; Section 4 presents a case study to explain applicability,
challenges, and limitations of coalitional game theory; and Section 5
summarizes the paper, and presents conclusion and future research directions.

##  2 Coalitional Game Theory

In game theory, games are generally categorized into two groups: (a)
coalitional games and (b) non-coalitional games. In non-coalitional games,
there is no coalition or cooperation between players and they compete among
each other to optimize their individual utility functions, while in
coalitional games the players form alliances or coalitions with each other to
optimize both individual and coalitional utility functions. A coalition must
always yield utilities that are equal to or greater than the individual
player’s utilities since members establish coalitions to optimize their
individual utility functions. Non-coalitional games focus mainly on maximizing
individual utilities of the players, while coalitional games focus on
improving joint utility of the coalition [14]. A coalitional game is described
by providing a value to each coalition. The following two elements comprise
the coalitional game:

  1. 1.

A set of players $\mathscr{N}$, also referred to as the grand coalition.

  2. 2.

A characteristic function $V(S):2^{\mathscr{N}}\rightarrow\mathbb{R}$ that
converts the set of all feasible player coalitions into a set of coalitional
worths or values satisfying the condition $V(\phi)=0$.

Every coalitional game specifies the characteristic function that represents
the worths or values of all coalitions. The total value of all members of a
coalition serves as the characteristic function of the coalition. Solution
paradigms such as the core, the Nucleolus, and the Shapley value are the most
popular ways used to allocate the overall payout or incentive among individual
players of a coalitional game.

###  2.1 Core of a Coalitional Game

In game theory, the core is the set of possible assignments that cannot be
enhanced more through any alternative coalitions. The core is a set of payout
assignments that ensures no player or player group has a motivation to quit
$\mathscr{N}$ to establish a new coalition. Mathematically, the core is
defined as follows [15].

$\mathcal{C}=\left\\{\alpha:\sum_{j\in\mathscr{N}}\alpha_{j}=V(\mathscr{N})\text{
and }\sum_{j\in S}\alpha_{j}\geq V(S),\forall S\subset\mathscr{N}\right\\}$
(1)

There is no certainty that the cores of coalitional games will always exist.
In many cases, the core is in fact empty, making it impossible to stabilize
the grand coalition [16]. Moreover, the core doesn’t always give a unique
solution and in many cases, the payoff distribution based on the core can be
unfair to some players [16]. Shapley value or some alternate solution concept
may be applied in these circumstances.

###  2.2 Nucleolus

The nucleolus is another important concept in coalitional game theory
introduced by Schmeidler [17] in 1969. It is founded on the idea of reducing
the dissatisfaction of coalition(s) starting with the most dissatisfied
coalition(s) [17]. The excess of a coalition is the difference between the sum
of actual payoffs received by players in the coalition and the worth or value
of the coalition. Nucleolus is defined as a payoff distribution vector
$\mathbf{x}$ such that the excess (given by (2)) of any potential coalition
cannot be lowered without raising any other higher excess.

$e_{S}(\mathbf{x})=V(S)-\sum_{j\in S}x_{j}\mbox{,}$ (2)

where $\sum_{j\in S}x_{j}$ denotes the actual value of total payoff received
by the players of coalition $S$ and $V(S)$ denotes the worth or value of
coalition $S$.

If the core is not empty, the nucleolus should lie in the core as well,
guaranteeing the grand coalition’s stability [17]. However, obtaining the
nucleolus might not be simple because of numerical issues [18]. Additionally,
none of the monotonicity requirements are guaranteed [18]. Moreover, the
payoff distribution based on the concept of the nucleolus can be unstable if
the core doesn’t exist. Therefore, when adopting the nucleolus, it might still
be essential to ensure that the core isn’t empty.

###  2.3 Shapley Value

The Shapley value is an approach to getting solutions of coalitional game
theory. In other words, the Shapley value is a method of distributing the
total payoff to each player when everyone plays the game. The Shapley value is
mathematically represented as follows [19].

$\psi_{j}(V)=\sum_{S\in 2^{\mathscr{N}},j\in S}\frac{(\lvert
S\rvert-1)!(n-\lvert S\rvert)!}{n!}[V(S)-V(S\backslash\\{j\\})]$ (3)

where $n=\lvert\mathscr{N}\rvert$ denotes the total number of players; $S$ is
a coalition that is a subset of $\mathcal{N}$; $S\backslash\\{j\\})$ is a
coalition set that excludes player $j$; and $2^{\mathcal{N}}$ is a set of
possible coalitions.

The Shapley value has a number of important properties, which are listed
below:

  1. 1.

Efficiency: The grand coalition’s value is equal to the total of all players’
Shapley values, therefore all gains are allocated among the players.
Mathematically,

$\sum_{j\in\mathscr{N}}\psi_{j}(V)=V(\mathscr{N})$ (4)

  2. 2.

Individual Rationality: When a player participates in a coalition, then its
Shapley value should exceed its individual value. Mathematically,

$\psi_{j}(V)\geq V(\\{j\\}),\forall j\in\mathscr{N}$ (5)

  3. 3.

Symmetricity: When two players in a coalition make the same contribution,
their Shapley values must be equal. Mathematically, for two players $i$ and
$j$ satisfying $V(S\cup\\{i\\})=V(S\cup\\{j\\})$ for each coalition $S$
without $i$ and $j$,

$\psi_{i}(V)=\psi_{j}(V)$ (6)

  4. 4.

Dumminess: When a player does not increase the coalition’s value, its Shapley
value should be zero. Mathematically, for player $i$ satisfying
$V(S)=V(S\cup\\{i\\})$ for each coalition $S$ without $i$,

$\psi_{i}(V)=0$ (7)

  5. 5.

Linearity: The Shapley value corresponding to the sum of characteristic
functions equals the sum of Shapley values corresponding to the individual
characteristic functions. Mathematically, for two characteristic functions
$V_{1}$ and $V_{2}$ of a coalitional game,

$\psi(V_{1}+V_{2})=\psi(V_{1})+\psi(V_{2})$ (8)

##  3 Applications of Coalitional Game Theory in Power and Energy Systems

This section presents some of the major applications of coalitional game
theory in power and energy systems including transmission and distribution
systems operations and planning.

###  3.1 Loss Reduction Allocation of Distributed Generators

A cooperative game theory-based approach has been implemented in [20] for loss
reduction allocation of distributed generators using the Shapley values (a
solution concept in cooperative game theory). The paper has presented a new
locational marginal pricing (LMP) strategy for distribution systems with
substantial integration of distributed generation in a competitive energy
market. The objective of the LMP technique presented in the paper was to
reward distributed generators for their contribution to lower power loss in
distribution systems resulting from the participation of all distributed
generators in providing demand. Additionally, an iteration-based algorithm has
been integrated with the proposed approach. In contrast to the existing LMP-
based methodologies, the method presented in the paper has been supposed to
offer distribution companies an effective tool for estimating the system
state.

###  3.2 Reliability-centered Maintenance

The concept of Shapley value has been utilized in [21] to determine the
critical components of the system for reliability-centered maintenance. The
paper has stated that the prevention of potential disruptions and the
provision of the necessary electricity for end-use customers of distribution
networks were two major functions of the generation side of power systems.
Since generator failures may have severe or minimal effects depending on the
location of generators and network structure, the paper has considered both of
these factors during reliability-centered maintenance. In addition to
attempting a fair distribution of outage implications to the participating
units in the case of $N-k$ contingencies, this study has been primarily
focused with the proposal of an index that could be used to sort out the
generators based on their outage impacts on power system reliability. The
proposed approach has employed Shapley Value to rank generators based on how
their failure will affect the reliability of the system. The proposed approach
can be used to identify the critical generators of the system, after which the
reliability-centered maintenance can be successfully carried out.

###  3.3 Under-frequency Load Shedding

A coalitional game theory-based approach has been proposed in [22] for under
frequency load shedding control, where a real-time digital simulator has been
utilized to compute rate of change of frequency (RoCoF). In order to
efficiently and accurately calculate the locations and amounts of loads that
need to be shed in order to regulate under frequency load shedding, the paper
has provided a two-stage strategy based on cooperative game theory. Using the
initial RoCoF referred to the equivalent inertial center, the total amount of
loads to be shed, also known as the deficit in generation or the disturbance
power, was calculated in the first step. In the second step, load shedding
amounts and locations were determined using the Shapley value. The Western
Electricity Coordinating Council (WECC) 9-bus 3-machine system has been used
to implement the proposed approach, and real-time digital simulators were used
for simulation. The findings demonstrated that the proposed under-frequency
load shedding technique can successfully restore the system to its pre-
disturbance state.

###  3.4 Formulation of Distributed Slack Buses

A coalitional game theory-based method for calculating the participation
factors of distributed slack bus generators has been proposed in [23]. The
effectiveness of the proposed method has been shown by comparing it to a
traditional method for computing the participation factors of distributed
slack bus generators. The paper’s proposed methodology was a two-stage
strategy. The worth (or value) of each participant generator and the
coalitions they were a member of was calculated in the first phase. The
Shapley value was employed in the second phase to establish participation
criteria for each participating generator. The mismatch power was then divided
among the several generators using the participation factors. Case studies on
the IEEE 14-bus, IEEE 30-bus, and IEEE 57-bus systems were used to show the
feasibility of the proposed methodology. The findings demonstrated that
systems with distributed slack buses, as opposed to those with a single slack
bus, have lower generation costs and power losses.

###  3.5 Sizing and Siting of Distributed Energy Resources

For the purpose of sizing and siting distributed energy resources (DERs), a
coalitional game-theoretic strategy has been developed in [24]. The k-means
method has been utilized to perform scenario reduction before identifying
potential locations for the deployment of DERs. The two-stage method for
choosing the best DER sites and sizes was presented in the paper. Using the
equivalent locational marginal prices (LMPs) per unit active power at each
bus, a certain number of prospective locations for DERs were chosen in the
first stage, and the worths of each prospective location and their coalitions
were calculated. The weighted average of LMPs for reduced sets of load
scenarios was used to calculate the equivalent LMPs. The Shapley value was
employed in the second stage to obtain the optimum placements and sizes for
DERs. Case studies performed on several IEEE systems demonstrated that
employing the proposed approach as opposed to the existing approaches lowered
the total cost of generation after DER deployment.

###  3.6 Integrated DER Energy Management

An integrated DER energy management strategy built on nucleolus estimate has
been proposed in [25]. The paper has presented a strategy to quickly estimate
the nucleolus by including the k-means clustering method, which uses a
distinctive marginal allocation pattern as the clustering features. The
nucleolus, a method of distributing these economic rewards, has been shown to
guarantee the DERs’ motivation to participate in coalitional games. The
increase in computational time of nucleolus with increase in number of players
imposes a hard limit on the system’s scalability. A proportional random
sampling approach has been proposed for performance assessment. The estimation
performances of different clustering algorithms were compared after pairing
with different clustering characteristics.

###  3.7 Transmission Expansion Planning

A mechanism for the distribution of transmission expansion expenses among
energy market players based on the core and nucleolus paradigms of coalitional
games has been proposed in [26]. Using a coalitional game for a certain number
of participants, the cost of transmission line expansion was divided among the
participants. Transmission line expansion has been expected to ease
transmission congestion, which is believed to be the transmission impediment.
The proposed cost allocation was demonstrated through an illustrative case
study consisting of an energy market model.

###  3.8 Small-signal Stability of Power Systems

In order to determine which factors are most important for assessing a small-
signal stability of a power system, the paper [27] has examined several
coalitional game theoretic models. Identifying the factors that have the
greatest impact on system stability will make it easier to operate and manage
a power system economically in general since network operators and relevant
parties would have to put less effort into network management, regulation, and
modeling. The scarce resources might be properly allocated and prioritized
after determining which factors have the most influence on small-signal
stability concerns. In contrast to prior methods, a priority ranking algorithm
based on a coalitional game theoretic approach has the benefit of taking into
account both the individual and all potential cumulative impacts of players.
In this paper [27], the most significant players have been found using a
multi-level strategy that accounted for the network power flow, small-signal
stability characteristics, and individual and coalitional behaviors of
players.

###  3.9 Pre-positioning of Movable Energy Resources

To enhance the resilience of the power supply, a strategy based on the
combination of graph theory and coalitional game theory to determine pre-
positioning locations of movable energy resources (MERs) has been presented in
[28]. The proposed method has been used to identify MERs’ pre-positioning
sites using weather forecast information to guarantee the quickest response
feasible in the case of a natural disaster. Numerous line outage scenarios
were created in the paper using the distribution lines’ fragility curves, and
a scenario reduction approach was then used to generate a collection of
reduced line outage scenarios. For each reduced line outage scenario, the
power distribution network was reconfigured using a graph theory-based
approach. The amount of curtailed critical loads and the probability of each
reduced line outage scenario have been used to determine the expected load
curtailment (ELC) associated to each site. The Dijkstra shortest path method
was used to calculate the best path to take in order to travel to each site.
Using the ELC and the optimum route, MER dispatch cost was calculated. The
potential sites for MER pre-positioning were using the MER dispatch costs. The
size of MER at each prospective location has been determined using the Shapley
value. A 33-node distribution system test bed has been used to verify the
proposed method for pre-positioning of MERs.

###  3.10 Microgrid Cooperative Energy Management

For the cooperative energy trading management of microgrids, a hybrid Energy
Management System (EMS) framework based on coalitional games has been
developed in [6]. The paper has determined the energy trading plan that aims
to minimize network power losses by using an efficient and robust non-linear
model and a characteristic function that ensures the grand coalition is the
right coalition structure. A collaborative plan for a moving horizon has been
created using the scheduling procedure. The monitoring procedure has employed
performance thresholds to track program implementation and detect disturbances
in order to improve the effectiveness of microgrids. To protect the privacy of
microgrids, each regional EMS was supposed to shares its state summaries with
the centralized EMS, which describe its power surplus or deficit for each time
frame of the planning horizon. The incentive allocation mechanism distributed
the power loss that was acquired as a result of the energy traded during the
implementation of the plan using a core-based paradigm. After comparing the
proposed framework with a coalition forming game-based methodology reported in
the literature, it has been deduced that the task of managing the power
exchange between microgrids must be represented as a canonical coalitional
game rather than a coalition forming game.

###  3.11 Peer-to-Peer Energy Trading

A framework based on coalitional game theory has been proposed in [29] to
speed up the development of reliable trading strategies and to motivate
participants. Depending on factors like region, peak energy consumption, peak
energy generation, and price mechanism, the proposed trading methodology has
been designed to provide different preferences at each timespan. The paper has
formulated a grand coalition with a goal to enhance the total social welfare
and make sure that all players of the game benefit from the policy. Due to the
fact that neither peer wishes to initiate a merge or split with respect to its
current state, the grand coalition formed by the coalitional game in the paper
satisfied Nash equilibrium criteria. The results in [29] demonstrated that
utilizing the optimal preference for each timespan was preferable than using a
single preference for the whole day. The paper has also performed an economic
analysis to determine how to fairly allocate the total payoff among all
players of the game. When applying the proposed strategy, customers save money
on their energy bills and prosumers earn high profit, according to the
economic analysis performed in the paper.

##  4 Reserve Allocation in Active Distribution Systems: a Case Study

A case study on reserve allocation in active distribution system based on [30]
is presented to explain applicability, challenges, and limitations of
coalitional game theory in power and energy systems. The layout of the
coalitional game theory-based approach proposed in [30] is as shown in Fig. 1.
A 33-node distribution system with total active and reactive power loads of,
respectively, 3715 kW and 2300 kVAr, is considered for the case study.

Figure 1: Layout of the Coalitional Game Theoretic Model for Reserve
Allocation [30]

To analyze the scalability of coalitional game theory-based approaches, two
different types of characteristic functions (worthiness index and power loss
reduction) are computed by varying the number of DERs (players) from 2 to 8.
The equivalent Shapley value is computed for each scenario and distribution
factors are then determined for reserve allocation among DERs. Table I shows
the number of DERs, their locations, and execution time when the study is
conducted on a 64-bit Intel i5 personal computer with processor speed of 3.15
GHz, 8 GB RAM, and Windows operating system. Similarly, Fig. 2 shows the plot
of execution time as the number of DERs is increased. The figure shows that
the execution time increases exponentially as the number of DERs (i.e.,
players of the coalitional game) increases, demonstrating that the coalitional
game theory-based approaches are highly unscalable. The coalitional game
theory-based approaches are, therefore, highly applicable in power system
planning problems where execution time is not a major concern compared to
power system operations and control problems.

TABLE I: Comparison of Execution Time With Increase in DERs | Number of
---
DERs (players)
| DER locations
---
(nodes)
| Execution
---
time (sec)
2 | 24, 32 | 0.02
3 | 7, 14, 24 | 0.05
4 | 7, 14, 24, 32 | 0.09
5 | 7, 8, 14, 24, 32 | 0.18
6 | 7, 8, 14, 24, 25, 32 | 0.42
7 | 7,8,14,24,25,30,32 | 0.99
8 | 7, 8, 14, 24, 25, 30, 31, 32 | 2.93
Figure 2: Plot of execution time versus number of DERs

##  5 Conclusion and Future Research Directions

This paper has presented a review of coalitional game theory applications in
power and energy systems. The paper started with the basic introduction to
coalitional game theory along with advantages and limitations of various
solution concepts of coalitional games including the core, the nucleolus, and
the Shapley value. The various applications of coalitional game theory were,
then, presented. A case study of reserve allocation in active distribution
systems was presented to point out applicability, challenges, and limitations
of coalitional game theory in power and energy systems.

In the case study, the execution time was computed by increasing the number of
players. The case study results showed that the execution time increases
exponentially as the number of players in coalitional games is increased. It
was, therefore, deduced that the coalitional game theory is applicable in case
of power system operations and control problems if there are few numbers of
players. On the other hand, the coalitional game theory-based applications are
still viable in case of power system planning problems where execution time is
not a prime concern. The consideration of marginal contribution of each player
while distributing the overall reward among all players makes the coalitional
game theoretic techniques based on Shapley values still favorable.

Since the existing approaches for computing the solutions of the coalitional
games are not scalable, further research is needed to develop approaches that
are computationally efficient and accurate enough. Since most of the solution
concepts are based on the enumeration of possible coalition sets and
computation of corresponding characteristic functions, the size of the
coalition set increases non-linearly with increase in the number of players.
Moreover, some coalitions might be more impactful and significant compared to
others. Based on this, some approximations can be made while determining the
solutions. This can help reduce the computational time while solving a
coalitional game.

## References

  * [1] Y. Chen, B. Ai, Y. Niu, K. Guan, Z. Han, Resource allocation for device-to-device communications underlaying heterogeneous cellular networks using coalitional games, IEEE Transactions on Wireless Communications 17 (6) (2018) 4163–4176.
  * [2] M. Gautam, N. Bhusal, M. Benidris, H. Livani, A cooperative game theory-based secondary frequency regulation in distribution systems, in: North American Power Symposium (NAPS), IEEE, 2021, pp. 1–6.
  * [3] N. Yildiran, E. Tacer, Game theory approach to solve economic dispatch problem, International Journal of Trade, Economics and Finance 6 (4) (2015) 230–234.
  * [4] J. Tan, L. Wang, A game-theoretic framework for vehicle-to-grid frequency regulation considering smart charging mechanism, IEEE Transactions on Smart Grid 8 (5) (2017) 2358–2369.
  * [5] D. A. Lima, J. Contreras, A. Padilha-Feltrin, A cooperative game theory analysis for transmission loss allocation, Electric Power Systems Research 78 (2) (2008) 264–275.
  * [6] P. L. Querini, O. Chiotti, E. Fernádez, Cooperative energy management system for networked microgrids, Sustainable Energy, Grids and Networks 23 (2020) 100371.
  * [7] M. H. Nazari, M. B. Sanjareh, A. Khodadadi, M. Torkashvand, S. H. Hosseinian, An economy-oriented dg-based scheme for reliability improvement and loss reduction of active distribution network based on game-theoretic sharing strategy, Sustainable Energy, Grids and Networks 27 (2021) 100514.
  * [8] M. Gautam, N. Bhusal, M. Benidris, H. Livani, A cooperative game theory-based secondary frequency regulation in distribution systems, in: 53rd North American Power Symposium (NAPS), IEEE, 2022, pp. 1–6.
  * [9] M. Gautam, N. Bhusal, M. Benidris, A cooperative game theory-based approach to sizing and siting of distributed energy resources, in: 2021 53rd North American Power Symposium (NAPS), IEEE, 2022, pp. 1–6.
  * [10] M. A. Bidgoli, A. Ahmadian, Multi-stage optimal scheduling of multi-microgrids using deep-learning artificial neural network and cooperative game approach, Energy 239 (2022) 122036.
  * [11] S. Yang, Z. Tan, J. Zhou, F. Xue, H. Gao, H. Lin, et al., A two-level game optimal dispatching model for the park integrated energy system considering stackelberg and cooperative games, International journal of electrical power & energy systems 130 (2021) 106959.
  * [12] M. I. Azim, W. Tushar, T. K. Saha, Coalition graph game-based p2p energy trading with local voltage management, IEEE Transactions on Smart Grid 12 (5) (2021) 4389–4402.
  * [13] A. Churkin, J. Bialek, D. Pozo, E. Sauma, N. Korgin, Review of cooperative game theory applications in power system expansion planning, Renewable and Sustainable Energy Reviews 145 (2021) 111056.
  * [14] M. Tan, Y. Zhou, L. Wang, Y. Su, B. Duan, R. Wang, Fair-efficient energy trading for microgrid cluster in an active distribution network, Sustainable Energy, Grids and Networks 26 (2021) 100453.
  * [15] L. S. Shapley, M. Shubik, Competitive outcomes in the cores of market games, International Journal of Game Theory 4 (4) (1975) 229–237.
  * [16] W. Saad, Z. Han, M. Debbah, A. Hjorungnes, T. Basar, Coalitional game theory for communication networks, Ieee signal processing magazine 26 (5) (2009) 77–97.
  * [17] D. Schmeidler, The nucleolus of a characteristic function game, SIAM Journal on applied mathematics 17 (6) (1969) 1163–1170.
  * [18] C. Luo, X. Zhou, B. Lev, Core, shapley value, nucleolus and nash bargaining solution: A survey of recent developments and applications in operations management, Omega (2022) 102638.
  * [19] I. Curiel, Cooperative game theory and applications: cooperative games arising from combinatorial optimization problems, Vol. 16, Springer Science & Business Media, 2013.
  * [20] K. Shaloudegi, N. Madinehi, S. Hosseinian, H. A. Abyaneh, A novel policy for locational marginal price calculation in distribution systems based on loss reduction allocation using game theory, IEEE transactions on power systems 27 (2) (2012) 811–820.
  * [21] F. Pourahmadi, M. Fotuhi-Firuzabad, P. Dehghanian, Identification of critical components in power systems: A game theory application, in: IEEE Ind. Appl. Society Annual Meeting, IEEE, 2016, pp. 1–6.
  * [22] M. Gautam, N. Bhusal, M. Benidris, A cooperative game theory-based approach to under-frequency load shedding control, in: IEEE Power & Energy Society General Meeting (PESGM), IEEE, 2021, pp. 1–5.
  * [23] M. Gautam, N. Bhusal, J. Thapa, M. Benidris, A cooperative game theory-based approach to formulation of distributed slack buses, Sustainable Energy, Grids and Networks 32 (2022) 100890.
  * [24] M. Gautam, N. Bhusal, M. Benidris, A cooperative game theory-based approach to sizing and siting of distributed energy resources, in: 2021 North American Power Symposium (NAPS), IEEE, 2021, pp. 01–06.
  * [25] L. Han, T. Morstyn, M. D. McCulloch, Scaling up cooperative game theory-based energy management using prosumer clustering, IEEE Transactions on Smart Grid 12 (1) (2020) 289–300.
  * [26] G. Erli, K. Takahasi, L. Chen, I. Kurihara, Transmission expansion cost allocation based on cooperative game theory for congestion relief, International Journal of Electrical Power & Energy Systems 27 (1) (2005) 61–67.
  * [27] K. N. Hasan, R. Preece, J. V. Milanović, Application of game theoretic approaches for identification of critical parameters affecting power system small-disturbance stability, International Journal of Electrical Power & Energy Systems 97 (2018) 344–352.
  * [28] M. Gautam, M. Benidris, Pre-positioning of movable energy resources for distribution system resilience enhancement, in: 2022 International Conference on Smart Energy Systems and Technologies (SEST), IEEE, 2022, pp. 1–6.
  * [29] S. Malik, M. Duffy, S. Thakur, B. Hayes, J. Breslin, A priority-based approach for peer-to-peer energy trading using cooperative game theory in local energy community, International Journal of Electrical Power & Energy Systems 137 (2022) 107865.
  * [30] M. Gautam, M. M. Lakouraj, N. Bhusal, M. Benidris, H. Livani, Allocating reserves in active distribution systems for tertiary frequency regulation, in: 2022 IEEE Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT), IEEE, 2022, pp. 1–5.


2010 Mathematics Subject Classification:11J06.Key words and phrases: Continued
fractions, Diophantine approximation.

Discrete part of the second Lagrange spectrum

Dmitry Gayfulin111This work was supported by the Russian Science Foundation
under grant No. 22-41-05001.

###### Abstract

Given an irrational number $\alpha$ consider its irrationality measure
function $\psi_{\alpha}(t)=\min\limits_{1\leqslant q\leqslant
t,q\in\mathbb{Z}}\|q\alpha\|$. The set of all values of
$\lambda(\alpha)=(\limsup\limits_{t\to\infty}t\psi_{\alpha}(t))^{-1}$ where
$\alpha$ runs through the set $\mathbb{R}\setminus\mathbb{Q}$ is called the
Lagrange spectrum $\mathbb{L}$. In the paper [6] an irrationality measure
function $\psi^{[2]}_{\alpha}(t)=\min\limits_{1\leqslant q\leqslant
t,q\in\mathbb{Z},q\neq q_{i}}\|q\alpha\|$ was introduced. In other words, we
consider the best approximations by fractions, whose denominators are not the
denominators of the convergents to $\alpha$. Replacing the function
$\psi_{\alpha}$ in the definition of $\mathbb{L}$ by $\psi^{[2]}_{\alpha}$,
one can get a set $\mathbb{L}_{2}$ which is called the ’’second’’ Lagrange
spectrum. In this paper we give the complete structure of discrete part of
$\mathbb{L}_{2}$.

##  1 Introduction

Consider an arbitrary irrational number $\alpha$. Denote by $a_{i},\
i\in\mathbb{Z}_{\geqslant 0}$ the partial quotients of its continued fraction
expansion

$\alpha=[a_{0};a_{1},a_{2},\ldots]=a_{0}+\cfrac{1}{a_{1}+\cfrac{1}{a_{2}+\ldots}},\leavevmode\nobreak\
a_{0}\in\mathbb{Z},\leavevmode\nobreak\
a_{i}\in\mathbb{Z}_{+},\leavevmode\nobreak\ i=1,2,\ldots.$ (1)

Let us denote by $\frac{p_{n}}{q_{n}}$ the $n$-th convergent fraction to
$\alpha$, i.e. $\frac{p_{n}}{q_{n}}:=[a_{0};a_{1},\ldots,a_{n}]$. Define
$\mathcal{Q}_{\alpha}:=\\{q_{1},q_{2},\ldots\\}$ to be the sequence of
denominators of the convergents to $\alpha$. The irrationality measure
function of $\alpha$ is defined as

$\psi_{\alpha}(t):=\min\limits_{1\leqslant q\leqslant
t,q\in\mathbb{Z}}\|q\alpha\|,\,\,\,\,\,\text{where}\,\,\,\,\,\|x\|=\min\limits_{n\in\mathbb{Z}}|x-n|.$

By Lagrange’s theorem on best approximations (see [3]), $\psi_{\alpha}(t)$ is
a piecewise constant function, moreover

$\psi_{\alpha}(t)=|q_{n}\alpha-p_{n}|=\|q_{n}\alpha\|\,\,\,\,\,\text{
for}\,\,\,\,\,q_{n}\leqslant t<q_{n+1}.$

Let

$\alpha_{n}:=[a_{n};a_{n+1},\ldots],\quad\alpha_{n}^{*}:=[0;a_{n},a_{n-1},\ldots,a_{1}].$

We say that two irrational numbers $\alpha$ and $\beta$ are equivalent if
$\alpha_{n}=\beta_{m}$ for some $n,m\in\mathbb{N}$. It is well known fact,
usually called Perron’s formula, that for any $n\in\mathbb{N}$ one has

$\|q_{n}\alpha\|=\frac{1}{q_{n}(\alpha_{n+1}+\alpha_{n}^{*})}.$

See [1], Appendix 1 for details. The Lagrange constant of an irrational number
$\alpha$ is defined as

$\lambda(\alpha):=\limsup_{t\to\infty}(t\cdot\psi_{\alpha}(t))^{-1}=\limsup_{t\to\infty}(\alpha_{t+1}+\alpha_{t}^{*}).$
(2)

The set of values $\lambda(\alpha)$ as $\alpha$ runs through the set of all
irrational numbers forms the Lagrange spectrum $\mathbb{L}$

$\mathbb{L}:=\\{\lambda\leavevmode\nobreak\ |\leavevmode\nobreak\
\exists\alpha\in\mathbb{R\setminus Q}\colon\lambda=\lambda(\alpha)\\}.$ (3)

One can find a nice and detailed survey of the results about the Lagrange
spectrum up to 1990s in a book [1].
Remark. Some authors, for example [6], define the Lagrange constant
$\lambda(\alpha)$ equal to
$\liminf\limits_{t\to\infty}t\cdot\psi_{\alpha}(t)$. Therefore, the Lagrange
spectrum, defined by these authors, contains the reciprocals of the elements
of $\mathbb{L}$ from our definition.

In [6] Moshchevitin considered an irrationality measure function

$\psi^{[2]}_{\alpha}(t):=\min\limits_{1\leqslant q\leqslant
t,q\in\mathbb{Z},q\notin\mathcal{Q}_{\alpha}}\|q\alpha\|.$ (4)

related to so-called second best approximations. Obviously,
$\psi^{[2]}_{\alpha}(t)$ is also a non-increasing peacewise constant function.
It is connected with the properties of best approximations by fractions, whose
denominators are not the denominators of the convergents to $\alpha$. Also, in
[6] an analogue of Lagrange constant was defined

$\lambda^{[2]}(\alpha):=\limsup_{t\to\infty}(t\cdot\psi^{[2]}_{\alpha}(t))^{-1}$
(5)

and the corresponding spectrum

$\mathbb{L}_{2}:=\\{\lambda\leavevmode\nobreak\ |\leavevmode\nobreak\
\exists\alpha\in\mathbb{R\setminus Q}\colon\lambda=\lambda^{[2]}(\alpha)\\}$
(6)

was considered. The structure of $\mathbb{L}_{2}$ in some sense is similar to
the structure of $\mathbb{L}$. The smallest elements of $\mathbb{L}_{2}$ form
a countable discrete set and $\mathbb{L}_{2}$ contains a Hall’s ray i.e.
$\exists\mu:(\mu,+\infty)\in\mathbb{L}_{2}$.

However, in the present paper we show that, unlike the classical Lagrange
spectrum $\mathbb{L}$, whose discrete part is connected with the properties of
so-called Markoff triples, the discrete part of $\mathbb{L}_{2}$ has a short
and simple description. We prove that if a real number $x$ belongs to the
discrete part of $\mathbb{L}_{2}$, then $x$ is equivalent to one of the
following numbers: $[1;\overline{1}]$, $[1;\overline{1,1,3}]$ or
$[1;\overline{1,1,1,1,3,(1,1,3)_{2k-1}}]$, where $k\geqslant 1$. We write
$(a_{1},\ldots,a_{n})_{m}$ if the pattern $a_{1},\ldots,a_{n}$ is repeated $m$
times and $\overline{a_{1},\ldots,a_{n}}$ if this pattern is repeated
infinitely many times.

It turns out that the discrete part of $\mathbb{L}_{2}$ is similar to the
discrete part of so-called Dirichlet spectrum $\mathbb{D}$, which is defined
as follows. Denote

$d_{n}(\alpha):=[a_{n};a_{n-1},\ldots,a_{1}][a_{n+1};a_{n+2},\ldots]$

and

$d(\alpha):=\limsup\limits_{n\to\infty}d_{n}(\alpha).$

Then $\mathbb{D}$ is defined as a set of values taken by $d(\alpha)$ as
$\alpha$ runs through the set of all irrational numbers. Spectrum $\mathbb{D}$
was studied by several authors (see for example [2], [4], [5]). It was shown
by Lesca [4] that if $d(\alpha)<2+\sqrt{5}$, which is the accumulation point
of the discrete part of $\mathbb{D}$, then $\alpha$ is equivalent either to
$[1;\overline{1}]$ or to $[1;\overline{(1)_{2k-1},2}]$ for some $k\geqslant
1$. Our proof is similar to his argument.

##  2 Results by Moshchevitin and Semenyuk

We start with the lemma from [6] which is the main tool to calculate
$\lambda^{[2]}(\alpha)$ of given irrational number $\alpha$. We follow the
notation of this paper but, as we already mentioned, we consider the
’’reverse’’ definition of $\mathbb{L}$ and $\mathbb{L}_{2}$. That is why,
$\varkappa^{i}_{n}(\alpha)$ in our notation equals
$1/\varkappa^{i}_{n}(\alpha)$ in the notation of the paper [6].

######  Lemma 1.

Suppose that an irrational number $\alpha$ is not equivalent to
$\frac{1+\sqrt{5}}{2}=[1;\overline{1}]$. Consider three quantities:

$\varkappa^{1}_{n}(\alpha)=\frac{\alpha_{n}+\alpha^{*}_{n-1}}{(1+\alpha^{*}_{n-1})(\alpha_{n}-1)},\,\,\,\,\,\,\varkappa^{2}_{n}(\alpha)=\frac{\alpha_{n+1}+\alpha^{*}_{n}}{(1-\alpha^{*}_{n})(\alpha_{n+1}+1)},\,\,\,\,\,\,\varkappa^{4}_{n}(\alpha)=\frac{\alpha_{n}+\alpha^{*}_{n-1}}{4}.$
(7)

Then

$\lambda^{[2]}(\alpha)=\limsup\limits_{n\to\infty\colon a_{n}\geqslant
2}\max(\varkappa^{1}_{n}(\alpha),\varkappa^{2}_{n}(\alpha),\varkappa^{4}_{n}(\alpha)).$
(8)

In the paper [6] the two smallest elements of $\mathbb{L}_{2}$ were
calculated.
Theorem A.

  1. 1.

The smallest element of $\mathbb{L}_{2}$ is
$\lambda_{1}:=\frac{\sqrt{5}}{4}\approx 0.559016$. Moreover, if
$\lambda^{[2]}(\alpha)=\lambda_{1}$, then
$\alpha\sim\frac{1+\sqrt{5}}{2}=[1;\overline{1}]$.

  2. 2.

The second smallest element of $\mathbb{L}_{2}$ is
$\lambda_{2}:=\frac{\sqrt{17}}{4}\approx 1.030776$. Moreover, if
$\lambda^{[2]}(\alpha)=\lambda_{2}$, then
$\alpha\sim\frac{1+\sqrt{17}}{2}=[2;\overline{1,1,3}]$.

In [7] P. Semenyuk calculated the third smallest element of $\mathbb{L}_{2}$.
Theorem B. The third smallest element of $\mathbb{L}_{2}$ is
$\lambda_{3}:=\frac{13\sqrt{173}}{164}\approx 1.042611$. Moreover, if
$\lambda^{[2]}(\alpha)=\lambda_{3}$, then
$\alpha\sim\frac{39+13\sqrt{17}}{82}=[2;\overline{1,1,1,1,3,1,1,3}]$.

##  3 Main result

For each $n\geqslant 3$ define
$\xi_{n}=[0;\overline{1,1,1,1,3,(1,1,3)_{2n-5}}]$ and

$\lambda_{n}:=\frac{[3;\overline{(1,1,3)_{2n-5},1,1,1,1,3}]+[0;\overline{1,1,1,1,(3,1,1)_{2n-5}}]}{4}.$
(9)

One can easily see that $\lambda_{3}$ defined in (9) is the same constant as
in Theorem B. Let us also denote by $\lambda_{\infty}$ the limit

$\lambda_{\infty}:=\lim\limits_{n\to\infty}\lambda_{n}=\frac{[3;\overline{1,1,3}]+[0;1,1,1,1,\overline{3,1,1}]}{4}=\frac{3\sqrt{17}+21}{32}\approx
1.042791.$

Now we are ready to formulate our main result.

######  Theorem 1.

  1. 1.

The spectrum $\mathbb{L}_{2}$ below $\lambda_{\infty}$ forms a discrete set

$(-\infty,\lambda_{\infty})\cap\mathbb{L}_{2}=\\{\lambda_{1}<\lambda_{2}<\ldots<\lambda_{n}<\ldots\\},$

where $\lambda_{1}$ and $\lambda_{2}$ are defined in Theorem A,
$\lambda_{n},n\geqslant 3$ is defined in (9). Moreover,
$\lambda_{\infty}\in\mathbb{L}_{2}$.

  2. 2.

For all $n\geqslant 3$ if an irrational $\alpha$ is such that
$\lambda^{[2]}(\alpha)=\lambda_{n}$, then $\alpha\sim\xi_{n}$.

##  4 Prohibited patterns

The following lemma was proved in [6] and [7]. For the sake of completeness,
we give a sketch of proof of it.

######  Lemma 2.

Assume that the continued fraction expansion
$[a_{0};a_{1},\ldots,a_{n},\ldots]$ of an irrational number $\alpha$ contains
infinitely many elements greater than $3$ or infinitely many patterns of the
form $2$, $33$, $313$, $31113$, $311111$, $1113111$. Then
$\lambda^{[2]}(\alpha)>\lambda_{\infty}$.

###### Proof.

See the table below. The bold script indicates the element $a_{n}$. To give an
example, let us prove the estimate on the third line. Suppose that $a_{n}=2$
for infinitely many $n$. It is clear that

$\lambda^{[2]}(\alpha)=\limsup\limits_{n\to\infty\colon a_{n}\geqslant
2}\max(\varkappa^{1}_{n}(\alpha),\varkappa^{2}_{n}(\alpha),\varkappa^{4}_{n}(\alpha))\geqslant\limsup\limits_{n\to\infty\colon
a_{n}\geqslant 2}\varkappa^{2}_{n}(\alpha).$

Note that the function $\varkappa^{1}_{n}(\alpha_{n},\alpha^{*}_{n-1})$ is
decreasing on both arguments while the functions
$\varkappa^{2}_{n}(\alpha_{n+1},\alpha^{*}_{n})$ and
$\varkappa^{4}_{n}(\alpha_{n},\alpha^{*}_{n-1})$ are increasing on both
arguments. Therefore, in order to obtain the lower estimate of
$\varkappa^{2}_{n}$, we need to substitute the lower estimates of
$\alpha_{n+1}$ and $\alpha^{*}_{n}$. As we see from the lines 1 and 2 of the
table below, without loss of generality one can say that $a_{i}\leqslant 3$
for all $i\geqslant 1$. Thus, $\alpha_{n+1}\geqslant[1;\overline{3,1}]$ and
$\alpha^{*}_{n}\geqslant[0;2,\overline{1,3}]$. Substituting these estimates to
(7) yields $\varkappa^{2}_{n}(\alpha)\geqslant 1.123722>\lambda_{\infty}$.

Pattern |  $\varkappa^{i}_{n}$ used | Lower estimate | Numerical value
---|---|---|---
$a_{n}\geqslant 5$ | $\varkappa^{4}_{n}$ |  20cm([5]+[0])/4 | $1.25$
$\boldsymbol{4}$ | $\varkappa^{4}_{n}$ | $[4;\overline{4,1}]+[0;\overline{4,1}]$ | $1.103553$
$\boldsymbol{2}$ | $\varkappa^{2}_{n}$ |  |  20cm$\alpha_{n+1}\geqslant[1;\overline{3,1}];\ \ \alpha^{*}_{n}\geqslant[0;2,\overline{1,3}]$
---
1.116515
$3\boldsymbol{3}$ | $\varkappa^{1}_{n}$ |  |  20cm$\alpha_{n}\leqslant[3;\overline{1,3}];\ \ \alpha^{*}_{n-1}\leqslant[0;3,\overline{3,1}]$
---
1.123722
$\boldsymbol{3}13$ | $\varkappa^{4}_{n}$ | $([3;1,3,\overline{3,1}]+[0;1,\overline{1,3}])/4$ | 1.080930
$\boldsymbol{3}1113$ | $\varkappa^{4}_{n}$ |  |  20cm$([3;1,1,1,3,1,1,\overline{3,1,1,1}]+[0;1,1,\overline{3,1,1,1}])/4$
---
1.050188
$\boldsymbol{3}11111$ | $\varkappa^{4}_{n}$ |  |  20cm$([3;1,1,1,1,1,1,\overline{3,1,1,1}]+[0;1,1,\overline{3,1,1,1}])/4$
---
1.044287
$111\boldsymbol{3}111$ | $\varkappa^{4}_{n}$ |  |  20cm$([3;1,1,1,1,\overline{3,1,1,1}]+[0;1,1,1,1,\overline{3,1,1,1}])/4$
---
1.054716

The lemma is proven. ∎

We will call the pattern $(b_{1},\ldots,b_{k})$ prohibited if the fact that
this pattern occurs in the sequence $(a_{1},a_{2},\ldots)$ infinitely many
times implies that $\lambda^{[2]}(\alpha)>\lambda_{\infty}$. In other words,
Lemma 2 states that all the patterns from the first column of the table above
are prohibited. The following corollary is an immediate consequence of Lemma
2.

######  Corollary 1.

Suppose that $\lambda_{2}<\lambda^{[2]}(\alpha)\leqslant\lambda_{\infty}$ for
some irrational $\alpha=[a_{0};a_{1},\ldots,a_{n},\ldots]$. Then there exists
$N$ such that the sequence $(a_{N},a_{N+1},\ldots)$ has the form
$(31111(311)_{n_{1}}31111(311)_{n_{2}}31111\ldots)$, where all $n_{i}\geqslant
1$.

Without loss of generality one can say that number $N$ from the previous
corollary equals $1$. We will frequently refer to the following classical
lemma concerning difference of two continued fractions.

######  Lemma 3.

Let $\alpha=[a_{0};a_{1},\ldots,a_{n},\alpha_{n+1}]$ and
$\beta=[a_{0};a_{1},\ldots,a_{n},\beta_{n+1}]$ be two continued fractions.
Then

$\beta-\alpha=(-1)^{n+1}\frac{\beta_{n+1}-\alpha_{n+1}}{q_{n}^{2}(\alpha_{n+1}+\alpha^{*}_{n})(\beta_{n+1}+\alpha^{*}_{n})},$
(10)

where $q_{n}$ is the denominator of the convergent
$\frac{p_{n}}{q_{n}}=[a_{0};a_{1},\ldots,a_{n}]$.

###### Proof.

Note that $\alpha^{*}_{n}=\beta^{*}_{n}$. Using Perron’s formula one can
easily see that

$\beta-\alpha=\biggl{(}\beta-\frac{p_{n}}{q_{n}}\biggr{)}-\biggl{(}\alpha-\frac{p_{n}}{q_{n}}\biggr{)}=\frac{(-1)^{n+1}}{q_{n}^{2}}\biggl{(}\frac{1}{\alpha_{n+1}+\alpha^{*}_{n}}-\frac{1}{\beta_{n+1}+\alpha^{*}_{n}}\biggr{)}=\frac{(-1)^{n+1}}{q_{n}^{2}}\frac{\beta_{n+1}-\alpha_{n+1}}{(\alpha_{n+1}+\alpha^{*}_{n})(\beta_{n+1}+\alpha^{*}_{n})}.$

∎

One can consider the value $q_{t}$ as the continuant of the sequence
$(a_{1},\ldots,a_{t})$. Let us give some definition. Suppose that $A$ is an
arbitrary (possibly empty) finite sequence of positive integers. By $\langle
A\rangle$ we denote its continuant. It is defined as follows: continuant of an
empty sequence $\langle\cdot\rangle$ equals $1$, $\langle a_{1}\rangle=a_{1}$,
if $t\geqslant 2$ then one has

$\langle a_{1},a_{2},\ldots,a_{t}\rangle=a_{t}\langle
a_{1},a_{2},\ldots,a_{t-1}\rangle+\langle a_{1},a_{2},\ldots,a_{t-2}\rangle.$
(11)

One can see that

$[a_{0};a_{1},\ldots,a_{t}]=\frac{\langle
a_{0},a_{1},a_{2},\ldots,a_{t}\rangle}{\langle
a_{1},a_{2},\ldots,a_{t}\rangle}=\frac{p_{t}}{q_{t}}.$ (12)

Rule (11) can be generalized as follows:

$\begin{split}\langle
a_{1},a_{2},\ldots,a_{t},a_{t+1},\ldots,a_{s}\rangle=\langle
a_{1},a_{2},\ldots,a_{t}\rangle\langle a_{t+1},\ldots,a_{s}\rangle+\langle
a_{1},a_{2},\ldots,a_{t-1}\rangle\langle a_{t+2},\ldots,a_{s}\rangle=\\\
=\langle a_{1},a_{2},\ldots,a_{t}\rangle\langle
a_{t+1},a_{t+2},\ldots,a_{s}\rangle(1+[0;a_{t},a_{t-1},\ldots,a_{1}][0;a_{t+1},a_{t+2},\ldots,a_{s}]).\end{split}$
(13)

Denote $\alpha_{\infty}:=[3;\overline{1,1,3}]$ and
$\alpha^{*}_{\infty}:=[0;1,1,1,1,\overline{3,1,1}]$. Then
$\lambda_{\infty}=\frac{\alpha_{\infty}+\alpha^{*}_{\infty}}{4}$.

######  Lemma 4.

The pattern

$111(311)_{2m}3111$ (14)

is prohibited for all $m\geqslant 0$.

###### Proof.

We will prove this statement by induction on $m$. The base case $m=0$ is
already considered in Lemma 2. Suppose that for all $m\leqslant k$ the pattern
(14) is prohibited. Let us also assume that the pattern (14) for $m=k+1$
occurs in the sequence $(a_{1},\ldots,a_{n},\ldots)$ infinitely many times but
$\lambda^{[2]}(\alpha)\leqslant\lambda_{\infty}$. Let $n$ be an index of the
first ’’3’’ in the group $(311)_{2k+2}$. Due to Lemma 1, to get a
contradiction it is enough to show that
$\varkappa^{4}_{n}(\alpha)>\lambda_{\infty}$. This is equivalent to the
inequality

$\alpha_{n}-\alpha_{\infty}>\alpha^{*}_{\infty}-\alpha^{*}_{n-1}.$ (15)

Let us obtain the lower estimate of $\alpha_{n}-\alpha_{\infty}$ using Lemma
3. We know that

$\alpha_{n}-\alpha_{\infty}=[\underbrace{(3;1,1)_{2k+2},3,1,1}_{\text{coinciding
part}},1,1,\ldots]-[\underbrace{(3;1,1)_{2k+2},3,1,1}_{\text{coinciding
part}},3,1,1,\ldots].$ (16)

The first different partial quotient has index $6k+9$, hence by Lemma 3 one
has

$\begin{split}\alpha_{n}-\alpha_{\infty}=\frac{[3;1,1,\ldots]-[1;1,1,\ldots]}{\langle
1,1,(3,1,1)_{2k+2}\rangle^{2}([3;1,1,\ldots]+[1;1,3,\ldots])([1;1,1,\ldots]+[1;1,3,\ldots])}>\\\
\frac{[3;1,1]-[1;1]}{\langle
1,1,(3,1,1)_{2k+2}\rangle^{2}([3;1]+[1;1])([1;1]+[1;1])}=\frac{1}{16\langle
1,1,(3,1,1)_{2k+2}\rangle^{2}}.\end{split}$ (17)

Now we obtain the lower estimate of $\alpha^{*}_{n-1}=[0;1,1,1,1,3,\ldots]$.
As the patterns $33$, $313$, and $1113111$ are prohibited, it extends as

$\alpha^{*}_{n-1}=[0;1,1,1,1,(3,1,1)_{2},\ldots].$

As the we need the lower estimate of $\alpha^{*}_{n-1}$, we write

$\alpha^{*}_{n-1}\geqslant[0;1,1,1,1,(3,1,1)_{2},3,\ldots].$

Which extends as

$\alpha^{*}_{n-1}\geqslant[0;1,1,1,1,(3,1,1)_{2},3,1,1,\ldots].$

By the induction hypothesis, the pattern $111(311)_{2}3111$ is prohibited.
Hence

$\alpha^{*}_{n-1}\geqslant[0;1,1,1,1,(3,1,1)_{3},3,1,1\ldots]=[0;1,1,1,1,(3,1,1)_{4}\ldots].$

Repeating the same argument $k$ times, we obtain that

$\alpha^{*}_{n-1}\geqslant[0;1,1,1,1,(3,1,1)_{2k+2},3,1,1,1,1,\ldots].$

Let us now estimate the difference $\alpha^{*}_{\infty}-\alpha^{*}_{n-1}$ from
above.

$\alpha^{*}_{\infty}-\alpha^{*}_{n-1}=[\underbrace{0;1,1,1,1,(3,1,1)_{2k+2},3,1,1}_{\text{coinciding
part}},3,1,1,\ldots]-[\underbrace{0;1,1,1,1,(3,1,1)_{2k+2},3,1,1}_{\text{coinciding
part}},1,1,\ldots].$

The first different partial quotient has index $6k+14$, hence by Lemma 3 one
has

$\begin{split}\alpha^{*}_{\infty}-\alpha^{*}_{n-1}=\frac{[3;1,1,\ldots]-[1;1,1,\ldots]}{\langle
1,1,1,1,(3,1,1)_{2k+3}\rangle^{2}([3;1,1,\ldots]+[1;1,3,\ldots])([1;1,1,\ldots]+[1;1,3,\ldots])}<\\\
\frac{[3;1]-[1;1,1]}{\langle
1,1,1,1,(3,1,1)_{2k+3}\rangle^{2}([3;1,1]+[1;1,1])([1;1,1]+[1;1,1])}=\frac{1}{6\langle
1,1,1,1,(3,1,1)_{2k+3}\rangle^{2}}.\end{split}$ (18)

Comparing (17) and (18), one can see that in order to obtain (15) it suffices
to show that

$\frac{\langle 1,1,1,1,(3,1,1)_{2k+3}\rangle}{\langle
1,1,(3,1,1)_{2k+2}\rangle}>\sqrt{\frac{8}{3}}.$

The last inequality easily follows from the trivial estimates

$\langle 1,1,1,1,(3,1,1)_{2k+3}\rangle>\langle
1,1,1,1,3,1,1\rangle\langle(3,1,1)_{2k+2}\rangle=41\langle(3,1,1)_{2k+2}\rangle$

and

$\langle 1,1,(3,1,1)_{2k+2}\rangle<3\langle(3,1,1)_{2k+2}\rangle.$

Lemma is proven. ∎

######  Lemma 5.

The pattern

$31111(311)_{2m+1}31111(311)_{2k+1}31111,$ (19)

where $k>m\geqslant 0$ is prohibited.

###### Proof.

We will use the approach of Lemma 4. Our goal is to show that the inequality

$\alpha_{\infty}-\alpha_{n}<\alpha^{*}_{n-1}-\alpha^{*}_{\infty}.$ (20)

holds for infinitely many $n$. Let $n$ be an index of the first ’’3’’ in the
group $(311)_{2k+1}$. Once again, we obtain the upper estimate of
$\alpha_{\infty}-\alpha_{n}$ using Lemma 3.

$\alpha_{\infty}-\alpha_{n}=[\underbrace{(3;1,1)_{2k+1},3,1,1}_{\text{coinciding
part}},3,1,1,3,1,1,\ldots]-[\underbrace{(3;1,1)_{2k+1},3,1,1}_{\text{coinciding
part}},1,1,3,1,1,\ldots].$ (21)

The first different partial quotient has index $6k+6$. Using the estimates
from (18), one can see that

$\alpha_{\infty}-\alpha_{n}<\frac{1}{6\langle 1,1,(3,1,1)_{2k+1}\rangle^{2}}.$
(22)

Now we need a lower estimate of $\alpha^{*}_{n-1}-\alpha^{*}_{\infty}$.

$\alpha^{*}_{n-1}-\alpha^{*}_{\infty}=[\underbrace{0;1,1,1,1,(3,1,1)_{2m+1},3,1,1}_{\text{coinciding
part}},1,1,\ldots]-[\underbrace{0;1,1,1,1,(3,1,1)_{2m+1},3,1,1}_{\text{coinciding
part}},3,1,1,\ldots].$

The first different partial quotient has index $6m+11$. Using the estimates
from (17), one can see that

$\alpha^{*}_{n-1}-\alpha^{*}_{\infty}>\frac{1}{16\langle
1,1,1,1,(3,1,1)_{2m+2}\rangle^{2}}.$ (23)

Comparing (22) and (23), we deduce that in order to obtain (20) it suffices to
show that

$\frac{\langle 1,1,(3,1,1)_{2k+1}\rangle}{\langle
1,1,1,1,(3,1,1)_{2m+2}\rangle}>\sqrt{\frac{8}{3}}.$

As $k\geqslant m+1$, it is enough to verify the inequality

$\frac{\langle 1,1,(3,1,1)_{2m+3}\rangle}{\langle
1,1,1,1,(3,1,1)_{2m+2}\rangle}>\sqrt{\frac{8}{3}}$ (24)

for all $m\geqslant 0$. As

$\langle 1,1,(3,1,1)_{2m+3}\rangle\geqslant\langle
1,1,(3,1,1)_{2m+2}\rangle\langle 3,1,1\rangle=7\langle
1,1,(3,1,1)_{2m+2}\rangle$

and

$\langle 1,1,1,1,(3,1,1)_{2m+2}\rangle\leqslant 3\langle
1,1,(3,1,1)_{2m+2}\rangle,$

the inequality (24) holds and the lemma is proven. ∎

As an immediate consequence of Lemmas 4 and 5, we deduce the following
corollary.

######  Corollary 2.

Suppose that $\lambda_{2}<\lambda^{[2]}(\alpha)<\lambda_{\infty}$ for some
irrational $\alpha=[a_{0};a_{1},\ldots,a_{n},\ldots]$. Then
$\alpha\sim\xi_{n}$ for some $n\geqslant 3$.

##  5 Lower estimates

In this section we show that $\lambda^{[2]}(\xi_{i})=\lambda_{i}$ and thus
complete the proof of Theorem 1. First, we prove two technical lemmas.

######  Lemma 6.

Let $\alpha=[a_{0};a_{1},\ldots]$ be an arbitrary irrational number. If
$a_{n}$ is the middle ’’3’’ in the pattern $311\boldsymbol{3}113$, then

$\max(\varkappa^{1}_{n}(\alpha),\varkappa^{2}_{n}(\alpha),\varkappa^{4}_{n}(\alpha))<1.04.$

###### Proof.

As the function $\varkappa^{1}_{n}(\alpha_{n},\alpha^{*}_{n-1})$ is decreasing
on both arguments and

$\alpha_{n}\geqslant[3;1,1,\overline{3,1,1,1}],\quad\
\alpha^{*}_{n-1}\geqslant[0;1,1,\overline{3,1,1,1}],$

we see that

$\varkappa^{1}_{n}(\alpha)\leqslant\frac{[3;1,1,\overline{3,1,1,1}]+[0;1,1,\overline{3,1,1,1}]}{(1+[0;1,1,\overline{3,1,1,1}])([3;1,1,\overline{3,1,1,1}]-1)}\approx
1.031440.$ (25)

The quantities $\varkappa^{2}_{n}(\alpha)$ and $\varkappa^{4}_{n}(\alpha)$ are
estimated in a similar way. As

$\alpha_{n+1}\leqslant[1;1,\overline{3,1,1,1}],\quad\alpha^{*}_{n}\leqslant[0;3,1,1,\overline{3,1,1,1}],$

we get the following estimate

$\varkappa^{2}_{n}(\alpha)\leqslant\frac{[1;1,\overline{3,1,1,1}]+[0;3,1,1,\overline{3,1,1,1}]}{(1-[1;1,\overline{3,1,1,1}])(1+[0;3,1,1,\overline{3,1,1,1}])}\approx
1.031440.$ (26)

Finally, as

$\alpha_{n}\leqslant[3;1,1,3,1,1,\overline{3,1,1,1}],\quad\
\alpha^{*}_{n-1}\leqslant[0;1,1,3,1,1,\overline{3,1,1,1}]$

we see that

$\varkappa^{4}_{n}(\alpha)\leqslant\frac{[3;1,1,3,1,1,\overline{3,1,1,1}]+[0;1,1,3,1,1,\overline{3,1,1,1}]}{4}\approx
1.030785.$ (27)

Combining the estimates (25), (26), and (27) yields the statement of the
lemma. ∎

######  Lemma 7.

Let $\alpha=[a_{0};a_{1},\ldots]$ be an arbitrary irrational number. If
$a_{n}$ is the middle ’’3’’ in the pattern $31111\boldsymbol{3}113$ or
$31111\boldsymbol{3}113$, then

$\varkappa^{4}_{n}(\alpha)>\max(\varkappa^{1}_{n}(\alpha),\varkappa^{2}_{n}(\alpha)).$

###### Proof.

We will give a proof for the pattern $31111\boldsymbol{3}113$ only, as the
proof for the second pattern is exactly same. One can easily see that
$\varkappa^{4}_{n}(\alpha)>\varkappa^{1}_{n}(\alpha)$ if and only if the
inequality

$(1+\alpha^{*}_{n-1})(\alpha_{n}-1)>4$ (28)

holds. As

$\alpha_{n}\geqslant[3;1,1,\overline{3,1,1,1}],\quad\alpha^{*}_{n-1}\geqslant[0;1,1,1,1,\overline{3,1,1,1}],$

we have the following estimate

$(1+\alpha^{*}_{n-1})(\alpha_{n}-1)\geqslant([1;1,1,1,1,\overline{3,1,1,1}])([2;1,1,\overline{3,1,1,1}])\approx
4.120747$

and the inequality (28) holds.

Using the the obvious properties $\alpha_{n}=a_{n}+1/\alpha_{n+1}$ and
$\alpha^{*}_{n}=1/(a_{n}+\alpha^{*}_{n-1})$ and the fact that $a_{n}=3$, one
can transform $\varkappa^{2}_{n}$ and $\varkappa^{4}_{n}$ as follows:

$\varkappa^{2}_{n}(\alpha)=\frac{3\alpha_{n+1}+\alpha_{n+1}\alpha^{*}_{n-1}+1}{(2+\alpha^{*}_{n-1})(\alpha_{n+1}+1)},\quad\varkappa^{4}_{n}(\alpha)=\frac{3\alpha_{n+1}+\alpha_{n+1}\alpha^{*}_{n-1}+1}{4\alpha_{n+1}}.$

Hence $\varkappa^{4}_{n}(\alpha)>\varkappa^{2}_{n}(\alpha)$ if and only if

$\alpha_{n+1}\alpha^{*}_{n-1}+\alpha^{*}_{n-1}-2\alpha_{n+1}+2>0.$ (29)

We know that

$\alpha_{n+1}\geqslant[1;1,\overline{3,1,1,1}],\quad\alpha^{*}_{n-1}\leqslant[0;1,1,1,1,\overline{3,1,1,1}].$

Substituting these estimates to (29), we can see that the inequality is
satisfied and therefore $\varkappa^{4}_{n}(\alpha)>\varkappa^{2}_{n}(\alpha)$.
Lemma is proven. ∎

######  Corollary 3.

$\lambda^{[2]}(\xi_{i})=\lambda_{i}$.

###### Proof.

It follows directly from Lemmas 6 and 7. ∎

######  Corollary 4.

$\lambda_{\infty}\in\mathbb{L}_{2}$.

###### Proof.

Consider

$\alpha=[0;(3,1,1)_{2n_{1}+1},3,1,1,1,1,(3,1,1)_{2n_{2}+1},3,1,1,1,1,(3,1,1)_{2n_{3}+1},\ldots],$
(30)

where $n_{i}$ is an arbitrary sequence of natural numbers that tends to
infinity. By Lemmas 6 and 7, $\lambda^{[2]}(\alpha)=\lambda_{\infty}$. ∎

Thus we completed the proof of Theorem 1. Also, from (30) one can see that the
set of real numbers satisfying $\lambda^{[2]}(\alpha)=\lambda_{\infty}$ has
continuum many elements. Note that the set of numbers satisfying
$\lambda^{[2]}(\alpha)=\lambda_{n}$ for each $n$ is countable as all such
numbers are equivalent to $\xi_{n}$.

Acknowledgements: I would like to thank Nikolay Moshchevitin for giving me the
formulation of the problem.

## References

  * [1] Cusick, T.W. and Flahive, M.E., _The Markoff and Lagrange Spectra_ , American Mathematical Society, 1989.
  * [2] Diviš В., Novak В., _A remark on the theory of diophantine approximations_ , Comment. Math. Univ. Carolinae, 12, No 1 (1971), 127—141.
  * [3] Khinchin, A.Ya., _Continued Fractions_ , University of Chicago Press, 1964.
  * [4] Lesсa J., _Sur les approximations diophantiennes á une dimension_ , L’Université de Grenoble (1968).
  * [5] Mоrimоtо S., _Zur Theorie der Approximation einer irrationalen Zahl durch rationale Zahlen_ , Tohoku Math. J., 45 (1938), 177—187.
  * [6] Moshchevitin N. G., _Über die Funktionen des Irrationalitatsmaßes_ , Dubickas, A. (ed.) et al., Analytic and probabilistic methods in number theory. Proceedings of the sixth international conference, Palanga, Lithuania, September 11-17, 2016. Vilnius: Vilnius University Publishing House. 123-148 (2017).
  * [7] Semenyuk P., _On a problem related to "second" best approximations to a real number. Preprint available at: https://arxiv.org/abs/2303.12716_

Dmitry Gayfulin,
Graz University of Technology, Institute of Analysis and Number Theory,
Steyrergasse 30/II, 8010 Graz, Austria
and
Big Data and Information Retrieval School
Faculty of Computer Science
National Research University Higher School of Economics
11 Pokrovsky boulevard, Moscow 109028 Russia
<EMAIL_ADDRESS>