Ariane Lambert-Mogiliansky

François Dubois
email: francois.dubois@math.u-psud.fr.

Transparency in Public Life A Quantum Cognition Perspective

Keywords: learning, quantum cognition, transparency learning, quantum cognition, transparency. AMS classification: 81Q99, 91C99

In this paper we investigate the implications of assuming that citizens are cognitively constrained for transparency in public life. We model cognitive limitations as reflecting a quantum property of people's mental representations of the world. There exists a multiplicity of incompatible (Bohr) complementary mental representations of a situation. As a consequence the framing of information plays a crucial role. We show that additional information can be detrimental to a quantum cognitively constrained agent: he may become more confused. We suggest some implications for the design of a public agency's website.

Introduction

Transparency is among the most debated issues in modern public life. The development of information technology has given rise to hopes for a modern truly democratic state based on transparency. As noted by Beth Noveck [START_REF] Noveck | Wiki Government: How Technology Can Make Government Better, Democracy Stronger, and Citizens More Powerful[END_REF], real applications have fallen short for those hopes. In part we suggest that this may be due to a narrow understanding of the concept of transparency. This paper is a contribution to the exploration of the links between access to information and transparency. The starting point is the recognition that access to information is not equivalent to transparency. Instead transparency is intimately related to learning. In this paper we suggest that a quantum approach to information processing by human receptors may shed some fruitful light on the public debate as well as provide insights of value for practical applications.

The information system community, among others, was early aware that in addition to the physical constraints, the transmission of information e.g., about a new information system, is conditioned by cognitive limitations. Appealing to cognitive scientists they formulate those limitations in terms of "mental models", "cognitive frames" or "scripts" that simultaneously enable and constrain understanding. Gioia writes about "definitions of (organizational) reality that serve as vehicule for understanding and action" (Gioia [START_REF] Gioia | Symbols, Script and Sense-making: creating meaning in the organizational experience[END_REF], p.50). "They include assumptions, knowledge and expectations expressed symbolically through language, visual images, metaphors and stories. Frames are flexible in content and structure having variable dimensions that skift in salience and content by context and over time" (Orlikowsky and Gash [START_REF] Orlikowsky | Technological frames: making sense of information technology in organizations[END_REF]).

In economics, we talk about "framing effects" when alternative descriptions of one and the same decision problem induce different decisions from agents. Kahneman and Tversky [START_REF]Choices, values and frames[END_REF] address framing effects by making the crucial point that "the true objects of evaluation are neither objects in the real world nor verbal descriptions of those objects; they are mental representations". To capture this feature, framing effects have been modelled as the "process of constructing a representation" as a measurement performed on the (quantum) state of the agent (Lambert-Mogiliansky, Zamir and Zwirn [START_REF] Lambert-Mogiliansky | Type indeterminacy -A Model of the KT(Khaneman Tversky)-man[END_REF]). In Lambert-Mogiliansky and Busemeyer [START_REF] Lambert-Mogiliansky | Quantum indeterminacy in Dynamic decision-making: Self-control through identity management[END_REF], we show how this approach is consistent with a number of central theories in psychology including e.g., Self perception and provides a tractable approach to questions related to identity and self-control. In this paper, we introduce element of a theory of learning based on those premises and suggest that it provides a fruitful way to capture some of the above mentioned concerns expressed by practitioners.

We propose that the cognitive process involved in information processing includes two steps: i. receiving information framed according to some representation; ii processing information in terms of ones preferred representation. This learning process is not Bayesian as soon as we allow for Bohr complementarity of representations. The issue of learning by non-classically minded agents has been approached in Danilov and Lambert Mogiliansky [START_REF] Danilov | Measurable Systems and Behavioral Sciences[END_REF][START_REF] Danilov | Decision-making under non-classical uncertainty[END_REF] and more recently in Busemeyer and Bruza [START_REF] Busemeyer | Quantum Models of Cognition and Decision[END_REF].

A central result in learning theory is that Bayesian updating (under weak conditions) converges to the truth. However critics have been raised on several aspects of Bayesianism (see e.g. Gilboa, Postlewaite and Schmeidler [START_REF] Gilboa | Rationality of Beleifs or: why savage's axioms are neither necessary nore sufficient for rationality[END_REF]. Departures from Bayesian updating may occur because they undervalue or overvalue priors (e.g., Epstein Noor Sandroni [START_REF] Epstein | Non-Bayesian updating: A theoretical framework[END_REF]). Alternative approaches have been developed in connection with Maxmin Expected Utility (Gilboa and Schmeidler [START_REF] Gilboa | Maxmin Utility with non-unique priors[END_REF]) and Multriple priors (Hanany and Klibanoff[12]). Our approach implies a novel departure from Bayesian updating appealing to the recent success of the quantum formalism in psychology and in social sciences (for a survey of recent advances see Khrenikov [START_REF] Khrennikov | Ubiquitous Quantum Structure -From Psychology to Finance[END_REF] and Busemeyer and Bruza [START_REF] Busemeyer | Quantum Models of Cognition and Decision[END_REF].

1) Learning by non-classically minded agents

It is a common place that human beings are not capable of holding very complex picture in mind (cf "small worlds" in [START_REF] Savage | The Foundation of Statistics[END_REF]. They consider reality focusing on one perspective at a time and show difficulty switching perspective as amply documented. What the quantum  Transparency in Public Life -A Quantum Cognition Perspective approach entails is that this inability to seize reality in its full richness has far reaching consequences beyond incomplete knowledge. When the perspectives are incompatible in the agent's mind, his understanding of reality does not look like a puzzle that is assembled progressively, instead the evolution of the picture of reality is subjected to disturbances (discrete jumps) which entails specific properties of the learning process.

In the present context the parallel with QM can be described as follows: the system is the subjective picture about the world, it is a psychic object. To gain information on the mental picture of the world two things can be done. One may add some information about the outside world. And one may perform a measurement of the picture by means of introspection. New information about the world transforms the picture (in a way similar to a preparation procedure). Thereafter, the agent processes information i.e., he "updates" his beliefs. This is modeled as a measurement that projects the new state (picture) onto one of the possible pictures defined by his preferred representation (see below).

Figure 1 is a well-known ambiguous picture. The mind may perceive a rabbit or a a duck. Both pictures are complete representations of the drawing: they confer a "meaning" to every detail. The brain oscillates between the two or settle for either one of them but cannot perceive both simultaneously. Both pictures are true but they are incompatible in the mind. The basic model Let the state (of understanding) of an agent be called a mental picture, we denote it |ϕ ∈ H where H is the Hilbert space of mental pictures of the (relevant) world. The present analysis addresses uncertainty exclusively linked to quantum indeterminacy reflecting cognitive constraints i.e., we shall be working exclusively with pure states. A distinctive feature of non-classical systems is the existence of dispersed pure states referred to as "intrinsic uncertainty". It is closely related to two other features of non-classical systems: the existence of incompatible measurements and the impact of the measurements on the state. 2no reason for the state to change. If all pure states are dispersion-free then measurements do not impact on pure states and therefore all measurements are compatible. On the contrary, if a state is dispersed then by necessity it will be modified by an appropriate measurement. On the other hand, the change in a pure state is the reason for 

• The notion of measurement

Before entering into the analysis let us remind of some basic notions and how they relate to our issue. Generally, a measurement is an interaction between a system and some measurement device, which yields some result, the outcome of the measurement that we can observe and record. Two measurements are compatible if they, roughly speaking, can be performed simultaneously or more precisely, if the performance of one measurement does not affect the result of the other.

In our context a measurement is an introspective operation that acts on the agent's mental picture. The agent's asks himself a question and an answer, the outcome of the mental process is brought to consciousness. We propose that the cognitive limitations documented by practitioners can be modelled as the result of incompatible mental operations that act on the mental picture.

• A preferred frame.

We shall assume that the agent seeks information because he has some concern in mind e.g., he wants to make a decision. This assumption is consistent with psychological and neurobiological evidence that human cognitive processes (including perception) are structured by some form of intentionality.

Generally, a representation is an observable R with eigenvalues {r 1 , ...r n } interpreted as the possible "eigenpictures" belonging the representation R 3 . The agent's state, a mental picture can written as a superposition of the possible eigenpictures in any representations of the (relevant) world:

|ϕ = i λ i |r i , j λ 2 i = 1, λ i ∈ R.
A decision problem is defined as a correspondance from D : H → A where H is the space of mental pictures of the world and A the set of actions. For each (mentally represented) state of the world, it defines which actions the agent wants to undertake.

Hypothesis 1

There exists a representation R * such that D is a coarsening of R * . 4 Hypothesis 1 implies that if the agent receives (maximal) information framed in representation R * he will know exactly what to do. We also say that R * is fully congruent with D. Generally, D has a lower dimensionality than H, i.e., distinct eigenpictures can induce the same action.

• The cognitive process.

In our context, it is in place to explicitly decompose the cognitive process of learning into two steps:

Step 1: Preparation The first step of the mental process is gaining information expressed within some representation R = R * (or frame -we use the terms interchangeably) . It corresponds to a fully deterministic evolution of the mental picture. It operates on the initial state(picture) so as to project it onto incompatibility of measurements. The initial outcome of a first measurement is not repeated because the system has been modified by a second measurement (see Danilov and Lambert-Mogiliansky [START_REF] Danilov | Measurable Systems and Behavioral Sciences[END_REF][START_REF] Danilov | Decision-making under non-classical uncertainty[END_REF]).

3 All the representations R, R * , etc. that we consider in this contribution have eigenspaces of dimension exactly equal to one. All these eigenstates are maximal information states for the individual. 4 A measurement M is coarser than M if every eigenset of M is contained in some eigenset of M , see Danilov and Lambert-Mogiliansky [START_REF] Danilov | Measurable Systems and Behavioral Sciences[END_REF][START_REF] Danilov | Decision-making under non-classical uncertainty[END_REF] p. 334.



Transparency in Public Life -A Quantum Cognition Perspective the one eigenpicture reflecting the information content provided (see below for a concrete example). In the terminology of QM it resembles a process of preparation 5 : |ϕ → |ϕ = |r i , where |r i is an eigenpicture of the R representation.

Step 2: Measurement After having received the information, the agent processes information i.e., updates his mental picture (r i ) with respect to his preferred representation R * . This is a non-deterministic evolution which we model as a measurement. We first express |ϕ = |r i in terms of the eigenpictures of the preferred representation, R * , |r i = j γ j |r * j applying R * we obtain R * |ϕ → |r * j with probability γ 2 j . We see that after completing the cognitive process corresponding to interpreting the information in his own mental model, the agent's actual state of information is some |r * j = |r i . The two states are not mutually exclusive (orthogonal) but they are incompatible in his mind which captures the cognitive limitation.

1.2)

Analysis: the value of new information We now develop a simple argument showing that information can increase the agent's relevant uncertainty. Uncertainty (intrinsic) is measured by the entropy of dispersion 6 in terms of the preferred representation: let |ϕ = j ν j |r * j , since γ 2 j is the probability for obtaining eigenpicture |r * j after the measurement R * , the (intrinsic) uncertainty associated with ϕ is defined

H (ϕ) = - j ν 2 j log ν 2 j
For the purpose of the argument, we shall assume that the agent's mental state is initially an eigenpicture of his preferred representation|ϕ = |r * 2 . This state reflects information that is perfectly congruent with R * but is not framed in R * 7 . But the agent is not aware of r * 2 unless he updates "his beliefs" which corresponds to the (measurement) operation of R * . If he did, he would obtain

R * |ϕ = |r * 2
He would then be fully determined with respect to the decision problem. There would not be any (relevant) uncertainty left with ν 2 = 1 we have H (ϕ) = 0. But assume that instead he acquires new information relative to another but related aspects of the issue. We denote this representation P. This corresponds to steps 1 of the cognitive process above. The mental state |ϕ is prepared into |ϕ equal to some |p i . "Enriched" with this new information, the agent now updates his mental picture with respect to his preferred representation (step 2):

|ϕ = |p 2 = j γ j |r * j → any|r * j with probability γ 2 j = 1
We see that while he previously potentially "knew" r * 2 (but was unaware of it) he is now is a state of hesitation where he believes that there is only a probability of γ 2 2 < 1 that the "true" 5 In the process of preparation a system is put into a specific state. 6 We talk about the entropy of dispersion rather than of probability distribution, because we are dealing with a pure state. See discussion above. 7 In the example "learning that the administration lacks standard of ethics" is equivalent to learning "it is worthwhile to complaint". The point is before the agent processed the information in his own frame (step 2), he is not aware of this.



Ariane Lambert-Mogiliansky and François Dubois eigenpicture is r * 2 . 8 The acquisition of new information has triggered the loss of some information leaving the agent in a state of intrinsic uncertainty captured by a strictly positive entropy:

H ϕ = - j γ 2 j log γ 2 j > 0.
Proposition 1. Assume that the agent's mental state is one eigenpicture of his preferred representation, acquiring additional information in terms of a representation that is not compatible with the preferred one leads to confusion measured by increased dispersion entropy. This is the central result of this paper. When two representations are incompatible in the agent's mind. Additional information is not always beneficial to the agent. It is unambiguously detrimental when the starting point is an eigenpicture of the preferred representation as illustrated in the argument above: the new information induces a strict loss of information implying confusion with respect to the concerns of the agent. More generally i.e., starting from an arbitrary eigenpicture (with non zero dispersion entropy) as in the example below, new information may either decrease or increase dispersion entropy.

We illustrate the result in Proposition 1 in figure 2 where the dimensionality of a representation is 2. The broad line corresponds to the preparation stage and the thin lines to the measurement. 2 is true because it reflects an information congruent with R * and |p i is also true. The agent is not mistaken. He simply cannot hold in one single picture both informations. The introspective operation when processing information p 2 involves the whole (cognitively limited) mind and therefore upsets earlier held beliefs.

• Classical cognition.

In order to better understand the result above let us consider the classical counter-part of the argument above. It is well-known that the quantum model includes the classical one as a special case when all measurements commute. It is important for the argument that follows to understand that we are not considering all possible classical models but the classical model corresponding to the quantum one where all the premises are the same except that all measurements commute. We below discuss other possible classical approaches. information as in the quantum case. Instead the interpretation is that his priors were wrong so new information brought him closer to the truth. So a legitimate question is: are we only talking about interpretation or do quantum cognitive limitations really have a more profound bearing on learning?

• Oscillating for ever.

Bayesian learning operates within a Boolean algebra. The objective is to learn the parameters of the model of the system. 9 Provided the priors are not inconsistent with the true model, we know (Schwartz 1965) that starting from any such priors Bayesian updating converges to the true state.

With quantum learning, we are in a Hilbert space, that is there exists a variety of resolutions of the system i.e., a variety of representations, of valid theories of the system. Those descriptions are not alternative to each other but complementary (in the sense of Bohr). As a consequence there exists no single true complete information state but a multiplicity of equally true maximal information states. Therefore, the state of knowledge of a quantum minded individual does not converge with new information but oscillates for ever. Consider again the example above. After the agent performed the introspective measurement R * , if the agent is being asked about his understanding in P, he will perform a new measurement of the eigenpicture resulting from the first measurement and p 2 will not be recovered with probability 1. Performing those measurements alternately, he will keep oscillating without converging i.e., without being able to settle for a definite value in both P and R * simultaneously. 10 Of course this example is simplistic and the agent might simply remember p 2 . But in more sophisticated context, we expect the modification of the mental picture to be effective. Moreover, our focus is on the consequences for decision-making of lost information which are far from selfevident.

2) Application: transparency in public life

We next address the issue of providing access to public information and its relationship with transparency in terms of the theory developed above. Consider a situation where a citizen suspects that there has been some serious wrongdoing and he must decide whether or not to file a formal complaint against a public administration. Since that is costly to him he wants to collect information to evaluate his chance of winning.

The government makes available information e.g., on a website. Information can be expressed and organized according various principles. For instance some information concerns the extent of responsibility and discretion at various step of decision-making. Another informs about the ethical rules various bureaus obey. Yet, another set of information takes the perspective of the personnel and informs about the conditions for recruitment and promotion. The assumption is that the different perspectives are incompatible in the citizen's mind. When he thinks in moral/ethical terms, he cannot simultaneously envision the implication of the allocation of responsibilities for the quality of decisions or the quality competence emerging from 9 Some consider also Bayesain updating with multiple priors (see e.g., Hanany and Klibanov [START_REF] Hanany | Undating prefrences with multiple priors[END_REF]). But there is no consensus as to how to proceed -in sharp contrast with Bayesian updating of single priors. 10 The general result is a transposition into cognition of the basic feature of quantum mechanics namely that it is not possible for complementary properties to have a determinate value simultaneously. In figure 3 we depict the case when the citizen learns the administration is competent (green plain arrow) and when he learns the process is discretionary (blue plain arrow). Recall that R * 2 (in red) is fully congruent with the requirements of decision-making. When provided the information framed according to R 1 and learning e.g., that the administration is competent. Instead of decreasing uncertainty with respect to decision-making, the new information actually increases uncertainty (dispersion entropy) thereby creating confusion in the agent's mind. The initial state (doted line) was pretty close to U, the new state C is almost equidistant to both E and U . In contrast learning that the decision processes are discretionary (projecting onto D) though not fully congruent, reduces decision uncertainty. As we see the extent of congruence it is of paramount importance for cognitively constrained agents. In contrast with the classical model where at worst orthogonal information is useless, we know from proposition 1 that information can be detrimental; the citizens get confused (increased dispersion entropy).

 Transparency in Public

Proposition 3. The government can increase citizens' confusion by providing information along a representation that is little congruent with the citizens' concerns.

This result implies that in our framework, truthful information can be used to manipulate the citizens away from their concerns in order to affect their decisions. The next section shows how full access to information can lead to confusion.

• Sequential information acquisition: the architecture of the website.

In this subsection we explore some implications of the results above for the architecture of the administration's website. Consider now a representation as a complete set of commuting observable. So for instance in R 3 , beside competence (in terms of formal education), a description of the principles for selection in recruitment, of the principles governing evaluation for promotion, 11 If the citizen pictures the administration as lacking ethical standard, that comforts his suspicion and he will definitely file a complaint. Conversely, if he is convinced the administration has high ethical standards, he will not file.



Ariane Lambert-Mogiliansky and François Dubois a description of the rules and processes to be followed is provided (from the point of view of their complexity/simplicity), etc... Similarly for the other representations e.g., R 4 provides information about the standards for decisions, the appeal procedures etc... Assume the website aims at providing full access to information. If the architect does not have in mind the quantum structure of the citizens' mind, the website will most probably be constructed so the progression in the tree mixes elements from different representations. Each new step entails a projection on a subspace of the representation to which the information belongs. But as we next show that has implication for the information previously "pictured", it is "lost" in the updating i.e., in the necessity for the citizen to be coherent i.e., fit information in one coherent to him picture.

To see this consider the following path. To facilitate the reading we let the eigenvalues of R 1 be labeled as a i and R 2 as b i the two representations are complementary in the mind of the citizen. Assume the citizen state is

|ψ = |b 1 = 3 i=1 λ i |a 1i .
This means that his knowledge is an eigenpicture of R 2 , he has a determinate understanding of the administration in that representation. Now the website guides him further with information "non a 3 ". The picture of the citizen evolves from

|b 1 = 3 i=1 λ i |a i → |ψ = λ 1 λ 2 1 + λ 2 2 |a 1 + λ 2 λ 2 1 + λ 2 2 |a 2 = |b 1
So the citizen is less indeterminate with respect to R 1 but he lost the determination he had in R 2 . With |a i = 3 j=1 γ ij |a j we can now write the citizen's state of information in R 2 :

|ψ = λ 1 λ 2 1 + λ 2 2 3 j=1 γ 1j |b j + λ 2 λ 2 1 + λ 2 2 3 j=1 γ 2j |b j
After redistribution in terms of the b j :

|ψ = λ 1 λ 2 1 + λ 2 2 γ 11 + λ 2 λ 2 1 + λ 2 2 γ 21 |b 1 + λ 1 λ 2 1 + λ 2 2 γ 12 + λ 2 λ 2 1 + λ 2 2 γ 22 |b 2 + λ 1 λ 2 1 + λ 2 2 γ 13 + λ 2 λ 2 1 + λ 2 2 γ 23 |b 3 .
So we see that in R 2 the citizen is represented by a relatively complex superposition of all 3 possible eigenpictures of R 2 . If he walks out from the website now, he is definitely more confused than when he started: he has no clear picture of anything. Adding yet another information belonging to a third representation will make his updating toward R 2 even more difficult.

Any learning process about a sufficiently complex system proceeds by step which can be identified as the sequential acquisition of coarse information. For quantum cognitively constrained citizens this corresponds to a sequence of preparation followed by possibly incompatible measurements. The more complex the system the more likely the cognitive constraints are binding i.e., the agent is not capable of synthesizing all information in one picture. Instead information is organized in a number of alternative perspectives of the system corresponding to alternative (incompatible) representations. We have the following claim Claim i. Sequential acquisition of information can be particularly confusing if it mixes inputs from different representations. ii. Full access to information about a complex system is generally not beneficial to cognitively constrained agents.

The first claim is illustrated in the example above. The second claim follows from recognizing that the more complex a system, the more likely information about it involves a number of incompatible representations. The claim demonstrates the distinction between access to information and transparency. One implication is that an ill-intentioned webarchitect while providing full access to information can manipulate citizens so they give up their ambition to file a complaint whatever the initial state of mind. In other words transparency can be defeated precisely by providing full access to information.

Concluding remarks

This paper is a first exploration of learning by cognitively limited agents where the limitations are modeled appealing to quantum like characteristics of the mind. A main motivation is that the quantum approach has shown successful in explaining behavioral anomalies in decision-making while it also seems able to capture concerns expressed by practitioners dealing with information transmission and communication. In particular, the fact that i. people reason about reality within the frame of some a representation ("mental script") or as we call it, a mental picture, ii, the multiplicity of potential representations of reality generates specific problems for information transmission and learning. We model cognitive limitations in terms of the multiplicity of Bohr complementary mental representations of one and the same reality. We find that under intrinsic uncertainty, additional information may contribute to increasing the confusion of people. The analysis reveals a new significance of informational congruence which allows shedding some light on the issue of transparency in public life. In particular, we find that indeed access to information is not equivalent to transparency and that even truthful and full access to information can be exploited to manipulate cognitively constrained people. Future research will aim at extending the argument to a setting with uncertainty due to both incomplete information and intrinsic uncertainty. It will also establish the asymptotic properties of learning by quantum minded agents and perform a systematic comparison with non-Bayesian learning models.

Figure 1 .

 1 Figure 1. What do you see ?

Figure 2 .

 2 Figure 2. Detrimental information

  Life -A Quantum Cognition Perspective the recruitment/promotion system. Therefore we define three non-commuting operators which for simplicity are two-valued: R 1 {rule-bounded (|R ), discretionary(|D )}; R 2 {High ethical standards(|E ), No ethical standards(|U )}; R 3 {Competent (|C ), Incompetent(|I )}. We assume one representation R 2 is fully congruent with D the decision problem i.e., whether he should file a complaint of not. 11 The initial state can be expressed in any of the representation: |ϕ = λ 11 |R + λ 12 |D = λ 21 |E + λ 22 |U = λ 31 |C + λ 32 |I .

Figure 3 .

 3 Figure 3. Transparency in public life; incompatible mental frames of an administration.

Contribution presented at Quantum Interaction -2014, Lihn in Filzbach, Switzerland, June 30th to July 4th,

To be published in Springer Lectures Notes in Computer Science.

If a state is dispersion-free, i.e., the outcome of every possible measurement is uniquely determined, there is

After the introspective process, he will end up believing r * 2 with some probability less than 1.

We next consider a classical situation where all representations are compatible in the citizen's mind. He can synthesize all information without constraint. Formally, this is expressed as follows. For simplicity let both P and R * be two dimensional as in the illustrative example of figure 2. When P and R * are compatible, a picture (a state) can have values in both representations simultaneously. This means that a state or picture can be represented as a vector in the four dimensional tensor product space P × R * spanned by the eigenvectors

Generally the picture (state of mind) ψ of the citizen is as before expressed as a superposition of the basis vectors:

Since we are dealing with a classical agent this can be interpreted as a belief state b (a random variable) in boolean space

with α i = c 2 i , i = 1, ..., 4 and reads as follows: the agent believes that with probability α 1 the true state is ω 1 . Now in order to compare with the quantum case above assume that the agent initially has an information that is completely correlated with r * 2 so prob {r

The agent now receives information in a way similar to the subsection above. So he receives information along P, he learns p 2 implying prob {p = p 1 } = 0 implying prob {ω = ω 2 } = 0 . the agent processes that information i.e., updates his priors into posteriors

The agent is now fully informed of the state of the world. So compared with the priors (2) there is no loss of information as in the quantum updating case.

Proposition 2. In the classical counter-part of the quantum model, additional information never increases the agent's uncertainty.

Proposition 2 underlines the implications of quantum cognitive limitations. In the absence of such limitations, i.e., when all representations are compatible in the mind of the agent, information is always beneficial and -in the classical counter part model -it reduces entropy. While if the citizen is cognitively limited, information can turn confusing.

Remark 2. It must be emphasized that the reasoning above relies on our assumption that we are dealing with a classical counter part where the agent learns that r * = r * 2 with probability 1 (corresponding to the pure state in the quantum model). If we relax slightly this assumption (i.e., allowing for incomplete information), the result in proposition 1 could be approached with a classical model of a different flavor. Assume the agent has priors that puts nearly all the weight (but not all) on r * 2 so α 1 = 0 and α 3 = 0 as in b in 1. Next, he receives information p 2 . If according to the agent's structural model, that information is highly correlated with r * 1 (which is not the case in the original model) he updates his beliefs and puts more weight on ω 1 and ω 3 than he initially had. He is now less certain about what to do than he was before he got the information. His new beliefs exhibit a distribution with higher entropy. However, he has not lost


M Larrañaga

U Ayesta

I M Verloop
email: verloop@irit.fr

Dynamic fluid-based scheduling in a multi-class abandonment queue

We investigate how to share a common resource among multiple classes of customers in the presence of abandonments. We consider two different models: (1) customers can abandon both while waiting in the queue and while being served, (2) only customers that are in the queue can abandon. Given the complexity of the stochastic optimization problem we propose a fluid model as a deterministic approximation. For the overload case we directly obtain that the cµ/θ rule is optimal. For the underload case we use Pontryagin's Maximum Principle to obtain the optimal solution for two classes of customers; there exists a switching curve that splits the two-dimensional state-space into two regions such that when the number of customers in both classes is sufficiently small the optimal policy follows the cµ-rule and when the number of customers is sufficiently large the optimal policy follows the cµ/θ-rule. The same structure is observed in the optimal policy of the stochastic model for an arbitrary number of classes. Based on this we develop a heuristic and by numerical experiments we evaluate its performance and compare it to several index policies. We observe that the suboptimality gap of our solution is small.

Introduction

Abandonment or reneging takes place when customers, unsatisfied of their long waiting time, decide to voluntarily leave the system. It has a huge impact in various real life applications such as the Internet or call centers, where customers may abandon while waiting in the queue, or even while being served. Abandonment is a very undesirable phenomena, both from the customers' and system's point of view, and it can have a big economical impact. It is thus not surprising that it has attracted considerable interest from the research community, with a surge in recent years.

An important line of research aims at characterizing the performance and impact of abandonments in systems, we refer to [START_REF] Brill | Level crossings in point processes applied to queues: single-server case[END_REF][START_REF] Baccelli | Single-server queues with impatient customers[END_REF][START_REF] Brandt | On the two-class M/M/1 system under preemptive resume and impatience of the prioritized customers[END_REF][START_REF] Gromoll | Fluid limits for processor sharing queues with impatience[END_REF][START_REF] Iravani | On priority queues with impatient customers[END_REF][START_REF] Ata | On scheduling a multiclass queue with abandonments under general delay costs[END_REF] for single-server models and [START_REF] Boxma | Multiserver queues with impatient customers[END_REF][START_REF] Boots | A multiserver queueing systems with impatient customers[END_REF][START_REF] Whitt | Efficiency-driven heavy-traffic approximations for many-server queues with abandonments[END_REF] for papers dealing with the multi-class case. We also refer to [START_REF] Dai | Many-server queues with customer abandonment: a survey of diffusion and fluid approximations[END_REF] for a recent survey on abandonments in a many-server system. More related to our present work are the papers that deal with optimal scheduling or control aspects of multi-class queueing systems in the presence of abandonments, see for instance [START_REF] Glazebrook | On the optimal allocation of service to impatient tasks[END_REF][START_REF] Atar | Scheduling a multi-class queue with many exponential servers: asymptotic optimality in heavy-traffic[END_REF][START_REF] Harrison | Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime[END_REF][START_REF] Argon | Scheduling impatient jobs in a clearing system with insights on patient triage in mass-casualty incidents[END_REF][START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Down | Dynamic control of a single server system with abandonments[END_REF][START_REF] Atar | On the asymptotic optimality of the cµ/θ rule under ergodic cost[END_REF][START_REF] Ayesta | A nearly-optimal index rule for scheduling of users with abandonment[END_REF].

As the performance criteria the most common objectives are maximizing the service completion reward or minimizing a combination of the waiting time and abandonment penalty. In the case of two classes of customers and one server, the authors of [START_REF] Down | Dynamic control of a single server system with abandonments[END_REF] assume exponential distributed service requirements and impatience times and show that, under an additional condition on the ordering of the abandonment rates, an index policy is optimal. Since the abandonment rate is not bounded, it is not possible to uniformize the system. In order to prove the result, the authors use a continuous-time formulation of a Markov decision process (instead of the discrete-time equivalent) in addition to a truncation argument. In the case of no arrivals and non-preemptive service, the authors of [START_REF] Argon | Scheduling impatient jobs in a clearing system with insights on patient triage in mass-casualty incidents[END_REF] provide partial characterizations of the optimal policy and show that an optimal policy is typically state dependent. It is worthwhile to mention that [START_REF] Argon | Scheduling impatient jobs in a clearing system with insights on patient triage in mass-casualty incidents[END_REF] is inspired by a patient triage problem which illustrates that abandonments are as well an important issue in other areas than information technology. As far as the authors are aware, the above two settings are the only ones for which structural optimality results have been obtained. State-dependent heuristics for the multi-class queue are proposed in [START_REF] Argon | Scheduling impatient jobs in a clearing system with insights on patient triage in mass-casualty incidents[END_REF] for two classes and no arrivals and in [START_REF] Glazebrook | On the optimal allocation of service to impatient tasks[END_REF] for an arbitrary number of classes including new arrivals.

In general, determining the exact optimal policy has so far proved analytically infeasible. Hence, researchers have focused on obtaining approximations of the optimal control. For example, in [START_REF] Ayesta | A nearly-optimal index rule for scheduling of users with abandonment[END_REF] the authors study a multi-class abandonment queue without arrivals and use the Lagrangian relaxation method [START_REF] Whittle | Restless bandits: activity allocation in a changing world[END_REF] to construct an index policy, which is optimal for a relaxed optimization problem. Another approach is to study the system in the Halfin-Whitt heavy-traffic regime. That is, the total arrival rate and the number of servers both become large in such a way that the traffic intensity approaches one. For the abandonment queue this was first studied in [START_REF] Garnett | Designing a call center with impatient customers[END_REF]. This scaling gives rise to a diffusion control problem, for which the optimal controls are investigated in [START_REF] Atar | Scheduling a multi-class queue with many exponential servers: asymptotic optimality in heavy-traffic[END_REF][START_REF] Harrison | Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime[END_REF] and shown to be state dependent. In an overload setting the abandonment queue has been studied under a fluid scaling in [START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Atar | On the asymptotic optimality of the cµ/θ rule under ergodic cost[END_REF], where the authors scale the number of servers and the arrival rate and show that the cµ/θ rule (i.e., the policy where strict priority is given according to the indices cµ/θ ) is asymptotically fluid optimal (here c is the holding plus abandonment cost, θ is the abandonment rate and µ the service rate). The overload assumption is crucial in their analysis, since under this assumption the trajectories of the fluid model converge to a strictly positive state which completely characterizes the performance under the average performance criteria. The cµ/θ -rule emerges naturally as the policy that optimizes the performance associated to this absorbing state. Without abandonments, the cµ-rule, i.e., strict priority is given according to the indices cµ, is optimal in a multi-class single server queue for average reward and discounted cost criteria, in the preemptive and non-preemptive cases, see for example [START_REF] Buyukkoc | The cµ rule revisited[END_REF]. The cµ/θ and the cµ index rules will play an important role throughout this paper.

In this paper, we investigate the fundamental question of how to share one common resource among multiple classes of customers in the presence of abandonments. We consider two different stochastic models: (1) customers can abandon when they are waiting in the queue and also while they are being served, (2) customers that are in the queue can abandon but customers in service cannot. Given the complexity of the problem it is not possible to solve the stochastic optimization problem. We thus propose a fluid model with non-linear dynamics, which can be interpreted as a deterministic approximation of the stochastic problem. We consider both the underload and the overload case, the former being considerably more difficult to solve. In an overload setting, we determine the optimal equilibrium point and show that under the cµ/θ rule the dynamics converge to this point, which in fact is non-zero. In the underload case the fluid model will empty in finite time, hence we will seek for the optimal trajectory that minimizes the cost of draining the fluid. The latter makes the analysis considerably harder than in the overload case. Using Pontryagin's Maximum Principle [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF] we solve completely the case with two classes of customers. The optimal solution has a remarkable structure, there exists a switching curve that splits the two-dimensional state-space into two regions such that: when the number of customers is sufficiently small the optimal policy follows the cµ-rule and when the number of customers is sufficiently large the optimal policy follows the cµ/θ -rule. Solving the optimal stochastic control problem numerically we observe this same behavior where the shape of the switching curve is very well approximated by the one found in the fluid model. In fact, the combination of the cµ rule and the cµ/θ rule is also observed numerically in the optimal stochastic control for more than two classes. We use this insight to propose a heuristic for the stochastic model (for an arbitrary number of classes). At last, by numerical experiments we evaluate the performance of the fluid-based heuristic and several index policies and observe that the suboptimality gap of our solution is small. We emphasize here that our heuristic works well across all loads, while the index policies cµ and cµ/θ , although being rather easy to implement, achieve only good performance in either the underload or the overload setting.

The approach of using the fluid model to find an approximation for the stochastic model finds its roots in the pioneering works by Avram et al. [START_REF] Avram | Stochastic networks[END_REF] and Weiss [START_REF] Weiss | On optimal draining of reentrant fluid lines[END_REF]. It is remarkable that in some cases the optimal control for the fluid model coincides with the optimal solution for the stochastic problem. See for example [START_REF] Avram | Stochastic networks[END_REF] where this is shown for the cµ-rule in a multi-class single-server queue and [START_REF] Bäuerle | Optimal control of single-server fluid networks[END_REF] where this is shown for Klimov's rule in a multi-class queue with feedback. For other cases, researchers have aimed at establishing that the fluid control is asymptotically optimal, that is, the fluid-based control is optimal for the stochastic optimization problem after a suitable scaling, see for example [START_REF] Meyn | Stability and optimization of queueing networks and their fluid models[END_REF][START_REF] Bäuerle | Asymptotic optimality of tracking policies in stochastic networks[END_REF][START_REF] Gajrat | Fluid approximation of a controlled multiclass tandem network[END_REF][START_REF] Maglaras | Discrete-review policies for scheduling stochastic networks: trajectory tracking and fluid-scale asymptotic optimality[END_REF][START_REF] Verloop | Asymptotically optimal parallel resource assignment with interference[END_REF]. We conclude by mentioning that the fluid approach owes its popularity to the groundbreaking result stating that if the fluid model drains in finite time, the stochastic process is stable, see [START_REF] Dai | On positive harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF][START_REF] Robert | Stochastic Networks and Queues[END_REF].

The remainder of the paper is organized as follows. In Section 2 we present the stochastic model with abandonments and the optimization problem. In Section 3 we introduce the related fluid model and solve its fluid control problem for the underload case (for two classes of customers) and for the overload case. In Section 4 we develop a heuristic for the stochastic model for an arbitrary number of classes and in Section 5 we numerically compare the performance of the fluidbased heuristic with that of the optimal policy and several index policies proposed in the literature.

Model description

We consider a multi-class single-server queue with K classes of customers. Class-k customers arrive according to a Poisson process with rate λ k and have an exponentially distributed service requirement with mean 1/µ k . A class-k customer can abandon the system after an exponentially distributed amount of time with mean 1/θ k . We define ρ k = λ k /µ k as the traffic load of class k and ρ = k ρ k as the total load. We assume that the server has capacity 1 and can serve at most one customer at a time, where the service can be preemptive. At each moment in time, a policy π decides which class is served.

Because of the Markov property we can focus on policies that base decisions on the current number of customers present in the various classes. For a given policy π , the control variable (S π

K k=1 S π k (t) ≤ 1.
We are interested in two different models, depending on whether or not a customer in service becomes impatient and hence can abandon:

• Stochastic Model 1 (SM1): customers can abandon both while waiting in the queue and while being served, see Fig. 1(a).

• Stochastic Model 2 (SM2): customers can abandon only while waiting in the queue, see Fig. 1(b).

Both models have been studied in the literature, e.g., in [START_REF] Down | Dynamic control of a single server system with abandonments[END_REF] the model SM1 is studied, while the authors of [START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Atar | On the asymptotic optimality of the cµ/θ rule under ergodic cost[END_REF][START_REF] Ayesta | A nearly-optimal index rule for scheduling of users with abandonment[END_REF] consider SM2.

For a given policy π , let N π k (t) denote either the number of class-k customers in the system (SM1) or the number of class-k customers in the queue (SM2). Let c k denote the holding cost per unit time for class-k customers. Let d k denote the cost for each class-k customer that abandons. Our objective is to minimize the average cost, that is,

min π lim sup T →∞ K k=1 1 T E T 0 c k N π k (t)dt + d k R π k (T ) = min π lim sup T →∞ 1 T E T 0 K k=1 ck N π k (t)dt ,
where R π k (T ) denotes the number of class-k customers that abandoned in the interval [0, T ], ck :

= c k + d k θ k , k = 1, . . . , K ,
and we used that

E(R π k (T )) = θ k E( T 0 N π k (t)dt).
We note that for model SM2 only waiting customers can abandon and can hence contribute to the abandonment cost. In addition, implicitly we assumed that for SM2 only waiting customers contribute to the holding cost. 1 For model SM1, all customers will have a contribution to the abandonment cost (a customer in service can abandon) and we have assumed that all customers contribute to the holding cost.

The above described stochastic control problems have proved to be very difficult to solve. In [START_REF] Down | Dynamic control of a single server system with abandonments[END_REF] optimal dynamic scheduling is studied for the model SM1 for two classes of customers (K = 2) with µ 1 = µ 2 = 1. In case c1 ≥ c2 and θ 1 ≤ θ 2 , the authors show that it is optimal to give strict priority to class 1, see [START_REF] Down | Dynamic control of a single server system with abandonments[END_REF]Theorem 3.5]. It is intuitively clear that giving priority to class 1 is the optimal thing to do, since serving class 1 myopically minimizes the (holding and abandonment) cost and in addition it is advantageous to keep the maximum number of class-2 customers in the system (without idling), since they have the highest abandonment rate. Outside this parameter setting, an optimal policy is expected to be state dependent, and as far as the authors are aware, no (structural) results exist for this stochastic optimal control problem. Therefore, in Section 3, in order to obtain further insight, we propose to solve a related fluid control model.

Fluid control model

In this section the stochastic models (SM1, SM2) presented in Section 2 are approximated by the deterministic fluid model, where only the mean dynamics are taken into account. That is, let n k (t) be the amount of class-k fluid and s k (t) the control parameter. Then the fluid dynamics is described by the following set of differential equations:

dn k (t) dt = λ k -µ k s k (t) -θ k n k (t), ∀k ∈ {1, . . . , K }, s k (t) ∈ S, n k (t) ≥ 0, ∀k ∈ {1, . . . , K }, ∀t, with S := s = (s 1 , . . . , s K ) s.t. K k=1 s k ≤ 1, s k ≥ 0 ∀k ∈ {1, . . . , K } .
For the fluid analysis we will make a distinction between two different scenarios: (1) ρ < 1, which we refer to as the underload and (2) ρ > 1, which we refer to as the overload setting. Note that in the case ρ < 1, any non-idling control (i.e.,

K k=1 s k (t) = 1 if K k=1 n k (t) > 0)
converges to the equilibrium point (0, . . . , 0). 2 Hence, when ρ < 1 we aim at minimizing the total cost until reaching the equilibrium point (0, . . . , 0). This can be written as min

s(t)∈S ∞ 0 K k=1 ck n k (t)dt.
1 For the model SM2, the latter was also assumed in [START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Atar | On the asymptotic optimality of the cµ/θ rule under ergodic cost[END_REF], while [START_REF] Ayesta | A nearly-optimal index rule for scheduling of users with abandonment[END_REF] assumed customers in service contribute to the holding cost as well. 2 Consider w(t When ρ > 1, an equilibrium point will necessarily be different than (0, . . . , 0). Hence, for ρ > 1 our objective is to minimize the average cost, i.e., min

) := K k=1 n k (t)/µ k . Then dw(t) dt = ρ -K k=1 s k (t) -K k=1 θ k µ k n k (t) < ρ -1 < 0, hence w(t) converges to zero.
s(t)∈S lim T →∞ 1 T T 0 K k=1 ck n k (t)dt.
Throughout the study we refer to this optimal fluid control problem as Problem P.

Optimal policy in underload for two classes of customers

In this section we assume ρ < 1 and solve the fluid control model. We focus on the case of two classes of customers, whose solution is already rather involved. However, it gives us intuition on the structure of the optimal policy for an arbitrary number of classes.

We will see that an optimal policy can be of two possible shapes: either a switching curve emerges, i.e., we prioritize one class above the switching curve and the other class below the switching curve, or one of the two classes is prioritized. This gives us four different type of strategies. As we show in the following proposition, the optimal strategy is fully characterized by the ordering of c1 µ 1 and c2 µ 2 and of c1 µ 1 /θ 1 and c2 µ 2 /θ 2 .

Proposition 1. Assume K = 2 and let λ k , µ k , θ k , c k and d k be given for k ∈ {1, 2}. Assume c2 µ 2 /θ 2 ≥ c1 µ 1 /θ 1 . If ρ < 1, then, an optimal solution s * (•) for Problem P under the total cost criteria is:

• if c2 µ 2 ≤ c1 µ 1 , then -s * = (0, 1) when n 2 > h(n 1 ), -s * = (1, 0) when n 2 ≤ h(n 1 ) and n 1 > 0, -s * = (ρ 1 , 1 -ρ 1 ) when n 2 ≤ h(0) and n 1 = 0,
where the switching curve h(•) is given by h(n 1 ) :=

a 1 n 1 + a 2 + (a 3 n 1 -a 2 ) θ 1 n 1 +µ 1 -λ 1 µ 1 -λ 1 θ 2 θ 1 a 4 n 1 + λ 2 θ 2 , (3.1)
with

a 1 = c2 µ 2 θ 2 (1 -ρ) ; a 2 = a 1 µ 1 θ 1 (1 -ρ 1 )
;

a 3 = -c2 µ 2 θ 2 -c1 µ 1 θ 1 (1 -ρ 1 ), and a 4 = c2 µ 2 θ 2 -c1 µ 1 θ 1 θ 2 µ 2 .
That is, serve class 2 until the switching curve h(•) is reached, then serve class 1 until n 1 = 0. From that moment on, keep n 1 = 0 and give the rest of the service to class 2, see Fig. 2(a).

• If c2 µ 2 ≥ c1 µ 1 , then -s * = (0, 1) when n 2 > 0, -s * = (1 -ρ 2 , ρ 2 ) when n 2 = 0.
That is, serve class 2 until n 2 = 0. From that moment on, keep n 2 = 0 and give the rest of the service to class 1, see Fig. 2(b).

The solution in the case where c2 µ 2 /θ 2 ≤ c1 µ 1 /θ 1 is equivalent with the indices swapped.

Remark 1 (Arbitrary Number of Classes).

Given the complexity to find an optimal solution for the fluid control model in underload when K = 2, we did not aim at obtaining an analytical solution for an arbitrary number of classes K . Instead, in Section 4 we develop a heuristic using the insights obtained for the case K = 2.

(a) Optimal path when c2 µ 2 ≤ c1 µ 1 .

(b) Optimal path when c2 µ 2 ≥ c1 µ 1 .

Fig. 2. Optimal strategy assuming

c2 µ 2 θ 2 ≥ c1 µ 1 θ 1
, and the optimal path.

Remark 2. Observe that the switching curve h(•) defined in Proposition 1 is decreasing in n 1 and hence it will emerge in the first quadrant if and only if

h(0) = (1 -ρ) µ 2 θ 1 θ 2 c1 µ 1 -c2 µ 2 c2 µ 2 θ 2 -c1 µ 1 θ 1 ≥ 0.
Since we are in the underload case this is equivalent to the condition

c1 µ 1 -c2 µ 2 / c2 µ 2 θ 2 - c1 µ 1 θ 1 ≥ 0.
Before proving the above proposition we first provide intuition for the structure of the optimal policy, which is characterized by a very simple rule based on the comparison of the indices cµ and cµ/θ . When the amount of fluid is small enough, the cµ rule is optimal. This can be explained as follows. Note that the derivative of the cost is given by

K k=1 ck dn k (t) dt = K k=1 ck (λ k -µ k s k (t) -θ k n k (t)
). The cµ-rule myopically minimizes the derivative and is hence optimal in the short run. Close to the origin this is exactly what the optimal control prescribes. However, in the long term, one cannot neglect the effect of abandonments. For example, if c1 µ 1 > c2 µ 2 , but θ 1 ≫ θ 2 , then the myopic rule would prioritize class 1.

However, this minimizes n 1 (t), which has a negative impact on the derivative of the cost (cf. the term θ 1 n 1 (t)). Hence, in the long run it might be good to keep the amount of class-1 fluid high, since class 1 has a high abandonment rate. In Proposition 1

we showed that in a state far from the origin, the index that appropriately combines the above described effects is the cµ/θ index. We will show in Proposition 2 that the cµ/θ rule is in fact optimal when ρ > 1, i.e., in the overload setting. The switching curve h(•), as defined in Proposition 1, describes the states in which it is optimal to switch from the ck µ k /θ k rule to the ck µ rule. We can learn the following from the formula for h(•):

• as we can see from Remark 2, the ratio between c1 µ 1 -c2 µ 2 and c2 µ 2 θ 2 -c1 µ 1 θ 1 determines h(0), and hence the height of the switching curve. From this we observe that as the difference in the values for the cµ index grows large (small) relative to that of the cµ/θ index, the height of the switching curve grows (goes to zero) and hence the optimal fluid control gets closer to the cµ rule (cµ/θ rule). • as the traffic load approaches one, i.e., ρ ↑ 1, the switching curve h(•) converges to h(•) with h(0) = 0 and h(n 1 ) < 0 for n 1 > 0. Hence, the cµ/θ rule is optimal for the fluid model as ρ ↑ 1. As we will see in Section 3.2, the cµ/θ rule is optimal in the overload setting (ρ > 1) as well, showing continuity in the optimal solution.

Remark 3 (Multi-Class Queue with Deadlines). In the case c k = 0, k = 1, . . . , K , the model becomes a multi-class queue with deadlines: customers need to be served before a deadline that is exponentially distributed with parameter θ k and in the case they do not receive service before their deadline they abandon the queue giving a cost d k . In this particular case the cµ rule reduces to dµθ rule and the cµ/θ rule reduces to the dµ rule.

We now proceed to the proof of Proposition 1. The following two lemmas are necessary in order to prove Proposition 1.

Their proofs are presented in the Appendix. The first lemma states that the index ck µ k determines the optimal action when the amount of fluid in both class 1 and class 2 is small.

Lemma 1. Let K = 2 and let n(0) = (ε, ε) with ε > 0 small enough. If ρ < 1 and c1 µ 1 ≥ c2 µ 2 (resp. c1 µ 1 ≤ c2 µ 2 ),
then it is optimal to give priority to class 1 (resp. class 2) until the origin is reached.

Assuming that it is optimal to serve class 2 in the initial point, the next lemma describes the two possible strategies.

Lemma 2. Let K = 2 and the initial conditions n(0) be given. Assume that it is optimal to prioritize class 2 at time 0. Then the optimal solution of Problem P will be one out of the following two strategies:

• if c1 µ 1 -c2 µ 2 / c2 µ 2 θ 2 -c1 µ 1 θ 1 ≥ 0, then the following control is optimal: -s * = (0, 1) if n 2 > h(n 1 ), -s * = (1, 0) if n 2 ≤ h(n 1 ) and n 1 > 0, -s * = (ρ 1 , 1 -ρ 1 ) if n 2 ≤ h(0) and n 1 = 0,
with h(•) the switching curve as defined in Proposition 1.

• if c1 µ 1 -c2 µ 2 / c2 µ 2 θ 2 -c1 µ 1 θ 1 ≤ 0, then the following control is optimal: -s * = (0, 1) if n 2 > 0, -s * = (1 -ρ 2 , ρ 2 ) if n 2 = 0.
The proof of Proposition 1 now follows easily.

Proof of Proposition 1. We first assume that c2 µ 2 /θ 2 ≥ c1 µ 1 /θ 1 and c2 µ 2 ≥ c1 µ 1 . Now assume that there is a state n such that it is optimal to serve class 1. Since the values for the indices cµ/θ and cµ are higher for class 2, Lemma 2 implies that class 1 should be given priority until it reaches 0. However, this is in contradiction with Lemma 1, which states that it is optimal to give priority to class 2 close to the origin. Hence, we have proved that it is optimal to give full priority to class 2. Now assume that c2 µ 2 /θ 2 ≥ c1 µ 1 /θ 1 and c2 µ 2 ≤ c1 µ 1 . Assume there exists a state such that n 1 > h 2 (n 2 ) where priority is given to class 1 (here h 2 denotes the switching curve of Lemma 2 if we had assumed class 1 was prioritized). Then Lemma 2 tells us that whenever the process reaches a point where n 1 ≤ h 2 (n 2 ) the priority will be switched to class 2 until the equilibrium is reached. This, however, is in contradiction with Lemma 1, since it tells us that class 1 should be prioritized close to the origin. Hence, by contradiction we obtain that for states far enough from the origin, priority should be given to class 2. By Lemma 2, first item, we then obtain the result.

Optimal policy in overload for an arbitrary number of classes

In this section we assume again an arbitrary number of classes, i.e., K ≥ 2. To complete the analysis of Problem P we are left with the setting ρ > 1, in which case the objective is to minimize the average cost (the latter being strictly positive).

The following proposition states an optimal control for the fluid model. Proposition 2. Let λ k , µ k , θ k , c k and d k be given for k ∈ {1, . . . , K }, and assume the classes are ordered such that c1 µ 1

θ 1 ≥ c2 µ 2 θ 2 ≥ • • • ≥ cK µ K θ K . If ρ > 1,
then an optimal solution s * (•) for Problem P under the average cost criteria is:

s * (t) = ρ 1 , . . . , ρ l , 1 - l(t) i=1
ρ i , 0, . . . , 0 , with l(t) := min{k : n k+1 (t) > 0}. That is, priority is given according to the index cµ/θ . Proof. We first determine the optimal equilibrium point. An equilibrium point satisfies 0

= λ k -µ k s k -θ k n k , for all k.
Hence, the optimal control (in equilibrium) that minimizes the equilibrium point is given by arg min

s∈S K k=1 ck n k = arg min s∈S K k=1 ck λ k -µ k s k θ k = arg min s∈S K k=1 - ck µ k θ k s k .
This is minimized by giving the highest priority according to the cµ/θ rule, that is the optimal equilibrium point is given by n * = (0, . . . , 0,

λ j+1 -µ j+1 (1- j i=1 ρ i ) θ j+1 , λ j+2 θ j+2 , . . . , λ K
θ K ) and s * = (ρ 1 , . . . , ρ j , 1-j i=1 ρ i , 0, . . . , 0), with j such that j i=1 ρ i < 1 and j+1 i=1 ρ i ≥ 1. It remains to be checked that under the control s * (•) as stated in the proposition, the fluid dynamics converge to the optimal equilibrium point. This can be seen as follows. Let n * (•) denote the trajectory corresponding to the control s * (•).

Consider w * j (t) := j k=1 n * k (t)/µ k . By definition of s * (t) we have dw * j (t)/dt = j k=1 ρ k -1 -j k=1 θ k n * k (t)/µ k < -(1 -j k=1 ρ k ) when w * j (t) > 0.
Hence, in a finite time T the process hits zero, w * j (T ) = 0, and stays there. From that moment on, class j + 1 is given capacity 1 -j k=1 ρ k if present. Hence, it follows directly that this converges to the point n * j+1 , which solves 0 = λ j+1µ j+1 (1 -j k=1 ρ k )θ j+1 n j+1 . Since for t > T we have n * j+1 (t) > 0, classes j + 2, . . . , K do not receive any service. Hence, their dynamics is described by dn * i (t)/dt = λ iθ i n * i (t), and n * i (t) converges to λ i /θ i , i ∈ {j + 2, . . . , K }.

We note that the cµ/θ rule has previously been proposed by Atar et al. in [START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Atar | On the asymptotic optimality of the cµ/θ rule under ergodic cost[END_REF], where optimal scheduling in the presence of abandonments was studied for the many-server setting. The rule was obtained by solving a fluid control model.

The fluid model is similar to the one of Proposition 2, but has the additional condition s k ≤ n k , which is due to the multiserver setting.

Optimal control comparison of stochastic model with fluid model

In this section, we compare the switching curve that we obtained for the fluid model with the optimal solution for the stochastic models SM1 and SM2 obtained numerically by value iteration. In Fig. 3 we make this comparison for different sets of parameters. Note that the optimal stochastic switching curve of SM1 is always below the switching curve of SM2. This is due to the fact that allowing customers to abandon while being served, as in SM1, makes the effect of abandonments more significant.

We consider the underload case ρ < 1 in Fig. 3(a) and (b), the critical regime ρ = 1 in Fig. 3(c) and the overload setting ρ > 1 in Fig. 3(d). Moreover, we note that Fig. 3(b)-(d) correspond to the parameters of Example 1 in Section 5.

In Fig. 3(a)-(b) the parameters are such that c1 µ 1 ≥ c2 µ 2 and c1 µ 1 /θ 1 ≤ c2 µ 2 /θ 2 , hence the optimal fluid solution is characterized by a switching curve and priority is given to class 2 above the curve and to class 1 below the curve. We observe that the fluid optimal switching curve approximates the stochastic optimal switching curve very well, except for a constant that apparently disappears after the fluid scaling. In Fig. 3(c)-(d) the optimal stochastic policy is characterized by a switching curve where class 2 is served in states above the curve and class 1 in states below the curve. The optimal control in the fluid model is however to give strict priority to class 2 (in the case ρ > 1), since c1 µ 1 /θ 1 ≤ c2 µ 2 /θ 2 . For Fig. 3(c) the average number of customers in the system SM1 under the optimal policy is (N 1 , N 2 ) = (0.7796, 4.1194) which lies below the switching curve. Hence, the stochastic optimal policy will give most of the time priority to class 1. The optimal fluid control does not capture this property since the fluid switching curve h(•) vanishes for ρ = 1. In Example 1 of Section 5 we will see that the suboptimality gap when applying the optimal fluid control to the stochastic model is around 30%. In the case ρ > 1 is large enough, our index policy turns out to work well, see the numerical Section 5. This is explained by the fact that the process is living above the Fig. 4. An example of the heuristics for the case K = 3 when c1 µ 1 ≥ c2 µ 2 ≥ c3 µ 3 and c3 µ 3 /θ 3 ≥ c1 µ 1 /θ 1 ≥ c2 µ 2 /θ 2 . switching curve. For example, for the parameters as chosen in Fig. 3(d), the average number of customers in the system SM1 is (N 1 , N 2 ) = (3.0088, 3.4849) which lies above the switching curve. Hence, the stochastic optimal policy will give most of the time priority to class 2, which coincides with the optimal fluid control. In Example 1 of Section 5 we will see that the suboptimality gap when applying the optimal fluid control to the stochastic model is small.

In Section 4 we discuss how to translate the fluid optimal solution to the stochastic setting. In Section 5 we will numerically evaluate the performance of the heuristic when applied to the stochastic model. In fact, we will observe good performance. However, we do not have any result on the suboptimality gap. In the literature, asymptotic fluid optimality results have been obtained for various dynamic scheduling problems in queueing models, see for example [START_REF] Meyn | Stability and optimization of queueing networks and their fluid models[END_REF][START_REF] Bäuerle | Asymptotic optimality of tracking policies in stochastic networks[END_REF][START_REF] Gajrat | Fluid approximation of a controlled multiclass tandem network[END_REF][START_REF] Maglaras | Discrete-review policies for scheduling stochastic networks: trajectory tracking and fluid-scale asymptotic optimality[END_REF][START_REF] Verloop | Asymptotically optimal parallel resource assignment with interference[END_REF]. More precisely, it is shown that when employing the optimal control resulting from the fluid model to the stochastic model, the fluid-scaled cost converges to the optimal cost of the fluid control model, the latter being in fact a provable lower bound on the stochastic cost. In this particular model the fluid model is presented as an approximation, there is no certainty that when applying the optimal fluid control in the stochastic model, this will be asymptotically optimal. We do believe though that when scaling λ k 's, µ k 's, the scaled queue length processes (when scaling space) behave according to the fluid dynamics. We note here that [START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Atar | On the asymptotic optimality of the cµ/θ rule under ergodic cost[END_REF] show in fact that the cµ/θ rule is asymptotically fluid optimal in a multi-server setting and assuming overload. Due to the multi-server setting, the authors of [START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Atar | On the asymptotic optimality of the cµ/θ rule under ergodic cost[END_REF] need a different limiting regime: the arrival rates and the number of servers are scaled, while the service rate of each server is kept fixed to µ. We do expect though, in the case of overload, that a similar proof technique can be applied to our model.

Heuristics for an arbitrary number of classes

In this section, we will propose a heuristic for the stochastic optimization model with abandonments. This heuristic is based on the insights we obtained from the fluid control model.

We first consider the overload setting. In that case, the optimal fluid policy is to give priority according to the cµ/θ-rule.

In Section 5 we will evaluate this policy when employed in the stochastic model (in overload).

We now consider the case of underload. Recall that in Proposition 1 we have seen that the optimal fluid control has a remarkable structure in the case of two classes: close to the origin the cµ-rule is optimal, and when one of the fluids is sufficiently large the cµ/θ -rule is optimal. We observe the same structural property in the optimal solution for the stochastic control problem obtained numerically, see Section 3.3 and Fig. 5 (left). Our approach is thus to develop a heuristic that follows this insight, that is, close to the origin it will behave according to the cµ-rule, and when the number of users in one of the classes is sufficiently large it will follow the cµ/θ -rule. It is not clear what should be the best choice for the threshold to decide whether the cµ rule or the cµ/θ rule should be applied.

We propose the following heuristic, which is based on the two-class fluid analysis: for a general K -class queue we compare all classes pairwise and calculate the switching curves of the paired systems, see for example Fig. 4 where

c1 µ 1 ≥ c2 µ 2 ≥ c3 µ 3 and c3 µ 3 /θ 3 ≥ c1 µ 1 /θ 1 ≥ c2 µ 2 /θ 2 .
Then, whenever the state (N 1 , N 2 , . . . , N k ) satisfies that all pairs (N i , N j ) lie under their corresponding switching curves, we give priority to the class with the highest value for cµ. However, if there is at least one state (N i , N j ) that lies above its corresponding switching curve, we will give priority to the class with the highest value for cµ/θ . For example, for the parameters of Fig. 4 we will give priority to class 1 when both states (N 2 , N 3 ) and (N 1 , N 3 ) lie below their corresponding switching curves and otherwise priority is given to class 3. When- ever the queue of one class is empty we analyze the system in the same way but only take into account the K -1 queues that are non-empty. For a better understanding we give a pseudo-code of the heuristic rule in Algorithm 1.

We propose an example with K = 3 to illustrate the heuristic we have just defined and to compare it to the optimal policy (obtained numerically by Value Iteration [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]). Let us consider the following set of parameters µ = [START_REF] Dai | Many-server queues with customer abandonment: a survey of diffusion and fluid approximations[END_REF][START_REF] Dai | Many-server queues with customer abandonment: a survey of diffusion and fluid approximations[END_REF][START_REF] Whitt | Efficiency-driven heavy-traffic approximations for many-server queues with abandonments[END_REF]

; θ = [1, 0.5, 0.25]; c = [1.7, 1.7, 1.7]; d = [2, 2, 4]; λ = [2, 2, 1]. Hence, c1 µ 1 ≥ c2 µ 2 ≥ c3 µ 3 and c1 µ 1 /θ 1 ≤ c2 µ 2 /θ 2 ≤ c3 µ 3 /θ 3 .
Under our heuristic, class 1 will be served when all three classes are close enough to the origin, according to the cµ rule, and class 3 will be served otherwise, according to the cµ/θ rule. Class 2 will be served in the following two cases: (i) when class 1 is empty and (N 2 , N 3 ) is sufficiently close to the origin (follows from the cµ rule) and (ii) when class 3 is empty and (N 1 , N 2 ) is sufficiently far from the origin (follows from the cµ/θ rule). In Fig. 5 we plot the actions under the optimal scheduling rule (calculated by Value Iteration) (left) and under our heuristic (right). We observe that the heuristic rule shows a qualitatively similar structure to the optimal solution. In Section 5.2 we will present a numerical comparison of its performance.

Algorithm 1 Algorithm to compute heuristic scheduling rule for an arbitrary K

Assume r queues are non empty.

Let N i be the state of class i ∈ {1, . . . , r}.

Compute the indices cµ and cµ/θ for i ∈ {1, . . . , r}. Given a pair of classes i and j, such that ci µ i /θ i ≥ cj µ j /θ j , compute the switching curve h ij as given by Equation (3.1). if for all i, j, N i ≤ h ij (N j ) then Give priority to the class with highest index cµ else Give priority to the class with highest index cµ/θ end if Fig. 5. Optimal policy and heuristic for a 3-class single server example for SM2. Circles indicate that class 1 is served, pluses that class 2 is served and absence of a sign corresponds to class 3 being served.

Numerical results

In this section we simulate the stochastic model and evaluate numerically the performance of the heuristic described in Algorithm 1. We compare the performance of our heuristic rule against the optimal policy. The latter is calculated using the Value Iteration algorithm [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]. We also simulate the following index policies available in the literature:

• the cµ/θ-rule. This rule was introduced in [START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Atar | On the asymptotic optimality of the cµ/θ rule under ergodic cost[END_REF] where it was proved to be asymptotically fluid optimal for a multiserver system in overload. As shown in Proposition 2 this rule is also optimal for our fluid model in overload.

• the cµ/θc-rule. This rule was derived in [START_REF] Ayesta | A nearly-optimal index rule for scheduling of users with abandonment[END_REF] for the system SM2 (without arrivals) with the modification that the user in service also contributes to the cost.

• the cµ-rule. This is the greedy or myopic rule that minimizes the instantaneous cost. This rule can be seen as a counterpart of the well-known cµ-rule [START_REF] Buyukkoc | The cµ rule revisited[END_REF] for the system with abandonments.

Before we start describing in detail the results, we provide below our main conclusions:

• the qualitative performance in the SM1 and SM2 systems are very similar.

• the cµ/θ and the cµ/θc-rules perform very well in overload.

• our heuristic (as proposed in Algorithm 1) performs very well across all loads.

For the sake of fairness we can mention that even though the index rules cµ/θ and cµ perform worse than the heuristic rule, they are simpler to implement since they are state independent.

We now present the scenarios we have simulated. In Section 5.1 we consider the case K = 2 and in Section 5.2 the case K = 3.

Performance analysis for K = 2

We consider the two models SM1 and SM2, and we calculate the relative suboptimality gap for the policies described above. In Example 1 and 2 we fix the parameters c, d, µ and θ and set ρ 1 = ρ 2 and vary the total workload ρ. In Example 3 we fix ρ and vary the value of θ 1 .

• Example 1: in this first example we set θ = [2, 0.05]; µ = [START_REF] Argon | Scheduling impatient jobs in a clearing system with insights on patient triage in mass-casualty incidents[END_REF][START_REF] Down | Dynamic control of a single server system with abandonments[END_REF]

; c = [1, 1]; d = [4, 0.3], such that c1 µ 1 ≥ c2 µ 2 and
c2 µ 2 /θ 2 ≥ c1 µ 1 /θ 1 . The results for this example are depicted in Fig. 6. In underload the heuristic and the cµ-rule behave optimally, while the cµ/θ and cµ/θc-rules behave very poorly. In Fig. 3(b) we plotted the switching curves corresponding to the load ρ = 0.73. In fact, the average number of users (in the SM1 system with ρ = 0.73) is given by (N 1 , N 2 ) = (0.4047, 1.5092) which is a state far below both the SM1 switching curve and the fluid switching curve. This shows why both our heuristic and the cµ-rule (this is the control below the switching curve) behave close to optimal.

In the overload case though, the cµ-rule incurs a high relative suboptimality gap while our heuristic and the cµ/θ and cµ/θc-rules are close to optimal. The latter conforms with what we expected as described in Section 3.3. We observe that when the load is close to the critical regime ρ = 1 the suboptimality gap is around 30%. Our heuristic will give priority to class 2 in the case ρ > 1 and has a switching curve very close to the origin in the case ρ = 1ǫ.

In Fig. 3(c), which corresponds to the current example, we see that the optimal policy for the stochastic optimization problem is described by a switching curve for ρ = 1. Hence, when we are in a state below the switching curve, class 1 will be given priority. The process when ρ = 1 lives on average close to the stochastic switching curve, therefore, our policy can be far from optimal, as discussed in Section 3.3.

• Example 2: in this second example we set θ = [1, 0.5]; µ = [START_REF] Atar | The cµ/θ rule for many-server queues with abandonment[END_REF][START_REF] Bäuerle | Optimal control of single-server fluid networks[END_REF]; c = [0, 0]; d = [5, 3.2], so that c1 µ 1 ≥ c2 µ 2 and c2 µ 2 /θ 2 ≥ c1 µ 1 /θ 1 . As explained in Remark 3, setting c 1 = c 2 = 0 gives a different interpretation of the model: customers will abandon the system when a certain deadline is met before they have attained full service. In this case the cµ/θ , cµ/θc and the cµ rules reduce to the dµ, dµ, and dθ µ rules, respectively. We observe that the index dµ does not perform well in underload but is close to optimal in overload. The opposite holds for the dθ µ rule. Our policy is optimal in underload and as good as the dµ index in overload, see Fig. 7.

In Fig. 8 we plotted the optimal switching curves for the stochastic models SM1 and SM2 (obtained by value iteration), as well as the optimal fluid switching curve h(•). Fig. 8(a) corresponds to load ρ = 0.8867. In that case, the average number of customers is given by (N 1 , N 2 ) = (0.6859, 2.6963), which is a state far below all switching curves. Hence, this shows why our heuristic and the cµ-rule perform close to optimal. On the other hand, when ρ = 1, Fig. 8(b), the optimal control in the fluid model is to serve class 2, so there is no switching curve. Under the optimal policy for the stochastic model, the average number of customers is given by (N 1 , N 2 ) = (0.763, 4.2703). This is a state far below the switching curves of the stochastic model. Hence, most of the time priority is given to class 1 under the optimal policy. This explains why our heuristic gives a positive optimality gap of 16%. However, as the load of the system increases (ρ > 1) the process will live more above the optimal switching curve for the stochastic model. See for example Fig. 8(c) for load ρ = 1.52 for which the average number of customers under the optimal policy is given by (N 1 , N 2 ) = (6.8054, 3.7244). This explains why our heuristic, which gives priority to class 2, has a suboptimality gap very close to 0%.

Remark 4 (Peak When Workload Close to 1). We observe in Examples 1 and 2 that when the workload is close to 1 a peak appears in the suboptimality gap for the heuristic rule. This can be explained by the following. In the proof of Lemma 2, see Appendix, we observe a switching curve whenever Therefore, as 1ρ 1ρ 2 → 0 the switching curve vanishes, that is, the heuristic becomes equivalent to the cµ/θ -rule. However, around ρ = 1 the optimal stochastic control still follows the cµ-rule in a non-negligible part of the state space, see for instance Fig. 8(b).

h(0) = (1 -ρ 1 -ρ 2 ) µ 2 θ 1 θ 2 c1 µ 1 -c2 µ 2 c2 µ 2 θ 2 -c1 µ 1 θ 1 > 0.
• Example 3: we consider the following parameters:

θ 2 = 0.1; µ = [8, 8]; λ = [2.8, 2.8]; c = [1, 1]; d = [0.5, 2]
, and we let θ 1 vary. Hence, ρ = 0.7, i.e., we are in underload. The results are plotted in Fig. 9.

When θ 1 ∈ [0, 0.4], we have c2 µ 2 /θ 2 ≥ c1 µ 1 /θ 1 and c2 µ 2 ≥ c1 µ 1 , in which case the heuristic gives priority to class 2, as do all the index policies. On the other hand, when θ 1 ∈ (0.4, 4], then c2 µ 2 /θ 2 ≥ c1 µ 1 /θ 1 and c1 µ 1 ≥ c2 µ 2 and a switching curve does appear in the heuristic. For the cases where no switching curve appears (θ 1 ∈ [0, 0.4]), all the index rules are optimal, but as soon as a switching curve emerges in the heuristic the cµ rule gives a positive suboptimality gap. The reason why the cµ-rule performs bad in this particular case is that as soon as the ratio c1 µ 1 -c 2 µ 2 c2 µ 2 /θ 2 -c 1 µ 1 /θ 1 becomes small, the switching curve gets close to zero and hence the cµ/θ rule becomes optimal.

Performance analysis for K > 2

We analyze the relative performance of the heuristic as explained in Section 4. Here we take the same example that λ i = λβ i , i = 1, 2, 3, denote the arrival rate of class-i jobs, where λ denotes the total arrival rate and β i is the fraction of class-i customers. We choose β i , i = 1, 2, 3, in such a way that ρ 1 = ρ 2 = ρ 3 . We vary the value of λ to change the total load in the system and we compute the relative suboptimality gap of all the policies, including the heuristic. The results are depicted in Fig. 10. We observe that our policy is optimal together with the cµ rule for very low loads but at some point, as the workload ρ increases, the cµ-rule starts performing increasingly worse. On the other hand, the cµ/θ and the cµ/θc rules become optimal when the load becomes larger than 1. Our heuristic keeps a low suboptimality gap throughout.

Conclusions

In this paper, we have proposed a fluid model to obtain an approximative optimal control for a multi-class single server queue with abandonments. Using Pontryagin's Maximum Principle we have completely characterized the fluid optimal control in the case of two classes, which provides very valuable insights into the solution of the stochastic problem for an arbitrary number of classes: close to the origin the optimal control behaves according to the cµ-rule and far from the origin according to the cµ/θ -rule. We then proposed a heuristic for the stochastic model for an arbitrary number of classes that follows this structure, and with numerical experiments we have shown that it performs very well.

There are several interesting research avenues that are worthwhile pursuing. An interesting problem is to establish the existence of a switch curve in the optimal policy of the stochastic problem. Another interesting open problem would be to show that the fluid-based heuristic is asymptotically optimal for the stochastic problem.

c1 n 1 (t) + c2 n 2 (t)dt.

In order to compute the trajectories n 1 (t) and n 2 (t), we will split up the time into two time intervals, [0, t 1 ] and [t 1 , t 2 ],

where t 1 is the moment when class 1 hits zero and t 2 when class 2 hits zero. After some algebra, we obtain that for the interval [0, t 1 ] the trajectories are as follows:

       n 1 (t) = ε + µ 1 -λ 1 θ 1 e -θ 1 t + λ 1 -µ 1 θ 1 = -θ 1 t ε + µ 1 -λ 1 θ 1 + ε + o(ε) t ∈ [0, t 1 ], n 2 (t) = ε - λ 2 θ 2 e -θ 2 t + λ 2 θ 2 = θ 2 t λ 2 θ 2 -ε + ε + o(ε) t ∈ [0, t 1 ].
We used here that t 2 ≤ n 1 (0)/µ 1 +n 2 (0)/µ 2 1-ρ = O(ε),3 hence e -θ 1 t = -θ 1 t + 1 + o(ε), for t ≤ t 2 . (Here o(ε) = g(ε) for g(•) a function that satisfies lim ε→0 g(ε)/ε = 0.) We note that since ε is chosen small enough, n 2 (t) > 0 for all t < t 1 . Time t 1 being the moment at which class 1 empties, we obtain

t 1 = ε θ 1 ε + µ 1 -λ 1 θ 1 = ε µ 1 -λ 1 + o(ε), therefore n 2 (t 1 ) = λ 2 θ 2 εθ 2 µ 1 -λ 1 + ε + o(ε). (A.1)
Recall that t 2 is the time at which class 2 is emptied. In the interval [t 1 , t 2 ] class 1 receives service ρ 1 and class 2 service 1ρ 1 . Hence, after some algebra we obtain that

   n 1 (t) = 0, t ∈ [t 1 , t 2 ], n 2 (t) = A ′ 2 e -θ 2 t + λ 2 -µ 2 (1 -ρ 1 ) θ 2 = A ′ 2 (-θ 2 t + 1) + λ 2 -µ 2 (1 -ρ 1 ) θ 2 + o(ε), t ∈ [t 1 , t 2 ],
where A ′ 2 is the constant of integration. Here we used that t = O(ε), hence e -θ 2 t = -θ 2 t + 1 + o(ε). Moreover, from (A.1) we obtain

A ′ 2 = -λ 2 θ 2 -εθ 2 µ 1 -λ 1 + ε + µ 2 (1-ρ 1 )-λ 2 θ 2 1 -θ 2 ε µ 1 -λ 1 + o(ε), hence, we have n 2 (t) = (λ 2 θ 2 + θ 2 (µ 1 -λ 1 ))ε + (µ 2 (1 -ρ 1 ) -λ 2 )(µ 1 -λ 1 ) -θ 2 2 ε + (µ 1 -λ 1 )θ 2 (-θ 2 t + 1) + λ 2 -µ 2 (1 -ρ 1 ) θ 2 + o(ε), = (λ 2 θ 2 + θ 2 (µ 1 -λ 1 ))ε + (µ 2 (1 -ρ 1 ) -λ 2 )(µ 1 -λ 1 ) -θ 2 2 ε + (µ 1 -λ 1 )θ 2 (-θ 2 t) + (µ 1 -λ 1 + µ 2 (1 -ρ 1 ))ε -θ 2 ε + µ 1 -λ 1 + o(ε), t ∈ [t 1 , t 2 ],
and from n 2 (t 2 ) = 0 we obtain

t 2 = (µ 1 -λ 1 + µ 2 (1 -ρ 1 ))ε -θ 2 2 ε 2 + (λ 2 θ 2 + θ 2 (µ 1 -λ 1 ))ε + (µ 2 (1 -ρ 1 ) -λ 2 )(µ 1 -λ 1 ) + o(ε) = (µ 1 -λ 1 + µ 2 (1 -ρ 1 ))ε (µ 2 (1 -ρ 1 ) -λ 2 )(µ 1 -λ 1 )
+ o(ε).

We can now compute the cost function:

C 1 (t, (ε, ε)) = t 1 0 c1 ε + µ 1 -λ 1 θ 1 (-θ 1 t) + ε + c2 ε - λ 2 θ 2 (-θ 2 t) + ε dt + t 2 t 1 c2 (λ 2 θ 2 + θ 2 (µ 1 -λ 1 ))ε + (µ 2 (1 -ρ 1 ) -λ 2 )(µ 1 -λ 1 ) -θ 2 2 ε + (µ 1 -λ 1 )θ 2 (-θ 2 t) dt + t 2 t 1 c2 (µ 1 -λ 1 + µ 2 (1 -ρ 1 ))ε -θ 2 ε + µ 1 -λ 1 dt + o(ε 2 ) = ε 2 c1 2(µ 1 -λ 1 ) + c2 2(µ 1 -λ 1 ) + λ 2 2(µ 1 -λ 1 ) 2 -c2 (λ 2 θ 2 + θ 2 (µ 1 -λ 1 ))ε + (µ 2 (1 -ρ 1 ) -λ 2 )(µ 1 -λ 1 ) 2(-θ 2 ε + (µ 1 -λ 1 )) (t 2 ) 2 -(t 1 ) 2 + c2 (µ 1 -λ 1 + µ 2 (1 -ρ 1 ))ε -θ 2 ε + µ 1 -λ 1 (t 2 -t 1 ) + o(ε 2 ), where (t 2 ) 2 -(t 1 ) 2 = (b 1 ε 2 + b 2 ε) 2 (-b 2 1 ε 2 + b 3 ε + b 4 ) 2 -ε 2 b 2 5 + o(ε 2 ) = b 2 2 ε 2 b 2 4 -ε 2 b 2 5 + o(ε 2 ), t 2 -t 1 = b 1 ε 2 + b 2 ε b 4 -b 5 ε + o(ε) = b 2 b 4 -b 5 ε + o(ε 2 ) + o(ε), with b 1 = -θ 2 , b 2 = µ 1 -λ 1 + µ 2 (1 -ρ 1 ), b 3 = λ 2 θ 2 + θ 2 (µ 1 -λ 1 ), b 4 = (µ 2 (1 -ρ 1 ) -λ 2 )(µ 1 -λ 1 ), b 5 = 1 µ 1 -λ 1 .
After some calculations, we then obtain

C 1 (t, (ε, ε)) = c1 ε 2 1 2(µ 1 -λ 1 ) + c2 ε 2 2(µ 1 -λ 1 ) + λ 2 2(µ 1 -λ 1 ) 2 + (µ 1 -λ 1 + λ 2 ) 2 2(µ 2 (1 -ρ 1 ) -λ 2 )(µ 1 -λ 1 ) 2 + o(ε 2 ).
By symmetry, the cost when instead class 2 is given priority is given by

C 2 (t, (ε, ε)) = c2 ε 2 1 2(µ 2 -λ 2 ) + c1 ε 2 2(µ 2 -λ 2 ) + λ 1 2(µ 2 -λ 2 ) 2 + (µ 2 -λ 2 + λ 1 ) 2 2(µ 1 (1 -ρ 2 ) -λ 1 )(µ 2 -λ 2 ) 2 + o(ε 2 ).
It can now be checked that C 1 (t, (ε, ε)) ≤ C 2 (t, (ε, ε)) if and only if c1 µ 1 ≥ c2 µ 2 , (given that we are in underload (ρ < 1)), which proves the result.

We now present the proof of Lemma 2. We will make use of Pontryagin's Maximum Principle and we will therefore first present the statement of the theorem adapted to our problem formulation. Theorem 1. Necessary conditions for an optimal control of problem P (for ρ ≤ 1) are given by the Pontryagin ′ s Maximum Principle [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]Theorem 3.26]: let s * (•) be an optimal control, piecewise continuous, and let n * (•) be the associated optimal trajectory. Let T be the optimal final time subject to optimization, i.e., T is such that n * (T ) = 0. Then, there exists a continuous function γ * (t) = (γ * 1 (t), . . . , γ * K (t)) = (0, . . . , 0) with piecewise continuous derivatives that for all t ∈ [0, T ] satisfies, Proof of Lemma 2. We assumed that ρ 1 + ρ 2 < 1 and as explained in Section 3 under any non-idling control the optimal final time is finite. We first solve for Eq. (A. Hence, under the optimal control the class with higher value for µ k C ′ k e θ k t + ck θ k value will be prioritized. Without loss of generality, we have assumed that for the given initial conditions n(0) priority is given to class 2 when t = 0. To determine whether there is a switch in priorities we study the following switching function:

φ(t) := µ 1 C ′ 1 e θ 1 t + c1 θ 1 -µ 2 C ′ 2 e θ 2 t + c2 θ 2 .
Hence, at time t, if φ(t) < 0, then it is optimal to prioritize class 2 and if φ(t) > 0, then it is optimal to prioritize class 1.

Recall that we assumed it to be optimal to serve class 2 at time 0, so that φ(0) < 0. Note that, this function can at most have one zero. Hence, two things can happen:

1. ∃ t ∈ [0, T ], s.t φ(t) = 0. We denote this time by t 1 , i.e., φ(t 1 ) = 0. Hence, the optimal action in the interval [0, t 1 ] is to prioritize class 2, and the optimal action in the interval [t 1 , T ] is to prioritize class 1. 2. ∄ t ∈ [0, T ] s.t φ(t) = 0. Hence, the optimal action is to prioritize class 2 for all t ∈ [0, T ].

Hence, it remains to be derived under which conditions a switch can occur, and in which state (n 1 , n 2 ) this happens. For the ease of notation we assume t 1 = 0, so the state (n 1 (0), n 2 (0)) = (n 10 , n 20 ) is a point on the switching curve. We further define t 2 as the moment at which the amount of fluid in class 1 empties and t 3 as the time at which the equilibrium (0, 0) is reached. Hence, s * (t) = (0, 1) for t = 0, s * (t) = (1, 0) for t ∈ (0, t 2 ], s * (t) = (ρ 1 , 1ρ 1 ) for t ∈ (t 2 , t 3 ].

We will now study the switching function, which fully characterizes which class is given priority. Note that the constants C ′

Fig. 1 .

 1 Fig. 1. Multi-class single-server queue with abandonments.

  (a) ρ = 0.6818. (b) ρ = 0.7321. (c) ρ = 1. (d) ρ = 1.4018.

Fig. 3 .

 3 Fig. 3. Switching curves for SM1, SM2 and the fluid control model.

  (a) Relative suboptimality gap for SM1. (b) Relative suboptimality gap for SM2.

Fig. 6 .

 6 Fig. 6. Performance comparison of policies for Example 1.

  (a) Relative suboptimality gap for SM1. (b) Relative suboptimality gap for SM2.

Fig. 7 .

 7 Fig. 7. Performance comparison of policies for Example 2.

Fig. 8 .

 8 Fig. 8. Comparison of switching curves for Example 2.

  was introduced in Section 4 with parameters µ = [10, 10, 9]; θ = [1, 0.5, 0.25]; c = [1.7, 1.7, 1.7]; d = [2, 2, 4]. Let(a) Relative suboptimality gap for SM1. (b) Relative suboptimality gap for SM2.

Fig. 9 .

 9 Fig. 9. Performance comparison of policies for Example 3, with load ρ = 0.7.

Fig. 10 .

 10 Fig. 10. Performance comparison of policies for K = 3.

  ∂H(n * , s * , γ * , t)∂n k ∀k ∈ {1, . . . , K },(A.2)in all the continuity points of s * (t) where H is the Hamiltonian of the system given by,H (n(t), s(t), γ (t), t) = µ 1 s 1 (t)θ 1 n 1 (t) . . . λ Kµ K s K (t)θ K n K (t)

	1.
	γ * k = -
	K		λ 1 
	ck n k (t) + γ T (t)	 	  ,	(A.3)
	k=1
	2.
	s (A.4)
	3.

* (t) = arg min s∈S H (n * (t), s, γ * (t), t), ṅ * k (t) = λ kµ k s * k (t)θ k n * k (t) (A.5)

in all the continuity points of s * (t), with n * (0) = n 0 , n * (T ) = 0, 4. and the transversality condition

H (n * (t), s * (t), γ * (t), t) = 0, ∀t ∈ [0, T ].

  2), which gives us γ * k (t) = C ′ k e θ k t + ck

	Hence, Eq. (A.4) is equivalent to solving	θ k	where C ′ k are constants of integration.
	arg min s∈S	2 k=1	-µ k C ′ k e θ k t +	ck θ k	s k .

(A.7)

  C ′ 2 , which appear in the switching function φ(t), are still to be determined. In order to obtain C ′ 1 , C ′ 2 , we will apply the transversality conditions of the Pontryagin's Maximum Principle in Eq. (A.6).If t = t 1 = 0, then s * 2 (t) = 1 and s * 1 (t) = 0. Using that γ * k (t) = C ′ k e θ k t + ck /θ k ,we obtain that the Hamiltonian for t = t 1 = 0 is given by H (n * (t), s * (t), γ * (t), t) = c1 λ 1 θ 1 -C ′

1 , 1 θ 1 n 10 -

This follows from the fact that the workload w(t) := n 1 (t)/µ 1 + n 2 (t)/µ 2 has a negative drift smaller than or equal to ρ -1, see the footnote in Section 3.

Acknowledgment

The Ph.D. fellowship of Maialen Larrañaga is funded by a research grant of the EADS Foundation (http://fondation.eads. com/).

Appendix

In this section we present the proofs of Lemmas 1 and 2, which were used in order to prove Proposition 1. In addition, we give the statement of Pontryagin's Maximum Principle.

Proof of Lemma 1. Lemma 1 states which class is optimal to serve close to the origin. We calculate the cost function when starting in a point very close to the origin (n 1 (0), n 2 (0)) = (ε, ε) when priority is given to class 1. We do the same for the case when priority is given instead to class 2. When comparing both cost functions, we get the condition under which prioritizing class 1 gives lower cost than prioritizing class 2. We note that, it is sufficient to compare the above described two policies: since the control appears linearly, we can assume that under the optimal policy full priority will be given to one class as long as we start close enough to the origin, see [START_REF] Chachuat | Nonlinear and dynamic optimization: from theory to practice[END_REF].

We first consider the control that gives full priority to class 1. When class 1 hits zero, ρ 1 is given to class 1 and 1ρ 1 to class 2, until the equilibrium (0, 0) is reached. The cost under this policy, starting in state (n 1 (0), n 2 (0)) = (ε, ε), is