F Teytaud
email: fteytaud@lri.fr

O Teytaud

Creating an Upper-Confidence-Tree program for Havannah

Monte-Carlo Tree Search and Upper Confidence Bounds provided huge improvements in computer-Go. In this paper, we test the generality of the approach by experimenting on another game, Havannah, which is known for being especially difficult for computers. We show that the same results hold, with slight differences related to the absence of clearly known patterns for the game of Havannah, in spite of the fact that Havannah is more related to connection games like Hex than to territory games like Go.

Introduction

This introduction is based on [START_REF] Wikipedia | [END_REF]. Havannah is a 2-players board game (black vs white) invented by Christian Freeling [START_REF] Wikipedia | [END_REF][START_REF] Schmittberger | New Rules for Classic Games[END_REF]. It is played on an hexagonal board of hexagonal locations, with variable size (10 hexes per side usually for strong players).

White starts, after which moves alternate. The rules are simple:

-Each player places one stone on one empty cell. If there's no empty cell and if no player has won yet, the game is a draw (very rare cases). -A player wins if he realizes:

• a ring, i.e. a loop around one or more cells (empty or not, occupied by black or white stones); • a bridge, i.e. a continuous string of stones from one of the six corner cells to another of the six corner cells; • a fork, i.e. a connection between three edges of the board (corner points are not edges).

These figures are presented on Fig. 1 for the sake of clarify.

Although computers can play some abstract strategy games better than any human, the best Havannah-playing software plays weakly compared to human experts. In 2002 Freeling offered a prize of 1000 euros, available through 2012, for any computer program that could beat him in even one game of a ten-game match.

Havannah is somewhat related to Go and Hex. It's fully observable, involves connections; also, rings are somewhat related to the concept of eye or capture in the game of Go. Go has been for a while the main target for AI in games, as it's a very famous game, very important in many Asian countries; however, it is no longer true that computers are only at the level of a novice. Since MCTS/UCT (Monte-Carlo Tree Search, Upper Confidence Trees) approaches have been defined [START_REF] Chaslot | Monte-Carlo Strategies for Computer Go[END_REF][START_REF] Coulom | Efficient selectivity and backup operators in monte-carlo tree search[END_REF][START_REF] Kocsis | Bandit-based monte-carlo planning[END_REF], several improvements have appeared like First-Play Urgency [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF], Rave-values [START_REF] Bruegmann | Monte carlo go[END_REF][START_REF] Gelly | Combining online and offline knowledge in uct[END_REF], patterns and progressive widening [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF][START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF], better than UCBlike (Upper Confidence Bounds) exploration terms [START_REF] Lee | The computational intelligence of mogo revealed in taiwan's computer go tournaments[END_REF], large-scale parallelization [START_REF] Gelly | The parallelization of monte-carlo planning[END_REF][START_REF] Chaslot | Parallel Monte-Carlo Tree Search[END_REF][START_REF] Cazenave | On the parallelization of UCT[END_REF][START_REF] Kato | Parallel monte-carlo tree search with simulation servers[END_REF], automatic building of huge opening books [START_REF] Audouard | Grid coevolution for adaptive simulations; application to the building of opening books in the game of go[END_REF]. Thanks to all these improvements, MoGo has already won games against a professional player in 9x9 (Amsterdam, 2007; Paris, 2008; Taiwan 2009), and recently won with handicap 6 against a professional player, Li-Chen Chien (Tainan, 2009), and with handicap 7 against a top professional player, Zhou Junxun, winner of the LG-Cup 2007 (Tainan, 2009). The following features make Havannah very difficult for computers, perhaps yet more difficult than the game of Go:

-few local patterns are known for Havannah; -no natural evaluation function; -no pruning rule for reducing the number of reasonable moves; -large action space (271 for the first move with board size 10).

The advantage of Havannah, as well as in Go (except in pathological cases for the game of Go), is that simulations have a bounded length: the size of the board.

The goal of this paper is to investigate the generality of this approach by testing it in Havannah.

By way of notation, x ± y means a result with average x, and 95% confidence interval [x -y, x + y] (i.e. y is two standard deviations).

UCT

Upper Confidence Trees are the most straightforward choice when implementing a Monte-Carlo Tree Search. The basic principle is as follows. As long as there is time before playing, the algorithm performs random simulations from a UCT tree leaf. These simulations (playouts) are complete possible games, from the root of the tree until the game is over, played by a random player playing both black and white. In its most simple version, the random player, which is used when in a situation s which is not in the tree, just plays randomly and uniformly among legal moves in s; we did not implement anything more sophisticated, as we are more interested in algorithms than in heuristic tricks. When the random player is in a situation s already in the UCT tree, then its choices depend on the statistics: number of wins and number of losses in previous games, for each legal move in s. The detailed formula used for choosing a move depending on statistics is termed a bandit formula, discussed below. After each simulation, the first situation of the simulated game that was not yet in memory is archived in memory, and all statistics of numbers of wins and numbers of defeats are updated in each situation in memory which was traversed by the simulation.

Bandit formula

The most classical bandit formula is UCB (Upper Confidence Bounds [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF][START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF]); Monte-Carlo Tree Search based on UCB is termed UCT. The idea is to compute a exploration/exploitation score for each legal move in a situation s for choosing which of these moves must be simulated. Then, the move with maximal exploration/exploitation score is chosen. The exploration/exploitation score of a move d is typically the sum of the empirical success rate score(d) of the move d, and of an exploration term which is strong for less explored moves. UCB uses Hoeffding's bound for defining the exploration term:

exploration Hoef f ding = log(2/δ)/n ( 1
)
where n is the number of simulations for move d. δ is usually chosen linear as a function of the number m of simulations of the situation s: δ is linear in m. In our implementation, with a uniform random player, the formula was empirically set to:

exploration Hoef f ding = 0.25 log(2 + m)/n. (2)
[1, 17] has shown the efficiency of using Bernstein's bound instead of Hoeffding's bound, in some settings. The exploration term is then:

exploration Bernstein = score(d)(1 -score(d))2 log(3/δ)/n + 3 log(3/δ)/n
(3) This term is smaller for moves with small variance (score(d) small or large).

After the empirical tuning of Hoeffding's equation 2, we tested Bernstein's formula as follows (with p = score(d) for short)

exploration Bernstein = 4Kp(1 -p) log(2 + m)/n + 3 √ 2K log(2 + m)/n. ( 4
)
Within the "2+", which is here for avoiding special cases for 0, this is Bernstein's formula for δ linear as a function of m.

We tested several values of K. The first value 0.25 corresponds to Hoeffding's bound except that the second term is added: Experiments are performed with 1000 simulations per move, with size 5. We tried to experiment values below 0.01 for K but with poor results.

K Score against

Scaling of UCT

Usually, UCT provides better and better results when the number of simulations per move is increased. Typically, the winning rate with 2z simulations against UCT with z simulations is roughly 63% in the game of Go (see e.g. [START_REF] Gelly | The parallelization of monte-carlo planning[END_REF]). In the case of Havannah, with uniform random player (i.e. the random player plays uniformly among legal moves) and bandit formula as in Eq. 2, we get the following results for the UCT tuned as above (K = 0.25):

Number

Guiding exploration

UCT-like algorithms are quite strong for balancing exploration and exploitation. On the other hand, they provide no information for unexplored moves, and on how to choose among these moves; and little information for loosely explored moves. Various tricks have been proposed around this: First Play Urgency, Progressive widening, Rapid Action Value Estimates (RAVE).

Progressive widening/unpruning

In progressive widening [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF][START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF][START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF], we first rank the legal moves at a situation s according to some heuristic: the moves are then renamed 1, 2, . . . ,n, with i < j if move i is preferred to move j for the heuristic. Then, at the m th simulation of a node, all moves with index larger than f (m) have -∞ score (i.e. are discarded), with f (m) some non-decreasing mapping from N to N. It was shown in [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF] that this can work even with random ranking, with f (m) = ⌊Km 1/4 ⌋ for some constant K. In [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF] it was shown that f (m) = ⌊Km 1/3.4 ⌋ for some constant K performs well in the case of Go, with a pattern-based heuristic. The algorithm proposed in [START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF] and now used also in MoGo is a bit different: an exploration term depending on a pattern-based heuristic and decreasing logarithmically with the number of simulations of this move is added to the score; for move

d in situation s, newScore(d, s) = score(d, s) + H(d, s)/ log(2 + m),
where as previously n is the number of simulations including move d at situation s. In the case of Havannah, we have no such heuristic. We decided to use heuristic-free progressive widening, as it was shown in [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF] that an improvement can be provided even if no heuristic is available (i.e. the order is arbitrary). This idea of using progressive widening without heuristic is a bit counter-intuitive. However, consider the following case. Consider a node of a tree which is explored 50 times only (this certainly happens for many nodes deep in the tree). If there are 50 legal moves at this node, then the 50 simulations will be distributed on the 50 legal moves (one simulation for each legal move), if you use the standard UCB formula instead of (without) progressive widening. Meanwhile, progressive widening will sample a few moves only, e.g. 4 moves, and sample much more the best of these 4 moves -this is likely to be better than taking the average of all moves as an evaluation function. We experimented with 500 simulations per move, size 5, various constants P and Q for the progressive widening f (m) = Q⌊m P ⌋:

Q, P Success rate against no prog. widening 1, 0.7 0,496986 ± 0,014942 1, 0.8 0.51 ± 0,0235833 1, 0.9 0.50 ± 0,0145172 4, 0.4 0,500454 ± 0,0134803 4, 0.7 0.49 ± 0,0181818 4, 0.9 0,485101 ± 0,0172619

These experiments were performed with the exploration formula given in Eq. 2.

We tested various other parameters for Q and P , without seeing a significant improvement. Perhaps improvements are possible by jointly tuning the Hoeffding's bound and the progressive widening formula.

Rapid Action Value Estimate

In the case of Go [START_REF] Bruegmann | Monte carlo go[END_REF][START_REF] Gelly | Combining online and offline knowledge in uct[END_REF] propose to average the score with a permutation-based statistical estimate. Precisely, the score for a move d in situation s simulated n times becomes: -α(n) → 0 as n → ∞, whereas α(n) is close to 1 for n small, so that the heuristic rave values are used initially, and eventually they are replaced by "real" values.

newScore(d, s) = (1 -α(n))score(d, s) + α(n)rave(d,
The difference between score(d, s) and rave(d, s) is that the proportion of won games in rave() is computed among all simulations containing d as move after situation s and not only all simulations with d as move in situation s. In the game of Go, RAVE values are a great improvement. However, they involve complicated implementations due to captures and re-captures. In the case of Havannah there's no such problem, and we'll see that the results are good. We used the following formula:

α(n) = + n), exploration = exploration Hoef f ding = K log(2 + m)/n.
R was empirically set to 50 (on games with size 5 with 1000 simulations per move); intuitively, R is the number of simulations before the weight of "RAVE" values is equal to the weight of "greedy" values. All scores below are against UCT with Eq. 2.

size 5 R=50, K=0.25, size 5, 1000 simulations/move 47.26% ± 4.0 % R=50, K=0.05, size 5, 1000 simulations/move 60.46% ± 2.9 % R=50, K=0, size 5, 1000 simulations/move 95.33% ± 0.01 % size 8 R=50, K=0, size 8, 1000 simulations/move 100% on 1347 runs K = 0 is then the best constant. This was also pointed out in [START_REF] Lee | The computational intelligence of mogo revealed in taiwan's computer go tournaments[END_REF] for the game of Go. We then tested larger numbers of simulations, i.e. 30 000 simulations per move. Disappointingly but consistently with [START_REF] Lee | The computational intelligence of mogo revealed in taiwan's computer go tournaments[END_REF], we had to change the coefficients in order to get positive results, whereas the tuning of UCT is seemingly more independent of the number of simulations per move. R=50, K=0, size 5, 30 000 simulations/move 0.53 ± 0.02 R=50, K=0.25, size 5, 30 000 simulations/move 0.47 ± 0.04 R=50, K=0.05, size 5, 30 000 simulations/move 0.60 ± 0.02 R=50, K=0.02, size 5, 30 000 simulations/move 0.60 ± 0.03 R=5, K=0.02, size 5, 30 000 simulations/move 0.61 ± 0.06 R=20, K=0.02, size 5, 30 000 simulations/move 0.66 ± 0.03

The first line corresponds to the configuration empirically chosen for 1000 simulations per move; its results are disappointing, almost equivalent to UCT, for these experiments with 30 000 simulations per move. The second line uses the same exploration constant as UCT, but it's seemingly too much. Then, in the following lines, using a weaker exploration and a small value of R, we get better results. [START_REF] Lee | The computational intelligence of mogo revealed in taiwan's computer go tournaments[END_REF] points out that, with big simulation times, K = 0 was better, but an exploration bonus depending on patterns was used instead.

As a conclusion, for large numbers of simulations, RAVE is not as efficient as for small values (when compared to UCT). Perhaps better tuning could yield better results. The main weaknesses of RAVE are:

-tuning is required for each new number of simulations;

-the results for large numbers of simulations are less impressive (yet significant).

On the other hand, the efficiency increases with the size of the action spacethis is promising for the application of RAVE to large action spaces. rate is lower than 50 % at the beginning (as the opponent, playing first, has the advantage initially). It then increases regularly until the end. The second game is presented in Fig. 3, with only 7000 simulations (nearly 2 seconds) per move. Consistently again, the estimated success rate is lower than 50 % at the beginning (as the opponent, playing first, has the advantage initially). It then increases regularly until the end.

Discussion

We could clearly validate in the case of Havannah the efficiency of some well known techniques coming from computer-Go, showing the generality of the MCTS approach. Essentially:

-The efficiency of Bernstein's formula, in front of Hoeffding's formula, is clear (up to 65%). -The constant success rate of UCT with 2k simulations per move, against UCT with k simulations per move, nearly holds in the case of Havannah (nearly 75%, whereas it is usually around 63% for MCTS in the game of Go [START_REF] Gelly | The parallelization of monte-carlo planning[END_REF]). However, the success rate is higher than in the case of the game of Go (around 75%). -The efficiency of the RAVE heuristic is clearly validated. The main strength is that the efficiency increases with the size, reaching 100 % on 1347 games in size 8. On ther other hand, RAVE becomes less efficient, and requires tuning, when the number of simulations per move increases -however, we keep 66% of success rate). -Progressive widening, in spite of the fact that it was shown in [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF] that it works even without heuristic, was not significant for us. In the case of Go, progressive widening was shown very efficient in implementations based on patterns [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF][START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF]. -Our program could defeat Havannah-Applet easily, whereas it was playing as black, and with only 2s per move instead of 30s (running on a single core).

Running more experiments was difficult due to lack of automated interface.

Fig. 1 .

 1 Fig. 1. Three finished games: a ring (a loop, by black), a bridge (linking two corners, by white) and a fork (linking three edges, by black).

  s) + exploration where -score(d, s) is the ratio of won simulations among simulations with situation s and move d in s, rave(d, s) is the proportion of won games among games containing move d after situation s.

Fig. 2 .

 2 Fig. 2. Left: the result of the game played against Havannah-Applet in size 5. Our program won very quickly, by a nice multiple constraint: the white opponent must play W1 (unless black wins by bridge). Then, black can connect to the lower-right edge with B1. Then, black has two opportunities for connecting to the right edge, B2a and B2b; white can only block one and black then realizes a fork. As seen on the estimated success rate, Havannah-Applet did not suspect this attack before the very last move. Right: estimated success rate for each of the opponents.

Fig. 3 .

 3 Fig. 3. Left: the result of the game played against Havannah-Applet in size 5. Our program was playing black and won by resignation. White has to play W1, otherwise black realises a bridge. Then, Black plays B1 and is connected to a second side. Next, White must play W2 (if Black plays W2 then Black has a fork). Finally, Black can play B2 and with with move, is connected to the third side (by B3a or B3b (White can't avoid this connection). Right: estimated success rate for each of the opponents.

4

  Games against Havannah-AppletWe tested our program against Havannah-Applet http://dfa.imn. htwk-leipzig.de/havannah/, recommended by the MindSports association as the only publicly available program that plays by the Havannah rules. There are 30 seconds per move, but we restricted our program was running in 8 secondes per move (first game) and 2.5 seconds per move (second game). In both cases, our program, based on RAVE, no exploration term, no progressive widening, was black (white starts and has therefore the advantage in Havannah). The first game (played with 8 seconds per move for our program, against 30s for the opponent) is presented in Fig.2. Consistently, the estimated success

	Success rate	Success rate
	estimated by estimated by
	Havannah-Applet our software
	62.6%	46.4%
	60.8%	47.2%
	64.0%	51.2%
	56.5%	54.8%
	62.5%	65.4%
	57.3%	63.7%
	71.0%	88.8%
	0.5%


Corentin Curchod

Philippe Caillou
email: caillou@lri.fr

Tiago Baptista

Which Buyer-Supplier Strategies on Uncertain Markets? A Multi-Agents Simulation

. Differently, this paper proposes to simulate and analyze buyer-supplier strategies in a micro and concrete market setting. It shows that the margin rate is not the only parameter to consider when choosing a buyersupplier strategy but that regularity of supply plays an essential role, and that pure loyalty is not necessarily the best strategy when market uncertainty increases.

Theoretical backround

Value is a central concern in strategy. More specifically, how value is shared among the different actors in an industry constitutes a core issue for the classical power-based approach of competitive advantage [START_REF] Brandenburger | value-based business strategy[END_REF]Porter, 1991) and more recently to the "architectural" view, considering that the amount of value the firm is able to capture depends on its capacity to shape the industry at its own advantage [START_REF] Jacobides | Benefiting from Innovation: Value Creation, Value Appropriation and the Role of Industry Architectures[END_REF]. The micro-level -i.e. the level at which negotiations and pricing do happen -is certainly the most appropriate when studying the real process of value sharing [START_REF] Brandenburger | value-based business strategy[END_REF]Zbaracki, 2007). The pricing process, since it constitutes the ultimate determinant of the amount of value captured by the firm over its clients, is more than an organizational routine: it is a capability that the firm should develop at both organizational and individual levels [START_REF] Dutta | Pricing Process as a Capability: A Resource-Based Perspective[END_REF].

Value sharing does happen at the firms' interfaces: between the firm and its clients, between the firm and its suppliers, among others. Generally, the locus for value sharing is the several intermediate markets that separate and, at the same time, link the interdependent activities along a value chain. These markets can be clearly bounded -the extreme case is the existence of well-defined marketplaces -or not; they can emerge from unexpected changes in the organization of the activities along the value chains [START_REF] Jacobides | Industry change through vertical disintegration: how and why markets emerged in mortgage banking[END_REF] or be stable. On these markets, firms are dividing value the concrete way, that is to say, they send individuals to negotiate. In this paper, we argue that firms' interrelations -the locus for value sharing -happen at the individual level, even if organizational processes and routines do exist. Negotiations, whether they occur on a well-defined competitive market or through specific bilateral relations, involve a complex intertwining of competition and cooperation (Sebenius, 1992). Literature has largely investigated the dynamics of negotiation and how competition and cooperation may occur through successive and clearly delineated sequences [START_REF] Adair | The Negotiation Dance: Time, Culture, and Behavioral Sequences in Negotiation[END_REF]. Some authors insist on the multiplicity of negotiation types, depending on the specific negotiation strategies that buyers will choose [START_REF] Cannon | Buyer-Seller Relationships in Business Markets[END_REF]Perdue and Summers, 1991) or the type of relationships buyers and sellers have, with a distinct focus on power-based [START_REF] Kim | Power Dynamics in Negotiation[END_REF] or relational and more equalitarian interactions [START_REF] Gelfand | Negotiating Relationally: the Dynamics of the Relational Self in Negotiations[END_REF].

We consider here that negotiation strategies depend on the type of relations the supplier and the client have together, and that these relations can be framed along a continuum from arm's length/short term to cooperative/long term type. Literature has shown how cooperation between buyers and sellers decreases the perceived risk on future transactions for both sides [START_REF] Heide | The Shadow of the Future: Effects of Anticipated Interaction and Frequency of Contact on Buyer-Seller Cooperation[END_REF] or may lead to a higher level of value creation and thus to competitive advantage [START_REF] Lavie | The Competitive Advantage of Interconnected Firms: an Extension of the Resource-Based View[END_REF].

Very little has been said, however, on the impact of market environment on the output of the different types of relations between buyers and sellers. Transaction cost economics and the strategy field proposed that in case of high uncertainty the best solution is to avoid market relations and to vertically integrate [START_REF] Afuah | Dynamic boundaries of the firm: are firms better off being vertically integrated in the face of a technological change?[END_REF]Richardson, 1996;Williamson, 1991), even if empirical tests show that the positive effects of vertical integration is far from obvious (Sutcliffe et al., 1998). Market uncertainty creates room for new organizational forms and new types of interfirm relations, sometimes called "flexible forms" (Volberda, 1996). But vertical integration cannot possibly constitute a global solution against market uncertainty, simply because in most industries firms are unable to vertically integrate, for financial or strategic reasons. In those cases, long-term suppliers relations may offer stability in unstable markets [START_REF] Heide | The Shadow of the Future: Effects of Anticipated Interaction and Frequency of Contact on Buyer-Seller Cooperation[END_REF]. But whether this solution is the most interesting in terms of value appropriation remains an unanswered question yet.

In this paper, we precisely propose to investigate these issues and, more specifically, which type of buyer-seller relation constitutes the best strategy for the seller when market uncertainty increases. The output we consider is the amount of value the seller is able to capture from the relation.

Methodology

The research adopts an experimental design based on a simulation of a real market for professionals in France, the "Rungis" market. The Rungis Market -which has the official label of "Market of National Interest" -locates near Paris and is the biggest market for fresh products in the world, with a surface area of 232 hectares. It gathers sellers of fresh products like fruits, vegetables, fishery goods or meat, all small or medium sized firms, and buyers like retailers or restaurateurs. The market is strictly controlled by market authorities and governmental bodies. Transactions happen by private mutual agreements between the buyer and the seller: there is no posted price by the sellers, no electronic quotation or auction mechanism. Governmental bodies publish a daily quotation list by product, based on the informal information they can gather on the market. The quotation list published day N gives averages prices collected day N-1 for each type of product and each quality. Since the goods are highly perishable and the time schedule for transactions is limited to 4 or 5 hours a day, the market is highly liquid and volatile. Because of the absence of rigid frame for pricing, each buyer is free to adopt a specific strategy with the sellers. Some spend much time to compare the different prices and qualities of the goods. Some others choose a seller for each good or bunch of goods and maintain long term relations with him. In the first phase of the research, one of the three authors obtained a pass to spend ten days on the market, and gathered data on the real day-to-day interactions between buyers and sellers, through interviews and observations. He obtained the right to spend time with the employees of two main wholesalers and observe their selling strategies. He also was able to follow a buyer during his purchases and to observe usual buyer-seller relational strategies. A total of 13 interviews were also carried out with sellers, buyers and market authorities. This phase followed an ethnographic approach as socio-economists of markets commonly do [START_REF] Abolafia | Markets as cultures: an ethnographic approach[END_REF]Sherry Jr, 1990) with an objective of pure description. At the end of the observation phase, a 80 pages report was written describing the functioning of the market. Then the second phase began. The second author transcribed the report into a frame for a multi-agents system model. This 14 pages algorithm were checked and discussed by the first author in a third phase, with numerous rounds of program rewriting and going back and forth between the case and the model. Due to the complexity of the agents' strategies, a 3d cognitive multi-agents simulation was chosen, with the following main advantages: i) the intuitive rule-based and agent-centred simulation definition; ii) the capacity to test different scenarii and study parameter sensitivity; iii) the human-friendly visualisation interface, essential for the validation of behaviours. In a fourth phase, the second and third authors wrote the program and designed the simulation, followed by a phase of calibration and validation. Concerning this latter phase, we retained two criteria: firstly, when considering a full day for a specific buyer, no incoherence or unrealistic behaviour should occur; secondly, the market should follow the law of supply and demand for each type of good. See appendix 1 for a short description of the program.

The experimental phase was designed as explained table 1. To compare basic strategies, we added 5 buyer agents to a realistic market simulation. Each of this "tested" buyers follow one of the prototypic strategies defined in Table 1.

Results

Figure 1 : average margins per day 23 and per strategy

when there is no market uncertainty (XP1)

Figure 2: average margin rates per day and per strategy when there is no market uncertainty (XP1)

Value appropriation when there is no market uncertainty (XP1)

Our first set of results shows that, when there is no market uncertainty, the search strategy (A) is more profitable in both absolute and relative value than the others. Figures 1 and2 give the evolution of the margins and the margin rates for each strategy A-E, from day 2 to day 32. Figures 1 and2 invite to make a distinction among three subgroups: strategy A, as already said, is highly profitable. On the opposite, strategies of building long term relations with one seller and a guaranteed price (B and C) leads to a low rate of profitability but acceptable level of profits. The strategy consisting in building long term relations with three sellers -but without a guaranteed price -leads to an increasing margin rate and still a low margin in absolute value. Difference between margin rates and margins in absolute value is due to differences in quantity bought. Figure 3 gives the average number of purchased goods for each strategy. Interestingly, one notices that the worst strategies in terms of profitability are also the best strategies in terms of regularity of supply: on average, each buyer adopting strategy B or C is able to purchase the totality of what he wanted to purchase. In other words, when developing long-term relations with one seller per product, the buyer has the guarantee to obtain what he needs -which is highly valuable when final clients are expecting regularity of supply -but at a higher price. A pure search strategy also leads to a good regularity in this market configuration. But, if one considers the time spent on the market (Fig. 7) the search strategy is not efficient compared to B or C. Intermediate strategies D and E, by which the buyer has three preferred sellers, are also time consuming and the buyer runs the risk to leave the market with a small portion of what he needs because most goods are already gone (see Fig. 3).

Figure 3: average number of products bought per strategy (A-E) for each market configuration. 4 Figure 4: average margin per day and per strategy (A-E) for each market configuration (XP1-XP4)

Value appropriation in the case of demand uncertainty (XP2)

Now, we introduce demand uncertainty on the market: buyers do not know if the demand will be highwith a risk of high prices and market shortage -or low. Figure 5 gives the average margin rate per strategy. The distinction we had in XP1 is even more clearcut now, between a group of very profitable strategies A and E and a group of low profitability strategies C and B. More striking, strategies consisting in delineating a submarket of three sellers (D and E) lead to bad outputs in terms of quantities purchased (Fig. 3). In this configuration, there is a final equivalence in terms of total margins between strategies performing well on the unitary margin but badly on the regularity of supply -D and E -and those doing well on the regularity of supply but leading to low unitary margins (B and C). But pure search is still a dominating strategy in terms of total profits (see Fig. 4).

Value appropriation in the case of supply uncertainty (XP3)

In the case of supply uncertainty, buyers do not know in advance which quantity of each good the market offers but, if they spend enough time and gather information, they can guess. Here, a buyer with one single preferred seller per product (strategies B and C) will be less profitable than a buyer with three preferred sellers per product (D and E), himself less profitable than pure search strategy (A). This is coherent with the idea that buyers must guess which quantity is offered on the market and may adapt their negotiation strategy accordingly. However, a second result is more puzzling: strategies D and B lead to higher margin rates than strategies E and C respectively (see Fig. 6), which means that organizing an external competition with the preferred seller or with the preferred group of sellers does not bring a surplus of value compared to pure loyalty. That is counterintuitive but may be explained by the fact that by switching to a new seller one day because this latter has an extra offer, the buyer may lose the favoured relationship with his usual seller. The one-time gain he will make can hardly exceed the repeated reward due the fact that sellers accept to decrease their price if their regular clients are loyal. In other words, in the case of highly volatile supply, risk-adverse and stable strategies are more profitable for buyers: when the firm has one or several preferred sellers, it will not run the risk to loose the advantages associated with these specific relations for a one time good opportunity. In the end, both pure search and pure loyalty strategies (A and B) lead to the same level of margin in absolute value (Fig. 4). When both supply and demand are highly volatile, buyers cannot easily guess the market price. They run the risk of either buying at an exaggeratedly high price or leaving the market with only a small portion of what they need. Concerning profitability, Fig. 8 clearly shows that strategies of competition among three sellers or more (A, D and E) bring a much higher margin rate than strategies of pure or relative loyalty towards a single seller (B and C). Contrarily to what happened in the other configurations, loyalty does no longer bring a clear advantage in terms of regularity of supply when the market is highly volatile (see Fig. 3). Consequently, when considering the total margin at the end of the day, the strategy consisting in creating submarkets of three sellers and limiting the search to them (D) outperforms the others except the pure search strategy, which has however the disadvantage of being three times more time consuming than D (Fig. 7). The strategy D is better than strategy E particularly when the ratio supply over demand is low: a limited submarket of three sellers is easy to handle for the buyer, who is able to make his purchases quickly enough and to avoid potential shortage. It is better than strategies B and C when the ratio supply over demand is high, because it gives more room for negotiation and comparison. The strategy D has thus a competitive advantage over the others, let aside strategy A much too time consuming. Strategy E is clearly a bad strategy regarding the regularity of supply, and, as a consequence, the total margin (the worst of the five strategies).

Discussion

Following transaction costs economics and its theoretical approach of vertical relations, authors in strategy largely agree that in the case of market uncertainty, short-term purely market-based relations lead to lower performance than long-term cooperative ones [START_REF] Heide | The Shadow of the Future: Effects of Anticipated Interaction and Frequency of Contact on Buyer-Seller Cooperation[END_REF], which may even go as far as vertical integration [START_REF] Afuah | Dynamic boundaries of the firm: are firms better off being vertically integrated in the face of a technological change?[END_REF]Sutcliffe et al., 1998). Our research partially contradicts this global idea and brings substantive new theoretical insights about at least two points: first, pure loyalty is on average less profitable than mixed strategies of both cooperation with a few suppliers and simultaneously bringing competitive pressure among them; secondly, the best strategies in terms of profitability may be the worst in terms of regularity of supply, depending on market uncertainty.

Our approach has some limitations, in particular the simulation is based on a specific real market which brings internal validity and consistency but also may lead to a lack of external validity. However, we consider that the underlying empirical market can be considered as an ideal-type for many forms of markets. This paper proposes a new tool to study buyer-seller strategies in the corporate world, based on multiagents simulation. This innovative method opens the door to experimental designs that are difficult -if not impossible -to realize in a purely empirical setting. This may have strong methodological, theoretical and empirical implications. For example, our results justify strategies we observed on the real market, like the restaurateurs, who need a strong regularity of supply and who are generally loyal to a single seller per good or, at the opposite, buyers spending hours strolling up and down the market, searching the very best prices for clients who do not expect regularity of supply. Our model renews the methodological apparatus for studying value repartition along value chains and paves the way for new experimental research on buyer-supplier strategies.

Appendix: main parameters of the simulation

Global market parameters

-Number of sellers = 20 -Number of buyers = 50 -Number of different types of good = 3. All goods are perishable.

-Quality ranges from 1 (perfect) to 0 (improper for consumption). Quality of unsold goods decreases day after day. -Published quotation everyday (see methodology).

Discussion protocol

Coherent with the market reality, the seller initiates the negotiation and asks for a type of product with a minimum quality. Discussions happen as follow:

-Seller: Hi -Buyer: HowMuchFor;Product; min quality -Seller: Propose;price (the starting price is fixed for each specific set of seller-product-quality) -Buyer: Propose;price;quantity, -Seller: Propose;price -Buyer: Propose;price;quantity...

until they reach an agreement or quit or switch to another product Buyers may look for very cheap items or for very good quality, depending on their final clients. They may have time for comparing the offers of several sellers or rush and buy to their usual sellers. To fit the real observed market, four kind of buyers interact, each having different strategies, defined from empirical observations.

Sellers buy goods to producers. They are able to propose a maximum of three different types of good to buyers, with different quality. They are aware of competition and adapt their prices. The unsold goods are stocked and proposed again the day after, with a lower level of quality.

Screenshot: Simulations where conducted using the BitBang Simulation Framework:

Figure 5 :

 5 Figure 5: average margin rates per day and per strategy in the case of demand uncertainty (XP2)

Figure 7 :

 7 Figure 7: Average time spent on the market per day and per strategy for each experiment XP1-4 Figure 8: average margin rates per day and per strategy in the case of high market uncertainty (XP4)

Table 1

 1

	: experimental design

A: search strategy, high propensity to compare prices, systematic negotiation, no loyalty B: long term relation with one seller for each good, stable prices negotiated once and for all C: same as B plus frequent check that other suppliers do not make better offers, capacity to change suppliers if a better offer. D: preferred relation with three sellers for each good, systematic comparison among these three and choice of the best offer E: same as D plus frequent check that other suppliers do not make better offers, capacity to change suppliers if a better offer.

More simulations are planned in the following months to reinforce the validity of the results.

The price that a seller pays to his producer for one lot of goods ranges from 10 to 20 depending on quality. Similarly, the price the buyer is able to set to his final client ranges from 20 to 40. The maximum margin per day for a buyer is thus 120 (3 top quality lots sold 40 on the final market and acquired for free from a seller)

In the experiments, we excluded days 0 to 5 which are not representative of the normal behaviour of the market (buyers and sellers build relationships and there is no obsolete goods on the market)

For each buyer A-E, the desired quantity is fixed and equal to 1 (lot) per category of product, thus a total of 3 lots of goods.

Perdue BC, Summers JO. 1991. Purchasing Agents' Use of Negotiation Strategies. Journal of Marketing Research 28(2): 175-189 Porter ME. 1991. Towards a Dynamic Theory of Strategy. Strategic Management Journal 12: 95-117 Richardson J. 1996. vertical integration and rapid response in fashion apparel. Organization Science 7(4): 400 Sebenius JK. 1992. Negotiation Analysis: A Characterization and Review. Management Science 38(1): 18-38 Sherry Jr JF. 1990. A Sociocultural Analysis of a Midwestern American Flea Market. Journal of Consumer Research 17(1): 13 Sutcliffe KM, Zaheer A. 1998. Uncertainty in the Transaction Environment: An Empirical Test. Strategic Management Journal 19(1): 1 Volberda HW. 1996. toward the flexible form: how to remain vital in hypercompetitive environments. Organization Science 7(4): 359 Williamson O. 1991. Comparative Economic Organization: the Analysis of Discrete Structural Alternatives. Administrative Science Quarterly: 269-296 Zbaracki MJ. 2007. A sociological view of costs of price adjustment: contributions from grounded theory methods. Managerial & Decision Economics 28(6): 553


Philippe Caillou
email: caillou@lri.fr

Michele Sebag
email: sebag@lri.fr

Pride and Prejudice on a Centralized Academic Labor Market

The Academic Labor Market in France can be viewed as a constrained Stable Marriage problem, pairing universities and candidates according to their (elitist) preferences. A Multi-Agent based model, calibrated after the empirical evidence, is used to investigate how universities can recruit the best candidates with high confidence. Extensive simulations suggest that universities can be divided in four categories: top and medium universities have no difficulty in attracting the candidates they have selected, contrarily to good and bad universities. In this paper, a learning mechanism is presented: universities are allowed to tune their expectations depending on whether they did succeed to attract candidates in the previous recruitment rounds. The impact of over/under estimations is analyzed with respect to the hiring efficiency and quality.

Introduction

National academic labor markets (ALMs) are strongly influenced by the culture and history of the country [START_REF] Musselin | European academic labor markets in transition[END_REF]. The French system examined in this paper reflects an egalitarian tradition; the hiring process globally aggregates the preferences of universities and candidates using a Stable Marriage-like algorithm [START_REF] Gale | College admissions and the stability of marriage[END_REF]. Due to administrative constraints (limited size of the short list), this centralized procedure might entail some hiring inefficiencies, where good universities might select top candidates, who will ultimately prefer better universities. Universities might therefore use less elitist and more secure recruitment strategies. The goal of this paper is to examine how strategies based on raising/lowering the university expectations might improve their hiring efficiency. In an earlier study of the French ALM [START_REF] Caillou | Modelling a centralized academic labour market: Efficiency and fairness[END_REF], a Multi-Agent (MA) simulation framework has been proposed to assess the hiring rate and the quality of the recruitment process. In this paper, this framework is extended, al-lowing universities to adjust their selectivity depending on their hiring success in the previous steps. The efficiency of the considered strategies is discussed with respect to the university position (relatively to the set of universities).

The paper is organized as follows. Section 2 briefly reviews and discusses relevant work. The French academic labor market (ALM) is presented in section 3. Section 4 describes the MA-based model. Section 5 discusses the lessons learned from extensive simulations conducted with this model, and the paper concludes with some perspectives for further research.

Related work

Centralized (labor) markets are based on the preferences of sellers (here, the candidates) and buyers (the universities). The combinatorial optimization problem of building an optimal pairing, referred to as Stable Marriage problem, has been extensively investigated since Gale & Shapley pioneering work [START_REF] Gale | College admissions and the stability of marriage[END_REF]. The French ministry actually uses a variant of the Stable Marriage algorithm (akin [START_REF] Baiou | Student admissions and faculty recruitment[END_REF]) to compute an optimal assignment of candidates to universities. Importantly, the procedure is shown to be truthful, in the sense that no agent could improve its outcome by lying about its preferences [START_REF] Ito | Instantiating the contingent bids model of truthful interdependent value auctions[END_REF]. The optimality and truthfulness properties however only hold in an idealized setting (rational agents, unbounded shortlists).

The French academic labor market has more specifically been studied by [START_REF] Musselin | European academic labor markets in transition[END_REF] in a sociological perspective. This work focuses on organizational, societal and cognitive aspects; the professional efficiency, the university organization and department cohesiveness, and the quality assessment are related to the hiring process. The Local Hiring phenomenon has been investigated in a specific area by [6], empirically measuring how the proximity between the PhD jury of a candidate and the jury of highly competitive national examinations, is correlated with the probability of success of the candidate.

On the computational side, a variety of social and economical problems have been investigated using multi-agent systems (MAs) [START_REF] Axelrod | Advancing the art of simulation in the social sciences[END_REF][START_REF] Tesfatsion | A constructive approach to economic theory[END_REF]. MAs have demonstrated their ability to both represent (cognitive) agents and constrained interaction rules, and provide insights into the dynamics of the system. More generally, MAs are increasingly being considered as a flexible and versatile modelling framework, enabling positive and normative investigations of phenomena out of reach of analytical studies, and supported by efficient programming environments (e.g., ModulEco [START_REF] Phan | From agent-based computational economics towards cognitive economics[END_REF] and RePast [START_REF] North | Experiences creating three implementations of the repast agent modeling toolkit[END_REF]). In an earlier work [START_REF] Caillou | Modelling a centralized academic labour market: Efficiency and fairness[END_REF], a MAS has been proposed to model the French ALM and study the local hiring problem; interestingly, local hiring (see below) was shown to be an efficient hiring strategy (as opposed to, a "bad university habit") in some settings.

The French Academic Labor Market

This section describes the French academic hiring process and the available ground truth.

The hiring process

• The list of all open positions in all universities is published by the State department. Every PhD1 is free to apply to any such position; the number of applications is not restricted.

• In each university, for each position, a jury is designated, selects candidates and interviews the selected candidates.

• Every selected candidate goes to every interview (except for conflicting schedules or if he has been formerly top-listed in a University he prefers).

• For each position, the jury publishes a shortlist of at most five names, selected among the interviewed candidates.

• Each candidate is informed of the positions he has been shortlisted for, together with his rank; he symmetrically ranks all positions (no length constraint) according to his preferences.

• All university shortlists and candidate ranking lists are sent to the ministry; a stable marriage like algorithm is used to compute the actual matching.

Empirical Evidence

In 2007, the number of open positions, the number of candidates and the number of applications in every discipline were published by the State department (Table 1). Three main categories were distinguished. In the first category, including Law, Economics & Management (L&M) disciplines, each candidate applies on average to 50% of the opened positions. In the other categories, including Science on the one hand and Literature and Humanities on the other hand (H&S), the number of candidates per position (pressure) is significantly higher and the number of applications per candidate is significantly lesser. Globally, the hiring process is efficient in the sense that the recruitment rate is 98%. The local hiring rate, that is the percentage of universities recruiting candidates who passed their PhD in this same university, is circa 28% (37% in L&M, 24% in Humanities and 28% in Science).

Agent Preferences

It might be safely assumed that universities aim at recruiting the best candidates while candidates aim at being recruited in the best universities. Usually each agent has however different quality criteria; and, would it exist, the "true quality" ordering is unknown.

The proposed modelling will thus proceed in a backward manner, assuming that there exists such a "true ordering", of which each agent preference ordering is a perturbed variant. Only two types of perturbations are considered at the moment, respectively based on locality preferences and on random noise (see below).

Formally, letting U denote the number of universities, it is assumed with no loss of generality that the set of universities {u 1 , . . . , u U } is ordered according to the "true ordering". Symmetrically, C denotes the number of candidates and {c 1 , . . . c C } the set of candidates ordered after the "true ordering".

Multi-Agent based Model

The MAS involves two types of agents, candidates {c 1 , . . . , c C } and universities {u 1 , . . . , u U }, where an agent index stands for its rank after the (unknown) "true ordering". Furthermore the model is spatialized, that is, to each agent are associated 2D coordinates (in [0, 1]). The home University of an candidate is the nearest one after the Euclidean distance.

Candidates

Candidate c i is characterized from five parameters. The first two parameters (in [0, 1]) govern his preference ordering: i) elitism e i stands for his bias toward the best universities; ii) locality ℓ i stands for his bias toward the nearest universities. A random perturbation, modelled as (1e iℓ i )V with V uniformly drawn in [0, 1], accounts for his subjective preferences. Overall, the quality q(i,t) of university u t for candidate c i is computed as (the lower the better):

q(i,t) = e i × t U + ℓ i × d(c i , u t ) + (1 -e i -ℓ i ) ×V
Three more parameters are used to model the application strategy of candidate c i . A risk-propensity parameter r i determines whether he rather applies to the top-ranked universities (according to the preference ordering q(i, •)), or to the universities best matching his own rank. Precisely, the strategic ordering of c i is defined as (the lower the better):

s(i,t) = r i q(i,t) + (1 -r i )
|i -t| C His application strategy is finally defined from the number N i of positions he will apply to; c i applies to the top N i universities after the ordering s(i,t). Independently, c i applies to his home University with probability h i (empirically, candidates always apply to their home university).

Universities

Likewise, university u t is characterized from four parameters. The first two parameters (in [0, 1]) govern his preference ordering: i) elitism e t stands for its bias toward the best candidates; ii) locality ℓ t stands for its bias toward local candidates. Lastly, a random perturbation modeled as (1e t )V with V uniformly drawn in [0, 1], accounts for the "subjective" preferences of university u t . Overall, the quality r(i,t) of candidate c i for university u t is:

r(i,t) = (e t × i C + (1 -e t )V )(1 -ℓ t .δ i,t )
where δ i,t is 1 iff c i is local to u t and 0 otherwise. University u t selects the candidates to be interviewed after its risk propensity r t and a SelfAssessment parameter o t , where o t is positive (respectively negative) if university u t tends to consider itself less attractive (respectively more attractive) than it is after the "true" university ordering. More precisely, its strategic ordering is defined as:

s ′ (i,t) = r t × r(i,t) + (1 -r t ) × |i -(t + o t )| C
Two settings, referred to as NoLearning and Learning, are distinguished in the following. In the NoLearning setting, o t is set to 0. In the Learning setting, o t is adjusted after each "move" (yearly recruitment). In the case the university did not recruit its candidate, it lowers its expectation and o t is incremented. Otherwise o t is decremented with probability α, where α is computed after the empirical hiring rate2 ). s

Interaction rules

Every candidate c i applies for the top N i positions after ordering s(i, •), where N i is uniformly selected in [1, Max.Application], and he applies to home university with probability h i .

Every university u t produces a shortlist of 5 names, the top 5 candidates after ordering s ′ (•,t) 3 .

Every candidate c i thereafter ranks the universities having shortlisted him after the q(i, •) ordering. Eventually, the candidates and universities preferences are aggregated by a variant of Stable Marriage algorithm [START_REF] Baiou | Student admissions and faculty recruitment[END_REF], an optimal matching is derived, and the recruitment decisions are made accordingly.

Simulation Results

Methodology and Experimental settings

The main two efficiency indicators of an ALM are the HiringRate (fraction of positions fulfilled) and the LocalHiring rate (fraction of positions fulfilled by local candidates). We further consider the FameLoss of each university, defined as the difference between the rank of the recruited candidate and its own rank (not fulfilled positions are not considered).

The key parameters of the MA-based model (number of positions, of candidates and maximal number of applications per candidate, size of the shortlist) are calibrated after the empirical evidence presented for the H&S disciplines 4 (section 4). The behavioral parameters (elitism, localism, risk-propensity) are set to the so- 2), studied and validated in [START_REF] Caillou | Modelling a centralized academic labour market: Efficiency and fairness[END_REF]. The simulations were performed using the RePast Framework [START_REF] North | Experiences creating three implementations of the repast agent modeling toolkit[END_REF]. All reported results are averaged over 1,000 independent simulations with same parameter setting.

No learning setting

In the NoLearning case (o t = 0), the results closely match the available ground truth: HiringRate rate is 97% (vs 94% in empirical data) and Local Hiring rate is 28% (vs 28%). Interestingly, the HiringRate and the average number of received applications do not vary linearly w.r.t. the university rank. More precisely, four categories of universities can be distinguished (Fig. 1):

• The Best (Top 8 universities) have a high HiringRate and receive many applications. The Best universities choose the best candidates, who come. The Local-Hiring rate is the lowest one (Fig. 2). • The Good (rank between 9 and 21) have a low HiringRate although they receive a high number of applications. These universities, in the shadow of the Best ones, particularly suffer from the limited size of the short list to select the best candidates. While many good candidates apply to the Good universities, if they are selected they seldom come; they go to the Best universities. with a disappointingly low rank. Furthermore, the FameLoss increases with the risk propensity (Fig. 3). This unexpected phenomena is blamed on the "subjectivity" effect involved in the preference r(•,t). The more risk-taker the university, the more it follows its own preference ranking, possibly selecting candidates with low rank due to subjective or local preferences.

Learning Universities Setting

In the Learning case, universities are allowed to increase/decrease their SelfAssessment depending on the success of the past hiring rounds. The results (averaged over 1000 independent runs) are measured after stabilization (1000 time steps). As could have been expected, learning makes universities more efficient: the HiringRate increases compared to the NoLearning case (Fig. 1). The SelfAssessment curve (Fig. 4) displays contrasted situations, mirroring the HiringRate curve (Fig. 1 -NoLearning case). Roughly speaking, the Best universities tend to overestimate themselves, the Good ones, to depreciate themselves (in order to anticipate the defection of their candidates), the Medium ones seemingly have no bias, and the Bad ones underestimate themselves.

The impact of the risk propensity is analyzed wrt the FameLoss, as the Hir-ingRate does not discriminate among good and bad universities in the Learning case. Fig. 5 suggests that the risk propensity has no impact on the FameLoss except for the Best universities, that should rather have a conservative strategy (low risk propensity).

In the meanwhile, the SelfAssessment parameter features a high impact on the FameLoss (Fig. 6). If Best universities overestimate themselves, the weight of their subjective preferences increases, which results in recruiting lower-ranked candidates everything else being equal. Inversely, Good universities should not deprecate themselves in order to minimize the Fame loss. Quite the contrary, the Medium and Bad universities optimize their FameLoss by underestimating themselves.

Conclusion

This paper, resuming an earlier work devoted to the inefficiencies of Centralized Academic Labor Market [START_REF] Caillou | Modelling a centralized academic labour market: Efficiency and fairness[END_REF], investigates how universities can increase their hiring rate. The proposed mechanism, relying on the self evaluation of the universities expectations, duly addresses the market inefficiencies regarding the Hiring rate. Extensive empirical investigations however suggest that this way of increasing the hiring rate can entail some undesirable Fame Loss. Specifically, Best and Good universities should not underestimate (respectively overestimate) themselves in order to recruit best or good candidates. Quite the contrary, Medium and Bad universities should deliberately underestimate themselves to secure the recruitment of acceptable candidates.

Further research will consider more comprehensive learning/optimizing setting for universities and candidates, allowing them to fine tune their behavioral parameters in order to maximize their consolidated Fame for universities, and their job quality for candidates.

Fig. 1 Fig. 2

 12 Fig. 1 HiringRate versus University Rank in the NoLearning and Learning cases

•

  The Medium (between 22 and 39) have a high HiringRate, despite the fact that they receive few applications. They interview good risk-adverse candidates and local candidates. The short-listed candidates (including local candidates) come, as the Medium universities is the best they can pretend to. Both HiringRate and LocalHiring rate are high. • The Bad (between 40 and 50) also receive few applications; they have a low Hir-ingRate and a very high LocalHiring rate. Like Medium universities, they interview good risk-adverse and local candidates; however their top-listed candidates are more likely to defect if they can, and the HiringRate therefore decreases. With respect to the FameLoss criteria, Fig 3 shows two groups of universities with significantly different behaviors: Best and Good universities recruit the best candidates they can attract whereas Medium and Bad universities recruit candidates

Fig. 3

 3 Fig. 3 Impact of risk-propensity on FameLoss, for Top, Good, Medium and Bad universities in the NoLearning case

Fig. 4

 4 Fig.4Over and Under assessment of Universities vs Rank (learning setting). Top universities tend to over-estimate themselves; good and bad universities tend to under-estimate themselves; medium universities show no bias.

Fig. 5

 5 Fig. 5 Impact of risk-propensity on FameLoss, for Top, Good, Medium and Bad universities in the Learning setting

Table 1

 1 The French academic labor market in 2007.

	2007	Total L&M Hum. Science
	Positions	2110 324 695 1000
	Candidates	9318 555 3135 5540
	Applications/candidate 8,3 26,8 8,8	6,0
	HiringRate	98% 94% 99%	99%
	LocalHiring rate	28% 37% 24%	28%
	nbSections	57	6	25	23
	Avg. nbJobs / sect.	37,0 54,0 27,8	43,5
	4 Academic Labor Market Modelling
	This section describes the Multi-Agent model proposed for the French academic la-
	bor market, together with the assumptions made regarding university and candidate
	preferences.

Table 2

 2 Parameter Values in the Simulations

		General		Candidates		Universities
	Positions Candidates Max.Application ω e i ℓ i	r i	h i e t	ℓ t	r t	o t
	50	200	20	.97 .7 .1 U[.1; 1] 1 .7 U[0, .2] U[.1;1] 0

A pre-filter referred to as "qualification" is used to reject PhDs with no teaching experience. This step is left out of the study for the sake of simplicity.

Formally, α is such that the average hiring rate converges toward the empiric rate ω. At the equilibrium, the expected increase equals the expected decrease:1 -ω = ω × α ⇒ α = 1 -ω ω

For the sake of simplicity, the impact of the live interviews is not accounted for in the model.

The L&M setting corresponds to a saturated market, where almost

50% of the candidates apply to every job; in this situation a high locality bias is needed to enforce a reasonable hiring rate, as shown in[START_REF] Caillou | Modelling a centralized academic labour market: Efficiency and fairness[END_REF].


Batoul Achaal

Mohamad Rida Mortada

Ali Mansour

Abbass Nasser

Wireless Communication Attack Using SDR and Low-cost Devices

Keywords: SDR, Wireless communication attack, GPS, RFID

While Wireless communication (WLC) enhances the user mobility and extends the connection and services to extreme isolated points, is the only way to establish a connection over long distance (mainly earth and space), it has many weak points: Interference, Spectrum limitations, bandwidth cost, various regulations, etc. But the major drawback is the security and risk vulnerabilities. To clarify this idea and highlight several security issues, we are working on the weak points of our wireless networks and communication protocols. In this manuscript, we develop several scenarios of Wireless attacks using simple and lowprice equipment. Indeed using Software Defined Radio (SDR), a potential hacker can now access a wide range of wireless-based communication like Keyless entry, GPS and RFID system. It can also interfer and jam several other WLC services and networks.

Introduction

SDR is a wireless enabling technology that can be used in a variety of applications. Its main goal is to replace analog components and hardwired digital devices -as feasible-in the transceiver, with programmable devices [START_REF] Mathew | Software-defined radio: a brief overview[END_REF]. A potential hacker can now tap into many form of wireless-based communication due to the low cost of SDR [START_REF] Mansour | New challenges in wireless and free space optical communications[END_REF]. Keyless, Radio frequency identification (RFID) tags, and Global Positioning System (GPS) are all examples under risk. In [START_REF] Flavio | Lock it and still lose it-on the security of automotive remote keyless entry systems[END_REF], the authors present the gap in keyless access systems employed by major manufacturers, and their weakness using a variety of equipment, including SDRs and low-cost RF modules. the GPS security remains a critical issue related to the global information infrastructure. Many methods of GPS attack are presented in [START_REF] Feng | Software-defined radio implemented GPS spoofing and its computationally efficient detection and suppression[END_REF] [START_REF] Larcom | Modeling and characterization of gps spoofing[END_REF] [START_REF] Wang | Time and position spoofing with open source projects[END_REF] based on SDR. Other critical attacks are directed to RFID systems. E-passports, access control, and payment systems are all examples of contactless cards and tags based on RFID systems. Attackers can pick up the radio signals and eavesdrop on the communication between a tag and a reader. With the introduction of SDR, it is now possible to use generic equipment and demodulate in software to jam and attack RFID system. Hereinafter, we mainly focus on WLC attacks that can be conducted using the following platforms:

1. The HackRf One 3 is a SDR peripheral that can transmit and receive radio signals at frequencies ranging from 1 MHz to 6 GHz. The first way to com-municate with the device is by hackrf transfer program 4 . The second method is using the GNURadio package. This paper discuss the most prevalent WLC attacks, using low-cost SDR devices. The first section "SDR based relay attack" explains how to use SDR to realize replay attacks. The two main categories of GPS-based threats, jamming and spoofing, are demonstrated in the " GPS Jamming & spoofing " section. In the third section, we discuss the ability to jam and eavesdropping RFID using commercial SDR, and finally we proposed an approach for a RFID tag emulator using low-cost devices.

SDR based relay attack

This section illustrates the concepts of using SDR in exploitation Cyber Security vulnerabilities, such a: relay attacks when applied to a remote-controlled car for capturing and replaying control signals. The relay attack is a security attack in which a data communication between two parties is intercepted and repeated with or without manipulation regardless the two parties' awareness. In our work, GNURadio and HackRF were used to hack a remote-controlled car. A simple attack may contain two phases. Intercept and record a control signal, and then replaying it later using the HackRF's transmit feature.

Capturing the control signal

Using a DVB-T & Gqrx or a spectrum analyser, one can analyze the intercepted signals; in our case, we found that the transmission system is using 27.15 MHz as a carrier frequency. GNURadio can be used to intercept the signal and store it in wave format. We identified and stored 4 control signals related to a remote-controlled car, we called these signals: Up -Down, Left and Right.

Transmission of the control signal

First, a flowgraph for replaying the signal must be created in GNURadio, Figure 1. The "Selector block", and the "QT GUI Range block" allow the transition between commands. "Throttle block" flow of samples such that the average rate does not exceed the specific rate. "Osmocom Sink block" replay the signal By adjusting appropriate transmission power and other parameters (carrier frequency, bandwidth, etc), we succeeded to overwrite the command of the remote-control and replace it by the signals generated by our GNURadio software and transmitted using the HackRF platform. This kind of scenario can be applied to control a wide variety of drones and remote-controlled devices.

SDR based relay attack applications

The authors of [START_REF] Yash | Cyber attacks on smart cars using SDR[END_REF] described replaying attacks on entry keys of cars, the process in there work carried out using SDR tools. The Honda City i-vtec in India was the test subject. The Replay attack was successfully executed in the experiment. We should point out that this type of easy relay attack will only work on older cars that don't have rolling code security. Samy Kamkar, a speaker at the 2015 Def Con conference 7 , described how he constructed a device called "RollJam" that can wirelessly break the rolling code protection afforded by wireless entry keys. The basic idea is to jam the signal using a SDR or another RF device, collect the second rolling code after two key pushes, and then replay the first. The attacker now has access to the second unused rolling code, which can be utilized at any time [START_REF] Kamkar | Drive it like you hacked it: New attacks and tools to wirelessly steal cars[END_REF].

GPS Jamming & spoofing SDR based

GPS Background

The global positioning system (GPS) have become ubiquitous in most modern activities, from network time synchronization to locating. GPS was created as a military system. However, due to its broad civilian use, it is subject to jamming and spoofing attacks, which are now possible to anyone with a SDR [START_REF] Feng | Software-defined radio implemented GPS spoofing and its computationally efficient detection and suppression[END_REF]. Based on data received from several GPS satellites, the GPS receiver estimates its own dimensional position. Each satellite has a precise record of its position and time, which it sends to the receiver [START_REF] Larcom | Modeling and characterization of gps spoofing[END_REF] [START_REF] Wang | Time and position spoofing with open source projects[END_REF]. The two carrier frequencies are L1 at 1575.42 MHz and L2 at 1227.60 MHz. [START_REF] Shah Zahid Khan | On GPS spoofing of aerial platforms: a review of threats, challenges, methodologies, and future research directions[END_REF]. In our project, we are mostly concerned with the L1 civilian band.

GPS jamming

The intentional interference or jamming GPS is defined in [START_REF]Vulnerability assessment of the transportation infrastructure relying on the global positioning system[END_REF] as the release of radio frequency energy of sufficient power and with the correct qualities to prevent receivers in the target area from tracking GPS signals. The implementation of a five GPS jamming techniques using low cost SDR platforms is detailed in [START_REF] Ferreira | Effective GPS jamming techniques for UAVs using low-cost SDR platforms[END_REF]. We constructed our platform to test in practical the capacity of SDR in jamming GPS. The HackRF One was used to send a signal developed in GNURadio in order to jam a mobile phone's GPS signal. A "noise source" with Gaussian type, with a sampling frequency of 2 MHz was chosen as the source. The transmission frequency was set at 1.57542 GHz, which is the L1 GPS frequency. The average power spectral density is approximately -50 dBW/Hz . Using the GPS Test app, we test the target phone's GPS location. Figure 2 illustrates the situation in which the app was unable to receives the original GPS signal, as a result, the application became unable to report the location of the mobile device during GNURadio code executing.

GPS spoofing

While jamming just needs emission of an effective interfering signal and is easily identified by the loss of services, spoofing is more complex since it sends erroneous data to a user expecting to receive reliable data [START_REF] Kazim | Review of spoofing and jamming attack on the global navigation systems band and countermeasure[END_REF] [START_REF] Goavec-Merou | GPS spoofing using software defined radio[END_REF]. The equipment required to spoof the GPS signal comprises a computer capable of creating the spoofed signal connected to a HackRF. To communicate with the HackRF in this situation, we use the hackrf transfer 8 utility. A classic GPS spoofing attack consists of two steps: creating a binary transmitting file, and broadcasting a fake GPS signal using the binary file previously created. GPS-SDR-SIM is an open source projects to create GPS baseband signal, a binary transmission file, that corresponds to the intended fake location, which can be found on GitHub 9 . The code was mainly generated by Takuji Ebinuma [START_REF] Wang | Time and position spoofing with open source projects[END_REF]. The daily GPS broadcast ephemeris file (BRDC) provides the precise location data of each satellite, allowing receivers to calculate position using prior information in a specific day. BRDC in RINEX format (Receiver Independent Exchange Format), can be downloaded from NASA Archive of Space Geodesy Data10 . The GPS-SDR-SIM takes the BRDC, and a desired location as input then, it creates a binary file named gpssim.bin 3a, that can be played back on a SDR platform in order to emulate fake GPS signals. For transmitting the signal, we use hack transfer with gpssim.bin as input data file, carrier frequency of 1575.42 MHz, and a sampling rate = 2.6 MHz, figure3b. The initial position is shown in Figure 4a, which is France. When the HackRF start transmitting, the "Google Map" changed positions point to a fake location Lebanon, Figure 4b. Figure 4c demonstrates the fake satellites viewed by the app.

GPS attack applications

In [START_REF] Aru Saputro | Implementation of GPS attacks on DJI phantom 3 standard drone as a security vulnerability test[END_REF], the authors apply these methods into DJI Phantom 3 Standard drone. According to the results of their study, GPS jamming and GPS spoofing attacks can cause the drone to lose control by disrupting the GPS signal. In addition, the authors of [START_REF] Zheng | Hijacking unmanned aerial vehicle by exploiting civil GPS vulnerabilities using software-defined radio[END_REF] fake-GPS-by-joystick11 project, which allows them to manipulate GPS receivers' reported position in real time using a joystick. Because of its high efficiency and ease of use, they use SDR platforms in all experiments.

RFID Jamming and Attacks

RFID Background

RFID systems work on the principle of using tags to identify items. The tags emit messages that can be read by RFID readers. The majority of RFID tags contain a unique identifier (UID). RFID tags are divided into two types, active and passive based on their electrical power source. Passive tags are introduced in most RFID applications because of their low cost. As a result, we'll concentrate our work on passive tags. In RFID passive applications, the tag (called Proximity IC Card (PICC)) receives the signal from the reader (called Proximity Coupling Device (PCD)) when it falls in its range. Subsequently, PICC stores the extracted energy of the reader PCD transmission. The technique behind is known as inductive coupling [START_REF] Weinstein | RFID: a technical overview and its application to the enterprise[END_REF].

Our goal is to present different ways for RFID jamming and eavesdropping. Then we proposed a method to emulate a tag spoofing the hacked one. We choose to use a RFID-RC52212 module connected to an Arduino UNO for the demonstration of some part. This module is based on ISO/IEC 14443 Type A 13.56 MHz contactless smart card standard.

RFID jamming

Reading RFID tag without permission, can lead to privacy issues. To overcome this problem, security-related changes to traditional standards have been made. The authors in [START_REF] Bothe | Enhancing privacy for passive UHF RFID using an SDR-based reactive jammer[END_REF] suggest a reactive strategy to prohibit unwanted access by artificially interfering with reader commands for a brief period of time to protect such tags. The idea behind their Jamming approach, is to use GNURadio with SDR devices to receive signal from PCD, analyse to detect the RFID activity and then transmit short, arbitrary signal pulses to interfere with the reader command. This approach can be used by attackers in jamming a legitimate passive ultra-high frequency (UHF) tag. Researchers worked on blocking the e-voting system that replaces paper votes with near-field RFID tags, and were successful in prevent the commmunication PCD-PICC [START_REF] Oren | RFID jamming and attacks on israeli e-voting[END_REF]. The authors demonstrated that transmitting a powerful signal on 14.408 MHz is enough to block the signal from the PICC. The answer of an ISO14443 PICC is transmitted using load modulation on a subcarrier 847.5 khz. Two side bands at 12.712 MHz and 14.408 MHz are produced. Both sidebands function as data carriers for the tag and are essentially the same, but only the top side band (14.408 MHz) is evaluated by the PCD [START_REF] Oren | RFID jamming and attacks on israeli e-voting[END_REF][19].

RFID Eavesdropping

In [START_REF] Frédéric | RFID eavesdropping using SDR platforms[END_REF] the authors describe a platform for recording RFID signals that includes a specific RFID antenna, a DVB-T receiver, an upconverter and a PC with GNURadio software. We rebuilt that platform in order to record the forward and backward signals coming from PCD and PICC respectively. In the next paragraph, we analyzed the signal that has been recorded. ISO/IEC 14443 is a half-duplex block transmission protocol. Request type A & B (REQA, REQB) commands are sent by the PCD to scan the field for tags, while there is no tag. If an Answer To re-Quest (ATQA or ATQB) is received, the procedure to activate card starts. Prior to the transmission of actual data, the standard defines Anticollision phases, which are used to verify that the tag is correctly selected. The PCD activates a specific tag. The PICC responds with a Select AcKnowledge (SAK) instruction, which indicates the tag's type. HALT command is used to deactivate the PICC [20]. The PCD signal and the PICC response, which have a higher amplitude, are shown in Figure 5a. The used binary code is a complement to the Manchester code that has already been read. Each byte is ordered from least significant bit to most significant bit, with a parity bit following each byte (red rectangle in Figure 6). We have successfully extracted the sent UID : 1554C005.

RFID PICC Emulator

Having recovered all the bits of signal including (bits of parity and checksum) and knowing whether the PCD or the PICC is doing the transmission, and understanding the functionality of standard, are all important for tag emulation. The Tag has been programmed to respond to commands based on specific protocol. As a result, simply replaying the recorded signal to make the PCD think the existing PICC in his field is not a choice. Without any external input, the authors of report [START_REF] Giechaskiel | Eavesdropping on and emulating MIFARE ultralight and classic cards using software-defined radio[END_REF] attempts to simulate both the reader and the tag. The hardware tag emulation implementation was not as successful. In the output, the signal's shape is alternated. Our goal is to imitate tag in terms of giving his UID and being able to notify his presence in the field of any PCD that works with ISO14443 and communicate with it. Knowing that, the transmission bit-rate of data must be equals to 106 Kbits/s. Therefor, we must modify the load at the receiver coil with a frequency of 106 KHz. Hence, the PIC16F877A microcontroller is used with a clock of 20 MHz which can reach such frequency (106 KHz) by toggling its output pin. The Figure 7 depicts the simplified circuit of RFID emulator. As we can see, the base of transistor is connected to PORTA 1 of microcontroller, while the coil is connected to a permanent load R1||C1 via a full bridge (the bridge is used to match between the AC coming from the coil and the DC coming from the control circuit). When the PORTA 1 is LOW, the transistor is open, thus, the coil faces a load represented by R1||C1. Otherwise, if the PORTA 1 is HIGH, then, the transistor is close and the load becomes R1||R2||C1 which is less than R1||C1. Therefore, in order to represent a digital "1" for example at PORTA 1 in Manchester coding, we must firstly set the PORTA 1 to LOW for 4.7µs then to HIGH for 4.7µs. In this case, if the coil is at the proximity of a RFID reader, the RFID reader will reveal a change in the electric current due to the change in the load in the secondary coil of the emulator, and thus it will be translated into a digital "1". By reversing the process the digital "0" is represented. In our case, we have succeeded in getting the PCD to read a UID from our emulator as if it were coming from a real PICC. However, the PCD reads a different UID each time, knowing that we always send the same data. Which leads us to suppose that the reader doesn't check the validity of the data received using the checksum field. Some noises and a loss of synchronization between the reader and the emulator leads us to these undesired results.

Conclusion

Wireless networks based on radio transmission have a number of vulnerabilities. These can be intercepted, injected, and jammed using low cost devices. In this paper, we gives a quick overview of different WLCs attack scenarios that can be carried out with low-cost hardware. SDR is ideal for a variety of attack and hack operations in different fields, such as keyless entry, GPS, and RFID systems. Finally, We used low-cost hardware to emulate the tag as part of our eavesdropping RFID attack. We were able to get the reader to read a UID from our emulator as though it came from an actual RFID tag. The reader, on the other hand, reads a new UID each time. In the future, we will work to correct the issues.

4Figure 1 :

 1 Figure 1: GNURadio flow graph for replaying the signals

Figure 2 :

 2 Figure 2: As a result of the jamming of initial GPS signal, the "GPS Test app" was unable to identify the location of the target mobile device.

  (a) GPS baseband signal Generated (b) Transmitting fake GPS signal

Figure 3 :

 3 Figure 3: GPS spoofing

  present a technique for stealing a flying DJI Phantom 3 Standard drone by exploiting civil GPS vulnerabilities. They use the Realtime-generate-(a) Initial position, France (b) Fake position (c) Satellites viewed by the GPS Test app

Figure 4 :

 4 Figure 4: Receiving fake GPS signals

  (a) Part of signal from PCD and PICC (b) Data transmission (UID)

Figure 5 :

 5 Figure 5: Recorded Signal

Figure 6 :

 6 Figure 6: UID extracting : "1554C005"

Figure 7 :

 7 Figure 7: RFID card emulator using PIC16F877A microcontroller

  2. Digital Video Broadcasting -Terrestrial (DVB-T) receiver 5 is a SDR radio receiver capable of receiving signals in the frequency band from 24 -1760 MHz. 3. GNURadio is an open source signal processing software development kit. It can handle a variety of input sources, processing blocks, and output formats. 4. Gqrx 6 is an open source software SDR, powered by the GNURadio. FFT plot, waterfall, and spectrum analyzer modes are among the main features.

https://www.passion-radio.fr/emetteur-sdr/hackrf-sdr-75.html

https://www.youtube.com/watch?v=UNgvShN4USU

We discussed it briefly in the introduction.

https://github.com/osqzss/gps-sdr-sim

https://cddis.nasa.gov/Data and Derived Products/GNSS/GNSS data and product archive.html

This is a derivative of the GPS-SDR-SIM project.

https://www.gotronic.fr/art-module-rfid-13-56-mhz-tag-rc522-25651.htm#complte desc

Acknowledgment

The authors are grateful to AID-DGA (l'Agence de l'Innovation de Defense a la Direction Generale de l'Armement -Minitsere des Armees) & ANR (Agence Nationale de le Recherche en France) for supporting our ANRASTRID -Project (ANR-19-ASTR-0005-03).