Vincent Nozick

Camera array image rectification and calibration for stereoscopic and autostereoscopic displays

Keywords: image rectification, stereoscopic displays, camera array, camera array calibration

This paper presents an image rectification method for an arbitrary number of views with aligned camera center. This paper also describes how to extend this method to easily perform a robust camera calibration. These two techniques can be used for stereoscopic rendering to enhance the perception comfort or for depth from stereo. In this paper, we first expose why epipolar geometry is not suited to solve this problem. Second, we propose a non linear method that includes all the images in the rectification process. Then, we detail how to extract the rectification parameters to provide a quasi-Euclidean camera calibration. Our method only requires point correspondences between the views and can handle images with different resolutions. The tests show that it is robust to noise and and to sparse point correspondences among the views.

Introduction

In recent years, stereoscopic technologies have been subject to an impressive growth and became incontrovertible in the movie maker industry. More recently, this technology has advanced from stereoscopic to autostereoscopic displays, involving more than two views and hence more than two cameras. The use of these multiview devices emphasizes technical issues in term of video stream synchronization, colorimetric correction, data compression, camera calibration or geometrical issues. This paper deals with the two last problems. More specif-ically, this paper presents an extension of an image rectification method [START_REF] Nozick | Multiple view image rectification[END_REF] to perform a camera calibration for an arbitrary number of views with aligned camera center. This technique can be used for stereoscopic rendering to enhance the perception comfort or for depth from stereo. In this paper, we first expose why epipolar geometry is not suited to solve this problem. We propose a non linear method that includes all the images in the rectification process. Our method only requires point correspondences between the views and can handle images with different resolutions. Then, we present a method to perform a quasi-Euclidean calibration of the cameras from the parameters computed during the rectification process. The tests show that the method is robust to noise and to sparse point correspondences among the views.

Stereo image rectification consists in the transformation of two images of the same scene such that for each pixel correspondence between the two views, the two pixels are aligned along the image horizontal axis. The main purpose of image rectification in computer vision is to optimize depth from stereo methods both in computational time and in robustness. A less known application concerns stereoscopic image visualization where the vertical parallax between any point correspondences should be minimized. The large majority of the proposed methods are dedicated to 2-views systems. In this paper, we present an image rectification method for more than two views, as depicted in Figure 1. Rectifying more than two views implies some constraints on the cameras' devices, especially the fact that the cameras' center should be aligned. Multiple view image rectification is essential for autostereoscopic camera setup and can have some applications for depth from stereo methods. A basic approach consists of pairwise image rectifications. In this paper, we propose an alternative method that ensures a computation providing a globally optimized solution using simultaneously all the views rather than pair by pair. Our method can handle images with different resolution, orientation and focal length. Then, we show how the computed orientation and focal length parameters are used to calibrate all the cameras.

Image Rectification

Image rectification methods have been known for long by photogrammetrists [START_REF] Slama | Manual of Photogrammetry[END_REF] and have been improved later by software approaches, like with Ayache and Hansen [START_REF] Ayache | Rectification of images for binocular and trinocular stereovision[END_REF]. Most of these early methods involved the camera to be calibrated, i.e. to know the camera projection matrices. Then, this constraint has been released with methods taking advantage of epipolar geometry to align the two images. The main issue of the image rectification process is that the rectified pair is not unique, as show in Figure 2. Most of existing methods deal with how to find an image rectification that minimizes the image distortion or that preserves some predefined image properties.

Robert et al. [START_REF] Robert | Applications of non-metric vision to some visually guided robotics tasks[END_REF] attempt to reduce the amount of distortion by finding the rectification transform that is closest to preserving orthogonality about the image centers. However, orthogonality is not an adequate criterion since even an Euclidean image rectification can involve a loss of orthogonality. Correcting this nonorthogonality might decrease the Euclidean property of the rectified images. Hartley [START_REF] Hartley | Theory and practice of projective rectification[END_REF] proposes a linear method to minimize the horizontal parallax among the point correspondences used for the rectification. Loop and Zhang [START_REF] Loop | Computing rectifying homographies for stereo vision[END_REF] decompose the rectification process into affine and projective components. Al-Zahrni et al. [START_REF] Al-Zahrani | Applications of a direct algorithm for the rectification of uncalibrated images[END_REF] propose a method that prevent the rectification process from a distortion on a selected common plane specified from 3 point correspondences on the two images. Gluckman et al. [START_REF] Gluckman | Rectifying transformations that minimize resampling effects[END_REF] propose a method to find the transformation that best preserves the sampling of the original stereo pair, i.e. each pixel in the unrectified im- age should map to a single pixel in the rectified image. Mallon and Whelan [START_REF] Mallon | Projective rectification from the fundamental matrix[END_REF] optimize each transformation in order to minimize perspective distortions, such that the rectified images look like the original images as closely as possible. Monasse et al. [START_REF] Monasse | Three-step image rectification[END_REF] perform an image rectification by three successive rotations. Isgrò and Trucco [START_REF] Isgrò | Projective rectification without epipolar geometry[END_REF] do not explicitly compute epipolar geometry but generate a rectifying pair of homographies that are conform to the fundamental matrix form of a rectified image pair. Finally, Pollefeys et al. [START_REF] Pollefeys | A simple and efficient rectification method for general motion[END_REF] propose a rectification method based on a reprojection onto a cylindrical surface instead of a plane in order to reach an optimal pixel distribution on the rectified images to avoid any pixel loss.

All these methods minimize an image distortion and thus are well suited for depth from stereo methods but not for stereoscopic rendering since the generated images are not consistent with a camera transformation that would result in a natural correction. In other words, there is no guarantee to obtain a pair of rectified images that corresponds or is close to an Euclidean camera setup. Moreover, most of these methods are based on epipolar geometry and hence cannot be directly extended to handle more than two views, as we will show in section 5.2.

3 Rectifying more than two views

Image rectification for stereoscopic rendering

In recent years, stereoscopic systems advanced from stereoscopic to autostereoscopic displays. These devices can provide more than two views simultaneously, usually around ten views, and the users do not need to wear any specific glasses. To provide a comfortable stereoscopic rendering, a stereoscopic image should avoid vertical parallax between correspondence points. This problem has been deeply studied (see Allison [START_REF] Allison | An analysis of the influence of vertical disparities arising in toed-in stereoscopic cameras[END_REF]) and can be corrected with an adequate image rectification if the cameras' center are aligned. This latter constraint makes possible to rectify an image with its right and left neighbors simultaneously. Finally, to reach orthostereoscopic rendering [START_REF] Lambooij | Visual discomfort in stereoscopic displays: a review[END_REF], i.e. the scene is perceived with its real geometric proportions, the image rectification should be Euclidean (i.e. metric). A quasi-Euclidean rectification where the respective camera focal lengths are coherent but only known up to a common scale factor, provides a quasi-orthostereoscopic rendering that is also acceptable.

Zhou and Li [START_REF] Zhou | Image rectification for stereoscopic visualization[END_REF] propose an image rectification dedicated to stereoscopic rendering based on epipolar geometry that provides good results, but is adapted only for two views. Fusiello and al. [START_REF] Fusiello | A compact algorithm for rectification of stereo pairs[END_REF] and later Fusiello et al. [START_REF] Fusiello | Quasi-euclidean uncalibrated epipolar rectification[END_REF] propose a non-linear method to rotate and zoom a pair of projective camera such that they fit to a pair of rectified camera, according to the epipolar constraints. This approach is specially well suited for stereoscopic rendering since this method provides quasi-Euclidean image rectification. However, this method is hardly to be extended to multiple images rectification since it is based on an implicit epipolar relation between the two cameras. Our method is mainly related to this approach, especially concerning the quasi-Euclidean rectification.

Rectifying more than two views

Ayache and Hansen [START_REF] Ayache | Rectification of images for binocular and trinocular stereovision[END_REF], Sun [START_REF] Sun | Uncalibrated three-view image rectification[END_REF] and also An et al. [START_REF] An | An efficient rectification method for trinocular stereovision[END_REF] present some methods to perform an image rectification over three views. They combine a horizontal image rectification between a central image and a left image, and a vertical image rectification between the central image and a bottom image. This approach is designed to extend depth from stereo methods to three views, however this technique cannot be used for three aligned cameras.

Kang et al. [START_REF] Kang | An efficient rectification algorithm for multi-view images in parallel camera array[END_REF] present an image rectification from multiple calibrated images. They adapt the images orientation and focal such that the cameras share a common image plane. Boutarel and Nozick [START_REF] Boutarel | Epipolar rectification for autostereoscopic camera setup[END_REF] present a GPU image rectification that can support multiple images. This method requires the camera to be calibrated and performs a projection on a common image plane, followed by a back projection on a set of ideal rectified cameras. This method can handle slight misalignment of the camera center if the common image plane is chosen carefully since it minimizes the error around this common projection plane. The main drawback of these latter methods is the need of calibrated cameras when all the other methods can deal only with point correspondences.

Camera array calibration

The camera calibration process for a camera array can be a laborious task. The cameras can be calibrated one by one, using a 3d pattern and the "gold standard algorithm" detailed in [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF].

A much easier way is to use a 2d pattern with the method presented by Zhang [START_REF] Zhang | A flexible new technique for camera calibration[END_REF], like in the reconfigurable camera array described in [START_REF] Zhang | A self-reconfigurable camera array[END_REF]. Lucchese [START_REF] Lucchese | Geometric calibration of digital cameras through multi-view rectification[END_REF] presents an extension of Zhang method designed for camera arrays. The main drawback of these methods is that an operator has to go on the scene to move the pattern such it is captured by all the cameras with various orientations.

A simpler method, based on point correspondences, consists in making a rough camera calibration and then perform a non-linear refinement. The estimated camera projection matrices are usually computed with the 5-points algorithm [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF][START_REF] Nistér | An efficient solution to the five-point relative pose problem[END_REF]. Then, the final camera calibration is performed with a bundle adjustment on all the data [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF][START_REF] Triggs | Bundle adjustment -a modern synthesis[END_REF]. If the process is successful, the camera calibration is accurate. The drawbacks of this method are first to require the cameras internal parameters to be known for the 5-points algorithm and second, to be very sensitive to the initial camera calibration. A moderately accurate initial calibration may lead to completely false result.

Notations

In this paper, we will follow the same notation as in [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. We indicate column vectors of P 2 in bold lower-case letters such as x = (x, y, w) ⊤ and column vectors of P 3 in bold upper case letters such as X. Row vectors are transposed column vectors, such as x ⊤ . The y coordinate of a vector is denoted by (•) y . Matrices are denoted by upper case letters, such as H. A set of points is denoted by an italic upper case letter like U and its cardinality by |U |.

Epipolar geometry and more than two views

Epipolar geometry [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF] is an usual support for stereo image rectification methods. Thus, it can also appear to be a good solution to rectify multiple images.

Epipolar geometry

The epipolar geometry describes the relations that exist between two images and can be described by the following equation:

x ′⊤ Fx = 0 where x and x ′ are homogeneous representation of corresponding points and the fundamental matrix F is the algebraic representation of epipolar geometry. An epipole is the projection in one view of the camera center of the other view. Numerically, the epipoles e and e ′ are the right and left null space of F and can be computed by solving the homogeneous equations:

Fe = 0 F ⊤ e ′ = 0 (1)

More than two views

Rectifying more than two views involves that the camera centers are aligned. Indeed, camera rectification process consists in the image transformation such that the rectified images share the same image plane. Moreover, the horizontal axis of the rectified images should be parallel to the camera baseline such the epipoles are matched to infinity in the horizontal direction. To satisfy this constraint for each view, the camera centers should be aligned. Figure 3 presents a example where the cameras are not aligned, background and forground can not be rectied simultaneously. If we consider more than two views where the camera centers are perfectly aligned, an extension of epipolar geometry is conceivable according to the fact that an image has a unique epipole whatever the other view. Indeed, if we consider N aligned cameras, the projection of the i th camera's center on the j th image is equivalent to the intersection of the line passing throw all the camera center and the j th image plane. Since this epipole e ij is constant ∀i ∈ {1 • • • N } i =j , then we note e ij = e j and the equation ( 1) leads to F ij e j = 0, where F ij is the fundamental matrix between the image i and j. This equation can be extended in a least square form:

     F 1j F 2j . . . F N j      e j = 0
Unfortunately, this approach is numerically unstable unless the cameras' center are perfectly aligned. Due to practical constraints, this condition is usually not perfectly satisfied. The alternative that consists of computing the average epipole between an image and all the others is also unstable since a misalignment of a camera center has strong consequences on the computed average epipole. Imagine the situation where an epipole is at infinity with one view and on a finite point with another. Computing the average position would have no meaning.

As a consequence, epipolar geometry appears to be incompatible with more than two views, neither by an overall process nor by pairwise computation.

Outline of our method

Image rectification process can be considered as a transformation on the images such that they share a common image plane. Let's consider a set of N cameras with projection matrix

P i = K i [R i | -R i c i ].
We want to find the corrected cameras

P ′ i = K ′ i [R ′ i | -R ′ i c ′ i ]
such that all the cameras' focal plane become coplanar. This transformation can be expressed by a rotation around the optical center and an update of the focal length. Without loss of generality, the camera coordinate system can be associated to the first corrected camera coordinate system. Hence, the projection matrices of the corrected cameras can be expressed as:

P ′ i = K ′ i [Id| -c ′ i ]
where the camera center are:

c ′ i =   x i 0 0  
During the image rectification process, we do not have to consider the cameras' position. Thus, the relation between the initial and the corrected projection matrix can be defined as an homography H i :

H i = P ′ i P -1 i = K ′ i Id i (K i R i ) -1 = K ′ i R -1 i K -1 i (2) Let R i = R -1
i be the rotation applied to P i to have the same the orientation as P ′ i . The equation ( 2) can be rewritten as follows:

H i = K ′ i R i K -1 i (3)
As depicted in Figure 4, the rectification problem becomes how to find R i and K ′ i such that H i rectifies the images. Given some point correspondences between each view, we want to find H i such that the transformed point correspondences are horizontally aligned.

Once the rotations matrices R i are retrieved, the only remaining information required to perform the camera calibration is the camera position. Assuming that the cameras are aligned, the camera order and position can be extracted from the point correspondences, as presented in section 9. The resulting camera calibration is quasi-Euclidean, meaning that the focal length are coherent among all cameras, but defined up to a common scale factor. This method is not related to epipolar geometry and hence can be extended for an arbitrary number of views. Moreover, it does not involve any prior knowledge about the cameras' projection matrices and requires only point correspondences between the views. Furthermore, contrary to epipolar geometry based methods, the minimal number of point correspondences is not 8 but 4 (i.e. the minimal point correspondence to define an homography). Finally, this method is well suited for stereoscopic rendering since the operations guaranty a quasi-Euclidean rectification.

Multiple view image rectification

Consider a set of point correspondences {x U k } where U k denotes the set of cameras involved by the k th correspondence and where ∀k, |U k | ≥ 2 (i.e. each correspondence relates at least two views).

Let K ′ i and R i the rectifying internal parameters and rotation for each camera, then the rectified point correspondences should be horizontally aligned:

(H i x k i ) y = y k , ∀i ∈ U k
where y k represents the vertical coordinate of the rectified point k on each view. In practice, the y k can be set as the average y-coordinate of the k th rectified points since the rectified point correspondences should have the same y-coordinate:

y k = i∈U k (H i x k i ) y |U k |
Hence, the homographies H i should satisfy:

(H i x k i ) y -y k = 0 (4)
We propose to find H i with a non-linear process where each K ′ i and R i are optimized to satisfy equation ( 4) by minimizing the residual error e over all rectified point correspondences:

e = k i∈U k |(H i x k i ) y -y k | |U k | (5)
The error computation of each correspondence k is normalized by |U k | since the correspondence points may not involve all the views. We perform a bundle adjustment on K ′ i and R i from each view using Levenberg-Marquartd method.

To simplify the computation process, we reduce the number of parameters of K ′ i by specifying a zero-skew, a unit aspect ratio and a principal point centered on the image. The only remaining parameter is the focal length. Hence, the cameras' internal parameter matrix is defined as follows:

K i =   f i 0 w i /2 0 f i h i /2 0 0 1   (6)
where w i and h i are respectively the width and height image resolution of the i th view. An usual initial value for the focal length

f i is f 0 i = w 2 i + h 2 i .
As suggested in [START_REF] Medioni | Emerging Topics in Computer Vision[END_REF] and [START_REF] Fusiello | Quasi-euclidean uncalibrated epipolar rectification[END_REF], it is numerically recommended to represent the focal length by a variable ranging in [-1, 1] using zero as an initial value for the non-linear computation. It is common to expect f to have a value roughly ranging in [f

0 i /3, f 0 i × 3], thus f i is represented by a value α i = log 3 (f i /f 0 i ).
Hence, starting the nonlinear process with the default focal length induces an initial value of α i set to zero. Then, during the nonlinear process, the current focal length is computed by:

f i = f 0 i 3 αi
Each rotation matrix R i is defined by three Euler angles θ x i , θ y i and

θ z i such that R i = R θ z i R θ y i R θ x i .
For each view, the unknowns are the focal length represented by α i and the three Euler angles θ x i , θ y i and θ z i which make a total of four unknowns per camera.

All the variables (θ x i , θ y i , θ z i , α i ) are set to zero at the beginning of the procedure, meaning no orientation change on the cameras and the default focal length. To avoid a free rotation of all the images around the cameras' base-line, we select a reference camera and force its angle θ x r to be zero during the minimization process. We also let the focal length f r of this camera constant for the same reasons.

As specified in equation ( 5), the point correspondences do not have to cover all the views. The only constraint is that each view should be directly or indirectly linked to all the others. Finally, our method can handle multiple view image rectification but is also very well suited for a two images rectification.

Different image resolution

In our method presented in section 7, we consider that all the input images have the same resolution. If it is not the case, the method should be adapted to overcome some computational errors. More specifically, a change in the focal length may lead to a misalignment for two images with different resolutions if the origin of the pixel coordinates is not centered. Indeed, the focal length variations provide centered transformations, but the image coordinates are not subject to this scale, as described in equation (3). Figure 5 shows that even with an adequate update of the focal length, the images are not aligned. This misalignment may lead to a rotation along the image baseline that will distort the image and degrade the image rectification. This problem does not occur if the pixel coordinates are centered, as depicted in Figure 6.

Therefore, our method should be modified such that the data is centered. Let H c i be the homography that centers the pixels of the i st image, defined as:

H c i =   1 0 -w i /2 0 1 -h i /2 0 0 1   (7)
Equation ( 3) becomes:

H i = H c-1 out K ′ i R i K -1 i H c i (8)
Where the matrix H c out is a centering homography corresponding to the output image format that specifies a common pixel coordinates origin for all the images. In practice, H c out can be the centering homography of the smallest image. Moreover, the intrinsic parameters matrices should not include the origin of the image, since the data is already centered. These matrices become:

K i =   f i 0 0 0 f i 0 0 0 1  
Finally, the non-linear process can find the best parameters to rectify the images. It is not required for the input views to have neither the same image resolution nor the same focal length. The bundle adjustment process is summarized by the minimization function described in Algorithm 1. If all the input images have the same resolution, Algorithm 1 can be simplified by replacing the equation of line 3 with equation (6) and the line 7 with equation (3). However using Algorithm 1 provides very good results whatever the image resolution and does not alter the numerical performance even if the images have the same resolution.

f i = 3 α i K i (0, 0) 3 K ′ i = diag(f i , f i , 1) 4 R i = eulerAngles(θ x i , θ y i , θ z i ) 5 end
compute the homographies

6 foreach camera i do 7 H i = H c-1 out K ′ i R i K -1 i H c i 8 end
compute the average vertical coordinates In practical situations, it is usual to have a setup where the cameras are not identified, meaning that the order of the cameras is unknown. This is typically the case with usb cameras where the camera identifier depends on the usb port detection order. The geometrical camera order can be retrieved using point correspondences between the images.

Camera coordinate system

Assuming that the cameras are rectified with Algorithm 1, the camera position can be computed from the corresponding points. Indeed, if we consider the point correspondences in the rectified camera coordinate system, the point correspondences disparity between views is proportional to the horizontal position of the camera. Note that this assertion is true only in the case of rectified camera.

Algorithm 2: ordering the images input : a set of k point correspondences {F i } (possibly incomplete) between n images. output: an ordering array a Since the rectified images have the same resolution, the common image system coordinate can be defined by any image point. A direct solution is to select the top left corner of the image, with coordinates (0, 0) ⊤ . Another easy solution is to choose the corrected principal point of the rectified images defined by the parameters (w i /2, h i /2) ⊤ used on the centering homography H c out presented in Equation (7).

1 a = 0n 2 foreach image I i do 3 foreach image I j>i do 4 left = 0 5 right = 0 6 foreach correspondence F k do 7 if F k (i) and F k (j) exists then 8 d = F k (i) -F k (j)

Ordering the cameras

As mention above, the rectification process involves that the disparity (in x-axis) of the point correspondences between views is proportional to the horizontal position of the camera. The method we propose consists in counting for each pair of image {I i , I j } i =j the number of point correspondences where the disparity from I i to I j is positive and respectively negative. These numbers will lead to a geometrical ordering of the two images. Extending the process to all pair of images will sort all the images. This method is described in Algorithm 2, where an element a i indicates the index of the i st camera.

Finally, in the case of aligned cameras with a nonuniform repartition, i.e. all the camera are not equidistant to their left and right neighbors, it is possible to extract the x-position of each camera from the disparity of the point correspondences. Indeed, equidistant cameras would involve a constant disparity between two pairs of consecutive cameras for a selected correspondence.

The computation of the camera x-position starts with the definition of a unit metric. It is standard to define the distance between the first and second camera as δx 0,1 = 1. Then, the distance δx 0,i between the first camera and the i st camera is computed from the average of the disparity ratio among all correspondences k:

δx 0,i = average d k (0, i) d k (0, 1) k or recursively with:      δx 0,1 = 1 δx 0,i+1 = δx 0,i + δx i-1,i .average d k (i, i + 1) d k (i -1, i) k
Thus, each camera center can be estimated with:

c i = (δx 0,i , 0, 0) ⊤ (9)

Point correspondence null space

We propose another approach to sort and find the position of the cameras using a Singular Value Decomposition (SVD). This approach is quite elegant but unfortunately not robust to false positive or missing point correspondences. Given a matrix of disparities between an arbitrary reference view and the other images, the centered and normalized disparities form a principal axis that can be extracted from a Principal Component Analysis or a SVD. This method is summarized on algorithm 3. The resulting vector a represents the sorted indexes of the cameras.

10 Cameras calibration

Rectified camera calibration

The rectified camera have the form:

P ′ i = Ki [Id| -c i ]
where the camera position c i is defined by Equation ( 9):

c i =   δx 0,i 0 0  
The internal parameter matrix Ki does not corresponds exactly to the matrix K ′ i . Indeed, at the beginning of the minimization process, it is assumed that all the input cameras have a default focal length. For example, if all cameras have the same image resolution, they will have an identical default internal parameter matrix, when in Algorithm 3: ordering the images with a SVD input : a set of k point correspondences {F i } (possibly incomplete) between n images. output: an ordering array a compute the disparity matrix

1 A = 0 kn 2 foreach correspondence F k do 3 foreach image I i do 4 A ki = F k (i) -F k (0)
a i = (n -1) × a i -am a M -am 16 end
17 return a reality, their focal length may differ. The rectification process will find a scale on this internal parameter such the corrected images share a common image plane parallel to the camera baseline. Hence this process involves that the rectified camera have actually the same focal length and internal parameter matrix K. More precisely, the focal length scale factor computed during the minimization process is related to the initial camera parameter but not to the corrected one. Figure 4 describes this process. Thus, the internal parameters of the rectified camera has the following form:

K =   f r 0 w out /2 0 f r h out /2 0 0 1  
where f r is the focal length of the reference camera and (w i , h i ) defined by Equation ( 7) and the output image format.

The resulting camera calibration is called quasi Euclidean, in opposition to Euclidean (metric) or perspective calibration. Quasi-Euclidean calibration means that the focal length f r of the cameras is defined up to a scale factor common for all the cameras. In our case, finding an adequate focal length f r makes the calibration Euclidean for all the cameras, providing metric reconstruction (for computer vision applications) or an orthostereoscopic rendering (for stereoscopic applications). Choosing a "standard" focal length will provide quite correct 3d reconstructions or stereoscopic rendering. This is absolutely not the case of a perspective reconstruction where the results have nearly no chance to be acceptable.

Initial camera calibration

According to section 6, the initial estimation of the original camera projection matrices are given by:

P i = K i [R i | -R i c i ] with R -1 i = R i
and where c i = (δx 0,i , 0, 0) ⊤ is the same camera center computed for P ′ i in Equation ( 9).

As specified in section 10.1, the initial value for the focal length f 0 i is a default value that is scaled during the minimization process, to converge to a final value fi . This process looks like how to transform similar focal lengths to find the corrected ones when in reality it is how to transform different focal lengths to make them identical. Hence, the initial camera focal length f i can be found with the inverse transformation, that is:

f i = f 0 i × f 0 i fi
So finally:

K i =   f i 0 w i /2 0 f i h i /2 0 0 1   and P i = K i R -1 i | -R -1 i c i (10)
Again, the calibration is quasi-Euclidean.

The resulting internal parameters have the principal point centred in the image. In practice, this approximation is acceptable for a large part of the camera systems. However, if more accuracy is required, this constraint can be relaxed using a bundle adjustment.

Results

We implemented our method in C++ using Eigen mathematic library [START_REF] Guennebaud | Eigen v[END_REF] and our implementation of Levenberg-Marquardt method implemented from [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF].

Input data

We tested out method on synthetic data and also on real data where the point correspondences were selected manually. Point correspondences detection is not the topic of this paper, there exist various automatic methods to find such correspondences that usually first find interest points [START_REF] Lowe | Distinctive image features from scaleinvariant keypoints[END_REF][START_REF] Bay | Speededup robust features (surf)[END_REF], then match them from an image to the other and finally detect outlilers [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF]. For multiple images, there exists dedicated methods like Avidan et al. [START_REF] Avidan | Centralized and distributed multi-view correspondence[END_REF] or Shafique and Shah [START_REF] Shafique | A non-iterative greedy algorithm for multi-frame point correspondence[END_REF], that can find robust point correspondences among several images.

The input images may also require a radial distortion correction. Indeed, radial distortion affects each part of the image differently and generates vertical disparity only in some parts of the image, leading to a less accurate image rectification. As all image rectification methods mentioned in this paper, we consider that the radial distortion has already been corrected on the input images as a preprocessing step. The radial distortion can be corrected using point correspondences with the method presented by Stein [START_REF] Stein | Lens distortion calibration using point correspondences[END_REF] or using the plumb line constraint with a non linear approach like with Devernay and Faugeras [START_REF] Devernay | Straight lines have to be straight[END_REF] or with a linear method as presented by Strand [START_REF] Strand | Correcting radial distortion by circle fitting[END_REF].

Finally, the tests of image rectification with more than two views are performed on images with camera centers aligned. A strong misalignment of the camera centers would lead to a rectification that may include strong vertical disparity between some corresponding pixels. Moreover, if the point correspondences are selected such they correspond to the same depth in the scene, the rectification process will succeed for this specific part part of the scene and may fail for the rest of the image, as shown in Figure 3 where the point correspondences where selected on the background of the scene. A misalignment of the cameras becomes a problem when the distance between a camera and the common camera baseline is not negligible compared to the distance between the cameras and the nearest objects of the scene. In any case, our method will minimize the global vertical disparity and rectify the images as much as it is possible.

Rectification tests for two views

We first tested our method on image pairs in order to compare our results with some state of the art methods, namely Hartley [START_REF] Hartley | Theory and practice of projective rectification[END_REF] since it is one of the most popular image rectification method and with Fusiello et al. [START_REF] Fusiello | Quasi-euclidean uncalibrated epipolar rectification[END_REF] since this method is known to be one of the most effective in term of image preservation. Indeed, as presented in Section 2, most of the existing image rectification methods directly minimize the image distortion but are not consistent with a camera transformation. These methods are usually linear and thus fast, but the image distortion constraints may involve some stereoscopic visual artifacts that does not appear with non-linear methods consistent with the pinhole camera model.

The tests were performed on our implementation of [START_REF] Hartley | Theory and practice of projective rectification[END_REF] and on the author implementation of [START_REF] Fusiello | Quasi-euclidean uncalibrated epipolar rectification[END_REF]. We selected some point correspondences manually and then computed the per-pixel error after rectification. The results are presented in Table 1. Our method performs every time better that [START_REF] Hartley | Theory and practice of projective rectification[END_REF] and is approximatively equivalent to [START_REF] Fusiello | Quasi-euclidean uncalibrated epipolar rectification[END_REF], i.e. sometimes a bit better and sometimes a bit worse. Figure 8 depicts some results with both better and worse vertical disparity minimization compared to [START_REF] Fusiello | Quasi-euclidean uncalibrated epipolar rectification[END_REF]. Finally, our method can compute an image rectification with at least 4 point correspondences where all the other methods require at least 8 point correspondences to compute a fundamental matrix. Figure 7 shows a result of our method with 4 point correspondences. In this kind of scene with smoke or fire, it is complicated to find more point correspondences.

Fig. 8 Left: Carcassonne images. Right: birthday cake. From top to bottom: input images, Hartley's method [START_REF] Hartley | Theory and practice of projective rectification[END_REF], Fusiello et al. [START_REF] Fusiello | Quasi-euclidean uncalibrated epipolar rectification[END_REF] and our method.

Rectification tests for more than two views

We first tested our method on synthetic data consisting in a set of aligned projective cameras with controlled focal length, image resolution and orientation. A bunch of 3D random points are projected on each camera to get point correspondences. We performed this procedure on five (800×600) virtual cameras and 50 point correspondences with various camera settings: where "different" means a 10% variation between each view on the concerned parameter. In this situation, even if we have the ground truth camera calibration parameters, there is no quantitative measure of the distortion that reflects the quality of the image rectification. Therefore we compute the average of the y-axis disparity between the average y k and the rectified points among each correspondence k. The procedure is repeated with an isotropic Gaussian noise on the correspondence points with various amplitudes. These results are summarized in Table 2 and show that the proposed method is robust to Gaussian noise. The tests also show that the method is a bit more efficient to correct orientation than focal length. The second part of our tests concerns the point correspondences density. We removed some point correspondences from the full data set such that some correspondences do not relate all the views. The results are presented in Table 3 and clearly show that our method still provides very good results, even when a large part of the point correspondences are missing. Next, we tested our method on real data where we selected the point correspondences manually. Figure 9 shows a set of images that could be encountered for a stereoscopic setup, i.e. with only few correction to do to get rectified images. Figure 10 presents a set of images with converging optical axis. A zoom of the vertical disparity of the corrected images is shown in Figure 12. Finally, Figure 11 depicts a sample with strong orientation differences between the input images. The results shows that our method performs very well even with initial views far from their rectified form.

These tests show that our method succeed to perform a quasi-Euclidean image rectification and hence can be exploited for a quasi-orthostereoscopic rendering. The computation of the matrices H i should be performed only once at the beginning of the video acquisition process and the video stream rectification can be computed on-line on the GPU as shown in [START_REF] Boutarel | Epipolar rectification for autostereoscopic camera setup[END_REF].

Cameras ordering tests

The image ordering method summarized on Algorithm 2 has been tested on synthetic data. The tests focus on point correspondence accuracy effects and on missing data robustness. We first generated a set of rectified image point correspondences where the x-coordinates were subject to a Gaussian noise. Our program generated 50 point correspondences among height 400 pixels wide images. Then, the images were randomly shuffled. We automatically launched a test loop and counted the number successful retrieval of the original order. As shown in Table 4, our method is robust to point corre- spondence inaccuracy. Indeed, the method is still robust to a noise of 10% of the image width (i.e. ±40 pixels) when a standard noise is usually expected to be 1% of the image width. Then, we tested the robustness of the ordering method (Algorithm 2) against missing point correspondences between views. Our program generated 50 point correspondences among 8 views. The images were randomly shuffled and some randomly selected points are removed. We automatically launched a test loop and counted the number successful retrieval of the original order. As show in Table 5, our method is very robust to missing point correspondences. The method is still robust with 50% of the data missing.

Calibration tests

We tested our camera calibration method on real data. We present two sets of images and their respective camera representations. The first data set consists in 8 converging images shown in Figure 1. The corresponding camera reconstruction is presented in Figure 14. A simpler form of the same data set is presented in Figure 10 where only four of the eight images appear. Its corresponding camera reconstruction is shown on Figure 13. Finally, we present a data set with four nearly parallel cameras and the associated camera reconstructions depicted in Figure 15. Moreover, we tested the calibration accuracy by measuring the reprojection error of 3D triangulated points from point correspondences. We also applied a bundle adjustment on our calibrated data to measure the reprojection error difference with an optimal calibration setup. Again, we used Levenberg-Marquardt method described in [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF] to implement our bundle adjustment. Our test first sorts the cameras and estimates the camera position with Algorithm 2. Then, the cameras are calibrated with Algorithm 1 and Equation [START_REF] Fusiello | Quasi-euclidean uncalibrated epipolar rectification[END_REF]. We perform a linear triangulation on the initial point correspondences to measure the reprojection error obtained with our method. Then, we apply a bundle adjustment on the data to measure how far is our method from an optimal solution. Finally, we directly apply a bundle adjustment from the ordered camera, without our calibration method, ı.e. with a good approximation of the camera position, but with camera principal ray parallel and default internal parameters. Table 6 presents the results of the test for two data sets. The results show that the proposed method is a good first estimation of the camera projection matrix. Moreover, our method is also a good initial solution for a bundle adjustment usually very sensitive to initial conditions. Table 6 shows that the default aligned camera projection matrices are not suited to be used directly for a bundle adjustment. Indeed, the bundle adjustment does not converge on the data set of

Conclusion

This paper presents an image rectification and calibration method that can handle more than two views. Our method does not involve any prior knowledge about the camera projection matrices and requires only point correspondences between the views. Moreover, the point correspondences between the views do not have to concern all the images simultaneously. Finally, the method supports input images with different image resolutions. This method is well suited to remove vertical parallax for stereoscopic rendering without any damage on the perspective perception since the operations performed during the rectification process guaranty a quasi-Euclidean rectification. To our knowledge, this is the only method that provides quasi-orthostereoscopic images without full camera calibration. The camera sorting and calibration process is a crucial tool for many stereoscopic applications.

Our method has been validated by several tests concerning both the robustness with inaccurate point correspondence and sparse point correspondences over all views.

Fig. 1

 1 Fig. 1 Multiple image rectification : (Up) height input images. (Down) the height rectified images.

Fig. 2

 2 Fig. 2 Image rectification solution is not unique. First row: two images to rectify. Second row: a possible image rectification. Third row: an horizontal scale preserves the rectificatio properties. Fourth row: a skew also preserves the rectificatio properties.

Fig. 3

 3 Fig. 3 Three unaligned cameras. The left and rigth images are rectified together. The middle image's background is also rectified with these two images. Scaling the middle image would align the foreground but misalign the background (see the lights around the head).

Fig. 4

 4 Fig. 4 Image rectification for each camera consists at most in a rotation and a change of focal length.

Fig. 5 Fig. 6

 56 Fig. 5 (a) Input images with different resolution. (b)The minimization process will include a centered variation of the focal length of the second image, i.e. a scale of the bigger image performed in the principal point coordinate system. The scale coeficeint is adequate but the fact that it is not performed on the image coordinate system generates a misalignment. (c) This misalignment can be reduced by a combining a rotation around the camera baseline. However, this image rectification is far from optimal.

Algorithm 1 :

 1 minimization function input : a set of candidates {(θ x i , θ y i , θ z i , α i )} a set of constant {(K i , H c i )} and {x U k } output: a set of H i and the alignment error get back the data 1 foreach camera i do 2

9 foreach correspondence x k U do 10 y k = 0 11 foreach i ∈ U k do 12 y 14 y 18 error = 0 19 foreach i ∈ U k do 20 error

 10111214181920 k + = (H i x k i )y 13 end k = y k /|U k | 15 end compute the global error 16 errorTotal = 0 17 foreach correspondence x k U do + = |(H i x k i )y -y k | 21 end 22 errorTotal + = error/|U k | 23 end 24 return errorTotal and {H i } 9 Cameras identification

7

  foreach correspondence F k do 8 center and normalize the set {A ki } i=0...n-1 9 end compute the right null space of A 10 UDV ⊤ = SVD(A) 11 a = last column of V normalize the data 12 am = min(a) 13 a M = max(a) 14 foreach image i do 15

Fig. 7

 7 Fig. 7 Image rectification with only 4 point correspondences.In this kind of scene with smoke or fire, it is complicated to find more point correspondences.

Fig. 12

 12 Fig. 12 Zoom of Figure 10. Vertical disparity of some point correspondences before and after image rectification (top of the black tea packet, top and bottom frame corners of the wooden box).

Fig. 9

 9 Fig. 9 Multiple image rectification : (Up) six input images. (Down) the six rectified images.

Fig. 10

 10 Fig. 10 Multiple image rectification : (Up) four input images. (Down) the four rectified images.

Fig. 11

 11 Fig. 11 Multiple image rectification : (Up) four input images. (Down) the four rectified images.

Fig. 13

 13 Fig. 13 Camera calibration of the set of images of Figure 10.

Fig. 14

 14 Fig. 14 Camera calibration of the set of images of Figure 1.

Fig. 15

 15 Fig. 15 Multiple image rectification: parallel setup. (Up) four input images. (Middle) the four rectified images, (Down) the calibrated cameras.

  Fig 11 and does not provide the optimal solution on data set from Fig 10 since one of the camera did not perfectly converge.

Table 1

 1 Average disparity in pixel computed on images pairs using different methods.

	Image pair	Hartley [14] Fusiello [10] our method
	Birthday Cake	0.643632	0.629794	0.597752
	Cluny church	0.434034	0.329592	0.324025
	Carcassonne	0.648803	0.548186	0.584983
	Beijing lion	1.19991	0.428227	0.577816

Table 2

 2 Average disparity (in pixel) on the y-axis between 50 point correspondences with five (800×600) images applied on various data sets defined in section 11.3. The data is corrupted by an isotropic Gaussian noise with standard deviation σ = 0.4 under various amplitudes.

	data set zero-noise Gaussian noise Gaussian noise
			ampl.: 2 pixels	ampl.: 5 pixels
	1	0.00	0.54	1.36
	2	0.06	0.55	1.36
	3	0.13	0.57	1.33
	4	0.11	0.56	1.37

Table 3

 3 Average disparity (in pixel) with sparse point correspondences on the y-axis. The tests are performed with different correspondences density by randomly removing some correspondences. The full data contains 50 point correspondences relating the five (800×600) images. These tests are applied on various data sets defined in section 11.3.

	data set full data 90% data 60% data 40% data
	1	0.00	0.00	0.00	0.00
	2	0.06	0.11	1.01	2.00
	3	0.13	0.07	0.07	0.07
	4	0.11	0.04	0.06	1.16

Table 4

 4 Robustness of the ordering method (Algorithm 2) against noise on the point correspondence x-position.

	Gaussian noise	success rate
	zero-noise	100%
	σ = 10% image width	100%
	σ = 25% image width	64%

Table 5

 5 Robustness of the ordering method (Algorithm 2) against missing point correspondence between views.

	missing data success rate
	50%	100%
	70%	98%
	90%	82%

Table 6

 6 Average reprojection error per point correspondences. The tests concern the two data sets from Fig 10 (1000 × 664) and Fig 11 (900 × 600).In any case, the camera's center are estimated with Algorithm 2. The average reprojection error is computed on data computed with our method, with our method followed by a Bundle Adjustment (BA), or directly with a Bundle Adjustment on the sorted cameras.

		→ sort	→ sort	→ sort
	data set → our method → our method
			→ BA	→ BA
	Fig 10	15 pixels	0.6 pixels	4.1 pixels
	Fig 11	45 pixels	3 pixels	no conv.

Gaspard Monge Institute, UMR 8049 Paris-Est Marne-la-Vallee University, France E-mail: vincent.nozick@univ-mlv.fr


Pierre Coucheney

Patrick Maillé

Bruno Tuffin

Impact of Competition Between ISPs on the Net Neutrality Debate

Keywords: Network neutrality, Game theory, Pricing

Network neutrality is the topic of a vivid and very sensitive debate, in both the telecommunication and political worlds, because of its potential impact in everyday life. That debate has been raised by Internet Service Providers (ISPs), complaining that content providers (CPs) congest the network with insufficient monetary compensation, and threatening to impose side payments to CPs in order to support their infrastructure costs. While there have been many studies discussing the advantages and drawbacks of neutrality, there is no game-theoretical work dealing with the observable situation of competitive ISPs in front of a (quasi-)monopolistic CP. Though, this is a typical situation that is condemned by ISPs, and, according to them, another reason of the non-neutrality need.

We develop and analyze here a model describing the relations between two competitive ISPs and a single CP, played as a threelevel game corresponding to three different time scales. At the largest time scale, side payments (if any) are determined. At a smaller time scale, ISPs decide their (flat-rate) subscription fee (toward users), then the CP chooses the (flat-rate) price to charge users. Users finally select their ISP (if any) using a price-based discrete choice model, and decide whether to also subscribe to the CP service. The game is analyzed by backward induction. As a conclusion, we obtain among other things that non-neutrality may be beneficial to the CP, and not necessarily to ISPs, unless the side payments are decided by ISPs.

I. INTRODUCTION

There has recently been a strong debate around the socalled network neutrality. The debate has been ignited by the increasing traffic asymmetry between Internet Service Providers (ISPs), mainly due to some prominent and resource consuming content providers (CPs) which are usually connected to a single ISP. The typical example is YouTube (owned by Google), accessed by all users while hosted by a single Tier 1 ISP, and whose traffic now constitutes a non-negligible part of the whole Internet traffic. Another example is the subscription-based video service Netflix, that is in the US the most bandwidth-consuming source of traffic, representing 23.3% of the total Internet traffic in late 2011 [START_REF] Sandvine | Global Internet phenomena report: Fall 2011[END_REF], while having commercial relationships with only one ISP. For those reasons, there has been a surge of protest among ISPs, complaining that the current Internet business model where ISPs charge both end-users and content providers directly connected to them, and have public peering or transit agreements with other ISPs, is not relevant anymore. The main solution proposed is that ISPs should also charge content providers that are associated with other ISPs [START_REF] Lenard | Net Neutrality or Net Neutering: Should Broadband Internet Services be Regulated[END_REF], as first advocated by Ed Whitacre (CEO of AT&T) at the end of 2005 [START_REF] Odlyzko | Network neutrality, search neutrality, and the never-ending conflict between efficiency and fairness in markets[END_REF].

The underlying concern is that investment is made by ISPs but content providers get an important part of the dividends. The revenue arising from on-line advertising (meaning showing graphical ads on regular web pages) is estimated at approximately a $24 billion in 2009 [START_REF] Ghosh | Expressive auctions for externalities in online advertising[END_REF], while textual ads on search pages has led to a combined revenue of $8.5 billion in 2007 [START_REF] Liu | Competing keyword auctions[END_REF], those figures increasing every year. Meanwhile, transit prices -which constitute the main source of revenues for transit ISPs -are decreasing. ISPs argue that there is no sufficient incentive for them to continue to invest on the network infrastructures if most benefits go to content providers. The threat is to lower the quality of service of CPs that do not pay any fee to them, or even to block their traffic. This possibility has led to protests from CPs and user associations, complaining that this might impact the network development and is an impingement of freedom of speech [START_REF] Odlyzko | Network neutrality, search neutrality, and the never-ending conflict between efficiency and fairness in markets[END_REF]. The debate was thus launched, essentially at the law and policy makers level, to decide whether the Internet should be neutral, i.e., all packets should receive equal treatments in terms of price and service. In the US, the Federal Trade Commission (FTC) released in 2007 a report not supporting neutrality constraints, increasing the debate at the political level. This debate is also active in Europe and in France, as illustrated by the open consultation on network neutrality launched in 2010. For instance, the French regulation authority, ARCEP, has published in its response a proposal intending to define how net neutrality could be implemented [START_REF] Arcep | Neutralité de l'internet et des réseaux : propositions et orientations[END_REF], [START_REF] Wong | Public consultations on Net Neutrality 2010: USA, EU and France[END_REF].

There has been an increasing attention in the literature on providing a mathematical analysis of the advantages and drawbacks of network neutrality. The idea is to investigate the output of the interactions between selfish actors that are end users, CPs and ISPs, using the framework of non-cooperative game theory [START_REF] Fudenberg | Game Theory[END_REF], [START_REF] Osborne | A Course in Game theory[END_REF]. Let us briefly describe here, non exhaustively, some important existing works in that direction. In [START_REF] Ma | Interconnecting eyeballs to content: A Shapley value perspective on ISP peering and settlement[END_REF], [START_REF]On cooperative settlement between content, transit and eyeball internet service providers[END_REF], the authors propose to share the revenue among providers using the Shapley value, the only mechanism that satisfies a set of axioms representing a sense of fairness; in this case CPs participate to the network access cost. The work in [START_REF] Musacchio | Network neutrality and provider investment incentives[END_REF] analyzes how neutrality or non-neutrality affects provider investment incentives, network quality, and user prices. A similar comparison is made in [START_REF] Musacchio | A two-sided market analysis of provider investment incentives with an application to the net-neutrality issue[END_REF] between a two-sided pricing scheme where ISPs are allowed to charge CPs, and one-sided pricing where such side-payments are not allowed. In each case, at the equilibrium of the game, the levels of investment in content and architecture are determined. The paper gives conditions on the ratio between parameters characterizing advertising rates and end-user price sensitivity, under which a non-neutral network outperforms a neutral one in terms of social welfare. On the other hand, [START_REF] Saavedra | Bargaining power and the net neutrality debate[END_REF] investigates the case where ISPs negotiate joint investment contracts with a CP in order to enhance the quality of service and increase industry profits. It is found that an unregulated regime leads to higher quality investments, but that ISPs have an incentive to degrade content quality. The paper [START_REF] Altman | A study of non-neutral networks with usage-based prices[END_REF] studies the implications of nonneutral behaviors, taking into account advertising revenues and considering both cooperative and non-cooperative scenarios. In [START_REF] Coucheney | Network Neutrality Debate and ISP Inter-Relations: Traffic Exchange, Revenue Sharing, and Disconnection Threat[END_REF], we analyze and compare thanks to game-theoretic tools three different situations of interactions between ISPs: the case of peering between the ISPs, the case where ISPs do not share their traffic (exclusivity arrangements), and the case where they fix a transfer price per unit of volume. The paper supports the transit price scenario and suggests a limited regulation (enforcing global connectivity) to prevent incumbent ISPs from having a dominant position in the bargaining. Finally, in [START_REF] Altman | Network non-neutrality debate: An economic analysis[END_REF], a game-theoretic model is considered with a single CP, a single ISP, a (consumers') demand function that depends on price and quality of service, and involving advertisement and network investment components.

In those works, there is in general a single ISP, and one or several CPs. Though, in practice, we often have ISPs in competition for customers, while for many services, the CPs are in a quasi monopoly, a characteristic ISPs complain about. (Typical examples are YouTube for non-copyrighted videos, and Netflix for movies and TV shows in the US.) We propose to specifically address this issue in this paper. Remark that in addition to [START_REF] Musacchio | A two-sided market analysis of provider investment incentives with an application to the net-neutrality issue[END_REF], considering competitive ISPs has been proposed in [START_REF] Njoroge | Investment in two sided markets and the net neutrality debate[END_REF], but with competition over consumers, quality and prices for heterogeneous CPs: none of those works consider a monopolistic CP as can be encountered for some applications. We already addressed this type of problem in [START_REF] Boussion | Net neutrality debate: Impact of competition among ISPs[END_REF], whose model was inspired by [START_REF] Altman | A study of non-neutral networks with usage-based prices[END_REF], users were assumed to always go with the cheapest provider. As a consequence, we ended up with a price war (a classical Bertrand competition) such that ISPs always decrease their subscription price in order to attract all demand.

We consider here a more realistic user association model such that users make their choice still based on the price of ISPs, but also on other unknown considerations, hence the use of a classical discrete choice model as in [START_REF] Coucheney | Network Neutrality Debate and ISP Inter-Relations: Traffic Exchange, Revenue Sharing, and Disconnection Threat[END_REF]. This requires a derivation of results totally different from [START_REF] Boussion | Net neutrality debate: Impact of competition among ISPs[END_REF]. To analyze that situation, we propose a multi-level game where decisions are taken at different time scales. The solutions of the games at the largest time scales, played first, are determined using backward induction, meaning that players anticipate the impact on, and the resulting solution of, the games played later on at smaller time scales.

The paper is organized as follows. Section II presents the basic assumptions of the model we are going to consider, the different levels of game, and the mathematical description of the investigated comparison between the neutral and the non-neutral regimes. It also describes how users select their ISP (if any), and how the aggregated demand at the CP is determined. The next sections present the various game levels End-users

ISP A p A ISP B p B CP 1 q A q B p 1
Fig. 1. Charging interactions between stakeholders. Prices p 1 , p A and p B are positive flat rates, whereas q A and q B are positive per volume unit prices.

for providers' decisions: we describe in Section III how the CP, anticipating the decisions of end users, chooses the content price. At a higher level, by backward induction, ISPs play a game on the access charge for end users; this competition is described in Section IV. We then describe the game at the highest level, on the economic relationships between the ISPs and the CP, by determining the side payments of the CP to the ISPs in Section V. We address the case when those prices are fixed by ISPs, based on a game; we also look at the case when they are decided by the CP, or by a regulator (maximizing the supply chain value for instance). Section VI concludes by discussing the impact and relevance of side payments on the providers' revenues, highlighting that it is not always in the interest of the ISPs (but could be), while an appropriate choice of side payments may increase the CP revenue. We also give in that section directions for future research.

II. MODEL

A. Topology and Pricing Structure

We consider a single CP, whose parameters will be indexed by 1, and two ISPs, named (and indexed by) A and B. The access prices charged to users are flat rate subscription fees, denoted by p 1 , p A and p B for respectively the CP, ISP A and ISP B. In order to study non-neutrality, we also introduce side payments q A and q B representing the per unit of volume prices that the CP has to pay to A and B, respectively. All prices are assumed to be positive. Finally, the set of end users is considered continuous and (without loss of generality) of mass one, so that we will indifferently refer to "mass" and "proportion" of users. The charges imposed by actors to other players are summarized in Figure 1, the arrows indicating the cash flows.

B. User Demand

Users have to pay both the ISP and the CP to access the content. Users first choose their ISP, to which they pay a flat-rate subscription fee, and then subscribe to the CP too if its (flat) fee is not too high. Since users need an Internet access, not only to reach the content of the CP, but also for other purposes (e-mail, web browsing, ...), we decorrelate the ISP choice from the (individual) decision to subscribe to the CP, hence the independence from p 1 . Among those access subscribers, the proportion who also subscribe to the CP depends on p 1 on the other hand, but not on the subscription price to the ISPs as a first-order model, assuming as a consequence that users do not relate their consumption of content to the previously paid ISP subscription fee.

Let us focus first on the ISP selection by users. In a previous work [START_REF] Boussion | Net neutrality debate: Impact of competition among ISPs[END_REF], we have considered users simply selecting the cheapest ISP (or choosing it randomly if price equality holds). However, this does not take into account the phenomenon of stickiness or loyalty of the users, highlighted in [START_REF] Caron | Application neutrality and a paradox of side payments[END_REF]. In the model considered here, user choices are influenced by the ISP subscription prices, but also by other considerations (reputation or preferences) that can be modeled as an additive noise to the main criteria determining the choice. We consider here a discrete choice model, a standard paradigm in economy, transportation, etc., and surprisingly not often applied in telecommunications. It is a common way to model how decision makers choose among a set of alternatives. Mathematically, we assume that a user has a valuation of the form v i = β log(1/p i ) + κ i for ISP i, and selects the highest-valued option (see [START_REF] Coucheney | Network Neutrality Debate and ISP Inter-Relations: Traffic Exchange, Revenue Sharing, and Disconnection Threat[END_REF] for details). The term κ i is an individual-specific random term, taking into account unknown aspects and assumed to follow a Gumbel distribution as in standard discrete choice models [START_REF] Ben-Akiva | Discrete choice analysis[END_REF]. We additionally assume that there is a fictitious price p 0 , assumed to be strictly positive, and representing the cost of the outside option, i.e., the perceived cost of not having access to the Internet. Thus if the (random) valuation associated with that outside option is larger than the ones associated with each ISP, the user prefers not to join the network. The parameter β > 0 represents the user sensitivity to the subscription prices: values of β close to zero lead to an uniform choice over the three alternatives (connecting to one of the two ISPs, or not having access to the Internet) regardless of the prices set, whereas large values of β make the users choose the least expensive option. The term log(1/p i ) expresses the dissatisfaction for higher prices, the logarithm being used to represent the fact that the same variation of price is felt smaller at high prices than at low prices: users are sensitive to relative price variations rather than absolute ones. Finally, the case p i = 0 leads to the maximal possible valuation independently of the random terms, meaning that ISP i attracts all users, or (say, from symmetry) half of them if the other ISP chooses a null price as well.

At a macroscopic level, by discrete choice analysis, the proportion (or equivalently, the mass) σ i of users selecting ISP i (with also j ∈ {A, B}; j = i), can be shown to equal from our expression of v i (see [START_REF] Ben-Akiva | Discrete choice analysis[END_REF] for a general derivation)

σ i =            p -β i p -β A + p -β B + p -β 0 if p A > 0 and p B > 0 1 if p i = 0 and p j > 0 1/2 if p A = 0 and p B = 0 0 if p i > 0 and p j = 0. (1)
This repartition function expresses the fact that all users select an ISP if at least one of the subscription prices is null (p A = 0 or p B = 0). Of course, the higher the price, the fewer subscribers; this effect increasing with the user sensitivity to price β.

In this paper, we propose a new aggregated user demand in terms of data volume on ISP i, where users having selected an ISP then decide whether to use the content offered by the CP, depending on the flat-rate price p 1 . We consider that users' willingness-to-pay for the CP service (i.e., the access to all the content offered by the CP) follows an exponential distribution with mean value 1/α > 0 over the population, independently of the ISP choice. Therefore, a proportion e -αp1 of each ISP's subscribers also subscribes to the CP, hence a number σ i e -αp1 subscribing to both the CP and ISP i. Note that the consequence of our assumption is an exponentially decreasing demand function (in terms of the CP price), a usual setting in economic theory.

We assume that there is an average volume D 0 of data that a user downloads from the CP if subscribing to it. The value will be helpful to compute the volume-based transit costs for the CP to the ISPs. This volume is assumed to be independent of the ISP choice. Instead of considering an average volume, we could say that it is the same value for all users without changing the expressions; an average value just allows to take into account the potential variations between users that are averaged when summing over all subscribers of an ISP. D 0 is additionally assumed independent of p 1 , meaning that users just get what they "need" if subscribing. As a result, the data volume for users subscribing simultaneously to the CP and to ISP i is given by:

D i = D 0 σ i e -αp1 . (2)
The parameter α > 0 can be interpreted as the sensitivity of users to the CP price: the global demand (sum of demands on all ISPs) is a decreasing function of α. Notice that demand does not directly depend on the side payments q A and q B . But the introduction of side payments will induce a reaction on the prices p A , p B and p 1 set by ISPs and the CP at equilibrium, which, in turn, indirectly affects demand. Finally, the global volume demand for CP data

D A + D B equals (σ A + σ B )D 0 e -αp1 .

C. Utility and revenue functions

Among the proportion σ A + σ B of users having accepted to pay for an access to the network, and then paying a flat-rate price p 1 to the CP, some would have accepted to pay more to benefit from the content of the CP. The surplus of users that would have accepted to pay p is p -p 1 , while the proportion of users willing to pay more than p is e -αp1 .

We can then compute the user welfare associated with the existence of the CP, as the sum over all users of the benefit they make accessing the content of the CP. Note that this does not include the benefit that users make by selecting an ISP, which is associated with other (free) on-line services. From our assumption of an exponential distribution of users' willingness-to-pay for the content (yielding a density αe -αx ), the user welfare due to the CP can be computed as:

UW CP = (σ A + σ B ) ∞ p1 αe -αx (x -p 1 )dx = (σ A + σ B ) e -αp1 α = D A + D B αD 0 . (3)
The utilities (revenues) of the ISPs come from the end users subscription fee, and from the CP through the possible side payment. The first one depends on the mass of users with the ISP, and the second one on the total amount of volume downloaded by users. Hence, for ISP i (i ∈ {A, B}), the revenue is

U i = p i σ i + q i D i . (4)
We can remark here that the revenue is always positive since we do not consider the cost of the network. The utility of the CP in this model is the sum of revenues gained by users subscribing through A and through B. Those gains come from the flat-rate subscriptions by users through each ISP i, p 1 σ i e -αp1 , but the volume-based side payments q i D i paid to i also have to be taken into account. The CP net benefit (utility) is thus given by

U 1 = (p 1 σ A e -αp1 -q A D A ) + (p 1 σ B e -αp1 -q B D B ) = (p 1 /D 0 -q A )D A + (p 1 /D 0 -q B )D B . (5)
Since p 1 is decided after q A and q B , the CP can also ensure a positive revenue by setting p 1 /D 0 ≥ max(q A , q B ).

D. Multi-stage Decision Problem

The decision variables are the prices p 1 , p A , p B , q A , q B , impacting end users (demand), as well as revenues of providers. Those variables are decided at different time scales or levels, that can be described as follows.

1) At the largest time scale, the side payments q A and q B are decided. In the neutral case, they are either fixed to 0, or determined as a common value. They can be different in the non-neutral case, and can be determined either by the ISPs (in a game), the CP, or a regulator. All those options will be investigated. Those determinations will be obtained anticipating the solution of the games below whatever the values of q A and q B (the so-called backward induction). 2) At a smaller time scale, for fixed values of q A and q B , the ISPs fix their prices p A and p B during a noncooperative game to attract customers and maximize their revenues. Here again, the decisions are made anticipating the solutions at lower levels. 3) At an even smaller time scale, the CP sets the price p 1 . Finally, for those fixed values of p 1 , p A , p B , q A , q B , users choose their ISP (if not too expensive), and decide whether to use the service offered by the CP, as described by formulas (1) and [START_REF] Lenard | Net Neutrality or Net Neutering: Should Broadband Internet Services be Regulated[END_REF].

All those interacting levels are now solved by backward induction, from the smallest time scale to the largest one.

It is possible to perform the same analysis with a different hierarchy in the three levels of game, assuming for example that subscription prices are decided before the side payments. Though, we think it is reasonable to consider that the decisions on side-payments to take place on a large time scale, given the difficulty, span, and costs of such decision processes. Similarly, regarding the time scale difference between prices set by the CP and by the ISPs, our approach is consistent with the (commonly spread) vision that CPs can adapt faster than ISPs, in part because of the different contract durations binding users to providers (larger durations with ISPs than with CPs), the various difficulties to switch ISPs, etc.; see also [START_REF] Economides | The economics of the internet backbone[END_REF].

III. CONTENT PROVIDER PRICE DETERMINATION

The CP aims at maximizing his revenue U 1 , for fixed values of p A , p B , q A , q B , making use of what the total user demand D A + D B , with D i given by (2), will be. For convenience, we define P i := p β i . Proposition 1. Given the side payments q A and q B and the prices p A and p B decided by the ISPs, the price of the CP maximizing its revenue ( 5) is

p * 1 =          P A P A + P B (D 0 q B + 1 α ) + P B P A + P B (D 0 q A + 1 α ) if p A > 0 or p B > 0, D 0 q A + q B 2 + 1 α if p A = 0 and p B = 0 (6)
Proof: We first consider the case p A > 0 and p B > 0. The derivative ∂U1 ∂p1 of the CP revenue is then equal to P 0 e -αp1 P A (αq B + (1 -αp 1 )/D 0 ) + P B (αq A + (1 -αp 1 )/D 0 ) P 0 P A + P 0 P B + P A P B which is strictly positive until p 1 achieves the value given in the first equation of ( 6), and strictly negative after. Hence the result.

If p A = 0 (and then P A = 0) and p B > 0 (the opposite case is symmetric and then omitted), the CP revenue is e -αp1 (p 1 -D 0 q A ), whose derivative is e -αp1 (1 -α(p 1 -D 0 q A )).

Finally, if p A = p B = 0, then the CP revenue is

1 2 e -αp1 (2p 1 -D 0 (q A + q B ))
, and its derivative is e -αp1 (1αp 1 + α 2 D 0 (q A + q B )). Notice that the optimal price does not depend on the outside option valuation p 0 . One can also check that it increases with the price p i of ISP i that has the biggest side payment q i , and decreases with the other price. In the limit (that can be interpreted as neutral) case q A = q B = q, the optimal pricing for the CP is qD 0 + 1/α whatever the value of p A and p B . In that case, as an important remark, the CP's revenue is

D A + D B D 0 α
, which corresponds to the CP-related user welfare:

the interest of users and that of the CP coincide here. Finally, we can remark that the optimal price for the CP is always greater than D 0 min(q A , q B ) + 1/α, because it is a convex combination of D 0 q A + 1/α and D 0 q B + 1/α. In particular, it is greater than the inverse of the user price sensitivity α.

IV. PRICING GAME BETWEEN ISPS

Before the users decide which ISP to join and the CP chooses p 1 , the ISPs play a pricing game, making use of what the CP and users decisions would be. In this section, we determine the Nash equilibrium solutions of this pricing game in an analytical way when there are no side payments, and numerically (because intractable) in the general case. Recall (see [START_REF] Osborne | A Course in Game theory[END_REF]) that a Nash equilibrium would be a price profile (p A , p B ) such that no ISP can improve (strictly) his utility by unilaterally changing his price. The best-response curves are defined as (by expliciting the dependence of U A and U B on p A , p B )

BR A (p B ) = arg max p A ≥0 U A (p A , p B ) and BR B (p A ) = arg max p B ≥0 U B (p A , p B ).
With those notations, a Nash equilibrium is a point

(p NE A , p NE B ) for which BR A (p NE B ) = p NE A and BR B (p NE A ) = p NE B .
Graphically, if we draw the two best-response curves on the same figure, the set of Nash equilibria is then the (possibly empty) set of intersection points of those curves.

A. No side payments

In the case where no side payments are established, q A = q B = 0, we get a simple formulation for the revenue of ISPs. From the previous section, the optimal CP pricing is 1/α. Using the notation P i := p β i , the revenue of ISP A is then (the revenue of ISP B being symmetrical)

U A =    P 0 P B p A P 0 P A + P 0 P B + P A P B if p A > 0 and p B > 0 0 if p A = 0 or p B = 0 (7)
We first stress that p A = p B = 0 is a Nash equilibrium since no player can strictly increase his revenue by unilaterally changing his action: the revenue always remains equal to zero. But setting one's price to zero is a dominated strategy, that is strictly dominated as soon as the adversary price is not zero: it always yields no revenue whereas a strictly positive revenue can be guaranteed with any other choice. Therefore it is not likely to be chosen by ISPs if another equilibrium exists. Proposition 2. Assuming that there are no side payments, i.e. q A = q B = 0, then

• if β ≤ 1,
= P NE B = ∞), • if 1 < β < 2,
there is a unique Nash equilibrium different from (0, 0) with

P NE A = P NE B = 2 -β β -1 P 0 ,
• if β ≥ 2, (0, 0) is the unique Nash equilibrium, yielding no revenue for the ISPs.

The proof relies on the following general result about symmetric games.

Lemma 1. If the best response functions BR

A and BR B are

• equal: BR A = BR B = BR, • single-valued,
• strictly increasing, then (p A , p B ) is a Nash equilibrium if and only if p A = p B = p with p a fixed point of the best-response function: p = BR(p).

Proof: (Lemma) The pair of prices (p A , p B ) is a Nash equilibrium if and only if p A = BR(p B ) and p B = BR(p A ). Let us suppose that p A = p B , for instance p A > p B (should the indexes be permuted). Then:

p B = BR(p A ) > BR(p B ) = p A ,
where the inequality comes from the strict increasingness of BR, hence a contradiction. At Nash equilibrium, p A = p B is then a necessary condition, and from the definition of such an equilibrium, it is necessary and sufficient to have p = BR(p).

Proof: (Proposition) Assuming that p A > 0 and p B > 0, the derivative of ISP A revenue ( 7) is P B P 0 (P A P B + P B P 0 + P A P 0 ) 2 (P A (1 -β)(P B + P 0 ) + P B P 0 ) .

Hence the derivative has the same sign as the affine function of P A : P A (1-β)(P B +P 0 )+P B P 0 . When β ≤ 1, that derivative is always strictly positive for P A ≥ 0, thus (by symmetry) each ISP should set infinitely large prices.

When β > 1, the derivative of ISP A revenue is strictly positive while P A is smaller than the unique root of the affine function above, and negative afterwards. Given p B > 0, the best-response of ISP A is then BR A (P B ) = P B P 0 (β -1)(P B + P 0 ) .

For the case β > 1, notice that the best response is the same function for ISP B due to symmetry, that equals BR(P ) = 1 (β-1)(1/P0+1/P ) , and is a strictly increasing function of P . Hence it follows from the previous lemma that every Nash equilibrium is symmetric, which results here in the necessary and sufficient condition at Nash equilibrium

P NE B = P NE A = BR A (P NE A ).
The last equation has a unique strictly positive solution in the case 1 < β < 2, the one given in the proposition, and no solution otherwise.

This proposition shows in particular that, when the price sensitivity of users is high (β ≥ 2), we are led to the same price war as in the model of Bertrand competition studied in [START_REF] Boussion | Net neutrality debate: Impact of competition among ISPs[END_REF]. But for smaller levels of price sensitivity, this does no longer happen: the price set by ISPs at equilibrium is strictly positive, hence providing some revenue from users to both ISPs.

B. Positive side payments

In the general case, the computation of the Nash equilibrium or even the best response function is not analytically tractable. We are then led to study numerically the price competition between ISPs. From here, we take α = 1, p 0 = 1, D 0 = 1, and β = 1.5. We remark that the choices of p 0 and D 0 are made without loss of generality (they correspond to unit changes of ISP prices and data volumes). The choice of α also corresponds to a unit change in the CP prices, and is therefore linked to that of p 0 (i.e. for a given user sensitivity to the 2. Set Pw of side payments (q A , q B ) for which the Nash equilibrium is such that p NE A = p NE B = 0, i.e. price war holds.

0 3 0 3 P w q A q B Fig.
CP price, the value of α is a consequence of the monetary unit choice, and thus is determined by the choice for p 0 ). Therefore our choice of α and of β are subject to discussion. We however stress here that we have also run experiments with other values (in the range (1, 2) for parameter β) and observed similar results.

Let us first remark that if the price set by an ISP (say ISP A) is equal to zero, then the other ISP (ISP B), at a Nash equilibrium, sets his price to zero as well. This is because ISP B does not attract any users if his price is not zero, and then his revenue is null, whereas the revenue is 1 2 q B D 0 e -α 2 D0(q A +q B )-1 otherwise, hence strictly positive. Numerical computations show that there is a set of side payments q A and q B for which the price war phenomenon between ISP happens. That set is shown in Figure 2. In the following, we will denote by P w the set of side payments for which a price war between ISPs takes place, leading to null subscription prices.

Figures 3 to 6 show the prices and revenues at Nash equilibrium (recall that this is for q A and q B fixed). Numerical computations point out the fact that the revenue of the CP, and the user welfare he creates, are always equal at equilibrium, the reason why we do not plot user welfare here. While this equality is clear when side payments are the same, our numerical results suggest that it remains true in the general case.

Figure 3 represents the price p NE A set by ISP A at Nash equilibrium, when the side payment q A varies, and for several ISP B side payments q B . This reveals that the price at equilibrium first decreases with the side payment set by the ISP, and then increases. For some value of the opponent ISP side payment, it goes to zero when a threshold is reached. That threshold corresponds to the case where the side payment revenue that ISPs get by setting their prices to zero, and then attracting the whole set of users, becomes larger than the one they get on a limited market share with both the subscription fees and the side payments. This is the price war situation: equilibrium subscription prices of both ISPs fall down to 0 as the side payments enter the "price war zone" P w highlighted in Figure 2, and each ISP finally only attracts half of the user

0 4 0 0.5 1 q A p NE A q B = 0 q B = 1 q B = 2 q B = 3
Fig. 3. ISP A user price p NE A at equilibrium as a function of the side payments q A with q B ∈ {0, 1, 2, 3}.

0 2 4 0 2 4 q A p * 1 q B = 0 q B = 1 q B = 2 q B = 3
Fig. 4. CP optimal price at equilibrium as a function of the side payments q A with q B ∈ {0, 1, 2, 3}.

set, hence the discontinuity. Finally, we observe that there is no monotonicity in the opponent side payment.

Figure 4 displays the optimal price p * 1 of the CP in terms of q A for different values of q B . We can notice the discontinuity due to the price war thresholds (for the cases q B = 1 and q B = 2, since there are no such thresholds for the two other cases from Figure 2). However, this discontinuity is barely visible, which is quite surprising when compared to that observed at the ISP level. It can also be remarked that the optimal price increases with q A (and q B ) both before and after the thresholds, but not in general. One can also check here the general property that p * 1 ≥ D 0 min(q A , q B ) + 1/α, which, in particular, ensures a strictly positive revenue to the CP.

Figure 5 shows that the revenue of ISPs is not monotonic with the side payment. Again, some discontinuities occur when side payments enter and leave the price war zone P w . Moreover, depending on the ISP B side payment, the maximal revenue of ISP A is reached either for a null side payment (e.g., when q B = 3.0) or for a strictly positive value (e.g., when q B = 0.0). This illustrates that predicting the effect of the various parameters in the output of the game(s) is a difficult task and game-theoretic tools are helpful here to get a result: a side payment increase can indeed lead to a content 0 4 0 0.2 0.4

q A U A q B = 0 q B = 1 q B = 2 q B = 3
Fig. 5. ISP A revenue at equilibrium as a function of the side payment q A with q B ∈ {0, 1, 2, 3}.

0 4 0 0.1 0.2 q A U 1 q B = 0 q B = 1 q B = 2 q B = 3
Fig. 6. CP revenue at equilibrium as a function of the side payment q A , with q B ∈ {0, 1, 2, 3}.

price increase by the CP to compensate for the loss, and a reaction of the other ISP; this also has an effect on demand and depending on the variations, this may or may not result in an ISP revenue increase.

On the other hand, the CP revenue, plotted in Figure 6, has a tendency to decrease with side payments, even if it is not strictly the case, as can be seen for q B = 1 and small values of q A . When a discontinuity occurs, the CP revenue is maximized for the smallest side payment leading to the price war. The non-monotonicity is due to the threshold for the price war between ISPs, inducing a discontinuity in the ISP prices. Because of those prices becoming null, the revenue jumps up.

Finally, over the price war set P w , the CP subscription price is p 1 = D 0 q A +q B 2

+ 1 α and the revenues are

U i = 1 2 q i D 0 e -αD 0 2 (q A +q B )-1 (8)
U 1 = UW CP = 1 α e -αD 0 2 (q A +q B )-1 . (9)
V. SIDE PAYMENTS DETERMINATION

We consider at the highest level three possibilities for the choice of the side payments q A and q B . We first look at the case when they are determined by the CP (even if unlikely in practice), then the case when they result from a game played

0 4 0 0.1 0.2 0.3 q A U 1 q B = 0.2 q B = 0.3 q B = 0.4
Fig. 7. CP revenue at equilibrium as a function of the side payment q A , with q B ∈ {0.2, 0.3, 0.4}. The maximal revenue is reached when q A = q B = 0.3.

between ISPs, and finally the case when they are determined by a regulator (e.g., to maximize social welfare).

Since we don't have the analytical expression for the ISPs price at Nash equilibrium, we provide numerical results, where we take α = 1, β = 1.5, p 0 = 1 and D 0 = 1.

A. Determined by the CP

The revenue of the CP is maximized when the side payments are q A = q B = 0.3 as illustrated in Figure 7 (instead of plotting a hard-to-read 3D-curve of CP revenue in terms of q A and q B , we have preferred to draw 2D-curves in terms of one of the parameters for various values of the second parameter close to optimal). It is interesting to notice that, for such a set of side payments, there is a price war on the user prices, i.e., p NE A = p NE B = 0 here. In fact it corresponds to the symmetric (q A = q B ) point of the price war set P w described in Figure 2 for which the sum of side payments is minimized. Indeed, if p NE A = p NE B = 0, then the revenue of the CP can be rewritten as U 1 = 1 α e -αD 0 2 (q A +q B )-1 , and then is maximized when q A + q B is minimal.

At this point the revenues of the stakeholders are U A = U B ≈ 0.04, and UW CP = U 1 ≈ 0.27. Hence the revenues of ISPs are much smaller than the one of the CP. Note that the situation is quite counter-intuitive, since the CP gains to introduce side payments. This is because those payments exacerbate the competition between ISPs, which is beneficial to end users, and finally to the CP who can reach more customers.

B. Determined by the ISPs, through a game

If we instead assume that the side payments are noncooperatively determined by the ISPs, we are led to study the best response of each ISP to the other ISP side payment. As shown in Figure 8, the best response is first increasing in the other ISP side payments, and then falls to zero above a threshold, which is approximately 2.80. Since the bestresponse to a null price is 2.80, it follows that (0, 2.80) and the symmetric point (2.80, 0) are Nash equilibria, and they are the only ones. It is interesting to notice that the resulting side

NE NE q A q B BR A (q B ) BR B (q A )
Fig. 8. The optimal side payment of each ISP as a function of the opponent ISP side payment. There is a threshold q i ≈ 2.80 beyond which the best response falls to zero. There are two Nash equilibria (NE) where one ISP sets its side payment to zero.

payments are not symmetric at Nash equilibrium, so are the revenues equalling 0.42 for the ISP with side payment 2.80 and 0.34 for the other ISP. Now let us compare that outcome to the case without any side payments. From Subsection IV-A, with β = 1.5, the revenue of ISPs is 0.33. Hence the ISPs global revenue increases by about 15%, which goes in the direction of ISPs arguments about side payments improving their revenue. On the other side, the CP revenue decreases from 0.25 to 0.06, hence losing nearly 75% of its value. The benefit of ISPs is then at the expense of the CP and consequently of the user welfare.

C. Determined by a regulator

A regulator can either decide to maximize the revenue of the supply chain (sum of utilities of the ISPs plus the CP), the user welfare (end-users surplus), or the social welfare (including user welfare and all providers utilities).

The total value of the supply chain is the total revenue got from the users, i.e., U 1 + U A + U B .

User welfare can be decomposed into two components: the user welfare due to the existence of the CP -that is computed in (3)-, and the user welfare due to the presence of the ISPs. Let us focus on the latter part: we have assumed that users not connected to the Internet perceive a cost p 0 (thus p 0 can be seen as the value of the connectivity service). When a user decides to subscribe to ISP i and pays the corresponding price p i , its benefit is then p 0 -p i with respect to the no-ISP situation: the user does not bear anymore the cost p 0 of not having Internet access, and instead perceives the monetary cost p i . Aggregating over the whole population, the user welfare that is due to the presence of the ISPs (with their prices p A and p B ) equals

UW ISPs = σ A (p 0 -p A ) + σ B (p 0 -p B ).
The global user welfare generated by the system (ISPs and CP) is therefore UW = UW CP + UW ISPs [START_REF] Ma | Interconnecting eyeballs to content: A Shapley value perspective on ISP peering and settlement[END_REF] Finally, social welfare is defined as the overall value of the service for the society. It therefore includes the surpluses of all actors, and equals SW = U 1 + U A + U B + UW Note that Social Welfare also corresponds to the total value that the service has for subscribers, without considering any monetary exchanges because they stay within the society. We indeed obtain, simplifying the sum of the terms in SW:

SW = (σ A + σ B ) p 0 + p 1 + 1 α e -αp1 ,
where the term (σ A + σ B )p 0 is the value of the connectivity service for ISPs' subscribers, and the other term is the value of the CP service for CP subscribers, computed as

(σ A + σ B ) ∞ p1 αe -αx x dx.
1) Side payments to maximize User Welfare: Since CP revenue and user welfare are equal at Nash equilibrium, it follows that user welfare is maximized when the CP revenue is maximized. This case has already been treated in Subsection V-A.

2) Side payments to maximize Social Welfare: We have obtained numerically that social welfare is maximized for the same side payments as the ones maximizing the CP revenue and the user welfare.

3) Side payments to maximize the supply chain value: The supply chain value is maximized when the side payments are both null, which has been studied in Subsection IV-A. In this neutral case the revenue of ISPs is approximately 0.33 whereas that of the CP (and the induced user welfare) is 0.25. We can remark that among the three alternatives considered in this subsection, this one leads to the fairest revenue sharing between stakeholders.

VI. DISCUSSION, CONCLUSIONS AND FUTURE WORK

We have provided in this paper a model describing the interactions between two ISPs in competition, a CP, and end users connecting to the network. With respect to the literature, we believe that considering competitive ISPs and a single CP is a more realistic representation of the current network where we have a quasi-monopoly for some applications (for instance YouTube or Netflix), while several ISPs are in competition (an argument of ISPs). The goal is to study the impact of side payments on providers' revenues, and conclude whether they can help reduce the unfairness of the current revenue sharing among all actors, as claimed by ISPs in the current network neutrality debate. We restricted the analysis to two ISPs because in many cases, competition is limited to a very small number of ISPs, and very often only two ISPs are available to a given user [START_REF] Economides | The economics of the internet backbone[END_REF]; but a numerical analysis can be extended to more than two.

In this paper, we have presented a three-level game where (from the largest to the shortest time scale) the side payments are first determined, then a pricing game is played between ISPs, followed by the content provider price, and finally, knowing all those prices, end users choose their ISP (or none if too expensive) and possibly decide to subscribe also to the CP service. All those levels are played by backward induction, meaning that players anticipate the solutions of the later games when choosing their strategies.

Our results have highlighted the fact that side payments, unless decided by ISPs, have little chance to address the concern from ISPs regarding the fairness of the revenue sharing associated with users accessing content through their infrastructures. This is due, to a great extent, to the competition played among ISPs on the access prices that drives their revenues to low values. On the other hand, the CP being in a monopolist situation, always obtains significant revenues. An interesting paradox we have highlighted is that side payments may be beneficial to the CP. Nevertheless, when side payments are decided by the ISPs (non-cooperatively), it can be beneficial to them, but at the expense of both the CP and the users. Remarkably, the side payments maximizing social and user welfare are the same than those maximizing the CP revenue. But looking at the whole supply chain, in order to avoid too big disparities between revenues of providers, the neutral case is the most suitable. If the side payments are decided non-cooperatively by ISPs, in our experiment, one (only) is a big winner, while the other ISP gains a bit more than in the neutral case. This asymmetry may be a problem and can create complicated tensions and negotiations.

As future research, we would like to go into several directions: first to include several CPs with different contents, but such that some end users are targeting only a subset of them, for all possible subsets. ISPs may also charge each other to let the CPs not connected to them reach their own customers (transit pricing). Other extensions to our model could include architecture investment and content innovation characteristics, for the ISPs and the CP respectively.

Pierre

  Coucheney received his Master degree in applied mathematics from université Paris 6, and his Ph.D. in computer science from university of Grenoble. He is currently in a post-doctoral position at Inria-Rennes, working on the network neutrality topic. His research interests include game theory and its applications to the optimization and economic modelling of networks. Patrick Maillé graduated from Ecole polytechnique and Telecom ParisTech, France, in 2000 and 2002, respectively. He has been an assistant professor at the Networks, Security, Multimedia department of Telecom Bretagne since 2002, where he obtained his PhD in applied mathematics in 2005, followed by a 6-month visit to Columbia University in 2006. His research interests are on game theory and economic concepts applied to telecommunication ecosystems: resource pricing, routing, consequences of user selfishness on network performance.

ACKNOWLEDGMENTS

This work has been supported by INRIA's ARC project MENEUR and EuroNF NoE's project INNIS on network neutrality, and by the French ANR VERSO project CAPTURES on competition between providers.