Cécile Bothorel

Christophe Lohr

André Thépaut

Fabrice Bonnaud

Gilbert Cabasse

From individual communication to social networks: evolution of a technical platform for the elderly

Keywords: Social Ties, Social Networks, Digital Life, Assistive Technology to Improve Quality

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The aging population is a very strong concern in Western countries. The significant increase in life expectancy leads to worry about increasing the quality of life of seniors. On the other hand, there is a strong link between aging and loneliness. This sentiment characterizes persons who do not communicate with their family and immediate friends, and whose number of social contacts decreased significantly. According to French statistics 1 , 74% of elderly people in France say they are suffering from loneliness.

If several other factors reinforce this feeling of loneliness (physical disabilities that limit the territory of life of elderly, loss of spouse, etc.) [START_REF] Pitaud | Responding to dependency in old age. Bold[END_REF], the loss of a social network is especially noticed. This phenomenon is observed when work colleagues are encountered less often, when friends are more remote or die, when family visits are becoming less frequent. Several studies [START_REF]INSEE: Enquête relations de la vie quotidienne et isolement[END_REF] show that the loss of a spouse (only one in five seniors lives together as a couple) also accelerates social isolation. Finally it is estimated that currently one quarter of residents in nursing homes might not suffer from physical dependence or psychological dependence, but from social dependence. Through technical platforms suitable and customizable, our multidisciplinary research team aims at improving the lives of the elderly living in retirement homes by preserving, enhancing, or creating social ties. Digital innovation is a huge issue nowadays to enhance the quality of life, autonomy or social life for elderly [START_REF] Rivière | Bien vieillir grâce au numérique[END_REF].

TV-Kiosk2 , very similar to our project, uses a simple Internet service, where "elderly can now stay in touch with their family and friends and get easy access to information provided by the care centre they life in. [...] A small-scale field trial is ongoing". Related works are still new studies, and eHealth techno-enthusiasts have still to evaluate socio-technical factors to maximise the likelihood of successful implementation and adoption [START_REF] Black | The impact of ehealth on the quality and safety of health care: A systematic overview[END_REF].

Through the AIPA project (2007-2010) 3 , we propose a TV-based service that allows elderly people living in nursing homes to be connected to their network of contacts. The project team has chosen to involve several players (seniors, families, professionals of the nursing home, retired volunteers, neighbourhood town hall, etc.) since the beginning of the design process. Sociologists have conducted individual and group interviews and have identified two types of services: the elderly receive emails, pictures, videos from their relatives, and also local news and obituaries from the regional daily press [START_REF] Bonnaud | Companymages/AIPA: offering communication and comfort services to the aged in institution[END_REF].

Sociologists also recruited 11 elderly people (aged 59 to 92, median age is 87), and their 65 relatives. These people have experimented the service for about a year. 3 of them did not much use it; 4 gave up. The 4 daily active participants were mostly people in good health with few visits from the caregivers. They were elderly people less visited by their family but with a strong emotional network and they enjoyed particularly getting news from their family through AIPA mediated services. While most of the users have shown a real interest, they expressed some suggestions for improvement. The socially active users felt a frustration because of their position as consumers; they asked for more active functionalities such as the capability to respond to the messages or comment on pictures sent by their relatives. Emotionally isolated people or people whose family was minimally involved, showed less enthusiasm for AIPA since the proposed contents were essentially social. The the other contents were much poorer. They asked for thematical contents or contents related to their hobbies.

Social Networks and New Challenges for Isolated People

Strengthen and Rediscover Relationships

Social studies show that virtual friendships are mostly the prolongation of real life ones. In general, people who interact in their virtual life also interact in their real life [6] [5]. People involved in many social activities will be very active online. We think in our current project Mazadoo that with new networking possibilities in AIPA-like systems we could interest such socially active old people. Beyond this standard behaviour, we find people who make new connections on the web before meeting in real life. For those individuals the aim of being online is first to share interests, passions, and not to extend their network just to extend it as a primary objective [START_REF] Lethiais | Les amitiés virtuelles dans la vie réelle: profil, motifs et modalités de construction[END_REF]. The emotionally isolated people identified in the AIPA study may be candidates to share knowledge, stories, passions, etc and maybe rediscover relationships through mediated networking.

We cannot talk about online social networks without focusing on Facebook usage. [START_REF] Adams | Senior user experience researcher at google[END_REF] observed that even if the average number of friends is around 130, most people interact regularly with 4 to 6 people. These few friends are considered as strong ties and are mostly people we meet often in real life. Social networks have changed some aspects of our weak tie relationships. Weak ties are unfrequent relationships with known people, such as old school mates. "In the past we would have to meet or phone them to catch up. Now, the social networks open an easy route to reconnect to them. Via newsfeeds and their wall, we can get back in touch in a lightweight manner. Although weak ties are much bigger in number, communication with them is unfrequent".

By introducing Social Networking Platforms (SNP) in our project, we aim at strengthening existing and close relationships for high sociable people, but also rediscover weak ties and develop hobby-oriented ties especially for those who feel isolated and are not involved in a real-life dense network. For the first ones, the web2.0 networking tools will bring a lot of (maybe light but frequent) exchanges; for the second ones, the tools will open the opportunity to create links with 'old' relationships or 'new' ones in relation with centres of interest.

From Point-to-Point Messaging to Community Interactions

In AIPA, family (and acquaintances) shared emails and photos through a dedicated service developed for this purpose in the project. Each member of the family shared his/her content with one older people. The elderly is the recipient, the family is the sender, with no mediated-interaction around a photo. But the elderly, as a matter of fact (see previous section), is asking conversing about a photo, about a message or about a video.

The contextual comments to a content is one of the signatures of SNPs. The publication of a photo (and its legend) becomes the scene of real feeds of reactions. People don't send content anymore as an attachment, but now publish them to a public (the public may be constrained and limited to a few friends). As blog posts, those publications are now a way to bring together people who interact as micro-and transient-communities; incidentally we observed that the published content becomes sometimes more an opportunity to meet friends than to collect comments about it.

Social networking appears as an interesting opportunity to keep elderly people involved in social interactions. Just like casual discussions at the baker's or when walking to the marketplace, social networking allows frequent, light and collective discussions with close family, but also with other people commenting on a photo or a web link.

Mazadoo: A Social Network to Connect Elderly People

The dedicated service provided by AIPA is quite simple to use, but the family has to subscribe, manage new credentials, upload their photos to this dedicated site, etc. It's expensive and time-consuming to manage several image repositories. Now, with the SNPs, e.g. Facebook, those sharing activities are easy and popular. In Mazadoo, we make the hypothesis that most relatives involved in our experiments will know and be regular users of social medias. We find that at the very first stage of the experiments, they actually are using Facebook. We hope that they will more easily and more often interact with their elderly family. We also hope that new participants will naturally become involved (nieces, cousins, grand-children, etc.).

Why is Mazadoo Using Facebook?

The aim of Mazadoo is to offer a link between people using a social network to communicate (with the computer interface proposed by the social network editor) and elderly people, who should be able to receive and respond from the social network, but using the Mazadoo TV interface. From the standpoint of the elderly, the underlying SNP is transparent. In fact, Mazadoo could be interfaced with any SNP.

Why the choice of Facebook against the competitors (Google, Twitter...)? From a technical point of view, the SNP must provide an open API in order for the Mazadoo platform to retrieve the interactions (messages, pictures, videos...) posted by the external users and inversely insert new interactions toward relatives on behalf of the elderly. The SNP should preferably offer a single tool to the relatives to support multiple interaction types (text, picture, video): send a private interaction to the elderly (like an email), send an interaction to a group of friends, including the elderly (like when you post on your Facebook wall), allow the friends to add comments to the contributions from others and provide some calendar functionalities (send an appointment to the elderly). The access to the SNP should be free, at least for the relatives. The SNP should also preferably be already known -and used -by a large audience of relatives. This indeed increases the possibility to get support from other relatives (children...), and thus accelerating the learning curve for using that platform. Retirement homes may also use the same SNP to communicate with the general public (and thus include the elderly, their relatives, and any external people interested in the activities), via a global page for the retirement home information.

Facebook is currently the only platform to respond positively to all those considerations. This also overcomes the only drawback of Facebook: its bad reputation about privacy disclosure. This reputation is based on cases that happened with Facebook accounts that are using the default privacy settings, which allow strangers to see your contributions. Mazadoo creates the Facebook accounts on behalf of the elderly, and tunes the privacy settings so that only friends can see their contributions. We gave courses to educate the family on these settings.

But Facebook is also THE social network: when you speak of social networks, the first platform that comes to mind is Facebook. Plugging Mazadoo into the favorite network of the end users makes it immediately usable by 600 million users worldwide. This predominent position of Facebook in the social networks also allows Mazadoo the benefit of a new information media: the Facebook pages. Facebook contains millions of pages about specific subjects that can be in the interests of the elderly: their favorite soap opera, their native village, a club for their hobby, the sport club or the school of their grandchildren, etc. This feature brings potential news hobbies to the ederly (not possible within AIPA).

The Services Provided by Mazadoo

These services can be split into two categories: personal services, provided in the room of the resident; and common services for all the residents of the retirement home such as common activities proposed by the coordinator of socio-cultural activities.

Individual Services. Using the remote control of the TV, the elderly channelflicks to the Mazadoo channel. This is a personal channel that provides, like a Facebook newsfeed, in a single screen, an adapted access to a set of services: messages from relatives, photo/video sharing from Facebook friends; reminders of activities proposed in the retirement home, via an interactive agenda from the retirement home Facebook page; a daily selection of videos, pictures and articles from local press (The Telegramme, a regional newspaper); and, in the near future, contents about their hobbies from Facebook pages.

Communication via social network friends.

The elderly person have a personal Facebook account. Relatives, as friends, benefit from all the usual Facebook features to communicate to the elderly : sharing status, pictures, videos (except links that cannot be adapted to Mazadoo); sending messages to all their friends including the elderly or private message to the elderly only. These interactions can be performed on a nomadic mode from anywhere (browser, smartphone). Some people (in particular teenagers) say that they never share with their parents or grand-parents what they share with their Facebook friends. This restriction is also true between private life and professional life. This multiple profile management is one of the issues we are working on. Adaptation. Obviously, the native Facebook web page cannot be read by the elderly on their TV screen. Mazadoo ergonomists and sociologists work with a representative panel of users to define the most adapted display of Facebook newsfeeds and content consultation. When the elderly channel-flicks to their Mazadoo channel, an adapted display of the newsfeed of her/his Facebook account, enriched with private messages, is provided. This homepage (Fig. 1) lists the latest received messages, pictures or videos, prefixed with the sender's profile picture. Because a TV screen is not adapted for the elderly to read a long text, all textual contents such as messages, comments or articles are vocalized (read by the TV through the Text-To-Speech technology).

Interaction. The elderly are not passive when receiving messages, pictures or videos. They can select the Like this button with the remote control. This action updates the Facebook content by adding the elderly to the list of people who like this item. For more interaction, the elderly can respond/comment by using the telephone to record a voice mail. By selecting the Respond button with the remote control, the phone rings and proposes to record a voice mail. The voice mail is seen as a link to an audio file and inserted as a comment to the original Facebook content.

Common services. One requirement of a retirement home is to provide visibility on their services (e.g. activities, meal menus) to visitors but also to remote family who are often also the payer. To fit this need, a Facebook page for the retirement home has been created: it compiles pictures and testimonies of activities, agenda for future events, comments, questions, etc. It can be consulted by people who say they fan.

Considering this agenda, Mazadoo enriched Facebook by providing to the retirement home coordinator the record of a reminder of an activity. This reminder is a voice message that is played to residents minutes before the activity. The phone rings and the message is played. A TV screen in the welcome hall of the retirement home displays a mosaic of contents automatically when dynamically extracted from the retirement home Facebook page. Visitors and residents have access to up-to-date meal menus, upcoming activities, pictures from previous events, etc.

Experimentation

Technical aspects. The Mazadoo architecture is based on cloud computing. Mazadoo services are provided by software running on servers, called the Mazadoo platform, hosted on the ImaginLab 4 data center. To minimize the number of servers, virtualization is performed. This single shared platform provides homogeneous services to two different retirement homes, located in different counties. It means that no servers are installed in retirement homes.

The Mazadoo platform, based on an Alcatel-Lucent solution, is a SIP powered infrastructure which provides: Voice and video Real time IP Communication, Unified messaging (text or voice messages deposit, notification and consultation), Text-to-Speech, conferencing, openness through standard XML Web Services for application development but also through the standard SIP protocol to support devices such as a Set Top Box. Mazadoo application is developed on top of this XML Web Service API. Users' devices are connected to the platform using SIP protocol. The Mazadoo application collects Facebook contents, aggregates and adapts them.

Participants. The 4 active volunteers plus 2 out of the 3 idle volunteers of our previous AIPA project have accepted to continue with the experiment of Mazadoo. Additionally Mazadoo is deployed in a second retirement home where 6 elderly have been recruited with 26 of their relatives. 6 other elderly persons interested in Mazadoo are to be enrolled. Sociologists and ergonoms are following the experiment and help in adapting Mazadoo to the observed usage. They closely follow the elderly and help them in learning how to use the system.

Conclusion

This paper describes a technical platform dedicated to the elderly in retirement homes. The goal is to offer services to preserve, enhance, or create social ties. The last evolution of the project Mazadoo has lead to new services belonging to the web 2.0 area. Elderly people are now connected to Facebook. For acceptability reasons, services are accessed via TV, remote control and phone. The elderly can receive messages (text, pictures, and videos) from their contacts, access to local news, check the calendar of the retirement home activities, etc. Moreover, they can now react to content, and post voice mail comments via their phone. This extends their cloud of friends. The project is conducted by a multidisciplinary team composed of industrialworkers, academics, engineers, ergonoms and sociologists. The prototype is deployed, installed in the individual rooms, and tested by some real users from two selected retirement homes. The professionals showed a strong interest and are opening Facebook pages for their institution to show activities and publications to the remote families, and also add agenda entries to the elderly peoples' newsfeeds. The cities involved are also animating Facebook content and communities. We are conducting interviews and usage studies since the end of the project.

Futures are now to add services such as: hobbies (accessing Facebook pages selected through preferences profile), social games, etc.

Fig. 1 .

 1 Fig. 1. Facebook news feed on TV

4

  ImaginLab is the very first platform in France to provide both hosted ICT technologies and a panel of users called the imaginers. ImaginLab data center provides services, such as Mazadoo, a panel of users through a very high speed internet connection based on FTTH (Fiber to The Home) and FTTB (Fiber To The Building) at 100 Mbps. More info on ImaginLab: http://vimeo.com/15623507, http://imaginlab.fr/blog-en/.

http://www.smartcareplatform.eu/content/tv-kiosk

Companymages/AIPA Project Home Page. https://www.companymages.eu, last visited January 2011.

Acknowledgments. The project participants wish to thank the staff of the residences of Kerlevenez (Brest, France) and Saint-Anne (Lannion, France), elderly volunteers and their families. Mazadoo project is supported by the French Media and Network Cluster (Pôle de compétitivité Images et Réseaux) and the French Governement (Direction Générale des Entreprises).


Patrick Maillé
email: patrick.maille@telecom-bretagne.eu

Bruno Tuffin
email: bruno.tuffin@inria.fr

On the ranking strategy in adword auctions

Search engines get revenue thanks to adword auctions, where commercial links are proposed and charged to advertisers as soon as the link is clicked through. Most search engines have chosen (or switched to) a revenue-based ranking and charging scheme instead of a bid-based one. We investigate here the relevance of that scheme when advertisers' valuation comes from a random distribution. We show that, depending on the search engine's click-through-rate, revenue-based does not always outperform bid-based in terms of revenue to the search engine. As a result, some search engines may have an interest to move to revenue-based ranking while others do not.

I. INTRODUCTION

Search engines are a key piece for web-browsing, allowing to easily find relevant web sites corresponding to given keywords. An important characteristic of their success, in addition to their efficiency, is that this service is free. In order to get a return on investment, search engines propose slots for commercial links to advertisers interested in specific keywords [1]. Those slots are allocated thanks to an auction scheme, hence the terminology adword auction.

There are usually a given number K of slots, ordered according to their visibility on the screen. Advertisers submit bids for specific keywords and each time there is a search on that keyword, advertisers are ranked and slots allocated according to a specific criterion: they can for instance be ranked according to their bid value, or by the revenue they can generate (this will be made clearer later). Advertisers may be charged each time their ad is displayed (scheme called Pay-Per-Impression), each time the ad is clicked (scheme called Pay-Per-Click), or each time the click results in a real sale (called Pay-Per-Transaction). The amount of money to be charged each time can be chosen among several possibilities:

• the first-price principle, where advertisers pay their bid,

• the so-called Generalized Second Price (GSP), where they pay the bid of the advertiser just below them in the ranking if the ranking strategy is based on bids; or the price such that the revenue generated corresponds to the (declared) one the advertiser below them if the ranking is based on revenue.

• Another option is to make use of Vickrey-Clarke-Groves (VCG) auctions: each advertiser pays the opportunity cost that its presence introduces to all other advertisers.

For more on adword auction description, the reader can look at [START_REF] Edelman | Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords[END_REF], [START_REF] Jordan | Designing an ad auctions game for the trading agent competition[END_REF], [START_REF] Lahaie | Sponsored search auctions[END_REF], [START_REF] Maillé | An overview of research on sponsored search auctions[END_REF] and the references therein.

The commonly used strategies are Pay-Per-Click and GSP [START_REF] Edelman | Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords[END_REF]. Though, there used to be some differences about the ranking strategy procedure used. While bid-based ranking was initially implemented by Yahoo!, Google has introduced a revenue-based ranking, ordering according to the value of the product of the bid by the Click-Through-Rate (CTR), which is the probability that the ad is clicked when displayed. Recently, Yahoo! has changed its ranking policy to a revenue-based one too.

Our goal in this paper is to investigate the best ranking strategy for search engines when Pay-Per-Click and GSP are applied to investigate whether (and when) the move from Yahoo! is relevant. Some papers have studied search engines optimal ranking strategies, see for instance [START_REF] Maillé | On the interest of introducing randomness in ad-word auctions[END_REF], [START_REF] Liu | Competing keyword auctions[END_REF]. In [START_REF] Maillé | On the interest of introducing randomness in ad-word auctions[END_REF], a comparison is made between a deterministic allocation based on GSP and a random assignment rule based on VCG. Deterministic allocation will produce a higher revenue for search engines but a lower utility for advertisers; it is argued that under competition, random allocation could eventually be the winner if advertisers have to choose. In [START_REF] Liu | Competing keyword auctions[END_REF], a game is applied between two search engines on the ranking policy (choosing between revenue-based and bid-based), given that advertisers choose to submit their ad at only one of them. A conclusion gives a potential reason explaining why Yahoo! has made the move. Though, the paper is based on the assumption that advertisers necessarily choose among the two engines. A practical justification of this could be based on budget constraints, but those are not included in the model of [START_REF] Liu | Competing keyword auctions[END_REF]. If advertisers bid truthfully and are sure that bidding is always beneficial, why not sending bids to both engines? We aim at investigating the best ranking strategy of search engines in that case. Actually, here the choice of a search engine does not have an influence on the other. Therefore the analysis can be performed by looking at an engine in isolation. The best strategy will depend on the engine parameters, such that its CTRs which can vary due to different presentations and be more or less attractive to the (heterogeneous) population.

The rest of this paper is organized as follows. Section II reviews the basic model, mostly inspired from [START_REF] Liu | Competing keyword auctions[END_REF]. Section III gives a closed-form expression for the average revenue of the search engine in terms of the probability distribution of the advertisers' valuation and the CTRs, for each engine strategy (bid-based and revenue-based). Section IV illustrates the kind of results that can be obtained by deriving the expression for a specific valuation distribution, namely the uniform one. A numerical comparison of the revenue is then performed in terms of the CTRs. Finally, Section V concludes and gives some directions for future research.

II. MODEL DEFINITION

We assume that a set of n advertisers submit bids to search engines for a given keyword. Bidders (advertisers) are assumed to be truthful about their valuation, and providers are assumed to apply Pay-Per-Click and GSP, so that submitting to all engines at the same time is the best option for advertisers (they will always end-up with a non-negative utility). As a consequence, search engines revenues are independent of the ranking-rule of competitors. The best strategy of an engine therefore only depends on its own choice. As a consequence, we consider a single engine in this paper, and compare the revenue when bid-based or revenue-based mechanisms are implemented, depending on the CTRs of advertisers. As we shall see, two engines may have different optimal strategies when the CTRs of advertisers differ from an engine to another.

Since our goal is to illustrate that phenomenon, we consider only one slot. As a side effect, GSP corresponds to VCG and truthful-bidding (i.e., bidding one's real valuation for a click on one's ad) is the optimal strategy for advertisers. In that context, consider n advertisers with respective bids (v i ) i∈{1,...,n} and CTRs (q i ) i∈{1,...,n} .

• A bid-based Pay-Per-Click GSP mechanism consists in giving the slot to the highest bidder i b := arg max i v i , and charging him the second-highest bid max i =i b v i at each click, hence yielding an expected revenue q i b max i =i b v i . • On the other hand, a revenue-based Pay-Per-Click GSP mechanism would give the slot to the bidder with the largest product bid×CTR, i.e., to the advertiser i r := arg max i q i v i . Then bidder i r would be charged at each click the lowest price p ir he could have bid while still getting the slot: p ir = 1 qi r max i =ir q i v i . As a result, the expected revenue for the seach engine would be q ir p ir = max i =ir q i v i .

To compare quantitatively the performance of both schemes, we consider a model definition similar to the one in [START_REF] Liu | Competing keyword auctions[END_REF]. Specifically, we assume that there are two classes of advertisers:

• high-quality advertisers, with CTR q h • low-quality advertisers, with CTR q l , such that q l < q h . The probability of being a high quality one is denoted by α. Advertisers also have different valuation per click v, distributed according to an absolutely continuous pdf F and density f , independent of the quality.

III. AVERAGE REVENUES

Remark that when considering specific instances, revenuebased ranking does not necessarily produce a larger revenue than bid-based one. Consider for instance n = 2 advertisers, where advertiser 1 has valuation v 1 = 0.7 and CTR q h = 0.6, and advertiser 2 has valuation v 2 = 0.5 and CTR q l = 0.1. In that case, with bid-based ranking rule, advertiser 1 is the winner, and the revenue will be v 2 q h = 0.3. With revenuebased ranking rule, v 1 q h > v 2 q l so advertiser 1 is still the winner, but the price per click is v 2 q l /q h and the generated revenue is v 2 q l = 0.05, less than with the bid-based strategy. The intuition is that the second-ranked bidder may be a lowquality advertiser, resuting in smaller price per click when using the revenue-based scheme. Note though that this is less likely to occur when the number of bidders increases.

In this section, we intend to quantify the prevalence and the expected impact of such situations, so as to determine the best revenue-making strategy. To do so, we derive closed-form expressions of revenues for both ranking strategies.

Proposition 1: The average revenue under bid-based ranking and charging is

R b = n(n-1)(αq h +(1-α)q l ) x(F (x)) n-2 (1-F (x))f (x)dx.
Proof: Thanks to the independence of valuation and quality, the average revenue under Pay-Per-Click and GSP is the product of the average CTR and the average value of the second highest bid. The average CTR is

αq h + (1 -α)q l .
The expected value of the second highest bid is determined from the law of order statistics. It is known that the density value of the k-th statistic X (k) , when ordered in a increasing order, within a sample of n independent random variables of density f and cdf F is (see [START_REF] David | Order Statistics[END_REF])

f X (k) (x) = n! (k -1)! (n -k)! (F (x)) k-1 (1 -F (x)) n-k f (x).
(1) Then the density of the second highest bid is (for

k = n -1) n! (n -2)! (F (x)) n-2 (1 -F (x))f (x).
The proposition immediately follows. Proposition 2: Define

G(x) = αF (x/q h ) + (1 -α)F (x/q l ) g(x) = α q h f (x/q h ) + 1 -α q l f (x/q l ).
The average revenue under revenue-based ranking and charging is

R r = n(n -1) x(G(x)) n-2 (1 -G(x))g(x)dx.
Proof: The expected revenue under the revenue-based rule is the expected value of Q × V , with Q the random value of the CTR and V the random valuation. Let G be the cdf of QV . We have

G(x) = P[QV ≤ x] = αF (x/q h ) + (1 -α)F (x/q l ).
The corresponding density is

g(x) = α q h f (x/q h ) + 1 -α q l f (x/q l ).
From ( 1), the density of the second largest value of

QV is n! (n -2)! (G(x)) n-2 (1 -G(x))g(x),
hence the proposition. The expressions in Propositions 1 and 2 are quite different, and difficult to compare in the general case. Nevertheless, we can remark that both are equal when there is no heterogeneity in CTRs, i.e., when α = 0 or α = 1. This was to be expected, since when all advertisers have the same CTR q the bid-based and revenue-based rankings are equivalent: for any bid profile, we have i b = i r , and the expected revenue of both schemes are the same:

q max i =i b v i = max i =ir qv i .
To study the case when there is heterogeneity among advertisers in terms of CTR, we consider a given distribution of valuations in the next section.

IV. EXAMPLE AND NUMERICAL ILLUSTRATION

Section III has provided general results. We analyze here how computations can be performed for a specific valuation cdf. We consider a uniform distribution over [0, 1], i.e.,

F (x) = x for x ∈ [0, 1].
In this case, under the bid-based strategy,

R b = n(n -1)(αq h + (1 -α)q l ) 1 0 x n-1 (1 -x)dx = n(n -1)(αq h + (1 -α)q l ) 1 n - 1 n + 1 = n -1 n + 1 (αq h + (1 -α)q l ).
Under the revenue-based strategy, first remark that ∀x ≥ 0,

G(x) = α min(1, x/q h ) + (1 -α) min(1, x/q l ).
Define β = α q h + 1-α q l and γ = α q h . The revenue can be expressed by decomposing the interval into three subintervals [0, q l ], [q l , q h ] and [q h , 1] as R r = n(n -1)

q l 0 x (βx) n-2 (1 -βx)βdx +n(n -1) q h q l x(γx + 1 -α) n-2 (α -γx)γdx +0.
Remark that the third line is obtained due to a null derivative on this interval. The two integrals can be computed; the first one yields

n(n -1)β n-1 q n l 1 n - βq l n + 1 ,
and the second one gives by multiple integration by part

n ˆ(γq h + 1 -α) n-1 (αq h -γq 2 h ) -(γq l + 1 -α) n-1 (αq l -γq 2 l ) - 1 γ [(γq h + 1 -α) n (α -2γq h ) -(γq l + 1 -α) n (α -2γq l )] - 2 (n + 1)γ ˆ(γq h + 1 -α) n+1 -(γq l + 1 -α) n+1 ˜.
Next figures illustrate the gain for specific parameters. q l = 0.1, q h = 0.7 q l = 0.1, q h = 0.3 q l = 0.5, q h = 0.7 α

Revenue

Bid-based Revenue-based Figure 1: Revenues in terms of α for different values of q l , q h , when n = 5. Here one can check that for low values of α, and low values of q l , the bid-based ranking rule may produce a larger revenue than the revenue-based one. On all the curves, when α ∈ {0, 1}, it can be verified that revenues are the same. Revenues also (obviously) increase with the proportion of high-quality advertisers, and with the CTRs.

Figure 2 displays the revenue in terms of the number n of advertisers for different CTR values. For a small number of advertisers the chances to get a larger revenue with bid-based ranking is larger. It is actually the case here when n = 2 for every value of α. But as the number of advertisers increases, this is less likely. This is due to the fact that we have more chances to have a high-quality advertiser in second position with the revenue-based rule, while the probability α of having Bid-based, q l = 0.1, q h = 0.7 Revenue-based, q l = 0.1, q h = 0.7 Bid-based, q l = 0.5, q h = 0.7 Revenue-based, q l = 0.5, q h = 0.7

Figure 3: Revenues in terms of n for different values of q l , q h , when α = 0.5. Figure 3 displays the revenue in terms of the number n of advertisers for different CTR values. As the number of advertisers increase, here again, revenue-based rule yields a larger revenue. Moreover, the average revenue asymptotically depends on the high-quality advertisers parameters with this rule (the two curves tend to coincide) because the second ranked advertisers tend to be a high-quality one. On the other hand, this is not true for bid-based ranking rule because the valuation is independent of the quality parameter.

Figure 4 displays the revenues in terms of q l , q h when n = 10 and α = 0.5. On this 3D curve, we have only considered the cases where q h > q l (revenues set to 0 otherwise). As a remark, bid-based and revenue-based get closer as q h and q l get closer, and are the same when q l = q h . Indeed, those two schemes are exactly the same in that case.

V. CONCLUSIONS

We have investigated in this paper the best strategy between revenue-based and bid-based rankings for search engines. This had already been studied in the literature when engines are in competition, but under the assumption that advertisers choose only one engine, an assumption that has not been justified. If we relax this assumption, then search engines can be considered in isolation (the strategy of the competitors does not have an influence on the revenue). We show here that under randomness over advertisers' valuation and CTRs, the best strategy is not always to apply revenue-based ranking and charging: it actually depends on the various parameters. We derive closed-form expressions for the expected revenues of both revenue-based and bid-based schemes. As an output, a search engine is able to decide, according to the advertisers parameters and reactions to the engine, the best strategy between the two choices.

Figure 2 :

 2 Figure2: Revenues in terms of α for different values of n when q l = 0.1, q h = 0.7.

Figure 1

 1 Figure1displays the revenue in terms of the proportion α of high-quality users for different CTR values. Here one can check that for low values of α, and low values of q l , the bid-based ranking rule may produce a larger revenue than the revenue-based one. On all the curves, when α ∈ {0, 1}, it can be verified that revenues are the same. Revenues also (obviously) increase with the proportion of high-quality advertisers, and with the CTRs.Figure2displays the revenue in terms of the number n of advertisers for different CTR values. For a small number of advertisers the chances to get a larger revenue with bid-based ranking is larger. It is actually the case here when n = 2 for every value of α. But as the number of advertisers increases, this is less likely. This is due to the fact that we have more chances to have a high-quality advertiser in second position with the revenue-based rule, while the probability α of having

Figure 4 :

 4 Figure4: Revenues in terms of q l , q h when n = 10 and α = 0.5.

ACKNOWLEDGMENT

This work was supported by Euro-NF Network of Excellence (http://euronf.enst.fr/) and the French research agency through the CAPTURES project (http://captures.inria.fr/).


Xingyu Zheng
email: xingyu.zheng@telecom-bretagne.eu

Patrick Maillé
email: patrick.maille@telecom-bretagne.eu

Cam Tu

Phan Le

Stéphane Morucci
email: stephane.morucci@swid.fr

Improving the Efficiency of Collaborative Work with Trust Management

The concept of trust has recently been introduced in the context of peer-to-peer networks, in order to deal with uncertainty regarding the behavior of imperfectly known agents. In this paper, we apply the notion of trust to situations of collaborative work, more precisely of document editing.

We suggest to use trust to compute a satisfaction score for each participant, in order to help select the successive editors of the document so as to avoid unnecessary readings by all collaborators after each modification. We assume that the document development process ends when all collaborators are satisfied with the quality of the document. Two mechanisms using trust to improve that process are proposed, and compared to the situation without trust. Extensive simulations suggest that trust can improve the efficiency of the collaborative work, while it can be implemented in a distributed manner.

I. INTRODUCTION

Many types of documents cannot be entirely produced by a single individual, and instead need to be jointly built by several collaborating participants. One can think of examples from diverse working sectors: law texts, research articles, project proposals, course textbooks, or encyclopedias (the most famous example being the online encyclopedia Wikipedia [www.wikipedia.org]). In all those cases, collaborative working is needed because of the prohibitive size of the document to be produced, and/or because of the diversity of the knowledge fields and competences involved.

There exists a variety of tools to facilitate collaborative work, such as online wikis or versioning softwares. Those are not indifferent to the outcomes of the collaborative working activity: it has for example been shown experimentally that structuring the processes in collaborative work systems improves the team results as well as the participant satisfaction [START_REF] Lowry | The impact of process structure on novice, virtual collaborative writing teams[END_REF]. Likewise, some advanced tools can be implemented to improve group awareness, parallelism, group memory, and coordination among collaborative workers [START_REF] Lowry | Using Internet-based, distributed collaborative writing tools to improve coordination and group awareness in writing teams[END_REF]. Now, an important challenge for collaborative work is to determine when and how to stop the document development process. Do all participants need to approve the final version? If so, when can it be considered that a version is a candidate for being sent for approval? Such questions might be difficult to answer when the number of collaborators becomes large. Likewise, it is not reasonable to assume that all collaborators go through the whole document after each modification by one of her peers, therefore some more fine-tuned management methods could significantly improve the development process efficiency.

In this paper, we suggest to address those questions by using the notion of trust [START_REF] Grandison | A survey of trust in internet applications[END_REF]. Several kinds of trust usages have been proposed, mainly for grid computing environments and peer-to-peer systems. Indeed, in those cases where each node shares its resources and benefits from those offered by its peers, trust mechanisms can be used to find the best peers to exchange with, or to avoid malicious nodes [START_REF] Ding | A dynamic trust management scheme to mitigate malware proliferation in P2P networks[END_REF], [START_REF] Li | A personalized group trust management system for collaborative services[END_REF], [START_REF] Zhang | A classification scheme for trust functions in reputation-based trust management[END_REF], [START_REF] Zhang | A trust inspection model based on society behavior similarity rule in dynamic networks[END_REF]. Remark moreover that inter-company (or even inter-personal) collaborations often rely on the (most often implicit) notion of trust, that can also be modeled and somehow automated in order to make the right business decisions [START_REF] Ruohomaa | Trust management for inter-enterprise collaborations[END_REF].

We propose here a new trust-based mechanism aimed at optimizing the process of collaborative document building. Our objective is to use trust as a tool to limit the total time and the total effort spent to reach the common objective of the group. More precisely, we intend to avoid unnecessary readings, and efficiently select editors during the development process.

The remainder of this paper is organized as follows. In Section II, we introduce the basic concepts of trust and show how it can be used to compute user satisfaction scores in a collaborative working environment model. Section III presents three models of collaborative working processes, where trust can be used to select the successive editors of the document. The performance of those schemes are compared through simulations in Section IV. We discuss the technical feasibility of our mechanism in Section V, and conclude and provide directions for future work in Section VI.

The results presented here follow the same model as the one we introduced in [START_REF] Zheng | Trust mechanisms for efficiency improvement in collaborative working environments[END_REF]. However, here we provide more complete performance results, considering a richer set of parameter values and also looking at a fairness measure (the effort repartition among participants). Moreover, with respect to the work of [START_REF] Zheng | Trust mechanisms for efficiency improvement in collaborative working environments[END_REF], this extended version describes an effective implementation of the proposed mechanisms through an OpenOffice plugin.

II. USING TRUST IN A COLLABORATIVE WORK

ENVIRONMENT

We consider a working system with a number I = |I| of agents who collaboratively contribute to the elaboration of a document. Those agents successively improve the document in an asynchronous manner, until it reaches a satisfying quality: an agent elaborates a first version of the document, that is afterwards edited and modified by the other agents in a certain order.

A. Definition of trust

Trust can be defined as a quantification of the confidence that an agent has in another agent to behave in an appropriate manner. Thus, trust represents the beliefs of one agent in the future actions of the other. In most trust-based models [START_REF] Golbeck | Inferring binary trust relationships in webbased social networks[END_REF], [START_REF] Khosravifar | An approach to comprehensive trust management in multi-agent systems with credibility[END_REF], [START_REF] Marti | Trust and reputation in peer-to-peer networks[END_REF], [START_REF] Suryanarayana | A survey of trust management and resource discovery technologies in peer-to-peer applications[END_REF], that quantification is summarized into a number in the interval [0, 1]. Consequently, trust values may also be interpreted as probabilities of the trusted agent to behave properly, from the point of view of the truster agent. We denote by I the set of agents, and for i, j ∈ I, by t i,j the trust value representing how much agent i trusts agent j.

The following conventions are classically taken:

• a trust value t i,j of 1 means that agent i perfectly trusts agent j, while t i,j = 0 means that agent i does not trust j at all; • the trust value t j,i can be different from t i,j , as trust scores materialize some subjective (thus, possibly biased) perceptions; • t i,i , representing the self-trust, is fixed to 1. For an agent i ∈ I, there are two ways of estimating how much she trusts another agent j ∈ I.

• Agent i can build her own trust score t i,j based on her experience from previous interactions with j. In peerto-peer systems, agent i can for example keep a record of satisfying and unsatisfying exchanges with peer j, possibly in the form of a weighted sum, where weights can be used to take into account the importance of the interaction or the time aspect [START_REF] Selc ¸uk | A reputation-based trust management system for P2P networks[END_REF]. In collaborative work, one can think of an evaluation score based on the contributions made by the collaborator in previous common works, which can also be quantified [START_REF] Javanmardi | Modeling trust in collaborative information systems[END_REF], [START_REF] Phan Le | Evaluating the trustworthiness of contributors in a collaborative environment[END_REF]. • If agent i does not have a sufficiently large history of interactions with j to compute an accurate trust estimation, she can ask some of her trusted agents to provide her with a recommendation score, and then combine the received values with her own trust in those recommenders to calculate t i,j [START_REF] Liu | Trust-based access control for collaborative system[END_REF]. In this paper, we do not consider that aspect of trust estimation; we assume that trust scores (t i,j ) (i,j)∈I 2 have been determined, and we rather focus on the use of those scores in collaborative work environments so as to optimize the joint work process.

B. Agent satisfaction scores during the collaborative work

An important feature of our model is that each editor k ∈ I has to associate to the document an evaluation score e k after her editing the document. That score, that we impose to be in the interval [0, 1], represents the subjective quality of the document for editor k. We assume here collaborators to be honest, so that they truthfully reveal the value of the document quality. Taking into account other reporting strategies driven by maliciousness or selfishness is above the scope of this paper.

The evaluation score is meant to be used by all the other collaborators, who combine it with their trust in the last editor of the document to compute a personal satisfaction score for the document. Formally, if Id last is the identity of the last document editor, each agent i ∈ I automatically computes the satisfaction score

s i := t i,Idlast × e Idlast , (1)
without even opening the document. This means that the participants take the declared score e Idlast into account, but are less optimistic in following the opinion of Id last when they do not trust that agent. In that sense, the multiplicative combination rule can be interpreted as providing a lower bound of the quality of the document: the document can be of high quality, but before agent i verifies that through a careful reading, she remains cautious and lowers the declared evaluation score, at a greater scale if she does not trust the last editor. Intuitively, this consists in viewing t i,Idlast as the trust value of i in Id last correctly estimating the quality of the document. An incorrect (from i's point of view) evaluation may be due to the last editor not being aware of all the elements in the document, or to agents i and Id last having different priorities and interests. That last possibility might be problematic in our case, since there would be here an incentive for editors to overestimate the evaluation. Therefore, in this paper we assume that the final objective of all agents is the same (namely, create a high quality -with the same standardsdocument), and that evaluation discrepancies do not stem from malicious behaviors but rather from imperfect perceptions.

III. MANAGEMENT OF COLLABORATIVE WORKING THROUGH TRUST

In this section, we introduce three different ways of managing the collaborative working environment. By management, we mean here the process of selecting the successive document editors.

Note that we implicitly assume that agents never edit the document at the same time, while most current collaborative work systems offer that possibility. However, in those cases the last agent to submit her version to the system is asked to deal with potential inconsistencies with the changes that have occurred since she last downloaded the document. That checking procedure could then be interpreted as an extra reading of the document, which would somehow be similar to the situation where agents successively modify the document.

A. Collaborative work model

We describe here the condition to end the editing process. We assume that each agent i ∈ I has a threshold b i ∈ [0, 1) that she considers to be the minimal satisfaction level for the document to be acceptable. Following the idea of collaborative work as a way to reach a consensus among participating agents, we consider that the document editing process stops when all agents are satisfied with the quality of the document, i.e., when the satisfaction scores (s i ) i∈I are such that

s i ≥ b i ∀i ∈ I. (2)
Until that condition is satisfied, we assume that users go on successively editing the document. We immediately notice that the process as we defined it may never converge: assume two agents i = j are such that their trust values for the other one are below their threshold level, i.e.,

∀k ∈ I, k = i ⇒ t i,k < b i k = j ⇒ t j,k < b j .
Then in that case, the condition (2) can never be met since evaluation scores e k are in the interval [0, 1].

For that reason, we slightly modify the calculation mode of satisfaction values, by introducing an aspect related to the document history. From now on, we consider that satisfaction scores (s i ) i∈I are computed according to the relation

s i := min (t i,Idlast +αn edit (i))×e Idlast , 1 , (3) where
• n edit (i) is the number of edits by agent i in the process, and • α is the bias in the satisfaction calculation, that corresponds to each extra edit of the document. The rationale behind that new expression is as follows: Since we assumed that agent evaluations are aimed at a common objective, and only differ because of imperfect knowledge of the document and of quality criteria, we can reasonably assume that the more an agent has gone through the document, the more confident she is in its quality. We upper bound the result by 1, so that satisfaction scores remain in the interval [0, 1].

Note that the new expression (3) ensures that the document development process stops if all unsatisfied agents have the possibility to edit the document.

In the remainder of this section, we describe the three development process management algorithms that are studied in the rest of the paper.

B. A naïve scheme: pure round-robin document editing

The first mechanism considered does not actually use trust values to manage the document development process. We only use satisfaction scores to decide when to stop the process, but the order in which participants edit the document is fixed. More precisely, we assume in that case that the "edit token" circulates in a round-robin fashion: if agents are numbered {1, 2, ..., I} (up to a permutation), then the identity of the editor just follows a simple rotation pattern 1, 2, ..., I, 1, 2, ..., until condition (2) is met.

Later in this paper, we will also assume that agent i may not always be available when it is her turn to edit the document. In the naïve scheme described here, we assume that in that case the token immediately goes to the next agent (i.e., the agent [(i mod I) + 1]), so that no time is lost waiting for i to be available again.

C. Using trust to choose the next editor: round-robin among unsatisfied agents

In this subsection, we propose to adapt the peer-to-peer strategy consisting in selecting, as the peer to download files from, one peer among all sufficiently trusted peers (i.e., those for which the trust level is above a given threshold).

In our collaborative work context, this can be translated into the following: the next editor of the document is still chosen according to a round-robin scheme, but only among agents i for which the current satisfaction value is below their quality threshold b i . In other words, we simply follow the scheme of the previous subsection, but skipping participants who are already satisfied with the current document quality.

Interestingly, that scheme can be completely decentralized. The circulation of the edit token can follow a pre-specified pattern as described in the previous subsection, with satisfied participants immediately transmitting it to their successor without modifying the document. (Notice that each participant computes her satisfaction score locally, based on the declared evaluation score and her trust values in the collaborators.) Moreover, detecting the end of the process is made easier: actually no agent will edit the document anymore if condition ( 2) is satisfied, so there is in any case no risk of unnecessary edits. To officially stop the process, one can imagine that if a participant receives the document and notices she was the last editor, then this means all other participants were satisfied with the document, and thus she can declare the process as terminated. In the case when collaborators are not always available, a more developed method needs to be defined. A possibility would be to automatically add to the document a flag stating that the agent was unsatisfied with the current version (when asked to edit it) but was unavailable; that method would avoid wrongly stopped processes.

D. Having the least satisfied agent improve the document

We now follow a different strategy inspired by peer-to-peer networks, where peers choose to download their requested files from the host with the highest trust value [START_REF] Ding | A dynamic trust management scheme to mitigate malware proliferation in P2P networks[END_REF]. We adapt that policy to the context of collaborative work, by giving the edit token to a collaborative agent k for whom the satisfaction score is the furthest below her threshold, i.e., the next editor is the (an

) agent k such that s k -b k = min i∈I (s i -b i ).
Intuitively, that third scheme should be more efficient than the one defined in Subsection III-C, since we choose to specifically target the minimal satisfaction minus threshold value, and the process ending precisely depends on that minimal value (it stops when min i∈I s ib i ≥ 0).

On the other hand, the potential extra efficiency of that scheme will have a price in terms of applicability, since implementing it in a fully decentralized way becomes difficult. Some possible solutions to choose the next editor according to that policy are given below.

• A central entity can be used to collect all satisfaction scores and notify the next editor. The satisfaction scores could be computed locally by each agent and transmitted to the entity. We can also imagine that they be computed within the central entity to minimize communication exchanges, but that would imply that each participant i ∈ I uploads her trust vector (t i,1 , ..., t i,I ) to the entity, which might not be well perceived: since trust values are private and sensitive data, agents may be reluctant to reveal them to the system, even with the assurance that they will not be disclosed to the other collaborators. Moreover, that solution would have the classical drawbacks of centralized systems, in terms of fault tolerance and communication overhead. • For the implementation to remain decentralized, a full rotation among participants without editing could be performed to collect the identities of the candidates for being the next editor. More precisely, in the document metadata, the identity of the current least satisfied collaborator k and the value of her dissatisfaction b ks k are checked out and updated if necessary, so that at the end of the round the document carries the identity of the next editor. While that scheme is decentralized, it still has the drawback of revealing some information about the trust value t k,Idlast , since all agents know the evaluation score e Idlast and thus have access to the dissatisfaction level of user k.

Due to those extra difficulties with respect to the mechanism proposed in Subsection III-C, we should be inclined to prefer that scheme over the simpler round-robin among unsatisfied clients, only if the efficiency gain of the development process is significant. Actually, the performance evaluation that we present in the next section does not show such a large gain.

IV. EXPERIMENTS

This section presents some simulation results aimed at evaluating the performance of the three management methods of Subsections III-B, III-C, and III-D.

A. Simulation model

The model we consider in this paper has several parameters, namely, the set of participants I, the trust values (t i,j ) i,j∈I , and the bias α that previous edits introduce in the satisfaction score computation (3). We moreover describe now how we model the participant behavior.

1) Trust values and satisfaction score computation: Trust values (t i,j ) i,j∈I are chosen randomly, according to a uniform distribution on an interval [t min , 1]. In our simulations, we consider different situations, with t min = 0.2, t min = 0.5, and t min = 0.8 to model low-trust and high-trust communities.

As regards the computation of the satisfaction score s i after each document modification, we follow relation [START_REF] Grandison | A survey of trust in internet applications[END_REF], where the bias α equals 0.1 in our simulations. Similarly, the quality threshold of each participant i is fixed to the same value b i = 0.9 ∀i ∈ I.

2) Contributor's availability:

In a collaborative working system, the participants may be online or offline over time. To model that aspect, we discretize time into slots (a slot corresponding to an agent editing the document), and consider that at each time slot, each participant is available with a given probability, independently of all other events. Unless otherwise stated, we fixed that availability probability to 0.5 in our simulations. With respect to the problem of contributors not being available, our three management schemes behave as follows:

• Naïve (round-robin) scheme: if the editor who is supposed to edit the document is not available, then the token immediately goes to the next one and no time slot is lost. • Round-robin among unsatisfied agents: if the next unsatisfied agent is unavailable, then the token goes to the next unsatisfied agent in the predefined order. If all unsatisfied agents are unavailable, then the time slot is lost (nobody edits the document). • Next editor=least satisfied agent: the edit token immediately goes to the unsatisfied participant i with the minimum value of s ib i , among available participants. As a result, like for the previous scheme the time slot is lost when all unsatisfied agents are unavailable. 3) Computation of the evaluation score: In a real implementation of our mechanisms, the evaluation score e would be set by the editor after her editing the document, according to her personal competences and knowledge of quality criteria. In our simulation model, we introduce some asymmetry among participants by associating to each one i ∈ I a performance level q i ∈ [0, 1], that can represent the "writing quality" of participant i. That performance level q i is here randomly chosen for each participant i ∈ I, according to a uniform law on [0.5, 1] in our simulations.

We then assume that each participant improves the quality of the document -at least from her point of view-when editing it, and that this improvement increases with her writing quality. More precisely, in our simulations the evaluation score e k set by editor k is computed according to the formula

e k := s k,prev + (1 -s k,prev ) × q k , (4)
where s k,prev is the satisfaction value that k had just before editing the document.

B. Performance measures

The efficiency of the document development process is measured by three performance metrics:

• the total duration of the document development process, that is measured by the number of iterations until a satisfying document quality is reached; • the total effort spent by the collaborating community during the whole process. To compute that measure, we use the quality parameter q k of the previous subsection, to also represent the effort spent by editor k each time she edits the document 1 . The total effort is then the sum over all editing slots of that value q k ; • the repartition of that effort among collaborators, that is quantified by the coefficient of variation of the participant individual efforts during the development process.

C. Results

We now present the performance comparison among the three schemes defined in Section III, focusing on the influence of the size of the collaborative community and the availability of participants.

In each case, we simulated the development of a document a sufficiently large number of times, so that the width of the 90% confidence intervals were at least 100 times smaller than the mean values plotted.

1) Effect of the number of participants: Convergence time. Figure 1 shows the average number of iterations that are needed before the document reaches a quality that is sufficient to all participants, for the three mechanisms defined before, while Figure 2 compares that convergence time for the trust-based schemes to the one for the naïve roundrobin mechanism. As could be expected, the convergence is faster when collaborators trust each other (i.e., when t min is larger). On the other hand, it unexpectedly appears that the naïve round-robin mechanism is the one that performs best when the number of collaborators is below 10. This is due to the fact that collaborators are assumed to sometimes be unavailable: while in the round-robin case, the documents goes on being improved even if no unsatisfied agent is available, this is not the case for our trust-based schemes and some time slots may be lost. On the contrary, when the number of collaborators becomes large, then such situations occur less frequently, and based management schemes always yield an improvement with respect to the naïve round-robin mechanism: when t min = 0.5, the total effort is reduced by about 20% for I = 50 collaborators, but the improvement is of less than 10% if there are less than 10 collaborators. Effort repartition. We plot in Figure 5 the variation coefficient of the effort repartition among participants. Simulation results indicate that both trust-based schemes allow a fairer repartition of the total effort than the naïve mechanism. To summarize, the simulations suggest that with few collaborators, introducing trust-based management will not improve the speed of the development process, and the improvement in terms of effort will be quite small. Therefore, in those cases it might not be interesting to use trust. On the other hand, when the number of collaborators becomes large, then applying one of our trust-based schemes yields a non-negligible improvement, in terms of time, of effort spent, and of fairness of the effort repartition. For both performance measures, the difference between the two trust-based schemes is always at the advantage of the one targeting the least satisfied agent, but remains small when compared to the improvement brought by trust. This suggests that the round-robin among unsatisfied agents should be preferred due to the implementation and privacy drawbacks of the other scheme.

2) Effect of the mean availability of participants: We now investigate the influence of participants availability over the development process. More precisely, we vary the probability of each individual user to be available, and observe the consequences on our performance measures. For simplicity reasons, we assume all agents have the same probability of being online. Simulations were carried out for a collaborative working group with I = 20 participants. Convergence time. Figure 6 shows the ratio in terms of convergence time of trust-based mechanisms with respect to the round-robin scheme. Interestingly, we remark that trust- based mechanisms yield an improvement in terms of time only when the participant availability is within an interval (around [0.3, 0.85] for our simulation parameters when t min = 0.5), while for extreme values convergence is faster with the roundrobin mechanism. For low values of the availability, this can be explained in terms of time slots losses (i.e., time slots where no agent edits the document), that occur for our trust-based mechanisms and not for the round-robin. For high values of the availability (take the extreme case where all agents are always available for simplicity), the difference may come from the fact that in the round-robin mechanism, all participants (even the satisfied ones) edit the document. There might be some cases where an agent is already satisfied with the document, but has a very high writing quality: in that case, with the round-robin mechanism the agent will improve the quality of the document significantly (thus benefitting to all participants), while she would not have edited it with a trust-based scheme.

Total effort. The same phenomenon occurs when considering the effort metric when participants are available very often: the round-robin scheme performs better. However this is not true anymore for low availability values since lost time slots have no impact in terms of effort.

Those results are illustrated in Figure 7, that moreover shows that the two trust-based schemes are almost insensitive to participant availability, while the total cost with the roundrobin scheme strongly decreases when participants are more frequently available. As a result, when the availability of participants is not known a priori, using trust enables to still control the total amount of effort needed to reach a satisfying document quality. OpenOffice has been chosen as the principal document editor in many companies, schools, as well as important projects. In order to increase the efficiency of the collaborative working process, we suggest to enable the use of our trust model in the OpenOffice editor using a dedicated plugin that interacts directly with OpenOffice menus. The plugin would be in charge of updating the evaluation records in the metadata (and possibly of storing trust values and computing satisfaction scores).

An OpenOffice text document is in fact a zipped package. An example of such a document is given below: The file meta.xml contains information about the document itself (metadata information). We propose to use that file to store data computed from our trust-based evaluation model. OpenOffice metadata information rely on six Dublin Core [START_REF] Weibel | The Dublin core: A simple content description model for electronic resources[END_REF] elements (title, subject, description, creator, date, language), and eight own defined metadata elements (generator, initial-creator, creation-date, keyword, editing-cycles, editing-duration, user-defined, document-statistics).

OpenOffice also allows users to define their own metadata parameters via a user-defined field. We exploit that flexibility by adding four user-defined fields into the metadata of the processed document:

• transaction_Id, that is a unique identifier for the transaction (i.e., the last edit); • E_last, the evaluation score set by the last editor;

• Id_nextEditor, the identity of the next editor (following the trust-based scheme); • (in order to have a fully decentralized scheme) trust_records: that element stores all trust values between participants in a format [Id1, Id2, t Id1,Id2 ] that represents the trust value of agent Id1 on agent Id2, for all Id1,Id2∈ I. Remark that we choose here to regroup all trust values within the document itself (more precisely, in its metadata) so as to prevent the need for extra software or files locally stored by agents. This implicitly means that in a first phase, agents are asked to declare their whole trust vector, which they might be reluctant to do. However, we believe that implementation will be simpler (because it is stand-alone) than other possibilities where trust vectors have to be stored and called locally.

Since the trust values of the type t k,k always equal 1 for all k ∈ I, we suggest to use the values t Id1,Id1 in trust_records to store the quality threshold b Id1 of each user.

Our plugin interacts directly with OpenOffice menus: when a menu item is selected, the corresponding method of our plugin is called instead of the genuine OpenOffice one. When a participant terminates the editing process, she has to select the Export menu which has been re-implemented by our plugin. The editor is then asked to enter an evaluation score that is then stored in the E_last field by our plugin. It also generates an identifier for that transaction, that is stored in the transaction_Id field. Finally, our plugin computes satisfaction values based on the identity of the last editor, the fields trust_records, transaction_Id, and E_last values; it then chooses the next participant that has to modify the document according to the policy chosen (roundrobin among unsatisfied agents, or least satisfied agent). The corresponding participant identity is then stored in the Id_nextEditor field. All those metadata are then saved in the meta.xml file. Only the elected participant(s) can then edit the document. When all satisfaction values are above the acceptability threshold, the editing process is considered terminated, and our plugin locks the document to prevent further modifications. To prevent malicious modifications and unauthorized access (to trust values for example), all content is encrypted using an X509 certificate. Only our plugin is able to decrypt that document.

The plugin has been developed using Java technology and relies on OpenOffice (v3.1) Java API. Metadata manipulation is made possible thanks to Java library jOpenDocument [www.jopendocument.org], a GPL free library. Bouncy Castle free libraries [www.bouncycastle.org] have been used for encryption.

VI. CONCLUSIONS AND FUTURE WORK

In this paper, we have proposed some new management methods, based on the notion of trust, to improve the process of collaborative document writing. Our simulation results show that trust can help reduce significantly the time and effort spent until a satisfying document version is produced, especially in the realistic cases when the number of collaborators is large and collaborators are not always available to edit the document.

We considered a simple model with strong assumptions to highlight some basic phenomena that occur when trust is used in such contexts. However, it would be interesting to extend that model in future work, in different directions. One could be to avoid asking editors to evaluate the document themselves; indeed that can be an incentive to declare an over-estimated score if agents' interests are not perfectly aligned. A possibility would be that the document be checked and evaluated by some collaborators [START_REF] Lowry | The impact of process structure on novice, virtual collaborative writing teams[END_REF], [START_REF] Sumiya | Development of a multimedia document management system for cooperative work environment[END_REF]. That would improve the accuracy of the evaluation score, but would also imply some extra evaluation effort.

Also, our simulations rely on a model of user behavior determining the quality improvement of each edit. Since in reality the contribution of each participant is hard to predict, some experiments of real collaborative work (for example with users jointly producing an OpenOffice document using our plugin) could give more insight about the efficiency of our trust-based mechanisms.

The assumption that we make in this paper, of all collaborators having the same objective, is quite strong. We would like to relax it and introduce some objective misalignment among participants, so that the interaction has to be robust to agent selfishness: to ensure that property, the system should be studied as a noncooperative game [START_REF] Osborne | A Course in Game Theory[END_REF], for which the agent equilibrium strategies should lead to a satisfying outcome.

As another research direction, we would also like to consider the possibility for agents to update their trust vector during the document development process, based on their perception of the contributions from their peers, as is suggested in [START_REF] Barber | Soft security: Isolating unreliable agents from society[END_REF] to detect malicious agents.

Finally, the probabilistic interpretation of the satisfaction value computation could be continued and enriched, in two directions:

• that computation could be based not only on the last version but also on the previous ones (e.g., if some participants do not know the last editor but highly trust the previous one),

• the trust values could be multidimensional, for example following the representation introduced in [START_REF] Jøsang | Artificial reasoning with subjective logic[END_REF].

Figure 1 .

 1 Figure 1. Total time until convergence for the three possibilities of next editor selection.

Figure 2 .Figure 3 .

 23 Figure 2. Time gain due to trust-based management.

Figure 4 .Figure 5 .

 45 Figure 4. Effort gain due to trust-based management.

Figure 6 .

 6 Figure 6. Time gain due to trust-based management.

Figure 7 .

 7 Figure 7. Total effort until convergence

In our opinion, it is quite realistic to consider effort and quality to be positively correlated, but the model can be complemented further by adding some randomness.

ACKNOWLEDGEMENTS

This work has been partially funded by the French Agence Nationale pour la Recherche through the FLUOR project.


Patrick Maillé
email: patrick.maille@telecom-bretagne.eu

Bruno Tuffin
email: bruno.tuffin@inria.fr

Jean-Marc Vigne
email: jm.vigne@telecom-bretagne.eu

Economics of Technological Games Among Telecommunication Service Providers

The telecommunication world keeps evolving, with the development of new technologies, and operators have to wonder if investing in the costly infrastructures and potential licenses as well as maintaining existing technologies is worthy. This has to be investigated in a competitive context. We propose in this paper to model and analyze a three-level game between two operators. At the highest level operators decide which technology to implement, possibilities being here 3G, WiFi and WiMAX. At the intermediate level, they fix their service price, while at the lowest level, customers choose their provider depending on price and quality of service. The model is analyzed by backward induction, where decisions at a level depend on the equilibria at the lower levels. Different real-life cost scenarios are studied, depending on whether or not operators already own the infrastructures and licenses: our model should help understanding their final decision.

I. INTRODUCTION

Competition among telecommunication providers is fierce. Providers do not only compete for customers by playing on their price and offered quality of service (QoS) but, due to the so-called convergence with terminals supporting multiple interfaces, they also have to choose which technology to operate. That issue is of increasing interest with the introduction of new interfaces and the possibility to get a license, such as currently with WiMAX [1] or LTE. The questions an operator should then ask itself are the following: is it worth paying a license and an infrastructure for being present in the new technology? Will it help to attract more customers, but then isn't it at the expense of other technologies already implemented? This has to be decided given the current positions (and forecasted decisions) of competitors, which also aim at maximizing their revenue. Another typical illustration comes from the third generation wireless licenses in France where the regulator wants to open a fourth license to increase competition. Candidates have to ponder the total cost with the revenue they will get from customers. This paper aims at helping with such decisions, not only for the operator but additionally for the regulator to define the appropriate license fees.

The model we present is made of three levels, corresponding to three different time scales. At the lowest level, given fixed operated technologies and service costs, customers spread themselves among available operators in order to get the "best" combination of price and QoS, where the QoS (or the congestion) they get depends on the choice of the other users. We assume that users are infinitesimal, so that the (selfish) decision of a single individual does not have any influence on the system behavior. The equilibrium analysis is therefore provided by the so-called Wardrop's principle [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]. This equilibrium is for fixed prices, but providers determine beforehand (by backward induction) what the resulting equilibrium (and therefore their revenue) would be for a given price profile, and play the corresponding pricing game accordingly. This constitutes the second level of game, the general framework being again that of non-cooperative game theory, and the equilibrium notion, the Nash equilibrium [START_REF] Osborne | A Course on Game Theory[END_REF], with atomic players here. Finally, at a larger time scale, providers can decide which technologies to operate. In order to make that decision, they have to compute what their revenue would be at the equilibrium or equilibria (if any) of the lower-level pricing game, and compare it with their costs. That choice, which also depends on the strategy of competitors, will be made in order to reach again a Nash equilibrium for this "technology game".

While users' distribution among providers and pricing games have been quite extensively studied [START_REF] Acemoglu | Competition and efficiency in congested markets[END_REF], [START_REF] Bernstein | A general equilibrium model for industries with price and service competition[END_REF], [START_REF] Maillé | Analysis of price competition in a slotted resource allocation game[END_REF], [START_REF]Price war with partial spectrum sharing for competitive wireless service providers[END_REF], [START_REF] Manshaei | On wireless social community networks[END_REF], [START_REF] Xing | Price dynamics in competitive agile spectrum access markets[END_REF], there is to our knowledge no other paper dealing with the technology game, especially using the result of the pricing game. Other multilevel games exists, the most notable one being [START_REF] Njoroge | Competition, market coverage, and quality choice in interconnected platforms[END_REF], but it rather models the interactions between Internet service providers and content providers. Our goal is here to answer the question about which technology a provider should implement, given the potential revenue and the potential infrastructure and license costs. We have not seen elsewhere this kind of study in a similar competitive context. We also provide typical and real-life competition situations of providers already installed but which could try to extend their technological range to increase their revenue.

The paper is organized as follows. In Section II, we describe the mathematical model and three levels of game for its analysis. Section III describes the user game, characterizing the (Wardrop) equilibrium. Section IV is devoted to the intermediate game on prices. it considers an average coverage zone and reviews the capacities for the different wireless technologies. Based on those numbers, the revenues at the equilibrium of the pricing game are displayed for each combination of technologies implemented by the providers.

Section V relates those revenues with implementation costs representative of real-life competition among provider. This leads to a technological game that is solved and analyzed for each considered specific scenario.

II. MODEL

Consider N providers in competition for customers (later on, we will take N = 2, but we keep the model description as general as possible). Each provider has to decide which set of technologies it will operate. There is a set T of available technologies, basically for us

T = {3G, WiMAX, WiFi}.
This set is partitionned into two subsets T p and T s : for the technologies in T p (= {3G, WiMAX}), each operating provider owns a license and a part of the radio spectrum, using it alone. On the other hand, for a technology in T s (T s = {WiFi} for us), the spectrum is shared by the customers of the competing providers. Define also S i as the set of technologies operated by i.

We assume that each provider i (1 ≤ i ≤ N ) prespecifies a price p i per unit of flow that a customers needs to pay if using its network. This price p i is the same whatever the technology used by customers at provider i. We also assume that users have terminals with multiple interfaces, allowing them to use any technology, and that they can sense the available QoS. As a consequence, they can choose the technology and provider offering the best combination of price and QoS.

Formally, let d i,t be the flow demand experienced at technology t by provider i, and d the vector of all flow demands. QoS is modeled by a congestion function ℓ i,t (d i,t ) for technology t ∈ T p operated by provider i, and ℓ t ( j d j,t ) for t ∈ T s , functions being assumed nonnegative, continuous and strictly increasing in terms of the total. Customers try to minimize their perceived price at technology t and provider i, defined by

pi,t (d) =        p i + ℓ i,t (d i,t ) if t ∈ T p p i + ℓ t   j d j,t   if t ∈ T s . (1)
This means that the perceived price is a linear combination of a monetary cost (the price charged) and a QoS cost (the congestion level). This model extends the one proposed in [START_REF] Acemoglu | Competition and efficiency in congested markets[END_REF], since here different technologies can be operated by a single provider, and some can also be shared.

We also assume that total user demand is a continuous function D(•) of the perceived price p, strictly decreasing continuous on its support and differentiable, with lim p→∞ D(p) = 0.

The system is characterized by by three different time scales: for all technologies with positive demand, the perceived price is the same, other technologies have higher larger perceived prices (otherwise some users would have an interest to change to a cheaper option).

• At the intermediate time scale, providers compete for customers by playing with prices for fixed sets of implemented technologies. The goal of each provider i is to maximize its revenue

R i = t∈Si p i d * i,t , (2)
playing on price p i and making use of what the user equilibrium d * = (d * i,t ) i,t would be for a given price profile. Since the revenue of a provider depends on the price strategy of competitors (through the user equilibrium), this is analyzed using non-cooperative game theory.

• At the larger time scale, providers have to chose which technologies to invest on. This is again analyzed thanks to non-cooperative game theory, using the equilibrium situation (p * i ) 1≤i≤N of the intermediate level.The goal is here again to optimize

R i = t∈Si p * i d * i,t -c i,t
(where c i,t represents the license and infrastructure costs to provider i to operate on technology t), by playing with the set S i .

III. THE USER LEVEL

The outcome of the interactions among nonatomic users should follow Wardrop's principle [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]: only cheapest options are chosen, and total demand corresponds to that cheapest price. Formally, given a technology configuration S = (S 1 , ..., S N ) and a price configuration (p 1 , ..., p N ), a Wardrop equilibrium is a tuple

(d 1,1 ..., d N,|S N | ) of positive real num- bers such that                      ∀i ∈ N , ∀t ∈ S i pi,t =      p i + ℓ i,t (d * i,t ) if t ∈ T p p i + ℓ t ( j:t∈Sj d * j,t ) if t ∈ T s ∀i ∈ N , ∀t ∈ S i d * i,t > 0 =⇒ pi,t = min j∈N ,τ ∈Sj (p j,τ ) i∈N t∈Si d * i,t = D( min i∈N ,t∈Si (p i,t ))
(3) The first equality gives the perceived price for each pair (operator, technology), the second one states that users choose the cheapest options, and the last one comes from the demandprice relation.

The nonatomic game that is played among users falls into the widely-studied set of routing games [START_REF] Beckmann | Studies in the economics of transportation[END_REF], [START_REF] Aashtiani | Equilibria on a congested transportation network[END_REF], [START_REF] Roughgarden | Selfish Routing and the Price of Anarchy[END_REF]. Indeed, the user problem can be interpreted as finding a route (i.e., a pair provider-technology) to reach the global internet, while congestion effects occur. Several powerful results exist for that kind of games, that we apply to prove existence and uniqueness of a user equilibrium for our particular problem.

Proposition 1: There always exists a user equilibrium. Moreover, the corresponding perceived price at each providertechnology pair (i, t) is unique.

Proof: Since all congestion functions are strictly increasing and demand at price 0 is strictly positive, then at an equilibrium all perceived prices are strictly positive. Then the existence of a Wardrop equilibrium directly comes from Theorem 5.4 in [START_REF] Aashtiani | Equilibria on a congested transportation network[END_REF] (just a few extra verifications are needed for the specific -and unrealistic -case where some providers set their price to 0).

For a Wardrop equilibrium, we denote by p the common perceived price of all options (i.e., pairs provider-technology) that get positive demand. Assume there exist two Wardrop equilibria d and d with different perceived prices, say p and p, and assume without loss of generality that p > p. Since the demand function is strictly decreasing on its support, then total demand for d is strictly smaller than for d. This means that either total demand on one of the shared technologies, or demand on one proprietary technology of a provider, is strictly smaller for d than for d. But following Wardrop's principle, this would mean that the corresponding cost for that technology is the minimal cost p for d, that is strictly larger (due to congestion cost increasingness) than for d, itself being larger than p, a contradiction. As a result, the perceived price p for options with demand is unique, and we necessarily have for each provider-technology pair (i, t):

t ∈ T p ⇒ pi,t = max(p, p i + ℓ i,t (0)) t ∈ T s ⇒ pi,t = p i + max(p -p t , ℓ t (0)),
where p t = min{p i , t ∈ S i }. All perceived prices are unique, which concludes the proof.

IV. THE PRICING GAME

In this section, we propose to analyze the pricing game in the case of two providers whatever the subset of technologies in {3G, WiMAX, WiFi} each of them implements. Providers aim at maximizing their revenue.

We assume that a set of users is positioned in a predefined zone and that all users have a terminal with multiple interfaces. We have in mind a specific zone covered by a 3G UMTS base station in France (composed of about 10 4 such zones). We additionally assume that the zone is covered by a WiFi 802.11g access point and a single 802.16e (WiMAX) base station. In our numerical application, we will choose realistic values of demand and capacities, and will only consider downlink for convenience. The realistic capacity values we consider are

• 28 Mb/s per operator for 3G [START_REF] Netpro | Le débit sur le réseau 3G d'Orange passe à 14 mb/s[END_REF];

• 40 Mb/s, still in downlink, for WiMAX technology [START_REF] Mag | WiMax 101 : the Evolution of WiMax[END_REF]; • 25 Mb/s for WiFi [START_REF]WiFi[END_REF]. We moreover assume the demand function D to be linear, given by (in Mb/s) D(p) = 300 -3p, with p in e/month. Hence no user is willing to pay more than 100 e monthly to benefit from the service. In our numerical computations, the congestion function ℓ i,t of a couple demandtechnology (i, t) is supposed to be the average waiting time of a M/M/1 queue of parameters (d i,t , C i,t ) if the technology t belongs to the set T p , and of parameters ( t∈Si d i,t , C t ) if t belongs to T s . Recall that the average waiting time of an M/M/1 queue with parameters (λ, µ) is 1/(µλ) -1/µ.

Using those parameters, we investigate numerically for each couple of technology sets (S 1 , S 2 ) the existence of a Nash equilibrium on the price war. Recall too that a Nash equilibrium is a price profile

(p * 1 , p * 2 ) such that ∀p 1 , p 2 ≥ 0 R 1 (p * 1 , p * 2 ) ≥ R 1 (p 1 , p * 2 ) and R 2 (p * 1 , p * 2 ) ≥ R 2 (p * 1 , p 2 ).
In words, no provider can improve its revenue by deviating unilaterally. In our numerical computations, we have always found that for any technology profile where shared technologies are operated by only one provider, there exists a unique non-null Nash equilibrium. However, proving analytically the existence and uniqueness of such a Nash equilibrium would deserve more work. To illustrate how those Nash equilibria are found, consider for instance the case where the two operators decide to propose only a WiMAX access to the users. Figure 1 displays the best responses (i.e., prices maximizing their revenue) of providers in terms of the price of the other. A Nash equilibrium is an intersection point of those two curves.

One can check that there exists a single non-null intersection point between the two curves, here approximately equal to (72.5, 72.5).

Table I displays the monthly revenues in euros of operators at the (non-null, if any) Nash price profile, for every technology profile. It is noticeable that the revenue is null for the two operators in a configuration in which they both choose the WiFi technology. This observation can be interpreted intuitively: if both providers implement WiFi, consider a nonnull price profile. For a provider, it is always worthy to price just below the competitor to attract all the WiFi users and then increase its revenue. But this is also valid for the competitor, so that we end up with a price profile (0, 0).

V. ILLUSTRATIVE TECHNOLOGICAL GAMES

In the previous section, we have seen how, whatever the set of technologies implemented by the providers, an equilibrium can be reached in the pricing game, with revenues from I. We now aim at investigating for different scenarios the outcome of the game on technologies. As in the previous section, we consider a zone (typical of France) covered by a single base station, for a period of one month. Estimated infrastructure plus license costs, if any, will therefore be divided by the approximately 10 4 zones in France and by the duration in months of the license rights. Let c i,t be the per zone and per month cost at provider i for technology t. The total technological cost at each provider is assumed additive, that is the cost total cost of provider i is c i,Si = t∈Si c i,t . This yields a cost matrix ((c 1,S1 , c 2,S2 )) S1,S2⊂T . Subtracting it to the revenue matrix of Table I, we get a net benefits (or utility) matrix that can be analyzed to determine if there is a Nash equilibrium at this largest time scale.

A. Symmetric game

For this first real-life scenario, we consider two incoming providers with symmetric costs. We assume the following costs: 3G license for 10 years of 649 Me [START_REF] Mobinaute | 4ème licence 3G : Orange fait pression auprès du gouvernement pour ralentir son attribution[END_REF], and infrastructure cost of 1.4 Be [START_REF] Capital | Mobiles : comment Free compte faire baisser les prix[END_REF]. The license cost (resp. the infrastructure cost) is then evaluated to 541 e (resp. 1167 e) per month and per zone, giving c 1,3G = c 2,3G = 1708 e. We also assume that a license costs 649 Me for WiMAX and the infrastructure costs 340 Me [START_REF] Wimaxday | Worldmax launches mobile WiMax network[END_REF], yielding c 1,WiMAX = c 2,WiMAX = 541 + 283 = 824 e. We assume that every access point is renewed each year and is bought at the average price of 600 e. As no license purchase is necessary for the WiFi [START_REF] Netpro | Le Wi-Fi devient officiellement une activité commerciale[END_REF], we get then c 1,WiFi = c 2,WiFi = 50 e.

In that case, we can remark that there exists again two Nash equilibria, ({WiFi,WiMAX},{WiMAX}) and ({WiMAX},{WiFi,WiMAX}). With respect to the previous situation, 3G is actually too expensive with the proposed license cost to be implemented.

B. A WiFi-positionned provider against a 3G one

Consider provider 1 as already installed in the Internet and WiFi (basically like the provider called Free in France), and wishing to extend its position, against a 3G-installed provider 2 (Bouygues Telecom for instance). WiMAX costs are assumed to be the same as in the previous subsection, this technology being a new one. Bouygues Telecom already owning an infrastructure, only its license cost of 649 Me accounts, giving c 2,3G = 541 e. The cost of the fourth license in France is fixed to 240 Me [START_REF] Mobinaute | 4ème licence 3G : Orange fait pression auprès du gouvernement pour ralentir son attribution[END_REF], and of the new infrastructure estimated at 1.0 Be [START_REF] Capital | Mobiles : comment Free compte faire baisser les prix[END_REF], so that c 1,3G = 1033 e per month and per site. For WiFi, we choose c 1,WiFi = 0 e and c 2,WiFi = 50 e to illustrate the better position of provider 1. The benefits matrix is given in Table II, with again best responses highlighted in bold. For this game, there are two non symetric Nash equilibria. The first one is ({WiFi,WiMAX},{3G,WiMAX}). Indeed, each operator chooses the technology on which it is already present, and additionally goes to the new WiMAX technology. The second Nash equilibrium is ({WiMAX},{WiFi,3G,WiMAX}) and corresponds to a situation where operator 2 proposes all technologies and operator 1 only proposes the WiMAX technology. Again, it is better not to fight on (the low-cost) WiFi. To have a Nash equilibrium with 3G implemented by provider 1, then the cost c 1,3G has to be reduced to 900 e, which would mean a license fee of 67 e (or equivalently a global 3G license selling price of 80 Me). In that case, the situation ({3G,WiMAX},{WiFi,3G,WiMAX}) would be a Nash equilibrium of the technological game: provider 1 would focus on licensed technologies, giving up on WiFi. On the other hand, if the monthly cost per site for 3G gets as low as 694 e, then provider 1 could keep operating WiFi, since the situation ({WiFi,3G,WiMAX},{3G,WiMAX}) would arise as a technological Nash equilibrium.

C. A single technology-positionned provider against a dominant one

This would for instance correspond in France to Free (strongly established in the Internet and WiFi networks), named provider 1 again, against Orange, named provider 2, already positionned on almost all technologies, except WiMAX, for which we keep the costs of previous subsections. The 3G costs are also considered the same as in the previous subsection, but WiFi costs are here the same, c 1,WiFi = c 2,WiFi = 0 e due to the presence of both providers on this technology. The results are displayed in Table III. One can see here that, again, two Nash equilibria exist and are similar to those of the previous game in part V-B. That is, the existence of the WiFi infrastructure for the provider 2 plays does not affect the Nash equilibria. Hence, we deduce that the impact of the WiFi infrastructure cost is negligible compared to the 3G and WiMAX license and infrastructure costs. As in the previous subsection, some conditions on the license fees can be derived for 3G to be deployed by operators at a Nash equilibrium.

VI. CONCLUSIONS

We have proposed a 3-stage model to study competition among telecommunication providers. Providers have two strategic decisions to make (namely, the price they sell the service and the set of technologies to operate) on different time scales, while users react to those decisions.

The model provides some insights about the conditions under which a technology can be chosen by providers. Through some numerical computations, we highlighted that regulatory decisions such as license fees can strongly affect the outcome of the noncooperative interaction among providers.

Future work could focus on those regulatory issues, and possibly exhibit some specific regulatory decisions which would favor the development of some given technologies in a country.

Fig. 1 .

 1 Fig. 1. Curves of best prices if both players propose the WiMax technology

TABLE III BENEFITS

 III MATRIX FOR THE WIFI-DOMINANT GAME

• at the shortest scale, for fixed prices and sets of offered technologies, users choose their provider and technology in order to minimize their perceived price. Customers are assume non-atomic. This leads to a user equilibrium situation (d * i,t ) i,t following the Wardrop's principle, where

ACKNOWLEDGMENT

This work was supported by Euro-NF Network of Excellence and the French research agency through the CAPTURES project.