Valeria Loscrí
email: valeria.loscri@inria.fr

Anna Maria Vegni
email: annamaria.vegni@uniroma3.it

Channel Modeling in a Phonon-based Quantum Network for Nano-communications

Keywords: Quantum computing, phonons, nano-communications, information capacity

Channel Modeling in a Phonon-based Quantum Network for Nano-communications

Valeria Loscrì, Anna Maria

INTRODUCTION

Traditional communication paradigms are not suitable in the context of nanotechnology, above all when applied in bio-medical contexts and for body networked systems. Specific features of human body need to be taken into account in order to derive a biological propagation model for nanocommunications. Di↵erent communication alternatives have been considered, such as molecular and nano-communications [START_REF] Akyildiz | Nanonetworks: A new frontier in communications[END_REF], acoustic [START_REF] Loscrí | An acoustic communication technique of nanorobot swarms for nanomedicine applications[END_REF], molecular communications based on Forster Resonance Energy Transfer (FRET) phenomenon [START_REF] Kuscu | Coverage and throughput analysis for fret-based mobile molecular sensor/actor nanonetworks[END_REF] just to mention some of them. A step towards the miniaturization at nanoscale level can be also moved by considering quantum phenomena. In fact, nanoscale cannot be considered as another step towards miniaturization, but it represents a kind of new scale [START_REF] Akyildiz | Internet of bionanothings[END_REF]. Quantum phenomena can be considered at a purely quantum level or as derived from both quantum and classical laws and components. A specific type of quantum particles is represented by phonons, that represent the quanta of mechanical vibrations or quanta of lattice Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. In this paper, we will focus on a specific context, namely body network systems, where phonons can be generated by photon-phonon interaction. Specifically, we will characterize phonons as information carriers, and derive a theoretical expression of the information capacity. Furthermore, since we can assume that the biological information processing takes place at the challenging regime where quantum meets classical physics, we will focus on a specific biological scenario with a sample of human tissue irradiated with an electromagnetic field, representing the source generation of the photon-phonon interaction. The rest of the paper is organized as follow. In Section 2 we derive a theoretical evaluation of the capacity. In Section 3 we show a concrete example of biological tissue irradiated with an electromagnetic field and we show the capacity information in the specific case under analysis. Finally, conclusions and future directions are drawn at the end of the paper.

INFORMATION CAPACITY

In this paper we are interested to derive a theoretical information capacity in a phonon-based quantum network. For this aim, we start by considering the computation of the information capacity in a "traditional case". In a classical communication channel, the information capacity, namely the maximum number of bits that can be delivered in a reliable way, is given by considering the maximum of the Von Neuman entropy [START_REF] Giovannetti | Capacity of nonlinear bosonic systems[END_REF] as S(⇢) = Tr[⇢ log 2 ⇢] where ⇢ represents the input states.

If we assume that the entropy S(⇢) is maximized on the states where the average energy is E = Tr[⇢H], and H is the Hamiltonian, then we can solve the constrained maximization of S(⇢) by using standard variational methods. This implies to solve the following equation:

⇢ S(⇢) 1 ln 2 Tr[H⇢] 2 ln 2 Tr[⇢] = 0, (1)
where is the Dirac function, 1 and 2 are Lagrange multipliers that consider the normalization constraint Tr[⇢] = 1, and the ln 2 factor is introduced to make possible the use of natural logarithms. Equation ( 1) can be solved by density matrix as ⇢ = e H Z( ) where Z( ) = Tr[e H ] is the partition function of the system, and is determined by solving

E = @ @( ) ln[Z( )]. (2)
We can easy compute the capacity of the quantum channel as:

C = S  e H Z( ) = E + ln[Z( )] ln 2 . (3)
Of course, this represents an ideal capacity, since for real systems we must also account for intrinsic phonon losses, backscattering and re-thermalization e↵ect.

From (1) we can argue that the evaluation of the system capacity can be done through the evaluation of its partition function Z( ), that is generally not easy to be derived.

PHONON CAPACITY IN A BIOLOGICAL CONTEXT

In this section, we will examine the capacity of a phononbased quantum channel for biomedical applications, assuming an electromagnetic radiation is incident to a portion of human tissue.

Let us consider the photon-phonon interaction as mediated by a homogeneous sample of identical elements (namely, the human cells), which are in harmonic modes of vibration. We can consider a system of n vibrating elements, each of them has an energy as

En = ✓ n + 1 2 ◆ hf, (4)
where En represents the energy of the n-th stationary state, f is the frequency of a normal mode that an element vibrates accordingly to, and h is the Planck's constant equal to 6.62606957 ⇥ 10 34 [J s].

When an element absorbs totally or partially a photon with an initial frequency fin, there is a phonon production that is regulated by Raman-Stokes scattering e↵ect, and an excited phonon will have a frequency f . This results in the n-th element to acquire a higher energy, and the absorbed energy will be En E0 = nphf, where np represents the number of phonons. When a photon interacts inelastically with one element, it contributes to generate a random number of phonons with a randomized value of frequency. Notice that we are assuming the maximum number of phonons generated since we do not have prior information regarding the maximum number of phonons that can be created in a single collision between a photon and a cell. Furthermore, we assume that all the phonons will have the same frequency f . This means that the number of phonons will be exactly equal to the upper bound i.e., k B T hf 1 2 . Then, after a few calculations, it follows that in the case of wideband systems, the capacity can be derived as:

C wb ' ⇡ ln 2 r 2n + 1 3 . (5)
In practice, we have determined that the capacity in the case of a homogeneous wideband channel is proportional to the number of phonons that are inversely proportional to the frequency. In the specific case of a biological tissue, there exists a frequency band in the range [10 3 , 10 12 ] Hz, where the energy absorbed reaches its maximum value and it seems that there is no appreciable absorption beyond this band. So, with the aim of characterizing the phonon-based quantum channel capacity, we considered this frequency range.

In Figure 1 we show the capacity of the system expressed in [qubit/s] by varying the frequency in the range [10 3 , 10 12 ] Hz. Since the number of phonons, at a fixed temperature, is higher at lower frequency modes, the capacity will be higher at lower frequencies. It is worth to recall that we are considering a 1 to 1 correspondence in the phonon generation from one incident photon. This means that for each photon generated there will be one phonon.

CONCLUSIONS

In this paper we analyzed specific quantum particles, named phonons, representing acoustic excitations, from a communication perspective. Specifically, we assumed phonons as potential information carriers. Through the radiation of an electromagnetic source on a biological tissue, we observe the generation of a photon-phonon interaction, that allows to derive the theoretical information capacity of these generated phonons.

The work dealt in this paper has as objective to start the characterization of a phonon-based networked system, that could be exploited in a future for addressing the design of nano-motors with specific features matching the environment under analysis. As future investigations, we aim to refine the model presented by taking into account of real phenomena.

Figure 1 :

 1 Figure 1: Capacity of phonon-based quantum channel versus frequency.


Anna Maria Vegni
email: annamaria.vegni@uniroma3.it

Valeria Loscrí
email: valeria.loscri@inria.fr

Performance of a Chirality-affected Channel exhibiting Giant Optical Activity for Terahertz Communications

Keywords: THz band, chirality effects, Giant Optical Activity, nanocommunications

Terahertz frequency band is an emerging research area related to nano-scale communications. In this frequency range, specific features can provide the possibility to overcome the issues related to the spectrum scarcity and capacity limitation. Apart high molecular absorption, and very high reflection loss that represent main phenomena in THz band, we can derive the characteristics of the channel affected by chirality effects occurring in the propagation medium, specifically, in the case where a Giant Optical Activity is present. This effect is typical of the so-called chiral-metamaterials in (4-10) THz band, and is of stimulating interest particularly for millimeter wireless communications.

In this paper, we analyze the behavior of specific parameters of a chiral-metamaterial, like the relative electrical permittivity, magnetic permeability and chirality coefficients, and from that we derive the channel behavior both for Lineof-Sight and No Line-of-Sight propagations. We notice the presence of spectral windows, due to peaks of resonance of chiral parameter. Finally, performances of the chiralityaffected channel have been assessed in terms of (i) channel capacity, (ii) propagation delay, and (iii) coherence bandwidth, for different distances.

INTRODUCTION

The increasing demand of wireless nanocommunication systems following the framework of Internet of NanoThings [START_REF] Akyildiz | The Internet of Nano-Things[END_REF] has motivated the need to design accurate channel models working in the Terahertz band [START_REF] Piesiewicz | Short-range ultra-broadband terahertz communications: Concepts and perspectives[END_REF][START_REF] Akyildiz | Terahertz Band: Next Frontier for Wireless Communications[END_REF]. This frequency band represents one of the most promising spectrum bands to enable ultra-high-speed communications, with the aim to overcome the spectrum scarcity and capacity limitations of current wireless systems. Indeed, existing channel mod-Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. NANOCOM'16, September 28-30, 2016, New York, NY, USA c 2016 ACM. ISBN 978-1-4503-4061-8/16/09. . . $15.00 DOI: http://dx.doi.org/10.1145/2967446.2967453 els adopted for lower frequency bands cannot be re-used for THz communications.

Many researchers have already presented novel channel models for THz band [START_REF] Jornet | Channel modeling and capacity analysis for electromagnetic wireless nanonetworks in the terahertz band[END_REF][START_REF] Llatser | Time-and frequency-domain analysis of molecular absorption in short-range terahertz communications[END_REF][START_REF] Piro | Terahertz communications in human tissues at the nanoscale for healthcare applications[END_REF][START_REF] Han | Multi-ray channel modeling and wideband characterization for wireless communications in the terahertz band[END_REF][START_REF] Zhang | Three dimensional end-to-end modeling and directivity analysis for graphene-based antennas in the terahertz band[END_REF], where molecular absorption and spreading loss are the main features studied in this frequency range. Another work [START_REF] Han | Multi-wideband waveform design for distance adaptive wireless communications in the terahertz band[END_REF] considers a multi-ray approach by assuming reflected, scattered and diffracted paths, in order to model the main THz-band channel features, such as the distance-varying spectral windows, and the temporal broadening effects.

As it can be noticed from previous works, the channel modeling in THz band is addressed through transfer functions that consider specific features, like molecular absorption loss, and spreading loss. However, there are other effects that deserve to be considered and analyzed, such as the electromagnetic chirality effect and the specific features of the propagation medium, that are normally neglected in classical modeling of transmission channels. The relative chirality parameter is a specific characteristic of a chiral homogeneous isotropic medium. Standard values are in the range [0, 1], but in particular media such as the chiral complex materials where a Giant Optical Activity (GOA) takes place, the relative chirality parameter is complex and varies with the frequency, showing multiple peaks at specific resonance frequencies [START_REF] Fang | Dual-band terahertz chiral metamaterial with giant optical activity and negative refractive index based on cross-wire structure[END_REF]. A material that exhibits a GOA and is affected by the chirality effects is called chiralmetamaterial [START_REF] Wang | Chiral metamaterials: Simulations and experiments[END_REF]. This is an artificial material that shows a frequency-dependent cross-coupling between the electric and magnetic fields. This interesting property is of great interest to many areas of science, like analytical chemistry and molecular biology.

In this paper, we consider a chiral-metamaterial exhibiting a GOA, and we analyze the specific behavior of channel transfer function in case of direct and multi-path propagation, in the (4-10) THz frequency range. Due to the resonant behavior of chiral parameter, the channel model shows specific frequency-dependent spectral windows, guaranteeing high bandwidth values.

This paper is organized as follows. In Section 2 we introduce the frequency-dependent behavior of specific parameters of a chiral-metamaterial. Starting from the concept of electromagnetic chirality [START_REF] Engheta | Chiral Materials and Chiral Electrodynamics: Background & Basic Physical Principles[END_REF][START_REF] Lakhtakia | Recent contributions to classical electromagnetic theory of chiral media: what next?[END_REF][START_REF] Lindell | Electromagnetic waves in chiral and bi-isotropic media[END_REF], we consider the chiral effects following the change in the propagation velocity and in the refractive index, due to the chiral impurities inside the propagation medium. These effects are evaluated also in the case when the considered medium exhibits a GOA [START_REF] Fang | Dual-band terahertz chiral metamaterial with giant optical activity and negative refractive index based on cross-wire structure[END_REF][START_REF] Zhou | Terahertz chiral metamaterials with giant and dynamically tunable optical activity[END_REF]. Then, in Section 3 we derive the corresponding chiralityaffected channel model for THz band, and present the re- lated frequency-dependent spectral windows. Section 4 is then devoted to the performances of the chiral channel, assessed in terms of capacity, propagation delay, and coherence bandwidth, in case of LoS and NLoS propagation modes. Finally, conclusions are drawn at the end of the paper.

FULL-WAVE PROPAGATION IN A CHIRAL-METAMATERIAL

This section is devoted to the design of a full-wave propagation model for THz band, when a GOA is working. Starting from the classic harmonic macroscopic Maxwell's equations, we consider the electromagnetic propagation inside a generic complex material, under the assumption that it is a linear and chiral medium.

Unconventional materials (i.e. metamaterials) are specifically considered since the GOA is reinforced by using thin metallic crossed-structure impurities in the host dielectric medium, that is chiral-metamaterials [START_REF] Wang | Chiral metamaterials: Simulations and experiments[END_REF]. Therefore, we will consider a time-harmonic generic linear material, where chiral (magneto/electric-optical) effects are included in the following constitutive relations, that can be written as:

B = ξ • E + µ • H D = ε • E + ζ • H (1)
where we remind that B is the magnetic displacement and H is the magnetic field, as well as D is the electric displacement and E is the electric field. Finally, the symbol • represents the scalar product operator, and ξ, µ, ε, and ζ are specific tensor quantities of the material.

From (1) we observe the chirality property through the dependence of (i) E in B, and (ii) H in D. Furthermore, the displacement field existing inside the material is generated by an excitation expressed in terms of intensity of the incident electro-magnetic field. Therefore, the material under consideration is a linear chiral medium.

We remind that the chiral effects have a two-fold meaning i.e., (i) an electric field applied on the material provides not only an electric induction, but also a magnetic displacement, and (ii) a magnetic field applied on the material provides not only a magnetic induction, but also an electric displacement, unlikely from other non-chiral materials.

As previously said, in this paper our attention is devoted to a particular class of chiral-metamaterials (GOA). In [START_REF] Zhao | Chiral metamaterials: retrieval of the effective parameters with and without substrate[END_REF], the authors show that for a GOA reciprocal material the specific constitutive relations are as follows:

B D = -j ξ 0 ξr c µ0µr ε0εr j ξ 0 ξr c • E H , ( 2
)
where it is clear that the natural dielectric (where ε b and µ b are the permittivity and permeability, respectively) becomes a metamaterial. Moreover, for a GOA material, at the frequency around 5 THz and 8 THz, there are four resonance frequencies of the ξr relative chirality parameter i.e., [4.8, 5.6, 7.9, 8.2] THz.

The same consideration is applied to the relative permittivity and permeability parameters, still in the (4-10) THz band. As reported in [START_REF] Fang | Dual-band terahertz chiral metamaterial with giant optical activity and negative refractive index based on cross-wire structure[END_REF], εr and µr are complex parameters, and the real part has a frequency-dependent behavior, with resonant peaks. Figure 1 (a), (b), and (c) depict the trends of real parts of εr, µr, and ξr, respectively, where it is easy to observe the resonant peaks.

Equation (2) becomes

B D = =   -j Ω ξ ω 0 ω ω 2 0 -ω 2 -jωγ µ0 µ b + Ωµω 2 ω 2 0 -ω 2 -jωγ ε0 ε b + Ωεω 2 0 ω 2 0 -ω 2 -jωγ j Ω ξ ω 0 ω ω 2 0 -ω 2 -jωγ   • E H , (3)
where ω = 2πf , ε0, and µ0 are the absolute permittivity and permeability, respectively. Then, the constitutive parameters of interest are:

ε = ε0εr = ε0 ε b + Ωεω 2 0 ω 2 0 -ω 2 + jωγ (ω 2 0 -ω 2 ) 2 + ω 2 γ 2 , (4)
µ = µ0µr = µ0 µ b + Ωµω 2 ω 2 0 -ω 2 + jωγ (ω 2 0 -ω 2 ) 2 + ω 2 γ 2 , (5)
ξr = Ω ξ ω0ω ω 2 0 -ω 2 + jωγ (ω 2 0 -ω 2 ) 2 + ω 2 γ 2 . ( 6
)
It is noted that the frequency resonant behavior of ξr is a like-Drude one, and Ωε, Ωµ, Ω ξ , γ, and ω0 are specific parameters of the GOA material [START_REF] Zhao | Chiral metamaterials: retrieval of the effective parameters with and without substrate[END_REF]. By simple computations, and assuming a lossy material i.e.,

ε b = Re [ε b ] + jIm [ε b ] µ b = Re [µ b ] + jIm [µ b ] (7)
we obtain

εr = Re [ε b ] + ω 2 0 (ω 2 0 -ω 2 )Ωε (ω 2 0 -ω 2 ) 2 +ω 2 γ 2 + j γω 2 0 Ωεω (ω 2 0 -ω 2 ) 2 +ω 2 γ 2 + Im [ε b ] , (8)
µr = Re [µ b ] + ω 2 (ω 2 0 -ω 2 )Ωµ (ω 2 0 -ω 2 ) 2 +ω 2 γ 2 + j γΩµω 3 (ω 2 0 -ω 2 ) 2 +ω 2 γ 2 + Im [µ b ] , (9)
ξr = ω 0 Ω ξ ω ω 2 0 -ω 2 (ω 2 0 -ω 2 ) 2 + ω 2 γ 2 +jω 0 Ω ξ γω 2 (ω 2 0 -ω 2 ) 2 + ω 2 γ 2 .
(10) Now, by posing the following expression for the square relative refractive index:

εrµr + ξ 2 r = (Re [εr] + jIm [εr]) (Re [µr] + jIm [µr]) + +(Re [ξr] + jIm [ξr]) 2 > 0,
(11) we observe that the following conditions hold for a GOA material:

Ωε = 1 + γ 2 ω 2 -ω 2 0 Re [ε b ] , (12)
Ωµ = 1 + γ 2 ω 2 -ω 2 0 Re [µ b ] , (13)
Ω ξ = 1 + γ 2 ω 2 -ω 2 0 Re [ε b ] Re [µ b ]. ( 14
)
It is observed that relations (12), [START_REF] Lakhtakia | Recent contributions to classical electromagnetic theory of chiral media: what next?[END_REF], and ( 14) state the connection between the host material parameters i.e., ε b , and µ b , and the specific GOA ones in order to obtain a positive refractive index in [START_REF] Wang | Chiral metamaterials: Simulations and experiments[END_REF]. Finally, the computation of the electro-magnetic field in the channel is carried out through the solutions of linear differential equations, arising from the following source-less Maxwell's equations:

∇ + jωξ • E = -jωµ • H ∇ -jωζ • H = jωε • E (15)
and the solving differential equations for E and H are given, respectively:

∇ -jωζ • µ -1 • ∇ + jωξ -ω 2 ε • E = 0 ∇ + jωξ • ε -1 • ∇ -jωζ -ω 2 µ • H = 0 ( 16
)
where ∇ is Kong's operator. Finally, by assuming the linear polarization of the electric field (i.e., E = Exx), we obtain the final differential equation for Ex, i.e.

α1Ex

CHIRAL CHANNEL MODEL

In this section, we present how the relative chiralilty parameter affects the channel performance in the (4-10) THz band, in the case of ray tracing propagation (i.e., LoS, and NLoS), and under the linear polarization hypothesis. Specifically, in NLoS case, we focus on reflected paths due at generic reflection centers located at z-plane. The reflection characteristics of the transmissive channel can be evaluated through the specific knowledge of the local planar geometry associated to the reflection centers.

The use of ray tracing techniques for channel modeling in THz band has been largely adopted, like in [START_REF] Han | Multi-ray channel modeling and wideband characterization for wireless communications in the terahertz band[END_REF], where Han et al. consider a multi-ray approach with one direct path, and other reflected, scattered, and diffracted paths. According to this approach, the channel model is the combination of several individual narrow sub-bands, each of them with a flat-band response. Assuming Ni narrow sub-bands, and in the case of stationary environment, the channel response in the i-th sub-band is given as

hi (τ ) = N i n=1 αi,nδ (τ -τn), (18)
where αi,n is the frequency-dependent attenuation, and τn is the propagation delay of the n-th ray in the multi-ray approach.

From (18), and according to the computations in [START_REF] Han | Multi-ray channel modeling and wideband characterization for wireless communications in the terahertz band[END_REF], we can derive the LoS and NLoS channel transfer functions in the case of chirality-affected channel with GOA, respectively as:

HLoS (f ) = H Abs (f ) HSpr (f ) e -j2πf τ LoS , (19)
and

HNLoS (f ) = νc 4πf (d1 + d2) e -j2πf τ NLoS -1 2 k(f )(d 1 +d 2 ) •R (f ) , (20)
where we assume the NLoS scenario is affected by reflected rays only, through the rough surface reflection loss i.e., R(f ).

In ( 19), H Abs is the transfer function due to the molecular absorption loss, while HSpr is the spreading loss that takes account for the chirality effect through νc that is the propagation velocity of the electro-magnetic field in a chiral homogeneous isotropic medium i.e.,

νc = c nc , ( 21
)
where c is the light propagation speed, and nc is the refractive index in a chiral medium i.e.,

nc = µrεr + ξ 2 r , (22)
with µr, εr and ξr frequency-dependent parameters, according to Figure 1. Finally, under the hypothesis of stationary scenario where the transmitter and the receiver are at a distance d [m], from (19) we obtain the propagation delay for the LoS ray as:

τLoS = d νc . ( 23
)
For the NLoS channel transfer function expressed in (20), by assuming d1 as the distance between the transmitter and a generic reflecting point, and d2 as the distance between this point and the receiver, we obtain the propagation delay of the j-th NLoS ray along the distance (d1 + d2), as

τNLoS = d1 + d2 νc . ( 24
)
From the expressions of channel transfer functions in ( 19) and (20), it is easy to compute the total path loss, as depicted in Figure 2 (a) in case of LoS and NLoS propagations, for different distances from transmitter to receiver, and assuming a specific reflecting angle for multi-path. By increasing the distance, the path loss has a higher trend. Moreover, similarly to the results in [START_REF] Han | Multi-wideband waveform design for distance adaptive wireless communications in the terahertz band[END_REF], the LoS propagation (black lines) provides higher values with respect to the NLoS scenario (blue lines). In both LoS and NLoS, the behavior is frequency-dependent, but in LoS propagation the path loss has a smoother trend, with some peaks at 5.8, 8.09 and 8.93 THz. On the other hand, for NLoS propagation, the peaks are well noticeable at 5.8 and 8.93 THz, while on the other frequencies, the trend is on average flat around 70, 100 and 120 dB for LoS at d = 1, 5, and 10 m, respectively.

Similarly to the analysis conducted in [START_REF] Han | Multi-wideband waveform design for distance adaptive wireless communications in the terahertz band[END_REF], we aim to characterize the spectral windows of chiral channel transfer functions in case of LoS and NLoS propagation. A spectral window is given by the portion of spectrum below a given path loss threshold. We expect to observe that the path loss peaks caused by the chiral effect create several spectral windows, with different bandwidths in each of them.

In the case of a path loss threshold set to 80 dB, the communication distance is limited for NLoS propagation at lower distance of 1 m, except the two peaks that are above this threshold, and correspond to 5.84 THz and 8.98 THz. According to the values assumed in [START_REF] Han | Multi-wideband waveform design for distance adaptive wireless communications in the terahertz band[END_REF], the threshold of 80 dB corresponds to no gains of transmission and reception antennas, and so to a multi-path propagation model.

In order to identify the spectral windows for LoS propagation, we have to increase the path loss threshold around 120 dB, so that a few windows appear for a distance of 1 m (see curve LoS for d = 1 m in Figure 2 (a)). However, in this case most of the path loss for LoS propagation is above the threshold, thus providing a reduced usable bandwidth. Figure 2 (b) depicts the usable bandwidth versus the distance for the path loss threshold of 120 dB. We notice that the available spectrum in LoS propagation is limited up to 4 m, reaching a maximum at 1.32 THz corresponding to a distance of 1 m. In contrast, the NLoS propagation reaches higher bandwidths, and then it decreases at 17 m where the bandwidth is 0.01 THz. The bandwidth rate in LoS is 75.5 GHz/m, while it reaches 3.90 THz/m in NLoS scenario.

It follows that an increase of the path loss threshold to 160 dB is expected to provide higher values of usable bandwidth in LoS propagation, as depicted in Figure 2 (c). Higher path loss thresholds rise from higher antenna gains, and the transmission becomes directional through the LoS path. In this case, the usage bandwidth in LoS propagation reaches higher values than those for the threshold of 120 dB. The lowest value is 0.01 THz for a distance of 15 m, and the average bandwidth rate for LoS propagation is 2.39 THz/m.

On the other side, for NLoS propagation, the usable bandwidth reaches approximately the maximum value of 6 THz for different distances, and then the average rate of the total usable bandwidth is 5.99 THz/m. As a result, we can conclude that within the range (4-10) THz the available bandwidth is almost the entire band, especially for NLoS propagation.

CHIRAL CHANNEL CHARACTERIZA-TION

Following the chirality-affected channel model presented in Section 3, in this section we investigate its main features in the (4-10) THz band. Specifically, we aim to characterize (i) the channel capacity, (ii) the propagation delay, and (iii) the coherence bandwidth.

Channel capacity and propagation delay

To evaluate the capacity limits in a chiral medium, we refer to the approach adopted in [START_REF] Han | Multi-ray channel modeling and wideband characterization for wireless communications in the terahertz band[END_REF], where the received signal has been decomposed as a sum of the sub-bands, each one with a narrow behavior and a flat-band response. The following constraint is adopted:

N B i=1 Pi ≤ PT OT , ( 25
)
where NB is the total number of sub-bands, Pi is the transmission power in the i-th sub-band, and PT OT is the total transmit power in the (4-10) THz band. Notice that, since the chiral parameter has a frequency-dependent behavior in (4-10) THz band, we consider only this frequency range. For NB sub-bands, the capacity can be defined as the sum of the single capacities in each sub-band i.e.,

C = N B i=1 Ci = N B i=1 ∆fi log 1 + |hi| 2 Pi ∆fiSN (fi) , ( 26
)
where SN is the power spectral density of the additive white Gaussian noise, and ∆fi is the sub-band range among two consecutive sub-bands i.e., ∆fi = fi+1 -fi, assumed as 10 GHz in our simulation results. We assume a flat power profile, that is the total power transmission is uniformly distributed over the entire operative band (i.e., from 4 to 10 THz). Also, we consider a power level of 46 dBm in all the sub-bands i.e., NB = 600. Figure 3 depicts the chirality-affected channel capacity with GOA in case of LoS and NLoS scenario. We notice that with a reduction of distance, the capacity decreases as well, and also the LoS scenario has a smoother behavior with respect to the frequency, while the NLoS shows an accentuate frequency-dependent trend, with distinguishable peaks at resonance frequencies. Specifically, in LoS, the capacity has an almost flat behavior, with a mean value of 0.22 Gbit/s for d = 10 m. Performances get worst in the case of NLoS propagation for d = 1 m, where we observe a degradation of capacity at 5.81 and 8.92 THz, corresponding to 25.65 Mbit/s and 24.47 Mbit/s, respectively.

From the expressions in ( 23) and ( 24), the propagation delay in LoS and NLoS scenarios is depicted in Figure 4. We observe the frequency-dependent behavior due to the chiral effect, and as expected, performance gets worst when the distance increases. An almost-flat behavior is shown for LoS at short distances (i.e., d = 1 m), while a resonant trend appears when increasing the distance, as well as in NLoS scenario due to the longer distances covered. Finally, we observe that the propagation delay both in LoS and NLoS case shows lower values corresponding to 5.81 and 8.92 THz.

Coherence bandwidth

The root mean square (rms) delay spread is a measure of how dispersive the channel is. It is expressed as [START_REF] Han | Multi-wideband waveform design for distance adaptive wireless communications in the terahertz band[END_REF]: where τi and τ 2 i are the first and second moments of the instantaneous power-delay profile, respectively. From (27) we can derive information about the coherence bandwidth, defined as the range of frequencies over which the channel correlation exceeds 50%.

σi = τ 2 i -τ 2 i , (27)
In our simulations, we consider two scenarios with a variable number of NLoS reflected rays i.e., (i) one, and (ii) five, and one direct ray. In both cases, we observe the frequencydependent behavior as typical of chiral materials exhibiting GOA. In Figure 5 (a) we show the coherence bandwidth in the case of one LoS and one NLoS path for different distances. As experienced in [START_REF] Han | Multi-ray channel modeling and wideband characterization for wireless communications in the terahertz band[END_REF], higher values are reached for shorter distances. However, we cannot compare our results to others obtained with pre-existing approaches, since the frequency range is not the same.

In our simulations, several peaks appear due to the chirality effects. This can allow tuning the frequency to resonant peaks in order to obtain higher performances. For example, for d = 1 m, the minimum value of rms delay is 0.33 ns, corresponding to 8.92 THz. This value corresponds to a symbol rate limited to 0.1/σi = 0.29 Gbit/s to avoid inter-symbol interference. Also, in this case, the coherence bandwidth is limited to 0.59 GHz at the frequency peak of 8.92 THz. On the other side, when the distance increases (i.e., d = 10 m), the minimum rms delay is 3.6 ns at 8.92 THz. This value provides a symbol rate limited to 27.71 Mbit/s, and the coherence bandwidth equals to 55.43 MHz, still at the same frequency.

Performances get worst in case of multiple reflected paths, as shown in Figure 5 (b). For d = 1 m the minumum rms is 0.78 ns, which corresponds to a symbol rate of 0.12 Gbit/s and a coherence bandwidth of 0.25 GHz. For higher distances (i.e., d = 10 m) the minimum rms is 7.31 ns, corresponding to a coherence bandwidth is 27.3 MHz and symbol rate of 13.6 Mbit/s.

CONCLUSIONS

In this paper, we have presented the performance of a chirality-affected channel with GOA, under the hypothesis of LoS and NLoS propagation in the (4-10) THz band. We considered the effects of the relative chiral parameter, assuming a frequency-dependent behavior with resonant peaks at specific frequencies. As a result, this affects the channel transfer function, as well as other performances. In particular, we identified the spectral windows that rise from the chiral effect, and the associated usable bandwidths. The spectral windows vary with the distance and the frequency, with corresponding bandwidths up to 6 THz, both in LoS and NLoS propagation. Other results allows to identify specific frequencies that guarantee high performances. As an instance, the rms delay is dependent on the distance and carrier frequency, and reaches minimum values at 8.92 THz, corresponding to higher coherence bandwidths. We can conclude that this particular material exhibiting GOA can guarantee high performances, especially at lower distances. Also, distance-adaptive and multi-carrier transmissions represent the more appropriate communication techniques that can benefit from the relationship between distance and bandwidth in the range (4-10) THz.

Figure 1 :

 1 Figure 1: Resonant frequency-dependent behavior of relative (a) electrical permittivity, (b) magnetic permeability, and (c) chirality parameter, in the THz band from 4 to 10 THz, [10].

Figure 2 :

 2 Figure 2: Spectral windows in a chiral-affected channel with GOA. (a) Path loss, and (b) total usage bandwidth for LoS and NLoS propagation in case of a path loss threshold of 120 dB, and (c) 160 dB.

Figure 3 :

 3 Figure 3: Capacity of a chirality-affected channel with GOA, versus frequency for LoS and NLoS propagation, and different distances.

Figure 4 :

 4 Figure 4: Propagation delay versus frequency in a chirality-affected channel with GOA, for LoS and NLoS propagation, and different distances.

Figure 5 :

 5 Figure 5: Coherence bandwidth in a chiralityaffected channel with GOA, in case of (a) one LoS and one NLoS path, an (b) one LoS and five NLoS paths.


Philippe Carmona
email: philippe.carmona@univ-nantes.fr

Directed polymer in random environment and two points state space

Keywords: MSC 2010 subject classifications: Primary 60K35 Directed polymer, random environment, free energy

We give an exact expression for the partition function of a continuous time DPRE on a two points state space.

Introduction

We are aware of just three1 models of directed polymer in a random environment for which the free energy at finite inverse temperature is well known:

1. The discrete polymer in dimension d = 1 with simple random walk paths and a log-gamma environment and boundary conditions: see Seppäläinen (2012). 2. The continuous time directed polymer with Poisson process paths and a Brownian environment : see O' Connell and Yor (2001). 3. The continuum random polymer with brownian paths and a white noise environment : see Amir, Corwin and Quastel (2011).

The origin of this note is to find the simplest possible model where some direct computations can be performed. Of course, this model is much less interesting than the three models above. Note also that we are even unable to generalize it to a three points state space ! Let us consider the simplest model of continuous time directed polymer in a random environment. Let ω = (ω(t)) t≥0 be the continuous time Markov chain on {1, 2} with generator:

L f (1) = f (2) -f (1) , L f (2) = f (1) -f (2) , (1.1)
that is the chain that spends an exponential time on 1 (resp 2) and the jumps on 2 (resp. 1). We let P i denote the law of the Markov chain starting from i, E i the associated expectation, and (W, ) the path space of piecewise constant cadlag functions from [0, +∞[ to {1, 2}. We set P = P 1 and E = E 1 .

The random environment consists of two independent standard Brownian motions (B i (t), t ≥ 0) defined on another probability space (Ω, , ).

For any t > 0 the (random) polymer measure µ t is the probability defined on the path space (W, ) by

µ t (dω) = 1 Z t e β H t (ω)-tβ 2 /2 (dω)
where β ≥ 0 is the inverse temperature, the Hamiltonian is

H t (ω) = t 0 d B ω(s) (s)
and the partition function is

Z t = Z t (β ) = E e β H t (ω)-tβ 2 /2 ,
It is well known, and for example established in (Carmona and Hu, 2006, Proposition 2.4) that the point to point partition function Z t (x, y)

:= E x e β H t (ω)-tβ 2 /2 1 (ω(t)= y) (1.2)
satisfy the Discrete Stochastic Heat Equation:

d Z t (x, y) = L Z t (x, .)( y) d t + β Z t (x, y)d B y (t) , (1.3)
in the Itô sense with inital conditions Z 0 (x, y) = δ x ( y) (from now on we shall fix as a starting point x = 1). Furthermore, the free energy is well defined

p(β ) := lim t→+∞ 1 t log Z t (β ) (a.s. and in L 1 ( )) , (1.4)
and is given by the limit (see (Carmona and Hu, 2006, Formula (15)))

p(β ) = - β 2 2 lim t→+∞ 1 t t 0 [I s ] ds , (1.5)
with I t the overlap

I t = µ ⊗2 t (ω 1 (t) = ω 2 (t)) = 1 Z 2 t 2 y=1 Z t (1, y) 2 .
Theorem 1.1. For this model of DPRE the mean ovelap converges:

lim t→+∞ [I t ] = α -(β ) (1.6)
with α -(β ) ∈ (0, 1) the smallest root of the polynomial

P β (X ) = 3β 2 X 2 -(5β 2 + 4)X + 2(1 + β 2 ) .
Consequently the free energy is

p(β ) = - β 2 2 α -(β ) .
Observe that as β → 0 + , α -(β ) → 1 2 as expected.

Proof of Theorem 1.1

To simplify notations we let X i (t) = Z t (1, i) and set Z 0 = 1 so that we have X 1 (0) = 1, X 2 (0) = 0, I 0 = 1 and (X 1 , X 2 ) is solution of the following simple system of stochastic differential equations:

d X 1 (t) = (X 2 -X 1 ) d t + β X 1 d B 1 (t) d X 2 (t) = -(X 2 -X 1 ) d t + β X 2 d B 2 (t) (2.1) It is easy to check that Z t = X 1 (t) + X 2 (t) is a martingale d Z t = β (X 1 d B 1 (t) + X 2 d B 2 (t))
with quadratic variation

d〈Z〉 t = β 2 (X 2 1 + X 2 2 ) d t = β 2 N t d t = β 2 Z 2 t I t d t ,
where we have set

N t = X 1 (t) 2 + X 2 (t) 2 so that I t = N t Z 2 t .
Without having to read Carmona and Hu (2006), one can infer directly that

log Z t = t 0 d Z s Z s - 1 2 t 0 d〈Z〉 s Z 2 s = t 0 d Z s Z s - β 2 2 t 0 I s ds so that 1 t [log Z t ] = - β 2 2 1 t t 0 [I s ] ds .
Let us do now some straightforward computations using Ito's formula

d X 2 1 (t) = ((β 2 -2)X 2 1 + 2X 1 X 2 ) d t + 2β X 2 1 d B 1 d N t = (4X 1 X 2 + (β 2 -2)N t )d t + 2β (X 2 1 d B 1 + X 2 2 d B 2 ) = (2Z 2 t + (β 2 -4)N t ) d t + 2β (X 2 1 d B 1 + X 2 2 d B 2 ) d〈N , Z 〉 t = 2β 2 (X 3 1 + X 3 2 )d t = β 2 (3Z t N t -Z 3 t ) d t = β 2 Z 3 t (3I t -1) d t .
In the last equation, we use the identity 2(a 3

+ b 3 ) = 3(a + b)(a 2 + b 2 ) -(a + b) 3 .
It is the only place where we really use the fact that the state space has only two points.

Let use the notation U t ∼ V t if U t -V t is a martingale. We have:

d I t = d N t Z 2 t - 2N t d Z t Z 3 t -2 d〈N , Z〉 t Z 3 t + 3N t d〈Z〉 t Z 4 t ∼ ((β 2 -4)I t + 2 -2β 2 (3I t -1) + 3β 2 I 2 t ) d t ∼ (3β 2 I 2 t -(5β 2 + 4)I t + 2(1 + β 2 ))d t = P(I t ) d t (2.2) with a = 5β 2 +4
6β 2 = 5 6 + 2 3β 2 and Let T = sup {t < t 0 : u(t) = α -}. On ]T, t 0 [ we have u ′ (t) ≥ P(u(t)) > 0 so u strictly increases on ]T, t 0 [, which is absurd since u(T ) = α -and u(t 0 ) < α -. Therefore, we have: ∀t > 0, u(t) ≥ α -.

P(X ) = 3β 2 (X 2 -2aX + a - 1 6 ) = 3β 2 (X -α + )(X -α -) with α ± := a ± a 2 -a + 1 6 . Since P(1) = 3β 2 (1 -a -1 6 ) = -2 we have α -< 1 < α + . We now
Observe that:

u ′ (t) = [P(I t )] = [P(I t ) -P(α -)] = 3β 2 (I 2 t -α 2 -) -(5β 2 + 4)(I t -α -) = 3β 2 [(I t + α -)(I t -α -)] -(5β 2 + 4) [I t -α -] ≤ 3β 2 (1 + α -) -(5β 2 + 4) [I t -α -] = -λ [I t -α -] .

If some interested reader finds another example where an exact computation of the free energy occurs, we are more than willing to incorporate it in this list

We shall check that λ > 0, and this implies, by Gronwall's Lemma,

6 > 1a. Either β ≤ 2 and then a ≥ 1 and we are done, or β > 2, a < 1, and we have to show that a 2a + 1 6 > (1a) 2 i.e. a > 5/6 which is true.


Patrice Perny

Paolo Viappiani

Abdellah Boukhatem

Incremental Preference Elicitation for Decision Making Under Risk with the Rank-Dependent Utility Model

This work concerns decision making under risk with the rank-dependent utility model (RDU), a generalization of expected utility providing enhanced descriptive possibilities. We introduce a new incremental decision procedure, involving monotone regression spline functions to model both components of RDU, namely the probability weighting function and the utility function. First, assuming the utility function is known, we propose an elicitation procedure that incrementally collects preference information in order to progressively specify the probability weighting function until the optimal choice can be identified. Then, we present two elicitation procedures for the construction of a utility function as a monotone spline. Finally, numerical tests are provided to show the practical efficiency of the proposed methods.

INTRODUCTION

Uncertainty is pervasive in human activities and represents an important source of complexity in individual and collective decision making. As soon as intelligent systems are used for supporting human decision making or simulating realistic human decision behaviors, preference modeling and preference elicitation becomes particularly important. In decision making under uncertainty and risk, preference models are used to represent uncertain outcomes and to provide normative decision rules for choice problems, but also to describe, predict or simulate observed human behaviors. Given a mathematical model used to compare the alternatives of a choice problem, preference elicitation consists in fitting the parameters of the model to a specific Decision Maker (DM), to capture her attitude towards risk. Then the model can be used to support her choices in complex situations involving a large number of alternatives or to integrate her value system into an autonomous decision agent. Considering this context, our paper aims at providing new tools for interactive decision support under risk.

Decision under risk is a standard formal framework for handling uncertainty in decision making, characterized by a probabilistic representation of uncertainty. In this framework, risky prospects are represented by probability distributions with a finite support, namely lotteries. In the seminal work of Bernoulli (1738;refer to [1954] for an English translation) and in the theory of von Neumann and Morgenstern (vNM) [1947], the values of lotteries are measured in terms of expected utility (EU). This well-known decision criterion is linear in probabilities and characterized by a utility function encoding the subjective value of any possible consequence for the DM; EU is used to compare lotteries and choice problems are solved by EU maximization. This choice model has been axiomatically justified in the context of risk by vNM [1947], but also in the more general context of uncertainty introduced by Savage [1954], where probabilities are not assumed to exist a priori.

From EU to RDU. Despite these axiomatic results and the intuitive appeal of EU theory, the model suffers from well known limitations, from a descriptive viewpoint. There exist situations where individuals may exhibit behaviors that are not consistent with EU theory, as illustrated by the so-called Allais's paradox. For example, people often prefer $3000 with certainty (choice A) to $4000 with probability .8 (choice B), but they prefer $4000 with probability .2 (choice D) to $3000 with probability .25 (choice C). Remarking that C = .25A + .75O and D = .25B + .75O where O is the choice to win nothing with probability 1, it turns out that such preferences violate the vNM independence axiom. This example, used by [START_REF] Kahneman | [END_REF] in their experiments, is frequently observed and known as the certainty effect: a reduction in probability of winning a reward creates a larger (negative) psychological effect when it is done from certainty than from uncertainty. Similar observations have been made in actual decision contexts, for instance in route-choice problems where evidence was found of violation of EU theory [Avineri and Prashker, 2004].

These experiments and others in the same spirit suggest that probabilities are distorted in the decision making process. More precisely, small probabilities (greater than 0) tend to be overestimated while large ones (smaller than 1) underestimated. This has motivated the introduction of a probabilistic transformation model to generalize EU, leading to evaluate the lottery (x 1 , p 1 ; . . . , x n ; p n ) that yields outcome x i with probability p i by i w(p i )u(x i ). This generalization of EU dates back to [Edwards, 1955] and appears also in prospect theory [START_REF] Kahneman | [END_REF]]. However, it can be easily shown that it violates the principle of stochastic dominance and could lead to select dominated alternatives; this is often considered as a serious weakness from a normative viewpoint. To overcome this problem, a solution proposed by Quiggin [1982] and Yaari [1987] consists in applying the probability transformation to the decumulative probability distribution function, and not to the probabilities of individual outcomes. This solution leads to the rank-dependent utility model (RDU) that consists in evaluating the lottery = (x 1 , p 1 ; . . . , x n ; p n ) such that x 1 ≥ . . . ≥ x n ≥ 0 1 by:

V ( ) = n i=1 w i k=1 p k [u(x i ) -u(x i+1 )] = w(p 1 )u(x 1 )+ n i=2 w i k=1 p k -w i-1 k=1 p k u(x i )
where x n+1 = 0 and w : [0, 1] → [0, 1] is a non-decreasing function such that w(0) = 0 and w(1) = 1. Note that the coefficient of u(x i ) in RDU depends on the cumulative probability of the outcomes greater or equal to x i (since outcomes are indexed to be sorted by decreasing order); this shows that this coefficient depends on the rank of x i in the set of possible outcomes. To illustrate the use of RDU, we compare the two following lotteries and with w(p) = p 2 and u(x) = √ x:

V ( ) = (.3) 2 (6 -5) + (.8) 2 (5 -3) + 1 2 3 = 4.37 and V ( ) = (.6) 2 (7 -2) + (1) 2 2 = 3.8, hence is preferred to . To give another example, let us remark that, for any lottery of type = (x + , p; x -, 1 -p), x + > x -, we have:

V ( ) = w(p)u(x + ) + (1 -w(p))u(x -)
Function w is referred to as the probability weighting function. It is worth noting that, when w(p) = p, RDU boils down to EU as we can see from the second formulation.

On the other hand, RDU is also known to be an instance of Choquet Expected Utility [Schmeidler, 1989]. More pre-1 As suggested by Gilboa [2008], it is more natural to think of the object of choice in Quiggin and Yaari's models as lotteries over final wealth (with positive outcomes) rather as prospects of gains and losses, because they did not emphasize gain-loss asymmetry in their theory.

cisely, it turns out to be the natural instance for decision making under risk due its compatibility with stochastic dominance [Wakker, 1990]. For more details about RDU theory see [Quiggin, 2012, Diecidue andWakker, 2001].

Let us mention also some well known variants of RDU theory. First, Yaari [1987] introduced and axiomatized a dual model to expected utility where transformations are applied to probabilities rather than to outcomes. This is a special case of RDU obtained when the utility function is linear in the outcomes. Moreover, the idea of rankdependent weightings was also incorporated by Kahneman and Tversky [1992] into prospect theory, leading to cumulative prospect theory. This theory extends the RDU theory to model different risk attitudes towards gains depending on whether above or below a reference level.

In this paper, we focus on the RDU model, and we address the problem of identifying, within a given (possibly large) set of lotteries, the preferred solution for a given DM consistent with RDU theory. This solution could be used for predicting a choice of the DM or even to make a recommendation. This requires to elicit, at least partially, the probability weighting function and the utility function. Note that the determination of RDU-optimal solutions has motivated various contributions in the past, e.g. [Nielsen andJaffray, 2006, Jeantet et al., 2012].

Incremental decision making.

A first approach to elicitation, standard in mathematical economics, aims to obtain a full description of preferences by the decision model, assuming that DM's preferences are observable on all possible pairs of alternatives. The elicitation process is justified by the axioms of the underlying theory and the components of the models are revealed point by point using systematic sequences of queries to obtain a precise specification of the model. To simplify the process, a frequent option used in economics (but also in artificial intelligence) consists in postulating a parametric form for each component of the decision model; queries are then used to fit the parameters. Refer to [START_REF] Wakker | [END_REF], Gonzalez and Wu, 1999, Abdellaoui, 2000] for full elicitation procedures proposed in economics for RDU, and to [Fürnkranz and Hüllermeier, 2003, Torra, 2010, Tehrani et al., 2012] for model-based preference learning.

Recently a number of works have tackled the elicitation of the components of the decision model in an adaptive way [Wang and Boutilier, 2003, Boutilier et al., 2006, Braziunas and Boutilier, 2007, Benabbou et al., 2014]; the aims is that of focusing on learning the "important" part of the utility, allowing to recommend near-optimal decisions with only partial information about the decision model. These incremental approaches consider all possible instances of preference model parameters consistent with the currently known information about the user; the user's responses allow to infer constraints on these parameters.

In this work, we consider the problem of incrementally eliciting the components of the RDU model by interactively asking queries to the DM; this aims to support the identification or approximation of an RDU-optimal choice. We first address the problem of eliciting the weighting function incrementally (Section 2) assuming that the utility is known. Afterwards, we will present utility elicitation procedures adapted to the rank-dependent utility model (Section 3). Finally, we provide numerical tests (Section 4).

ELICITATION OF THE PROBABILITY WEIGHTING FUNCTION

Decision makers exhibit various decision behaviors when they are confronted to choices involving risky prospects. Within RDU theory, this diversity of attitudes towards risk can be modeled by controlling the definition of the two components of the model, namely the utility function and the probability weighting function. Since these two components are strongly interlaced in RDU, their joint elicitation is quite challenging. Fortunately, these two components concern two separate and well identified risk-components, on the one hand marginal utilities induced by the shape of the cardinal utility function [Chateauneuf and Cohen, 1994], and on the other hand the probabilistic risk-attitude towards probabilistic mixtures induced by the shape of the probability weighting function [Wakker, 1994]. They can be observed separately using proper preference queries as shown in [Wakker andDeneffe, 1996, Abdellaoui, 2000]. In this section, the utility is assumed to be known (already elicited or known to be linear (Yaari's model), and we focus on the elicitation of probability weights.

ON PROBABILITY WEIGHTING FUNCTIONS

The probability weighting function is necessarily nondecreasing but can take different forms depending on the attitude of the DM towards risk. For instance, in Yaari's model, weak risk aversion which consists, for any lottery , in preferring E( ) for sure to (where and Cohen, 1994]. Moreover, in the RDU model, strong risk aversion which consists in preferring to whenever stochastically dominates at second order, is equivalent to using a convex weighting function and a concave utility [START_REF] Hong | [END_REF]. Finally, several experiments including those of [START_REF] Kahneman | [END_REF] lead to propose an inverse S-shaped function. For example, the use of the weighting function given in Figure 1 The following parametric expressions for w(p) have been proposed in the literature [START_REF] Cavagnaro | [END_REF], among several others:

E( ) is the expected value of ) is equivalent to w(p) ≤ p for all p ∈ [0, 1] [Chateauneuf
TK : w(p) = p r (p r +(1-p) r ) 1/r with 0.28 < r ≤ 1 Prelec : w(p) = e -s(-ln p) r with 0 < r ≤ 1; 0 < s LinLog : w(p) = s p r s p r +(1-p) r with 0 < r, s
where TK denotes the parametric form proposed by Tversky and Kahneman (the w plotted in Figure 1 is of this type, with r = 0.6). Note that Prelec and LinLog make use of two parameters (r and s) while TK is based on a single parameter. Karmarkar [1978] proposes a parametric form that is a special case of LinLog with s = 1.

Choosing a priori a specific parametric form among these different options and others, with the idea of learning the parameters, may generate errors due to not taking into account the specificity of the DM that may be revealed during the elicitation process. Instead, we propose a new approach based on a much more flexible parametric construction based on the definition of w as a piecewise polynomial spline function. Moreover, we will adopt an incremental elicitation approach in order to reason with the possible functions w that are consistent with the current preference information of the DM. In the spirit of incremental decision making, by considering additional preferences (obtained by asking queries), we will be able to progressively narrow down our model of the DM until we are able to identify the preferred alternative.

INCREMENTAL ELICITATION OF w

We assume here that the utility function is known and we reason with an incompletely specified weighting function w ∈ W , W being the set of admissible probability weighting functions at a given step of the process. Initially, W can be all non-decreasing functions on the unit interval such that w(0) = 0 and w(1) = 1 or an approximation of them representable by a given family of parametric functions. The utility function u being fixed, we will denote V ( ; w) the RDU value of lottery for weighting function w. Each time a preference statement of type " + is at least as good as -" is obtained, this induces a new constraint V ( + ; w) ≥ V ( -; w) that further restricts W .

In order to make a decision when probability weights are imprecisely known, we will use minimax regret which is a standard decision criterion for robust decision making under uncertainty [Savage, 1954]. It was more recently proposed by Boutilier et al. [2003Boutilier et al. [ , 2006] ] for decision-making under utility uncertainty. Moreover, minimax regret can be used as a driver for preference elicitation and incremental decision making.

Let L be the set of lotteries representing the alternatives of the decision problem. If we knew the DM's specific w, then the optimal choice would be any element of arg max ∈L V ( ; w). However, since w is not known precisely, we need to provide a recommendation based on the current information. We are interested in evaluating the loss that can result from choosing a decision instead of the optimal one. To this end, we use the following notions of regret. The pairwise maximum regret PMR of against is the maximal value that the difference V u ( ; w) -V u ( ; w) can take for any admissible function of w ∈ W . The max regret MR of a choice is defined as the maximum pairwise regret when the adversary is chosen among all lotteries in L. Finally, the minimax regret MMR is the minimum value of max regret. More formally:

PMR( , ; W ) = max w∈W [V ( ; w) -V ( ; w)] (1) MR( ; W ) = max ∈L PMR( , ; W ) (2) MMR(W ) = min ∈L MR( ; W ) (3)
Then we recommend one of the decisions associated with the minimum value of max regret, i.e. lottery * ∈ arg min ∈L MR( ; W ). This is a regret-optimal decision given the current preference information. By definition, recommending * means to be robust with respect to the possible realizations of w ∈ W .

In addition of being a criterion for decision-making, minimax regret can be used to drive the elicitation of further preference information. We assume an interactive setting where the system (a decision-support agent) can ask additional queries in order to improve the quality of the recommendation. If the current minimax regret value is higher than a given positive threshold, we ask another query to the user. Different types of queries can be asked to the user; among the many possibilities, comparison queries, asking the user to state which choice is best among two presented to him, are particularly natural. It is however important to ask informative queries in order to quickly converge to a recommendation of high value. An effective heuristic to choose the next query is the current solution strategy [Wang andBoutilier, 2003, Boutilier et al., 2006]; it asks the user to compare the regret-optimal lottery * with its adversarial challenger a = arg max ∈L PMR( * , ). This will often reduce minimax regret: if the user states that * is preferred to a , in the next computation of minimax regret, the adversary will have to choose another lottery, leading to a reduction of regret (unless there were ties in the max regret computations). If, instead a is preferred to * , the regret-optimal choice in the next computation will necessarily be a choice other than * , and, again, we will likely reduce regrets.

Assume P to be a set of pairs ( + , -) for which we know that the DM considers that + is at least as good as -.

Let W = {w : ∀( + , -) ∈ P, V ( + ; w) ≥ V ( -; w)}, our goal is to compute PMR( , , W ). This corresponds to solving the following optimization problem:

max w [V ( ; w) -V ( ; w)] (4) s.t. w(0) = 0, w(1) = 1 (5) w(p) ≤ w(q), ∀p, q ∈ [0, 1] : p ≤ q (6) V ( + ; w) ≥ V ( -; w), ∀( + , -) ∈ P (7)
Such optimization is not however directly feasible. First, the monotonicity constraint (6) on the unit interval represents implicitly an infinity of constraints. If we only impose monotonicity on probabilities involved in the lotteries of L, it still represents a large number of constraints. Moreover, constraint (7) is quite difficult to handle. Even if we assume that w belongs to one of the families of parametric curves considered in the previous subsection, the resulting constraints will not be linear in the parameters. In the next subsection we will see how these problems can be overcome by defining w as a monotone spline function.

A MODEL BASED ON I-SPLINE FUNCTIONS

Spline functions are piecewise polynomials whose pieces connect with a high degree of smoothness. They are very useful in data interpolation and shape approximation due to their capacity to approximate complex shapes through curve fitting and interactive curve design while preserving an important property, missing in many other interpolation methods: they guarantee that smooth curves will be generated from smooth data [Beatty and Barsky, 1995]. The use of piecewise polynomials in non-linear regression extends the advantage of polynomials by providing greater flexibility, local effects of parameter changes and the possibility of imposing constraints on estimated functions [Ramsay, 1988].

One important feature of spline functions is that they can be generated by linear combinations of basis spline functions.

A basis of splines particularly appealing for non-linear regression is the M-spline family [Ramsay, 1988]. M-splines of order k are functions M i , i = 1, . . . , m which are polynomials of degree k -1. They can be used to approximate any function defined on a given interval [a, b] by a spline of the form f = i λ i M i . To define M i precisely, we need to introduce a sequence of knots t = {t 1 , t 2 , . . . , t l } such that a = t 1 = . . . = t k , b = t l-k+1 = . . . = t l and ∀i, t i ≤ t i+1 . The basis constructed from sequence t contains m =| t | -k spline functions of order k denoted M i (x; k, t), i = 1, . . . , m, and defined for k = 1 by:

M i (x; 1, t) = 1 ti+1-ti if x ∈ (t i , t i+1 ) 0 otherwise
For k > 1 and t i+k > t i , M i is defined recursively by:

M i (x; k, t) = k[(x-ti)Mi(x;k-1,t)+(t i+k -x)Mi+1(x;k-1,t)] (k-1)(t i+k -ti)
and otherwise M i (x;k,t) = 0. In particular, we have M i (x;k,t) = 0 whenever k > 1 and t i+k = t i .

Note that M i (x;k,t) is strictly positive in (t i , t i+k ) and 0 elsewhere, with an integral equal to 1. Moreover, it is a polynomial of degree k -1 so that, for any piecewise polynomial function of the form f = i λ i M i , adjacent polynomials have matching derivatives up to order k -2. Hence, a good choice for k in practice is k = 3 because, in this case, we generate piecewise quadratic f functions with matching first derivatives while preserving a local influence of every components. Choosing a lower k would loose continuity of the first derivative and choosing a higher k would increase the range (t i , t i+k ) of influence of every component M i , which diminishes controllability of the model. As an example, the family of splines M i (x; 3,t), i = 1, . . . , 5 defined on the unit interval from subdivision t = (0, 0, 0, 1 3 ,2 3 , 1, 1, 1) is given in the left part of Figure 2. Finer spline decompositions could be obtained using finer subdivisions. Moreover, it is possible to use non-equally-spaced knot sequences to have a finer control of the shape in some parts of interval [a, b]. However, practical tests show that using too many nodes is counterproductive to generate smooth and regular curves.

We may define the probability weighting function w as a weighted combination of M i -spline functions with probably good fitting possibilities. However, this would not guarantee to obtain a non-decreasing weighting function w. To get rid of the monotonicity constraint (6), we need another basis specifically designed for the generation of non-decreasing spline functions. The solution is given by monotone regression splines that provide very nice descriptive possibilities, as demonstrated by Ramsey [1988]. Such spline functions are non-decreasing because they are generated by conical combinations of basis I-spline functions, i.e., non-decreasing functions defined as the integrals of the M-splines (which are positive). Formally, these functions denoted I i (x; k, t), i = 1, . . . , m are defined by:

I i (x; k, t) = x a M i (y; k, t) dy
Let j be the index such that t j ≤ x < t j+1 , the value of an I-spline is computed as follows:

I i (x; k, t) =          1 if i < j -k + 1 0 if i > j j s=i t s+k+1 -t s k + 1 M s (x; k + 1, t) otherwise
As an illustration, the family of splines I i (x; 3,t), i = 1, . . . , 5 for subdivision t = (0, 0, 0, 0, 1 3 , 2 3 , 1, 1, 1, 1) is given in the right part of Figure 2.

REGRET MINIMIZATION WITH I-SPLINES

The computation of PMR is the main building block to compute minimax regret. In order to compute MR and MMR, it is indeed sufficient to perform a quadratic number of PMR optimizations 2 . We now focus the discussion on PMR computations and show that the optimization of regrets is drastically simplified when weighting function w is defined by a conical combination of I i -splines:

w(p) = m j=1
λ j I j (p; k, t), λ j ≥ 0, j = 1, . . . , m (8) Note that, k and t being fixed, function w is completely characterized by vector λ = (λ 1 , . . . , λ m ) ∈ R m + . So the elicitation of the entire function boils down to the elicitation of vector λ. In that case the RDU criterion reads, for any lottery = (x 1 , p 1 ; . . . ; x n , p n ), as follows:

V ( ; λ) = n i=1 m j=1 λ j I j ( i k=1 p k ; k, t)[u(x i ) -u(x i+1 )]
By permuting the two first summations in the above formulation, we obtain V ( ; λ) = λ v( , k, t) where v( , k, t) ∈ R m is a vector whose j th component is equal to

n i=1 I j ( i k=1 p k ; k, t)[u(x i ) -u(x i+1 )].
Hence PMR values can be reformulated using vector λ and a set Λ of admissible weighting vectors replacing W . We obtain:

PMR( , ; Λ) = max λ∈Λ [V ( ; λ) -V ( ; λ)] = max λ∈Λ λ [v( , k, t) -v( , k, t)]
Moreover, the constraint V ( + ; w) ≥ V ( -; w) present in ( 7) takes now the form of a linear constraint λ [v( + , k, t) -v( -, k, t)] ≥ 0. Hence the set

Λ P = {λ ∈ R m + : ∀( + , -) ∈ P,λ [v( + , k, t) -v( -, k, t)] ≥ 0}
is a convex polyhedron. Therefore, under the assumption that I-spline functions are convenient to describe the probability weighting function, the computation of PMR for a given pair of lotteries ( , ), initially introduced as a difficult optimization problem, see Equations (4-7), can now easily be achieved by solving the following linear program:

max λ [v( , k, t) -v( , k, t)] s.t. λ [v( + , k, t) -v( -, k, t)] ≥ 0, ∀( + , -) ∈ P λ i ≥ 0, i = 1, . . . , m.

THE ELICITATION ALGORITHM

Algorithm 1 details the steps involved in our regret-based approach for the elicitation of w. Given a dataset of decisions (lotteries) L (for each decision we are given a specification of the numerical outcomes and their associated probabilities) and a set of initial preferences P (that could be empty), we compute the initial minimax regret value v, the max-regret-optimal decision * and the adversarial decision a . We then start asking queries.

Function Query simulates the question/answer protocol. It takes two lotteries as input and returns the preferred lottery among the two. After each user's response we recompute the minimax regret value, the regret-optimal decision * , and its challenger a . We loop until the regret drops below a positive threshold ε. Queries are asked according to the current solution strategy (analogue to the strategy used in [Boutilier et al., 2006]), that requires the user to compare * with a . The least preferred among * and a is removed from L as it is dominated by the other. This guarantees a strict reduction of |L| at every step, ensuring a linear convergence in the number of lotteries. The practical efficiency of this algorithm is illustrated in Section 4.

Note that when the lotteries in L involve a large number of branches, we cannot expect a DM to be able to compare them with confidence. In such cases, we recommend to work with two sets of lotteries: the actual set L of lotteries (in which the preferred solution must be found), on which pairwise regrets are computed, and a second set of simpler lotteries used only for preference queries. For the latter, we may use lotteries of type p = (M, p; 0, 1 -p) (where M is the top outcome) and ask the DM to compare p , for some probability p, to some certain consequence x in [0, M ]. Under the assumptions u(0) = 0 and u(M ) = 1, we derive from the response either w(p) ≥ u(x) or the reverse inequality, thus reducing uncertainty on function w and, in most cases, the MMR on actual lotteries.

UTILITY ELICITATION IN RDU

In the previous section, we have discussed the elicitation of the weighting probability function in the RDU model, assuming the utility function was known. We discuss now the elicitation of function u when w is not known. The main difficulty to overcome lies in the fact that functions u and w are strongly interlaced in the computation of RDU values, due to products of type w( i k=1 p i )u(x i ). A given value u(x i ) may impact differently on preferences, depending on the probability weighting function. Fortunately, there is a part of DM preferences that are not impacted by w and that can be used to elicit u. We present two illustrations of this idea in the two next subsections. The fist one provides a precise spline function interpolating a sample of points of the utility curve constructed with the gamble tradeoff method proposed by [START_REF] Wakker | [END_REF]. The second proposes an alternative approach based on simple queries aiming at obtaining the certainty equivalent of simple lotteries.

USING THE GAMBLE TRADEOFF METHOD

We first recall the principle of the gamble tradeoff method [START_REF] Wakker | [END_REF] to construct points on the utility curve. To start with an example, let us consider the two following lotteries:

= (c, p; b, 1 -p) and = (d, p; a, 1 -p) for a probability p ∈ (0, 1), where a, b, c, d are four distinct outcomes such that a < b < c < d. Then it can be easily checked from the definition of RDU that the DM is indifferent between and (i.e., V ( ) = V ( )) if and only if:

[u(b) -u(a)](1 -w(p)) = [u(d) -u(c)]w(p) (9)
To construct some points of the utility function u(x), x in [0, M ], we need two reference values α and β chosen in such a way that M < α < β. Then, the gamble tradeoff method consists in generating the increasing sequence defined by r 0 = 0 and r i = Query( i , i ) for i > 1 where:

i = (α, p; r, 1 -p) i = (β, p; r i-1 , 1 -p)
and Query( i , i ) is a function asking to the DM which value r makes the two lotteries indifferent and returns this value. The sequence is generated until r ≥ M . By construction we have V (r i , 1 -p; α, p) = V (r i-1 , 1 -p; β, p).

Similarly we have V (r i+1 , 1-p; α, p) = V (r i , 1-p; β, p).

From these two equalities, we obtain, from equation ( 9):

[u(r i ) -u(r i-1 )](1 -w(p)) = [u(β) -u(α)]w(p) [u(r i+1 ) -u(r i )](1 -w(p)) = [u(β) -u(α)]w(p) Hence u(r i+1 ) -u(r i ) = u(r i ) -u(r i-1
), therefore:

u(r i+1 ) = 2u(r i ) -u(r i-1 ) (10)
Since u is defined up to a positive affine transformation, we can set, without loss of generality, u(r 0 ) = 0 and u(r 1 ) = 1. Hence, using (10) we obtain u(r i ) = i for all i ≥ 0 which means that the utility function should interpolate points (r i , i). Moreover, the density of values r i within a given interval can be increased (resp. decreased) by changing parameters α and β to reduce or increase the difference β-α.

Assume that q points (r i , i) have been constructed with the gamble tradeoff method, these points can be interpolated using I-spline regression. So we define the utility function as a piecewise quadratic monotone spline u(x) = k λ k I k (x, 3, t) for a uniform knot sequence t. Then, coefficients λ k can be determined by minimizing the distance of the constructed points to the spline u. This is achieved by solving the following linear program Π:

min q i=1 e i s.t. e i ≥ i -k λ k I k (r i , 3, t), i = 1, . . . , q e i ≥ k λ k I k (r i , 3, t) -i i = 1, . . . , q λ k ≥ 0, k = 1, . . . , q.
This approach leads to a precise utility function; however, it is not incremental and does not provide an easy control on the number of points elicited on the utility curve.Moreover, preference queries involved in the process are somewhat more complex than in the certainty equivalent method. In the next subsection we present an incremental approach with simpler preference queries that gives control on which points are constructed.

USING THE CERTAINTY EQUIVALENT

An incremental utility elicitation procedure is proposed by Hines and Larsen [2010] with the aim of eliciting utilities while removing the effects of probability weighting from users answers. Using pairwise max regret minimization, they propose to elicit preferences in both cumulative prospect theory and expected utility theory by determining a specific probability value p * that allows to ask outcome queries where the effect of w cancels out. This idea could be used here but can be simplified in our context. Note that their definition of regret is based on the EU model and would not be the most appropriate to derive robust recommendations with respect to RDU. In order words they assume that EU is the right model to produce recommendations, but observe preferences biased by distorted probabilities as in cumulative prospect theory and RDU.

We propose here another incremental approach involving simpler preference queries based on the use of certainty equivalent. It consists first in identifying a probability p * such that w(p * ) = 1/2. To this end, we only need to construct the two first elements r 1 , r 2 following r 0 = 0 in the sequence defined in the previous subsection. Then we ask the DM for which probability p * she is indifferent between lottery = (r 2 , p * ; r 0 , 1 -p * ) and lottery = (r 1 , 1) yielding r 1 with certainty. Since by construction, u(r 0 ) = 0, u(r 1 ) = 1 and u(r 2 ) = 2, V ( ) = u(r 0 ) + w(p * )[u(r 2 ) -u(r 1 )] = 2w(p * ) and u( ) = 1. This leads to 2w(p * ) = 1 and therefore w(p * ) = 1/2. Now the utility curve can be incrementally constructed on any interval [0, M ] using simple indifference queries based on the following principle: let r -and r + be any two distinct values in [0, M ] such that u(r -) and u(r + ) are known (initially we choose r -= 0 and r + = M and we set u(0) = 0 and u(M ) = 1). Then a new point can be constructed between positions r -and r + by asking the DM for the certainty equivalent of lottery (r + , p * ; r -, 1 -p * ). If the answer is r (meaning that she is indifferent between the lottery and winning r for sure) we obtain u(r) = u(r -) + w(p * )(u(r + ) -u(r -)) = w(p * )u(r + ) + (1 -w(p * ))u(r -). Since w(p * ) = 1/2 we finally obtain u(r) = (u(r -) + u(r + ))/2. When u is defined as a monotone spline, the new point will induce new constraints further restricting the set of possible utilities.

Denoting (r i , u(r i )), i = 1, . . . , q the points already defined at iteration q, utility uncertainty within interval [r i , r i+1 ] is bounded above by δ i = u(r i+1 ) -u(r i ) due to monotonicity of u. The next query is selected to obtain a new point in the interval [r k , r k+1 ] which maximizes δ k ; we ask for the certainty equivalent of lottery (r k+1 , p * ; r k , 1 -p * ). The process can be iterated to refine progressively the intervals until the desired number of points is reached or the maximal δ i drops below a given threshold. Finally, a monotone regression spline is generated using the linear program Π introduced in subsection 3.1 to approximate the elicited points.

NUMERICAL TESTS

Incremental elicitation of w. In order to model function w, we used I-spline defined from the non-uniform knot sequence t = (0, 0, 0, 0, .1, 0.9, 1, 1, 1, 1). The use of knots at positions .1 and .9 instead of 1/3 and 2/3 induces a small left shift of I 1 (x, 3, t ) and a small right shift of I 5 (x, 3, t ) so as to include extremely concave or convex transformations in the family of splines that can be generated. This allows to model extremely risk-averse or risk-prone attitudes if necessary.

In the first series of experiments, we validate our choice of monotone splines for identifying the DM's probability weighting function w. Defining this function as w(x) = 5 j=1 λ j I j (x, 3, t ), we used a linear program similar to Π (see Subsection 3.1) to fit parameters λ j to different standard weighting functions, presenting various curves from extremely concave to extremely convex, including Sshaped and inverse S-shaped curves as well. The fitting possibilities of model w defined from I-splines are shown in Figure 3. In particular, we are able to approximate, with a single model, different kinds of distortion functions w (concave, convex, S-shaped) that usually require different parametric models (Prelec, TK, LinLog; see Section 2.1).

The instances where the approximation is good but not ideal are those with an extreme steepness (first instance, for very small value of p, and fourth instance, for very high values of p, in Figure 3). These situations (w extremely steep) will be rare in practice and correspond to shapes that could be even better described with a more specialized knot sequence. We conclude that the use of I-splines give us good approximations; splines allow us to learn w without committing to a specific parametric form.

In the second series of experiments, we observe the number of queries needed to determine the winning lotteries within sets of different sizes. The set L is constructed by repeatedly generating at most k outcomes in [0, 1000] and a probability distribution on these outcomes to build a new lottery (with k branches) at step i; this lottery i is inserted in L only if no stochastic dominance holds in { i } ∪ L. The process is continued until the desired number of lotteries is obtained. We made experiments with lotteries with k = 2, 3, 5, 10 branches and a simulated DM. For small sets of alternatives (typically 100 lotteries) the procedure solves the problem after very few questions. To test the scalability of the approach to larger sets we have generated instances including 1000 or 2000 lotteries. Interactions with the DM are simulated by generating answers to preferences queries using RDU with an inverse S-shaped probability weighting function w 0 , unknown from the elicitation procedure, and a linear utility function. For each set of lotteries we observed the reduction of the minimax regret (expressed in percentage of the initial max regret before asking any query) as the number of queries increases. For comparison, we also observed the regret reduction obtained with an heuristic that randomly selects the new pair of lotteries to be compared. The resulting curves are plotted in Figure 4, respectively in green and red. At the same time, we observed the reduction of real regrets defined as the difference V ( * 0 ; w 0 ) -V ( * ; w 0 ) where * 0 is the optimal lottery for the actual weighting function w 0 , and * is the solution minimizing the current max regret M R( ; W ). This third curve is plotted in blue in Figure 4. This experiment has been repeated multiple times on randomly generated instances and the results are very similar.

Considering the green and blue curves showing the diminution of max regret and real regret in Figure 4, it appears that the winner can be determined exactly among 1000 lotteries in about 10 queries (in worst case 15 preference queries). This considerably improves the results obtained with the random strategy. Similar tests have been performed for 2000 alternatives. The curves have similar shape and show that less than 10 additional queries are necessary. In fact, we could stop earlier, when minimax regret is very small (even if not exactly zero). The elicitation procedure can indeed be seen as an anytime algorithm. It can be interrupted before reaching a null regret, at any time of the process, and return the current minimax regret solution. We can also provide the associated max regret as a performance guarantee on the quality of the returned solution. Typically, as can be seen from the curves, stopping the elicitation when the minimax regret drops below a given percentage of the initial max regret (or below a given absolute threshold) will save a significant percentage of queries (at least 33% in our tests) without affecting significantly the quality of the recommendation. The efficiency of this approach is due to the fact that in most cases, the parameters of the decision model do not need to be precisely know to be able to determine a necessary winner, i.e., a lottery such that V ( ; w) ≥ V ( ; w) for all ∈ L and all w compatible with the available preference information.

Utility elicitation. We present now an example of construction of a monotone spline on the [0,1000] interval, to reveal and model the implicit utility function of a DM in RDU theory, from observed preferences involving lotteries with outcomes in this interval. The answers of the DM to preference queries have been simulated by a RDU model with an inverse S-shaped probability weighting function w(p) defined by the TK model introduced in Section 2 with parameter r = 0.5, and a concave utility defined by u(x) = 1 -(1 -x/1600) 4 . We successively use the two methods proposed in Section 3 to elicit points and generate the regression spline. We first use the gamble tradeoff method as described in 3.1 with α = 1050 and β = 1600 to obtain the sequence r 0 ,. . . ,r 6 . We compute by linear programming the parameters λ k of the monotone regression spline f that fits best points (r i , i) and define u(x) = f (x)/f (1000) to obtain u(1000) = 1. In Figure 5, points (r i , u(r i )) are represented by round points (in red), and we show the resulting utility function (in blue).

The construction of the monotone spline with the certainty equivalent method is also shown in Figure 5; the elicited points are represented by + (in green), numbered by order of generation, and the resulting utility function is so close to the previous one that they are indiscernible.

CONCLUSION AND PROSPECTIVES

In this paper we proposed an incremental approach for the elicitation of the RDU model. A first novelty concerns the use, within the RDU theory, of minimax regret in order to incrementally elicit the probability weighting function w and to produce robust recommendations with respect to the uncertainty in probability weights. A second novelty is the use of monotonic regression splines as a model of the probability weighting function, allowing the representation of a wide variety of decision behaviors and the optimization of pairwise max-regrets by linear programming. We also extend the proposed approach to cases where the utility u is also unknown. Our experiments show that, despite the expressivity of the model, the elicitation burden is reasonably low in practice, due to the fixed and limited number of parameters used in splines approximating u and w, and the active learning process implemented for w. There are at least two natural continuations of this work. The first one consists in extending the approach for cumulative prospect theory to model different risk attitudes towards gains and losses. The second would be to jointly learn functions u and w using an incremental approach based on regret minimization, with the aim to save more preference queries.

  in Yaari's model allows to explain the preferences observed on lotteries A, B, C, D presented in the introduction. We have indeed V (A) = 3000 w(1), V (B) = 4000 w(0.8), V (C) = 3000 w(0.25) and V (D) = 4000w(0.2). Since w(0.2) ≈ 0.26, w(0.25) ≈ 0.29, w(0.8) ≈ 0.60 and w(1) = 1 we obtain V (A) > V (B) while V (C) < V (D).

Figure 1 :

 1 Figure 1: Inverse S-shaped function w.

Figure 2 :

 2 Figure 2: Basis functions Mi(x; 3,t) and Ii(x; 3,t)

Figure 3 :

 3 Figure 3: Monotone approximations of w(p).

Figure 4 :

 4 Figure 4: Regret reduction, |L| = 1000, 100 runs.

Figure 5 :

 5 Figure 5: The spline approximating u(x)

  Algorithm 1: Regret-based elicitation of w Input: L, P, ε Output:

	v ← MMR(Λ P );
	while v > ε do
	p ← Query( * , A );
	L ← L \ the least preferred in { * , a };
	P ← P ∪ {p};
	v ← MMR(Λ P );

* begin * ← arg min ∈L MR( ; Λ P ); A ← arg max ∈L PMR( * , ; Λ P ); * ← arg min ∈L MR( ; Λ P ); A ← arg max ∈L PMR( * , ; Λ P ); end end

In fact, a more efficient strategy consists in implementing an alpha-beta search procedure, in this way it is possible to prune several cases and compute a much lower number of PMRs[Braziunas, 2011].

Acknowledgement

Work supported by the French National Research Agency through the Idex Sorbonne Universités, ELICIT project under grant ANR-11-IDEX-0004-02. We benefited from discussion with Angelina Vidali and Enrico Diecidue.