Keywords: socio-technical regime, transition, strategic niche management, unlocking rules

Why aren't they locked in waiting games? Unlocking rules and the ecology of concepts in the semiconductor industry.

In a multi-level perspective, regimes can be clearly described as long as they remain stable. To understand how regimes and niches interact during transition, the article contrasts two models of regimes in transition(s). The classical model of evolutionary niches suggests misalignments between rules and competition between niches. Transition management, technological innovation systems and works on transition pathways suggest a second model based on "unlocking rules", which support collective work on a structured set of emerging technologies. The latter model is illustrated with a case study on the International Technology Roadmap for Semiconductors (ITRS).

Introduction

This paper deals with transitions in socio-technical regimes and the nature of regimes when they are in transition. In a multi-level perspective (Geels 2004;[START_REF] Kemp | Regime shifts to sustainability through processes of niche formation: The approach of strategic niche management[END_REF][START_REF] Nill | Evolutionary approaches for sustainable innovation policies: From niche to paradigm?[END_REF], transitions from one socio-technical regime to another can be explained by the interplay of stabilizing mechanisms at the regime level and (regime-) destabilizing pressure of new societal needs (at the landscape level), combined with the emergence of radical innovation at the niche level. This multi-level framework accounts for some historical transitions (eg [START_REF] Geels | Technological transitions as evolutionary reconfiguration processes: A multi-level perspective and a case-study[END_REF]2005)) and for a specific form of policy for socio-technical regime transitions: strategic niche management (SNM). SNM advocates the creation of socio-technical experiments in niches to facilitate the incubation process of the new technology while being protected from the constraints of the dominant regime. However, some authors have underlined that SNM as a change strategy can have a limited impact [START_REF] Caniëls | Strategic niche management: Towards a policy tool for sustainable development[END_REF][START_REF] Nill | Evolutionary approaches for sustainable innovation policies: From niche to paradigm?[END_REF]. A "good" niche has to meet such demanding conditions (good choice of technology, experiment, market diffusion strategy, etc.) that in many cases, the niches are not capable of changing the socio-technical regime [START_REF] Caniëls | Strategic niche management: Towards a policy tool for sustainable development[END_REF][START_REF] Smith | The governance of sustainable sociotechnical transitions[END_REF].

Along similar lines, it has been suggested [START_REF] Markard | Technological innovation systems and the multilevel perspective: Towards an integrated framework[END_REF]) that although it is indeed important to understand what happens at the niche level, it is also critical to understand what happens beyond that level, at the meso-level. At this level niches compete [START_REF] Geels | Technological transitions as evolutionary reconfiguration processes: A multi-level perspective and a case-study[END_REF] but also combine or aggregate (Geels 2005) and complementary effects of developments in different niches appear [START_REF] Nill | Evolutionary approaches for sustainable innovation policies: From niche to paradigm?[END_REF]. Few studies have been done at this level [START_REF] Genus | Rethinking the multi-level perspective of technological transitions[END_REF] creating a major gap in the literature. To address this gap, we investigate the management of a set of niches, at the meso-level of the regime, whilst the regime is in transition. But, first of all, how can we characterize regimes in transition?

In the model of transition in socio-technical regimes (Geels 2004), the regime in transition is described as a stable combination of rules, actors and technical systems that competes with niches where the regime rules are loosened [START_REF] Geels | Technological transitions as evolutionary reconfiguration processes: A multi-level perspective and a case-study[END_REF]. However, this model leaves several open questions regarding the relationship, during the transition, between the regime level and the niches. Is the incumbent regime simply competing with the niches or is it able to interact and hybridize with them to mutate into a new regime? Are there alternatives to the evolutionary model?

To study these alternative models, in the first section we use the complementary perspectives of transition management and technological systems of innovation, which have studied situations where transition is managed at the regime level. In this situation, the logic of management has generated specific rules for the transition [START_REF] Kemp | Transition management as a model for managing processes of co-evolution towards sustainable development[END_REF]. Contrary to the evolutionary model where rules are loosened, weakened and then substituted by a new and more robust set of rules, in transition management and with technological systems of innovations, there are rules to support the transition. Our research question is: what are these rules, which do not lock new paths but create them? In cases where there are such rules, who are the actors and what kind of technical system can be associated with them?

In the second section, we show that the literature helps to characterize an alternative model for regimes in transition that relies on rules at the regime level, which we call "unlocking rules". We illustrate this with a case study of how the International Technology Roadmap for Semiconductors supports regular transitions in the semiconductor regime (third section). This illustration helps us analyse other facets of a regime with unlocking rules at the regime level: i) at this level, actors and rules deal with the ecology of concepts of technical systems that can be imagined by the actors at a certain point in time (and not only with the existing system); ii) the actors coordinate and work together on these concepts in a specific collaborative setting, which we call a "college of the unknown" (fourth section).

Models of regime in transition

Transition management and technological systems of innovation provide insights into alternative features of the evolutionary approach to technical change. [START_REF] Carlsson | On the nature, function and composition of technological systems[END_REF] conceptualized a "technological system of innovation as an entity that creates novelties and supports established technologies at the same time." They interpreted both the technological system and the sectoral system of innovation concept, which includes an innovation element that creates, diffuses and uses new products (or technologies) and a production element, which is "responsible" for established products (or technologies). The latter is responsible for incremental innovation (and could be assimilated into a stable socio-technical regime); the former is responsible for radical innovation, which can lead to significant transformations. Fundamentally, this analysis considers a system that integrates a capacity to innovate, both incremental and radical. It is a meso-level approach that reaches well beyond niche level processes [START_REF] Markard | Technological innovation systems and the multilevel perspective: Towards an integrated framework[END_REF] and can help to analyse the regime in transition.

The logic of unlocking rules

In this perspective, a main input of technological systems of innovation is the notion of structural and functional analysis [START_REF] Bergek | Analyzing the functional dynamics of technological innovation systems: A scheme of analysis[END_REF]Hekkert et al. 2007), which helped identify several sub-functions assigned to innovation systems: the generation and diffusion of knowledge, the guidance of search process, the creation of markets, entrepreneurial experimentation, legitimization, etc. They can be seen as rules leading to radical innovation. Instead of leading to path dependency, these rules tend to create paths.

Transition management has also pinpointed rules for the generation of radically new technologies. It is a model for managing transitions [START_REF] Kemp | Transition management as a model for managing processes of co-evolution towards sustainable development[END_REF] that includes the meso-level for a regime in transition. As a management model, it relies on rules and principles: long-term thinking as a framework for short-term action, thinking in terms of multiple domains, a focus on learning and learning about a variety of options and adaptive portfolios. This is not "intelligence" for planning, but an organized, stimulated Darwinist process of variation and selection. Once again, we find rules that do not lead to path dependency but, on the contrary, are formulated to overcome it. For instance, these rules counterbalance firms' tendency to have restricted technological horizons and bounded visions [START_REF] Rosenberg | The direction of technological change: Inducement mechanisms and focusing devices[END_REF], thus avoiding technologies with long development times. Whereas the rules identified in stabilized regimes tend to lock into a dominant design, these rules unlock by aiming to create new design paths.

Let's begin by analyzing the rules that unlock cognitively. With Nelson and Winter's approach [START_REF] Nelson | In search of useful theory of innovation[END_REF], a technological regime is defined as "the rule-set or grammar that is characteristic for the development of a technology and that guides not only the search activity of engineers, but also the actions and interactions of the other actors involved in technical development." Nelson and Winter gave the example of DC3 aircraft in the 30s, which defined a particular technological regime: metal skin, low wing, piston powered planes. The rules stabilize a representation of the object, of the functional target and the way to reach it. They lock potential paths by determining a technological trajectory.

By contrast, certain rules can create paths. For instance, the rules invented and taught at the Bauhaus design schools by famous teachers such as Klee, Itten and Kandinsky unlocked cognitive paths. Itten's course was an archetypal example of unlocking rules in art [START_REF] Itten | Design and form, the basic course at the Bauhaus and later[END_REF] [START_REF] Klee | On modern art[END_REF]: the laws of form, colour and shape helped students to disentangle too self-evident relationships between material-shapecolour-emotion and enabled them to explore beyond the clichés ("a warm fibrous wood"). We know the effects in term of generativity (famous objects, new grammars of forms, etc.). In engineering too, it has recently been shown that design theories and methods gain in generativity over time [START_REF] Hatchuel | Functions of innovation systems: A new approach for analysing technological change[END_REF]. The generative power results from the rules set by the new design theories, which increase the capacity to rigorously use more diverse types of knowledge and to consciously break away from technological routines. These theories propose unlocking rules, to be embedded in the design reasoning. They can be as simple as: "in the case of an alternative between two solutions, design a third one." They can be rules to inhibit the reuse of locking rules (eg rules to formulate design briefs such as "an aircraft without a piston engine"; "wood is not necessarily fibrous"; or "agriculture is not necessarily unsustainable") or to encourage the opening of new ones ("an aircraft with fuel cells").

In the logic of socio-technical regimes, rules are extended to include sociotechnical aspects [START_REF] Kemp | Regime shifts to sustainability through processes of niche formation: The approach of strategic niche management[END_REF]. Geels suggested that two other forms of rules be analyzed: regulative rules, ie explicit formal rules, which constrain behaviour and regulate interaction (eg government regulation) and normative rules, which confer values, norms, expectations and responsibilities and are internalized through socialisation processes (Geels 2004) (p. 904). Are there normative and regulative unlocking rules?

Normative unlocking rules can be seen in artistic milieus, where provocative, critical, inspiring comments are welcome and considered the relevant social behaviour. Here too, the example of Bauhaus provides interesting normative rules: students were encouraged to work together, to cross-evaluate their works and provide each other with constructive criticism [START_REF] Droste | Bauhaus Archiv Museum Für Gestaltung[END_REF], ie to inspire, stimulate and educate each other, as a means of providing the mutual enrichment and development of the individuals involved. In innovation management, innovation teams and innovative firms have been described as using organic ways of acting together, which can be seen as normative unlocking rules [START_REF] Burns | The management of innovation (Social science paperbacks)[END_REF][START_REF] Le Masson | Strategic management of design and innovation[END_REF][START_REF] O'connor | Major innovation as a dynamic capability: A systems approach[END_REF] since people are required to rapidly change the targets of the projects, to demonstrate radical innovation and to involve other stakeholders in their projects. In transition management, rules such as "societal experiments as bottom-up experiments" call for interaction in a way that unlocks the process. Normative locking rules are caused by social groups and support their stability. There are also rules that are caused by groups and which are likely to change the group, the individuals and the objects they are used to dealing with. In this sense, they are normative unlocking rules.

There are also regulative unlocking rules. Voluntary agreements [START_REF] Aggeri | Environmental policies and innovation : A knowledge-based perspective on cooperative approaches[END_REF] are an example of regulative rules at the European level, intended to give stakeholders the incentive to create new paths. Regulative rules can unlock, in the sense that they facilitate the emergence of alternatives (instead of configuring a regime towards a given path).

Transition management and technological innovation systems suggest that in certain cases of regimes in transition, some rules at the regime level unlock rather than lock. Locking and unlocking rules can be compared as follows: i) unlocking rules tend to break dominant design rules, whereas locking rules tend to stabilize one path; ii) unlocking rules are open-ended (increase the variety of potential paths), whereas locking rules are deterministic (decrease uncertainty). Note that unlocking rules are not a weakened form of locking rules. Works on regimes and dominant design have underlined that (locking) rules can be strong or weak and that they can constrain (to follow a framework) as well as enable (inside this framework). Unlocking rules are not necessarily enabling, as they can also be either strongly or weakly unkocking. They can constrain and enable the breaking of the dominant design rules and the generation of new paths.

The logic of actors and systems with unlocking rules

We have clarified a type of rule that can exist in some regimes in transition. Are there forms of actors and forms of "systems" that are consistent with such centrifugal forces?

Once again, transition management literature provides some insights. It analyzes the logic of "systems" and actors at the meso-level of a regime in transition and shows that it requires "special innovation platforms and support for selected paths" [START_REF] Nill | Evolutionary approaches for sustainable innovation policies: From niche to paradigm?[END_REF]; the actors should be able to coordinate their actions in order to adjust the exploration to take into account the learning acquired in all the niches. It is a model of governance for shaping processes of co-evolution using visions, transitions, experiments and cycles of learning and adaptation. The actors do not compete with one another, as described in the evolutionary process, but are required to work closely together, although not all the aspects of the technologies are known. They collaborate in the unknown.

Technical systems in transition at the regime level must be described differently. (Geels 2005) underlined the role of combination and aggregation between niches. [START_REF] Nill | Evolutionary approaches for sustainable innovation policies: From niche to paradigm?[END_REF] recommended that various transition paths should be explored, to avoid lock-in to a particular path. Analyzing the development of infant industries [START_REF] Caniëls | Strategic niche management: Towards a policy tool for sustainable development[END_REF] underlined the role of complementary developments in providing inputs or consuming outputs of a technology. In such situations, the borders of the system cannot be limited to the past regime but have to include the emerging technologies experimented in niches.

To conclude, the logic of unlocking rules helps identify an alternative to the evolutionary model of regimes in transition. In the latter, niches compete and follow an evolutionary path that enables some of them to become a new regime, which may replace the incumbent one. Unlocking rules suggest an interactive, generative model, in which the regime in transition takes part in the emergence of niches and evolves in close interaction with them, before finally being transformed into a new regime. A synthetic comparison is proposed below.

Case study: the International Technology Roadmap for Semiconductors

The logic of unlocking rules and the associated model of regimes in transition can be illustrated with the case of an industry roadmap, the International Technology Roadmap for Semiconductors (ITRS). ITRS intervenes at the meso-level of the semiconductor development regime. All the industry's major players (integrators, suppliers, universities, customers) use the ITRS to discuss and work together on the future technological generations (from +2 to +15 years). We used historical published and unpublished raw data from the ITRS and incorporated the key material gathered by [START_REF] Schaller | Technological innovation in the semiconductor industry: A case study of the international roadmap for semiconductors[END_REF]. We added to this historical material thanks to our own deep involvement in the ITRS process. One of the authors of this paper has attended 11 face-to-face meetings and over 25 conference calls of the ITRS International Roadmap Committee (IRC) since 2005 and has had access to working documents from several of the ITRS' specialized working groups. He has conducted in-depth interviews with most IRC members, with experts in many of the ITRS working groups (2 to 5 people in five special interest groups -one on photolithography, three on device architecture, one on materials) and with researchers in research labs in the US (in particular Stanford Nanoelectronic Group and Stanford Nanofabrication Facility, 6 interviews) and in Europe (LETI in France, 8 interviews).

We analyze the following three key aspects of the case: first, we check for case relevance by showing why ITRS is at the meso-level of a regime in transition(s); second, we describe the relationship between the incumbent regime and the niches; third, we focus on micro-processes inside this meso-level. In this way, we gradually bring to light the unlocking rules found in a regime in transition, and the actors and systems related to this kind of rule.

Case relevance: ITRS and the meso-level of a regime in transition(s).

We check that the semiconductor industry can be considered as a regime in transition. First, it shows a priori all the features of a regime: there are complex systems with many interdependencies, high sunk investments, complex actor networks, high sunk costs in R&D, specialized top-level expertise in very specific domains, etc.

Second, we find the expected pattern of tensions and niches: • Tensions: for more than a decade and for each new generation, engineers and scientists consider that the next generation will have to overcome critical bottlenecks with breakthrough technologies. Customer needs are changing; new businesses and functions are emerging regularly (RF filters, camera sensors, gyroscopes for smartphones and gaming, electronics for touch screens, etc.). • There are also a large number of niches in the semiconductor industry: each actor (integrator, supplier, R&D lab, etc.) regularly creates original prototypes to be developed further. Third, there have been changes in the regime -not only once, but regularly over several decades. On the face of it, the regime is governed by Moore's law whereby technologies are designed to be able to exponentially increase the number of components incorporated per integrated circuit by regular dimensional scaling. However, Moore's law has actually been responsible for multiple regime changes. For instance, it caused the emergence of new technologies and breakthrough architectural solutions, as in the case of photolithography for the semiconductor industry [START_REF] Henderson | Architectural innovation : The reconfiguration of existing product technologies and the failure of established firms[END_REF] or the use of new materials (in the last decade, the semiconductor industry, which was initially limited to silicon, has explored almost all the elements in the periodic table). Moore's law has also regularly changed the relationship between actors because, for each generation, there are always several ways of designing the whole system, so that the individual technology suppliers have always faced open-ended questions in terms of the performances they have to achieve in the system.

Moore's law can be seen as an unlocking rule as it obliges the actors to regularly open new technological paths. Contrary to the case of DC3, Moore's law constantly sets new technological challenges (see below) as well as market challenges (eg by inventing new uses for computer power [START_REF] Gawer | Platform owner entry and innovation in complementary markets: Evidence from Intel[END_REF]).

In this context, ITRS has a clear objective, defined since 1994 as follows: "The Roadmap is analogous to paved roads of proven technology, unimproved roads of alternative technologies, footpaths towards new technologies, and innovative trails yet to be blazed." (Semiconductor Industry Association 1994). Right from the start, it was therefore clearly the intention of ITRS' proponents to tackle changes in the technological regime.

Nonetheless, the ITRS is not a niche: • it has lived through several regime shifts (the ITRS effort was first initiated at the US national level in 1993); • it encompasses almost all the industry's players in all geographic areas: its International Technology Working Groups (ITWG) address almost all aspects of semiconductors (design, process, instruments, etc.) and are composed of experts from industry (chip-makers (50% of the members) and their equipment and materials suppliers (25%), research institutes (20%) and government agencies (5%)). The overall coordination of the ITRS process is the responsibility of the International Roadmap Committee (IRC), which has two to four members from each sponsoring region (Europe, Japan, Korea, Taiwan and the United States). • ITRS' audience is very large: the great majority of the research programs in the leading institutions we visited are explicitly related to ITRS roadblocks. • ITWGs do not carry out experiments: the members do experiments in their companies or labs, or report on experiments made elsewhere. Hence, the ITWGs are not niches but they report on and stimulate niche activities. ITWG members meet on a regular basis, most often organizing side-meetings while attending scientific conferences in their field. In addition, general ITRS meetings are held three times a year and are an opportunity for the IRC and all the ITWGs to get together to share information about the general direction of their work, solve pending issues and have cross-ITWG discussions, thereby ensuring overall coordination. The ITRS report is released annually.

Hence, we can say that the semiconductor industry is a case of a regime in repeated transitions and that the ITRS is at the meso-level. We can already identify a logic of unlocking rules, eg the initial mission of the ITRS and Moore's Law.

Unlocking rules for managing niches at the meso-level

How does the ITRS manage the interaction between the regime and the niches?

Revealing and sharing the challenges

The niches are first managed at the level of the Overall Roadmap Technology Characteristics (ORTC), a series of tables providing a consolidated summary of the key performance targets for various product lines (DRAM, Flash memory, microprocessor). They are not the result of existing technologies but a set of targets for designing future technologies capable of following Moore's Law.

By identifying the targets that have not been reached yet or that have proved to be out of reach with the existing technologies, ITRS helps reveal and share challenges at the industry level. It provides targets to be met by future niches.

Monitoring and supporting niche expansion

ITWGs translate these ORTC targets into more specific ones and identify potential solutions.

We can illustrate this by studying how an ITWG managed the emergence of a radical technology. As the dimensions of transistors continue to shrink, new physical effects arise, such as "gate leakage" due to the onset of a tunnelling effect through the gate oxide layer. The need for new gate dielectrics was identified by the ITRS as early as 1994, calling for new technological developments. A first solution was mentioned in 1997 and led to a more precise description of the technological niche for this issue.

Several niches were then monitored in the reports, with regular analysis of their likely performance and date of availability (a first breakthrough technology was launched in 2009). If we take a closer look at the monitoring process, we can see that target performance levels evolved considerably for two reasons:

• As knowledge accumulated, it became possible to set more precise schedules and more relevant performance levels.

• The quantitative evolutions were linked to the discovery of what was attainable in the technological path in question but also to the evolutions in other, complementary, technologies. For each challenge, the industry studied and developed other "knobs to turn". These alternative technological concepts were themselves subject to progress, which explains how the rate of progress on the technologies could be tuned. We find the same pattern in other ITWGs, which follow similar unlocking rules: identification of a need for a technological breakthrough, clarification of the technological concepts to be further explored and monitoring of the niches with relative positioning of the technologies.

Structuring a set of alternatives

To understand how a set of technological alternatives can be managed, we analyze the evolution of one such set over time. Figure 2 Since the engine of the semiconductor industry's evolution has been its ability to fabricate ever-tinier devices, one of its most recurrent research challenges has been to find ways to etch ever-smaller features. This part of the integrated circuit fabrication process is known as "lithography", and a whole research community is busy with its improvements. Within the ITRS, a specific ITWG is dedicated to its study. The finest resolution that can be reached by drawing with a laser is proportional to the wavelength of the illuminating light (Rayleigh principle). Since 1980, lithography equipment makers have therefore used lasers with decreasing wavelengths, ie 436nm, 365nm, 248nm and 193nm. Accordingly, the ITRS 2001 edition envisaged that optical lithography could be extended by developing 157 nm technology. Beyond 157 nm, solutions using extreme ultraviolet (EUV -13nm wavelength) or electron-beam direct-write were to be developed. However, using a different illumination wavelength is a costly alternative. To prolong the lifetime of the 193nm platform, several alternatives were indicated, such as controlled over-etching, and the development of better resists, to improve image contrast. These alternative technologies concerned breakthrough paths, e.g. distinguishing between printed gate length (following Rayleigh) and the final "physical" gate, hence allowing to decrease the latter while keeping the same wavelength.

Over time, the different niches built an interesting pattern. At a low level, new technology candidates were continuously introduced to reach the functional requirements within the existing platform. They shared many attributes with the existing platform. Many of these new technology candidates nonetheless broke away from some parts of the existing paradigms (eg "physical gate length = printed gate length" and "one print per feature" were respectively broken by over-etching and double patterning).

In parallel, research continued on the next platform: 157nm (until 2005) and Extreme UV, which requires the creation of in-depth knowledge on refraction optics.

On a third level, significant research efforts were also being made on another disruptive challenger, multiple e-beam lithography. Finally, "out-of-the-box" technologies were given visibility, by being included in the list of potential solutions, even though they were very abstract technological concepts (see "directed selfassembly" or nano-imprints).

ITWG niche management therefore appears to be based on unlocking rules. They do not offer alternative, emerging technologies, but monitor their emergence and differentiation. Using a biological metaphor, unlocking rules do not emerge in a selection process but in a speciation process: several distinct cells, presenting complementary features, can finally emerge from "stem" cells.

Unlocking rules for collective work at the meso-level.

Building potential solutions: handling divergent positions and negotiating in the unknown How do the actors work together to build a set of alternatives? What are the rules for collective work? We describe how new candidates for potential solutions were discussed in a specific field, device architecture. In late 2009 / early 2010, at the request of major memory manufacturers, two working groups held seminars to "reach approximate consensus on any "New Memory" technologies sufficiently mature to benefit from accelerated development" (internal working document). For each technology, proponents presented the pros and cons and the research needed, and circulated a white paper prior to the meeting. A "friendly critic" then presented a balanced assessment and finally, votes and discussions helped to identify critical research needs.

A closer look at the process reveals that far from being a judging process, it was a knowledge-building and knowledge-sharing one. For instance, the voting criteria were not decided on before the process began, but after the review of the white papers, ie taking into account the knowledge on the topic acquired during the process itself. Likewise, over the course of the face-to-face meeting, the classification of the technologies under review was changed, from 4 to 5 families, with some technologies moving from one family to another.

The ITWGs explained in a caveat that "the intent of this recommendation is to highlight technologies for additional roadmapping investment -but not at the expense of investment in or exploration of other candidates' approaches. We are not picking winners and losers". This was indeed the case, since all the technologies studied during the exercise were still present in the August draft versions of the 2011 ITRS edition.

Conditions for sharing information: collaboration and competition

Why do members take an active part in collaborative processes of this sort? Our data shows that disruptive technologies for semiconductors require transformations in large areas of the ecosystem. Alone, the disruptive innovator has very little chance of meeting all the conditions of compatibility in a complex, evolving system. We analyzed the schedules of ITRS meetings in detail. A working group typically spends between half and two thirds of the duration of the meeting in interaction with other working groups. The experts of one ITWG discuss, in detail, how the technological alternatives addressed by their own ITWG interact with those of the other ITWGs. The ITRS provides an arena to support the early propagation and integration of disruptive technologies: the innovators can benefit from early criticism; the providers of complementary technologies and the integrator can prepare for early integration; even the providers of incumbent technology can set relevant targets for their own technology developments.

Why do members participate fairly? According to ITRS participants, the different ITRS processes, such as regular updates, cross-ITWG meetings, regular evaluations, etc., all make it difficult for one actor to appropriate the proceedings for its own purposes. A free-rider is always possible, but would be rapidly excluded.

Conclusions

A model of regime in transition, based on strong unlocking rules

The ITRS illustrates a model of a regime in transition that does not follow the archetypal "evolutionary" pattern but is more based on a synergistic interplay between niches and the regime level. With regard to models of regimes in transition, we draw the following conclusions.

First, transitions rely heavily on unlocking rules. • Regulative rules: the official goals of ITRS consist in opening new paths "yet to be blazed" and in identifying the limit of the technical norms stabilized in the past generation in order to put them into movement. • Normative rules: at ITRS, the "proper" behaviour does not consist in "hiding" disruptive questions. On the contrary, the organizational routines all aim at revealing the open issues and the expected breakthrough, with the identification of technical challenges, rigorous monitoring of alternative technologies and regular comparisons between alternatives, putting potential technologies to the test of all the facets of the systems. The ITRS system is based on co-stimulation, friendly criticism and support for technology development. "Don't pick winners or losers" is the norm used to stimulate proposals, encourage participants, support the initiatives and to enrich and extend paths. • Cognitive unlocking rules are particularly striking at ITRS. The first is Moore's law. As described above, Moore's law does not lock-in but unlocks, in the sense that it stimulates radical technological innovation as well as disruptive market explorations. In dealing with niches, ITRS' basic cognitive rules consist in identifying and generating alternative technologies to make sure that the future performances will be met. It systematically builds multiple alternatives to each existing technology, encompassing improvements to the technological platform, emergence and preparation of credible alternatives (the next platform) and the proposal of crazy ideas. The logic of ITRS consists in regularly increasing the variety of alternatives (instead of selecting).

The logic of a system with unlocking rules: an ecology of concepts of sociotechnical systems

Second, we confirm that in a situation with many unlocking rules, the actors work on the incumbent system as well as the alternative niches. The case study provides conceptual refinements on this extended "system". ITRS actors use knowledge on the existing socio-technical system (its limits, design parameters, value, predictable improvements, etc.) but also work on several future alternative technologies addressed, or to be addressed, in niches. In these descriptions, emerging technologies are still partially unknown. In a regime in transition, the borders of the "system" have to be extended to the bundle of alternatives around this system. This bundle of technologies has a series of structures and interdependencies. Some alternatives have a lot in common. They are all part of the same platform or paradigm (the lithography paradigm using the 193nm laser). Others, on the contrary, break some rules at a very high level (e-beam, Gutenberg-style imprints, selfassembly, etc. all break the design rule "with lithography") or a lower level ("a lithography device based on Extreme UV (13nm) laser"). Over time, ITRS tends to maintain a structured set of technological alternatives, with three main types of expansions: improvements to the existing platform, creation and maturation of reasonable medium-term alternatives and crazy explorations.

There is a critical dynamic underlying this structured set. The dynamics are not only defined by the competition and selection processes but also by variety generation, synergies and speciation:

• Variety (re)generation: some niches help generate new ones, with a view to constantly maintaining the capacity to reach the required performance over time.

• Symbiosis: in ITRS, niches combine into more sophisticated solutions, as learning in one niche supports expansion in another. • Speciation: niches evolve in accordance with evolution in other niches, not by competing with each other but in order to reach a mutually beneficial positioning to cover specific performance areas. Finally, unlocking rules generate and are based on what can be called an ecology of concepts of socio-technical systems. The notion of ecology of concepts helps to characterize the structure of the alternatives that the actors are able to imagine and work on at a certain point in time. It underlines that the alternatives in this ecology grow together, with synergies and interdependent speciation.

The logic of actors working with unlocking rules: college of the unknown.

Third, we confirm that in a situation with unlocking rules, actors work in close collaboration. In the evolutionary model of transitions, only a few, "deviant" actors work in niches on alternative technology; the semiconductor industry follows a model of collaboration in the unknown. We can refine our description of this collaboration.

The collaborating actors are both "technology suppliers" and technology "users" (Intel, STMicroelectronics, Infineon, etc.), who are themselves strong designers. In this regime in transition(s), all the actors are able to set innovative targets, to investigate technology breakthroughs, to explore the new uses of emerging technologies, etc.

These actors do not necessarily share competences (which would be critical for confidentiality and IPR reasons), they discuss the nature of the open questions, unsolved problems and critical challenges. In this "exchange in the unknown", the "supplier" provides "ideas" and "stimuli" to support the design activities of the "receiver". The unlocking rules described above correspond to the rules governing the interactions between designers at this meso-level: they do not select each other ("we don't pick winners or losers"); beyond mutual prescription, the actors in ITRS interact as "design stimulators". They inspire each other. This logic of inspiration between actors is well known in art (artists in artistic milieus inspire each other and the artists inspire the viewers). Whereas usual approaches in technology management tend to underline evaluation-selection logics or prescription logics, ITRS provides inspiration-based coordination between designing actors.

ITRS gives visibility to a network of interactions that are mainly oriented towards enriching the ecology of concepts. We label this organization a college of the unknown, by analogy with the "invisible colleges" of Diana Crane [START_REF] Crane | Invisible colleges. Diffusion of knowledge in scientific communities[END_REF] who, studying research networks, noticed that a clique of researchers with direct and indirect links were influencing the works of the rest of the community. ITRS is also a college, where members know each other and have a great influence on the rest of the industry. However, this college is not oriented toward one scientific field but to the exploration of emerging technologies and the sustained renewal of the ecology of concepts.

ITRS illustrates a model of regimes in transition. It does not follow the "evolutionary" pattern but a generative, interactive model. It is based on unlocking rules (instead of locking rules), which support collegial work in the unknown (instead of independent, competing entrepreneurs) and maintain an ecology of concepts of socio-technical systems (instead of an evolutionary pathway of niches) (see figure 3

below).

Figure 2 -Regimes in transition with unlocking rules vs. locking rules

More generally speaking, this model, inspired by transition management and technological innovation systems, calls for further research on alternatives to the evolutionary model. It represents a form of sustained breakthrough innovation, organized at meso-level and involving intensive design activities. It suggests a design regime, ie a regime whose logic is the constant "transition" or, better still, the constant renewal of products, competences and uses. Such a design regime can be characterized by the design capacities of the actors, by the design rules that link these actors and by the ecology of concepts structuring their efforts. When design capacities are limited, when design rules focus on conformation, when the ecology of concepts is fixed by the representation of the existing socio-technical system, then the design regime is stabilized into one socio-technical regime and plagued by waiting games. When design capacities increase and become more collective, inside colleges dealing with the unknown, when unlocking rules are introduced, when the ecology of concepts is living and constantly enriched, then more dynamic design regimes emerge. Today, the semiconductor industry is a good example of such a design regime. Doubtless other industries are also currently undergoing transformation, from a stabilized to a more dynamic design regime. The notions of unlocking rules, ecology of concepts and college of the unknown might help guide their transformation and provide new insights for public policies to support it.

Biographies

  represents the structure of the potential solutions explored for lithography and the technological alternatives given in ITRS updates from 2001 to 2009.

Figure 1 -

 1 Figure 1 -ITRS: potential solutions for lithography 2001-2009. Solution paths on the bottom left-hand side have a lot in common. Solution paths on the top right-hand side are largely unknown and have very few features in common.

  Armand Hatchuel, Pascal Le Masson and Benoit Weil are Professors at MINES ParisTech, for the Design Theory and Methods for Innovation chair. Their last book, Strategic Management of Innovation and Design, was published by Cambridge University Press in 2010. Armand Hatchuel and Benoit Weil are deputy directors of the Center for Management Science at MINES ParisTech. Armand Hatchuel is a member of the French Academy of Technologies and columnist for management issues at Le Monde.

Table 1 : two models of regimes in transition(s)

 1

		Model 1: evolutionary,	Model 2: generative, interactive
		substitutive
	Interaction between	The weakened regime is	The regime contributes to the
	niches and the	replaced by a winning	emergence of niches and is
	regime	niche	transformed into a new regime
			through synergies and
			hybridizations
	Rules	Locking: stabilizes one	Unlocking: inhibits lock-in,
		path, reduces uncertainty	generates multiple paths.
	Actors	Individual entrepreneurs	Collaboration in the unknown
		with their own strategy
	System	A weakened system is	Actors work on the incumbent
		replaced by one	system and on the alternatives
		stemming from a niche	in niches

Patrick Cogez is Director of Innovation and External Research, within STMicroelectronics Technology R&D organization. He is STMicroelectronics representative within the steering committee of the International Technology Roadmap for Semiconductors.


Waiting Games: innovation impasses in situations of high uncertainty

Douglas K. R. Robinson, Pascal Le Masson , Benoit Weil What are waiting games?

Two companies competing in the same sector of sustainable energy technologies, having developed a novel technology, and both waiting for the other to make the first move and introduce the innovation, which would present the first and best opportunity to really learn about public acceptance of the innovation.

A start-up venture in the medical devices sector waiting for established companies to invest in the early phases of the development of a new demonstrator; these companies waiting for the start-up to demonstrate the reproducibility of its demonstrator.

A company in the emerging field of nanomedicine waiting for regulatory decisions of the traditional organizations mandated to make these decisions, with the latter waiting for the new technology to stabilize so that its risks and benefits can be assessed…

The above sketches refer to situations in which technological innovation has reached an impasse: one side waiting for the other to make an important move without which this party cannot move on. The challenge for innovation has shifted from meeting uncertainties to breaking through a waiting game. The topic of 'waiting games' -or technology impasseshas not been addressed in the innovation literature, while it is clearly important to understand the phenomenon, and to be able to do something about it. We call this a waiting game because it occurs over and above the strategies of individual actors, even if there is general acceptance that the technology is promising and innovation is necessary.

Radical or architectural innovation processes are full of uncertainties and unknowns, and are accompanied by high expectations. To create new products and services, new values and social relations, actors have to come to terms with these aspects and develop strategies accordingly. There is an additional challenge in that the structure of this situation can lead to innovation impasses where little of significance happens because actors wait for others to make a first -and potentially risky -move. This special issue explores the variety of waiting games and their dynamics, and offers suggestions about breaking through them.

Waiting games, with their first mover problem, are strategic games in the real world (Scharpf 1997). To overcome them requires a transition at the collective level, amidst high uncertainty.

The waiting game may be linked to the design process itself, were cognitive/conceptual lockin prevents breaking out of an incumbent technological development pathway into fresh and novel areas. Another form of waiting game is linked to existing technologies like fuel cells which remain limited to niche applications, and have difficulty breaking out of them, even when there are strong expectations (Bakker et al. this issue). The papers in this special issue address the variety of waiting games, mostly among the actors involved in developing a new technology, but also linked to a "wait and watch" attitude of regulators (d'Silva et al.). Le Masson et al. ask the important converse question, why are actors in the semi-conductor industry not locked into waiting games.

The contributions

The special issue provides five contributions, exploring the emergence, avoidance and

Emerging themes and research perspectives

Each paper offers insights that both contribute to several issues of contemporary studies of innovation and provide a platform for further investigation. We describe these themes in the following drawing exclusively on the contributions in this special issue.

(1) Shared narratives of the future can lead to waiting games. Bakker et al. propose that hype related to the rhetorical expectations race provides a temporary niche/bubble allowing time to build ties -reinforcing the classical logics of promissory narratives acting as an engine that powers innovation. Similar to Agogue et al. and Paradian et al., they suggest that hyping as a strategy to align actors and power innovation, is a risky affair since the niche created by the hype in the incumbent design regime may collapse over very short periods of time. This was the case for hydrogen fuel cell technologies, with the consequence that those who focused attention on the rhetorical expectations race suffered from the collapse of the hype. They propose two strategies:

• Modest promising, which provides longer time frames to build ties with less destructive collapses. However they argue that there is little incentive for individual actors to remain modest, though there IS a collective incentive -with rewards in the long-run (thus a call for expectations management at the meso-level of industrial consortia)

• Rapid use of the bubble and the resources it provides, that is to match rhetoric with activities in an attempt to create more stable networks that can "weather the storm" if and when the hype bubble is to collapse.

The danger, they posit, is that if you do not follow one of these two strategies, a promising technology may fall victim to waiting games (post-disappointment) and lie in the trough of disillusionment for some time, during which the competencies and knowledge accumulated during the hype may reduce. They end with detailing how some firms attempt to maintain the knowledge base on hydrogen fuel cells through maintaining the positive elements provided by the hype through the continuation of small R&D projects whilst waiting for the promising technology to leave the trough of disillusionment, a clear example of a waiting game leading to innovation impasse.

Parandian et al. reveal the paradoxical effects of diffuse and open ended promises which are

powerful in policy discourse, but which may hinder the realization of these promises.

Innovation actors are reluctant to invest in concrete developments because the promises are open-ended and demand is not articulated. This is a structural issue and leads to waiting games in which actors are entangled. They argue that there are two promise dynamics (1)

those of big open-ended promises (Umbrella promises) and ( 2) more concrete promise requirement cycles -they are not independent and that one can speak of dual dynamics.

"Expectations are important because it is through them that future value of technological options are articulated and to some extent become stabilised"… "Expectations, when shared, allow some coordination and there are now attempts at joint coordination of emerging technologies and their future application" But as they (and Agogue et al.) argue, when a vaguely defined umbrella promise1 is widely accepted -and sometimes blackboxed -they can function as a protection, but also can lead to dual dynamics which act as a disincentive to innovators and the emergence of waiting games.

They offer a solution, by suggesting that socio-technical scenarios and interactive workshops (combined under the banner of constructive technology assessment) can provide a means of understanding the processes and patterns which actors enact, which lead to waiting games (stimulating reflexivity) Agogué et al. reinforce this by revealing, what they have dubbed as situations of "orphan innovation", where shared narratives actually correspond to fixations and where promises can be misleading. They unpick the locked-in narratives of the future by using the entrance point of design regimes, they explore the relationship between the repertoire of concepts in the community, the knowledge that is present, and the design paths that connect the "unknown", the imaginary, and the known. Their findings show that applying design theory in workshop settings can act as a tool to support reflexivity of the designers on their own assumptions and practices as well as allowing the articulation of alternative narratives. The alternative narratives can act as a means of assessing the robustness of the reservoir of options and can also become new design paths themselves.

Le Masson et al. argue that "quality control" of expectations and how they shape the exploration process can be located at the level of institutions (such as R&D or industrial consortia). Through their striking case of the ITRS roadmap, they provide insights into the effects of quality control of expectations and institutionalized unlocking provide a means of serial-disruptive-design.2

(2) Managing the "unknown"

The unknown and its promises not only require a more sophisticated descriptive language, they also call for a form of management, that should be strongly collaborative and would deal The papers pave the way to new studies on the collective management of "the unknown" and they suggest that this management itself might be the critical resource for contemporary industrial dynamics. Managing a collective design space appears as managing a new kind of "collective good", a collective good that is no more related to limited natural resources but related to the (limited) exploration and creative capacities. D'Silva et al. describe a distributed, multiple-actor, diverse and experimental regulatory landscape able to design new regulations located at the micro, meso and macro-level. These actors would be in charge of unlocking rules, would question "umbrella promises" expectations and provide a forum for expectations management (including hypes).The contributions in this special issue relating to the creative process (Agogué et al. and Le Masson et al.) suggest that waiting games can be both the cause and effect of limits to the creativity of innovators. A new actor is needed, who need not be an innovator herself but would be charged with enhancing the collective innovation capacities. The studies in the special issue help to frame what the roles and features of such actors could be: They would maintain an "ecology of concepts", to regularly open "path in the unknown", to rejuvenate regulations, to support collaboration between "expectations enablers" and "selectors", to organize "innovation race" and "avoid expectations" races.

Taken together, the three cross-cutting themes we have drawn out from the contributions, to this special issue, provide an interesting perspective on industrial dynamics and sociotechnical regimes. The contributions show that there are ways to improve expectations management and to create situations which are not conducive to waiting games. For actors who wish to create a productive industrial sector, governance system, or innovation avenue, the capacity to collectively explore, structure and regenerate the unknown and the imaginary is a going concern. In this way, management of innovation moves away from production regimes to design regimes (Le Masson et al.), where activities and performance will be oriented towards the expansion of the imaginaries and their quality control.

Conclusion

Waiting games are an element of disruptive innovation where uncertainty and the degree of unknowness is high. This special issue of TA&SM provides insights into how uncertainties and unknowness can lead to waiting games, but each contribution has offered suggestions on how to handle, use or avoid waiting games. We hope that this issue will provide a nucleus for further academic and practical explorations of waiting games in potentially radical innovations.

  management of waiting games in a variety of innovation contexts. Bakker et al. provide insights into the emergence of the hydrogen fuel cell technology waiting game, showing how actors' rhetorical 'expectations races' influence the emergence of a promising field. They highlight that, for the hydrogen fuel cell case, the large disappointments following the initial large hype has led to fuel cells being relegated to the trough of disillusionment where they are doomed to waiting games. They offer advice for expectations management to avoid waiting games that are connected to hype/disappointment dynamics. Parandian et al. continues the theme on sociology of expectations for the field of organic large area electronics and nanotechnologies, showing how the dual dynamics of promising can lead to waiting games. They emphasise the need to articulate the expectations and visions of suppliers and users of the potential innovations as a means to reduce the possibility (or mitigate the effects of) waiting games. D'Silva et al. provide a case where waiting games were a high possibility but have been avoided (so far) through the unlocking of a dominant regulation regime. They show how an innovation impasse in nanomedicine would have ensued if the traditional wait and watch strategies of legislators and regulators had been followed. The case provides insights about how waiting games were avoided, but also reveal management insights through the notion of institutionalising what Le Masson et al. have dubbed "unlocking rules". This notion of unlocking rules is elaborated in the two final contributions. Agogué et al. takes the bull by its horns, by developing management tools to assess and break out of innovation impasses that lead to waiting games. They draw on two cases of regional clusters focusing on two different innovation issues, where there is large investment and a high demand for solutions, but stagnant innovation processes. They use this as an opportunity to explore the fundamentals of lock-in and provide a conceptual framework based on three types of innovation pathways. This conceptual framework allows an assessment of the innovativeness of search processes in these clusters as well, in conjunction with other tools based on design theory, being applied to unveil previously unarticulated innovation pathways. Le Masson et al. pose the question, Why aren't the actors in the semiconductor industry locked into waiting games? The answer to this, they propose, is the regular articulation and design of collective expectations along with mechanisms for unlocking the socio-technical configurations within a particular design regime. To understand how the dominant design regimes and emerging design regimes (niches) interact during transformations in the semiconductor sector, the article contrasts two models of regime in transition: (1) the classical model of evolutionary niches which suggests misalignments between rules and a competition between niches, and (2) a second model based on unlocking rules supporting collective work on a structured set of emerging technologies. This second model is illustrated with a case study on the International Roadmap for Semiconductors (ITRS).

  with new objects: Bakker et al. suggest to manage expectations, and support more collaborative explorations between expectations enactors and selectors; D'Silva et al. underline that regulation can support innovation (and avoid waiting games) if it remains a place for collaborative probe and learn activities-so that the emergence and design of regulation should be managed and is not necessarily the contingent results of complex political games; Parandian et al. illustrate how some critical technical challenges should be considered as collective goods (such as encapsulation in OLAE) and managed as such; Le Masson et al. underline how the actors of semiconductor industry were able to collectively manage an ecology of concept.

( 3 )

 3 New organizations for supporting the exploration of the unknown?This management of collective exploration might require new actors and institutions. Le Masson et al. describe the International Technology Roadmap for Semiconductor as a college for the unknown, Agogué et al. suggest the emergence of "architects" of paths in potentia, is an ideal place to go for their strategy of moderate hyping.

Umbrella promises are a discursive phenomenon, creating narratives -such narratives fit into recent policy discourse

Bakker et al. affirm this as a location for such management of expectations -that the collective / consortia level


Michel Benaim

Olivier Raimond

Bruno Schapira

STRONGLY VERTEX-REINFORCED-RANDOM-WALK ON A COMPLETE GRAPH

Keywords: 2010 Mathematics Subject Classification. 60K35 Vertex reinforced random walk, strongly reinforced regime, complete graph. 1

We study Vertex-Reinforced-Random-Walk (VRRW) on a complete graph with weights of the form w(n) = n α , with α > 1. Unlike for the Edge-Reinforced-Random-Walk, which in this case localizes a.s. on 2 sites, here we observe various phase transitions, and in particular localization on arbitrary large sets is possible, provided α is close enough to 1. Our proof relies on stochastic approximation techniques. At the end of the paper, we also prove a general result ensuring that any strongly reinforced VRRW on any bounded degree graph localizes a.s. on a finite subgraph.

Introduction

This paper considers a Vertex-Reinforced Random Walk (VRRW) on a finite complete graph with weights w α (n) := (n + 1) α in the strongly reinforced regime α > 1.

Such a process is a discrete time random process (X n ) n≥0 living in E = {1, . . . , N} and such that for all n ≥ 0 and j ∈ E,

P(X n+1 = j | F n ) = w α (Z n (j))
k =Xn w α (Z n (k))

1 {Xn =j} ,
where Z n (j) := n ℓ=0 1 {X ℓ =j} is the number of jumps to site j before time n, and F n = σ(X k ; k ≤ n).

The linear regime (i.e α = 1) has been initially introduced by Pemantle [P] on a finite graph and then extensively studied for different type of graphs by several authors ( [START_REF] Pemantle | Vertex-reinforced random walk on Z has finite range[END_REF][START_REF] Tarrès | Vertex-reinforced random walk on Z eventually gets stuck on five points[END_REF][START_REF] Volkov | Phase transition in vertex-reinforced random walks on Z with non-linear reinforcement[END_REF][START_REF] Limic | VRRW on complete-like graphs: almost sure behavior[END_REF][START_REF] Benaïm | Dynamics of Vertex-Reinforced Random Walks[END_REF]).

The main result of the present paper is the following: Theorem 1.1. Let N ≥ 2 and α > 1 be given. Then the following properties hold.

(i) With probability one there exists 2 ≤ ℓ ≤ N, such that (X n ) visits exactly ℓ sites infinitely often, and the empirical occupation measure converges towards the uniform measure on these ℓ sites. (ii) Let 3 ≤ k ≤ N. If α > (k -1)/(k -2), then the probability to visit strictly more than k -1 sites infinitely often is zero. If α < (k -1)/(k -2), then for any 2 ≤ ℓ ≤ k, the probability that exactly ℓ sites are visited infinitely often is positive.

This result has to be compared with the situation for Edge Reinforced Random Walks (ERRW). Limic [L] (see also [LT]), proved that for any α > 1, and for any free loops graph with bounded degree, the ERRW with weight w α visits only 2 sites infinitely often. It has also to be compared to the situation on the graph Z, where for any α > 1, the VRRW with weights (w α (n)) visits a.s. only 2 sites infinitely often.

It might be interesting to notice also that when we add one loop to each site, i.e. when at each step, independently of the actual position of the walk, the probability to jump to some site i is proportional to w α (Z n (i)), then Rubin's construction (see [D]) immediately shows that the walk visits a.s. only one site infinitely often. In fact with our techniques we can study a whole family of processes which interpolate between these two examples: for c ≥ 0, consider the process with transitions probabilities given by

P(X n+1 = j | F n ) = w α (Z n (j))1 {Xn =j} + c w α (Z n (j))1 {Xn=j} k =Xn w α (Z n (k)) + c w α (Z n (X n ))
, with the same notation as above. The case c = 0 corresponds to the VRRW on a free loop complete graph, and the case c = 1 corresponds to the VRRW on a complete graph with loops. Then for any c ≥ 1, the process visits a.s. only 1 site infinitely often, and when c ∈ (0, 1), various phase transitions occur, exactly as in Theorem 1.1, except that the critical values are this time equal to

[k -(1 -c)]/[k -2(1 -c)],
for 2 ≤ k ≤ N and localization on 1 site is always possible and occurs even a.s. when α > (1 + c)/(2c). Since the proofs of these results are exactly similar as those for Theorem 1.1, we will not give further details here. Finally let us observe that similar phase transitions as in Theorem 1.1 have been observed in some random graphs models, see for instance [CHJ, OS].

The paper is organised as follows. In the next two sections we prove some general results for VRRW with weight w α , on arbitrary finite graphs, which show that in the good cases a.s. the empirical occupation measure of the walk converges a.s. to linearly stable equilibria of some ordinary differential equation. In section 4 we study in detail the case of a complete graph, we describe precisely the set of linearly stable equilibria in this case, and deduce our main result, Theorem 1.1. Finally in the last section we prove a general result ensuring that strongly reinforced VRRWs on arbitrary bounded degree graphs localize a.s. on a finite subset.

A general formalism for VRRW

We present here a general and natural framework for studying VRRW based on the formalism and results introduced in [B] and [BR]. Such a formalism heavily relies on stochastic approximation technics and specifically the dynamical system approach developed in [B2].

Let A = (A i,j ) i,j≤N be a N × N symmetric matrix with nonnegative entries. We assume that A i,j > 0 for i = j, and that j A i,j does not depend on i. Let α > 1 be given. We consider the process (X n ) n≥0 living in E = {1, . . . , N}, with transition probabilities given by

P(X n+1 = j | F n ) = A Xn,j (1 + Z n (j)) α k≤N A Xn,k (1 + Z n (k)) α
, where Z n is defined like in the introduction. The case of the VRRW on a complete graph is obtained by taking (1)

A i,j = 1 -δ ij .
For i ≤ N, set v n (i) = Z n (i)/(n + 1). Note that if A i,i = 0 and X k = i then X k+1 = i. In particular for any such i, and n ≥ 1, v n (i) ≤ (1/2 + 1/(n + 1)) ≤ 3/4. In other words, for all n ≥ 1, v n belongs to the reduced simplex

∆ := v ∈ R N + : v i ≤ 3/4 if A ii = 0 and i v i = 1 .
In the following, we might sometimes view an element f = (f i ) i≤N ∈ R N as a function on E, and so we will also use the notation f (i) for f i . Now for ǫ ∈ [0, 1] and v ∈ ∆ we let K(ǫ, v) denote the transition matrix defined by

(2) K i,j (ǫ, v) := A i,j (ǫ + v j ) α k A i,k (ǫ + v k ) α , for all i, j ≤ N. To shorten notation we let (3) K(v) := K(0, v).
Two obvious, but key, observations are that

P(X n+1 = j | F n ) = K Xn,j ((n + 1) -1 , v n )),
and

lim n→∞ K((n + 1) -1 , v) = K(v).
Hence, relying on [B] and [BR], the behavior of (v n ) can be analyzed through the ordinary differential equation v = -v + π(v), where π(v) is the invariant probability measure of the Markov chain with transition matrix K(v).

The limit set theorem

3.1. The limiting differential equation and its equilibria.

For v ∈ ∆, set v α = (v α 1 , . . . , v α N )
, and ( 4)

H(v) := i,j A i,j v α i v α j = Av α , v α .
Note that H is positive on ∆. Hence one can define

π i (v) = v α i (Av α ) i H(v) , i = 1, . . . , N.
From the relation

v α j (Av α ) i K i,j (v) = A i,j v α i v α j , it follows that K(v) is reversible with respect to π(v).
For r = 0, 1 set T r ∆ = v ∈ R N : i v i = r and let ı : T 1 ∆ → ∆ be the map defined by ı(v) = argmin{ yv : y ∈ ∆}. Since ∆ is convex ı is a Lipschitz retraction from T 1 ∆ onto ∆.

Let now F : T 1 ∆ → T 0 ∆ be the vector field defined as

(5)

F (v) = -v + π(ı(v)).
Note that F is Lipschitz. Thus by standard results, F induces a global flow Φ : R × T

1 ∆ → T 1 ∆ where for all x ∈ T 1 ∆, t → Φ(t, x) := Φ t (x) is the solution to v = F (v) with initial condition v(0) = x.
For any subset I ⊂ {1, . . . , N}, we let

∆ I := {v ∈ ∆ : v i = 0 ∀i ∈ E \ I}, denote the I-face of ∆. We let int∆ I = {v ∈ ∆ I : v i > 0 ∀i ∈ I} denote the (relative) interior of ∆ I . For v ∈ ∆ we let supp(v) = {i ∈ E : v i = 0}
, so that v always lies in the supp(v)-face of ∆.

Lemma 3.1. The flow Φ leaves ∆ positively invariant: ∀t ≥ 0, Φ t (∆) ⊂ ∆; and for each I ⊂ E, the face ∆ I is locally invariant:

∀v ∈ ∆ I , ∀t ∈ R, Φ t (v) ∈ ∆ ⇔ Φ t (v) ∈ ∆ I .
Proof. For all v ∈ ∆, π(v) lies in ∆. Indeed for the Markov chain having transition matrix K(v) the empirical occupation measure lies in ∆ and by the ergodic theorem (for finite Markov chains) the same is true for π(v). Hence F (v) points inward ∆ for all v ∈ ∆, proving that ∆ is positively invariant. Since F i (v) = 0 when v i = 0, each face is locally invariant.

Let C = {v ∈ ∆ : F (v) = 0},
denote the equilibria set of F . Relying on stochastic approximation theory [START_REF] Benaïm | Vertex-reinforced random walks and a conjecture of Pemantle[END_REF][START_REF] Benaïm | Dynamics of Stochastic Approximations[END_REF][START_REF] Benaïm | A class of self-interacting processes with applications to games and reinforced random walks[END_REF] it will be shown below (Proposition 3.5) that (v n , n ≥ 1) converges almost surely to C. The next result is similar to the case α = 1 (see for instance [P]):

Lemma 3.2. The map H : ∆ → R is a strict Lyapunov function, meaning that ∇H(v), F (v) is positive for all v ∈ ∆ \ C. Proof. One has ∂ i H(v) = 2αv α-1 i (Av α ) i . Thus ∇H(v), F (v) = i 2αv α-1 i (Av α ) i -v i + v α i (Av α ) i H(v) = 2α H(v) - i v α-1 i (Av α ) i v i 2 + i v α-1 i (Av α ) i 2 v i ≥ 0,
with equality only when v α-1 i (Av α ) i does not depend on i ∈ supp(v), i.e. only when v is an equilibrium.

Remark 3.3. The barycenter v = (1/N, . . . , 1/N) is always an equi- librium. Lemma 3.4. H(C) has empty interior. Proof. The computation of ∂ i H(v) shows that (∂ i -∂ j )H(v) = 2α(v α-1 i (Av α ) i -v α-1 j (Av α ) j ).
Hence, for all v in the relative interior of ∆,

F (v) = 0 ⇔ ∇H(v) = 0. In other word C ∩ int∆ = ∇H -1 (0) ∩ int∆. By Sard's theorem, it follows that H(C ∩ int∆)
has measure zero, hence empty interior. Similarly, for each face I, H(C ∩ int∆ I ) has empty interior. This proves the lemma.

Proposition 3.5. The set of limit points of (v n ) is a connected subset of C.

Proof. By proposition 3.3 and Theorem 3.4 in [B] or Proposition 4.6 in [BR], we get that the limit set of (v(n)) is an internally chain transitive set for Φ. Since H is a strict Lyapunov function and H(C) has empty interior, it follows from Proposition 6.4 in [B2] that such a limit set is contained in C.

In particular, when all the equilibria of F are isolated, then v n converges a.s. toward one of them, as n → ∞.

Remark 3.6. When A is not symmetric, the convergence result given by Proposition 3.5 fails to hold. Indeed, an example is constructed in [B] with N = 3 and α = 1 for which the limit set of (v n ) n≥1 equals ∂∆. This behavior persists for α = 1 + ǫ and ǫ > 0 small enough.

3.2.

Stable and unstable equilibria. An equilibrium v is called linearly stable provided all the eigenvalues of DF (v), the differential of F at point v, have negative real parts. It is called linearly unstable if one of its eigenvalues has a positive real part. Now we will see with the next result that to study the stability or instability of the equilibria, it suffices in fact to consider only those which belong to the interior of ∆. In the following we let (e 1 , . . . , e N ) denote the canonical basis of R N .

Lemma 3.7. Let v be an equilibrium. Then, for i, j ∈ supp(v), we have

D e i -e j F (v) = (α -1)(e i -e j ) + α ℓ v α ℓ (A ℓ,i v α-1 i -A ℓ,j v α-1 j ) H(v) e ℓ ,
and for i / ∈ supp(v),

D e i -v F (v) = -(e i -v).
Furthermore, the eigenvalues of DF (v) are all reals.

Proof. For any i, j ≤ N, and v ∈ ∆,

∂ j (Av α ) i = αA i,j v α-1 j ,
and then by using that A is symmetric, we get

∂ j H(v) = 2αv α-1 j (Av α ) j .
Thus

∂ j π i (v) = δ i,j α v α-1 i (Av α ) i H(v) + α v α i A i,j v α-1 j H(v) -2α v α i (Av α ) i H 2 (v) v α-1 j (Av α ) j .
Now assume that v is an equilibrium, and let i, j ∈ supp(v). We get with Lemma 3.2

∂ j π i (v) = δ i,j α + α v α i A i,j v α-1 j H(v) -2αv i ,
and then

∂ j F i (v) = δ i,j (α -1) + α v α i A i,j v α-1 j H(v) -2αv i .
On the other hand if v i = 0 or v j = 0, then

∂ j π i (v) = 0,
and thus

∂ j F i (v) = -δ i,j .
The first part of the lemma follows. To see that eigenvalues are real, we may assume without loss of generality that v ∈ int(∆). Note that

∂ j F i (v)v j = ∂ i F j (v)v i .
Therefore, the transpose of DF (v) is self adjoint with respect to the dot product (x, y) = i v i x i y i , and this concludes the proof of the lemma.

As announced above we deduce Corollary 3.8. An equilibrium on a face is linearly stable (respectively unstable), if and only if, it is so for the restriction of F to this face.

Proof. Indeed, assume that v is an equilibrium on a face ∆ I associated to some subset I. Then the previous lemma shows that for any i / ∈ I, e iv is a stable direction. So the result of the corollary follows from our definitions of stable and unstable equilibria.

In other words to study the stability or instability of equilibria, and we will see in the next two subsections why this question is important, it suffices to consider those belonging to the interior of ∆.

3.3.

Non convergence towards unstable equilibria. The purpose of this section is to prove the following result.

Theorem 3.9. Let v * be a linearly unstable equilibrium. Then the probability that v n converges towards v * is equal to 0.

Proof. Let us recall now that for g ∈ R N and i ∈ E, we use the notation g(i) = g i . For u, v ∈ R N , we also set uv := i u i v i , and u = sup i |u i |. Furthermore, C will denote a non-random constant that may vary from lines to lines.

For v ∈ ∆, let Q(v) be the pseudo-inverse of K(v) defined by:

(I -K(v))Q(v)g = Q(v)(I -K(v))g = g -(π(v)g)1,
for all g ∈ R N , with I is the identity matrix and 1(i) = 1 for all i ∈ E.

Then by a direct application of the implicit function theorems (see Lemma 5.1 in [B]) one has Lemma 3.10. For any v ∈ ∆ and i ∈ E, Q(v), K(v)Q(v), and

(∂/∂ v i )(K(v)Q(v)
), are bounded operators on ℓ ∞ (E), the space of bounded functions on E, and their norms are uniformly bounded in v ∈ ∆.

Now for all n ≥ 1 and i ∈ E, we can write

v n+1 (i) -v n (i) = 1 n + 1 -v n (i) + e i (X n+1 ) . Note that K (n + 1) -1 , v n = K(ṽ n ),
where

ṽn (i) = v n (i) + 1/(n + 1) 1 + N/(n + 1) for 1 ≤ i ≤ N.
Note also that ṽnv n ≤ C/n. Let next z n be defined by

z n (i) = v n (i) + K(ṽ n )Q(ṽ n )e i (X n ) n for 1 ≤ i ≤ N.
Then Lemma 3.10 implies that z nv n ≤ C/n. Moreover, we can write:

(6)

z n+1 -z n = F (z n ) n + 1 + ǫ n+1 n + 1 + r n+1 n + 1 ,
where ǫ n+1 and r n+1 are such that for all 1 ≤ i ≤ N,

ǫ n+1 (i) := Q(ṽ n )e i (X n+1 ) -K(ṽ n )Q(ṽ n )e i (X n ),
and

r n+1 = 4 k=1 r n+1,k , with r n+1,1 = F (v n ) -F (z n ) r n+1,2 = π(ṽ n ) -π(v n ) r n+1,3 (i) = K(ṽ n )Q(ṽ n )e i (X n ) 1 - n + 1 n r n+1,4 (i) = K(ṽ n+1 )Q(ṽ n+1 )e i (X n+1 ) -K(ṽ n )Q(ṽ n )e i (X n+1 ), for 1 ≤ i ≤ N.
By using the facts that F and π are Lipschitz functions on ∆, v nṽn + v nz n ≤ C/n, and by applying Lemma 3.10, we deduce that

r n+1 ≤ C/n. Moreover, we have E[ǫ n+1 | F n ] = 0. Since v * is linearly unstable there exists, by Lemma 3.7, f ∈ T 0 ∆ and λ > 0 such that (i): D f F (v) = λf and, (ii): f i = 0 for i ∈ E \ supp(v * ).
Such an f being fixed, we claim that on the event {v n → v * },

lim inf n→∞ E[(ǫ n+2 f ) 2 | F n+1 ] + E[(ǫ n+1 f ) 2 | F n ] > 0. (7)
To prove this claim, we first introduce some notation: for µ a probability measure on E, and g ∈ R N , denote by V µ (g) the variance of g with respect to µ

V µ (g) := 1 2 1≤j,k≤N µ(j)µ(k) g(j) -g(k) 2 .
Then for any n ≥ 0 and i ≤ N, let µ n,i be the probability measure defined by µ n,i (j) = K i,j (ṽ n ). Set also

V n (i) := V µ n,i (Q(ṽ n )f ). Then we have that E[(ǫ n+1 f ) 2 | F n ] = V n (X n ). Furthermore, when v n converges toward v * , K(ṽ n ) and Q(ṽ n ) converge respectively toward K(v * ) and Q(v * ). Thus, for any i ∈ E, lim inf n→∞ V n (i) ≥ V * (i) := V µ * i (Q(v * )f ), where µ * i (j) = K i,j (v *
), for all j ≤ N. Next by using the fact that when X n = i and A i,i = 0, then X n+1 = X n , we get that

lim inf E[(ǫ n+2 f ) 2 | F n+1 ] + E[(ǫ n+1 f ) 2 | F n ] ≥ min i c * (i), where c * (i) := min j∈A i (V * (i) + V * (j)),
and

A i := E if A i,i = 0 E {i} if A i,i = 0.

Now by using that

Q(v * )f -K(v * )Q(v * )f = f -(v * f )1 (recall that π(v * ) = v * ), we see that Q(v * )f has constant coordinates on supp(v * ), if and only if, f has constant coordinates on supp(v * ).
But since f ∈ T 0 ∆ and f i = 0 for i ∈ supp(v * ); this cannot be the case. Since µ * i (j) > 0, when j = i and j ∈ supp(v * ), it follows already that c * (i) > 0, for all i / ∈ supp(v * ). Now let i ∈ supp(v * ) be given. If A i,i = 0, then again we have V * (i) > 0, and thus c * (i) > 0. Now assume that A i,i = 0. If #supp(v * ) ≥ 3, then there can be at most one value of i, for which V * (i) = 0, and thus in this case we have c * (i) > 0 as well. Let us then consider the case when #supp(v * ) = 2, and say supp(v * ) = {i, j}. Recall that if A i,i = 0, then V * (i) > 0. However, we cannot have A i,i = A j,j = 0, since otherwise v * i = v * j = 1/2 and by lemma 3.7 v * is linearly stable. Finally we have proved that in any case min i c * (i) > 0. Theorem 3.9 is then a consequence of (7) and Corollary 3.IV.15 p.126 in [Du].

3.4. Convergence towards stable equilibria and localization. Theorem 3.11. Let v * be a linearly stable equilibrium. Then the probability that v n converges towards v * is positive.

Proof. follows from Corollary 6.5 in [B] since any linearly stable equilibrium is a minimal attractor.

Theorem 3.12. Let v * ∈ ∆ be a linearly stable equilibrium. Then a.s. on the event {lim n→∞ v n = v * }, the set E \ supp(v * ) is visited only finitely many times.

The proof follows directly from the next two lemmas: Lemma 3.13. There exists ν > 0 such that on the event

{lim n→∞ v n = v * }, lim n→∞ n ν v n -v * = 0.
Proof. This is similar to Lemma 8 in [BT]. We give here an alternative and more direct proof relying on [B2]. Since v * is a linearly stable equilibrium there exists a neighborhood B of v * , a constant C > 0 and λ > 0, such that Φ t (v)v * ≤ Ce -λt , for all v ∈ B (see e.g [R], Theorem 5.1). Let τ n = n k=1 1/k and let V : R + → ∆ denote the continuous time piecewise affine process defined by a) V (τ n ) = z n and b) V is affine on [τ n , τ n+1 ]. By (6) and Doob's inequalities, the interpolated process V is almost surely a -1/2 asymptotic pseudo trajectory of Φ, meaning that lim sup

t→∞ 1 t log sup 0≤h≤T Φ h (V (t) -V (t + h) ≤ -1/2
for all T > 0. For a proof of this later assertion see [B2], Proposition 8.3. Now, by Lemma 8.7 in [B2] lim sup

t→∞ 1 t log( V (t) -v * ) ≤ -min(1/2, λ)
on the event {v n → v * }. This proves that z nv * = O(n -min(1/2,λ )), which concludes the proof of the lemma.

Lemma 3.14. For any I ⊆ {1, . . . , N}, and ν ∈ (0, 1), a.s. on the event

E ν (I) := { lim n→∞ v n (i) n ν = 0 ∀i ∈ I},
the set I is visited only finitely many times.

Proof. For m ≥ 1, set

E m,ν (I) := {|v k (i)| ≤ k -ν ∀k ≥ m ∀i ∈ I}.
Note that on E m,ν (I), at each time k ≥ m, the probability to jump to some vertex i ∈ I, is bounded above by p k := N 1+α k -αν . Let now (ξ k ) k≥m denotes some sequence of independent Bernoulli random variables with respective parameters (p k ) k≥m . Then for any n ≥ m, on E m,ν (I) the number of jumps on I between time m and n is stochastically dominated by

Z n := n k=m ξ k .
However, it is well known that a.s. lim sup Z n /n 1-ν ′ < ∞, for any ν ′ < αν ∧ 1. We deduce that a.s. for any

ν ′ < αν ∧ 1, E m,ν (I) ⊆ E ν ′ (I). Since E ν (I) ⊆ ∪ m E m,ν(I)
, we deduce that a.s. for any ν ′ < αν ∧ 1,

E ν (I) ⊆ E ν ′ (I).
Since α > 1, it follows by induction that a.s.

E ν (I) ⊆ E β (I),
for any β ∈ (1/α, 1). But a simple application of the Borel-Cantelli lemma shows that for any such β, a.s. on E β (I), the set I is visited only finitely many times. This concludes the proof of the lemma.

The case of the VRRW on a complete graph

In this section we study in detail the case of the VRRW on a complete graph described in the introduction. In other words, A is given by (1).

Since the case N = 2 is trivial, we assume in all this section that N ≥ 3.

We first study the stability of the centers of the faces. As already explained, this reduces to analyze the center of ∆.

Lemma 4.1. Let v = (1/N, . . . , 1/N) be the center of ∆. Then v is a linearly stable (respectively unstable) equilibrium if α < (N -1)/(N -2), (respectively α > (N -1)/(N -2)).

Proof. Lemma 3.7 shows that for all i = j,

D e i -e j F (v) = -1 + α N -2 N -1 (e i -e j ).
The lemma follows immediately.

By combining this lemma with Corollary 3.8, we get Lemma 4.2. Let v be the center of the face ∆ I associated with some subset I with cardinality k ≤ N. Then v is a linearly stable (respectively unstable

) equilibrium if α < (k -1)/(k -2), (respectively α > (k - 1)/(k -2)).
It remains to study the stability of the other equilibria. We will see that they are all unstable, which will conclude the proof of Theorem 1.1.

First we need the following lemma, which shows that coordinates of equilibriums take at most two different values.

Lemma 4.3. Let v be an equilibrium in the interior of ∆, which is different from its center. Then #{v i : i ≤ N} = 2.

Proof. Let a = i v α i and b = i v 2α i .
Since v is an equilibrium, we have for all i,

v i = v α i a -v α i a 2 -b .
Since all coordinates of v are positive by hypothesis, this is equivalent to

f (v i ) = a -b/a, for all i, where f (x) = -x 2α-1 /a + x α-1 . Now observe that f ′ (x) = x α-2 -(2α -1)x α /a + (α -1) ,
does not vanish on (0, 1) if a ≥ (2α-1)/(α-1), and vanishes in exactly one point otherwise. Thus for any fixed λ ∈ R, the equation f (x) = λ, has at most one solution in (0, 1), if a ≥ (2α -1)/(α -1), and at most two otherwise. The lemma follows.

Let v be an equilibrium in the interior of ∆, which is different from its center. Lemma 4.3 shows that its coordinates take exactly two different values, say u 1 and u 2 . Since the action of permutation of the coordinates commutes with F , we can always assume w.l.g. that v i = u 1 , for i ≤ k, and v i = u 2 , for i > k, for some k ≤ N/2. Denote now by E k the set of such equilibria (those in the interior of ∆, not equal to the center of ∆, and having their first k coordinates equal as well If α ≥ (N -1)/(N -2), then ϕ ′ (1) ≤ 0, thus ϕ has at most one zero in (0, 1) and no zero in (0, ∞). Together with Lemma 4.4 this proves the first part of the lemma. If α > (N -1)/(N -2), then ϕ ′ (1) > 0, and thus ϕ has no zero in (0, 1) and exactly one zero in (0, ∞), in which the derivative of ϕ is negative. The fact that this zero corresponds to an unstable equilibrium will then follow from (8) below. But before we prove this fact, let us consider now the case k > 1 and α < (N -1)/(N -2), which imply that ϕ(0) > 0 and ϕ ′ (1) > 0. Thus ϕ vanishes in exactly one point in (0, 1) and another one in (1, ∞), and again the derivative of ϕ in these points is negative. So all that remains to do is to prove the following fact

If v ∈ E k is such that ϕ ′ (t(v)) < 0, then v is unstable. (8) Let us prove it now. For t ∈ (0, ∞), set u 1 (t) = 1/(k + (N -k)t)
and u 2 (t) = tu 1 (t). Then let v(t) ∈ (0, 1) N , be the point whose first k coordinates are equal to u 1 (t) and whose last Nk coordinates are equal to u 2 (t). Then we have

H(v(t)) = k(k-1)u 1 (t) 2α +2k(N-k)t α u 1 (t) 2α +(N-k)(N-k-1)t 2α u 1 (t) 2α ,
and after some computation we find that

F (v(t)) = - tu 1 (t) 2α+1 H(v(t)) ϕ(t) e k ,
where e k is the vector, whose first k coordinates are equal to -(Nk) and whose last Nk coordinates are equal to k. Then notice that

D e k F (v(t)) = c(d/dt)F (v(t)
), for some constant c > 0. But recall that when v(t) is an equilibrium, ϕ(t) = 0. Thus

d dt F (v(t)) = - tu 1 (t) 2α+1 H(v(t)) ϕ ′ (t) e k .
So if ϕ ′ (t) < 0, e k is an unstable direction, proving (8). This concludes the proof of the lemma.

Lemma 4.6. The number of equilibriums in ∆ is finite.

Proof. Let v ∈ ∆, such that that v i = u 1 > 0, for i ≤ k, and v i = u 2 > 0, for i > k, for some k ≤ N/2. Set t = u 2 /u 1 , so that u 1 = (k + ℓt) -1
and u 2 = tu 1 and where ℓ = N -k. Recall (see the proof of Lemma 4.5) that v is an equilibrium if and only if φ(t) = 0, where φ :]0, ∞[→ R is defined by

φ(t) = (ℓ -1)t 2α-1 -ℓt α + kt α-1 -(k -1).
Studying φ, we show that two situations may occur: 1 is the only solution or there exist two other solutions, distinct from 1. This proves that E k contains at most 2 equilibriums. And therefore, one can check that the number of equilibriums in the interior of ∆ is at most 2 N -1.

Lemmas 4.4 and 4.5 show that any equilibrium in the interior of ∆, which is not equal to the center of ∆ is linearly unstable. Together with Lemma 4.2, Lemma 4.6 and Theorems 3.9, 3.11 and 3.12 this concludes the proof of Theorem 1.1.

Almost sure localization

In this section we prove a general result on the localization of strongly reinforced VRRWs. First we recall that given a locally finite graph G, and w : N → (0, ∞), we can define the VRRW (X n ) n≥0 by

P(X n+1 = y | F n ) = w(Z n (y)) z∼Xn w(Z n (z))
1 {Xn∼y} , with Z n (•) as in the introduction, and where the symbol X n ∼ y means that X n and y are neighbours in G. We say that the VRRW is strongly reinforced when

∞ n=0 1 w(n) < ∞. (9)
It is easy to see that under this hypothesis the walk can localize on two sites with positive probability. But something more can be said: Theorem 5.1. Let w : N → (0, ∞) be a weight function satisfying (9), and let G be a graph with bounded degree. Then a.s. the VRRW on G with weight w visits only a finite number of sites.

Proof. We adapt an argument of Volkov who proved the result when the graph is a tree (see [V1]). Let d > 0 be such that any vertex in G has degree at most d and let ε ∈ (0, 1) be such that εd 3 < 1.

It will be convenient to introduce a Rubin's construction of the walk. Similar ones were introduced already by Sellke [Sel] and Tarrès [T2], see also [BSS].

To each pair of neighbours x ∼ y of G we associate two oriented edges (x, y) and (y, x), and denote by E the set of oriented edges obtained in this way. Then we consider a sequence (ξ e ℓ ) e∈E,ℓ≥0 of independent exponential random variables, such that for any e and ℓ, the mean of ξ e ℓ equals 1/w(ℓ). We will also use the notation:

ξ x = (ξ (x,y) ℓ ) y∼x,ℓ≥0 ,
for any vertex x of G. Then given the sequence (ξ x ) x∈G , and a vertex x 0 of G, we construct a continuous time process ( Xt ) t≥0 as follows.

First X0 = x 0 . Then for each oriented edge (x 0 , y), we let a clock ring at time ξ (x 0 ,y) 0

, and let the process jump along the edge corresponding to the clock which rings first (at time min y∼x 0 ξ (x 0 ,y) 0

). At this time we also stop all clocks associated to the edges going out of x. Now assuming that ( Xt ) has been constructed up to some jumping time t, and that Xt = x, we use the following rule. For any y ∼ x, if during the time between the last visit to x before t (which we take to be 0 if t is the first time the walk visits x) and t the walk has visited y, then start a new clock associated to the edge (x, y) which will ring at time ξ (x,y) k , with k the number of visits to y before time t. If not, then restart the clock associated to (x, y) which has been stopped after the last visit of the walk in x, or start a new clock which will ring after a time ξ (x,y) 0 if both x and y have never been visited yet before time t. Then the walk jumps again along the edge associated to the clock which rings first at the time when it rings, and then we stop all clocks associated to edges going out of x. Then it is a basic and well known fact that a.s. two clocks never ring at the same time, so that this construction is a.s. well defined, and that if (τ k ) k≥0 is the sequence of jumping times (with τ 0 = 0), then ( Xτ k ) k≥0 has the same law as the process X starting from x 0 . Now for any vertex x and integer N ≥ 1 we consider the following event

E x (N) := ℓ≥N ξ (x,y) ℓ < min z∼x ξ (x,z) 0 ∀y ∼ x .
Note that, denoting by d x the degree of x,

P(E x (N)) = y∼x E e -dxw(0) ℓ≥N ξ (x,y) ℓ = l≥N 1 - d x w(0) w(ℓ) dx ≥ l≥N 1 - dw(0) w(ℓ)
d using in the last inequality that d x ≤ d. So that, when ( 9) is satisfied, we can fix N such that P(E x (N)) ≥ 1ε, for all x.

To each vertex x, let τ x be the first time the walk visits x. When τ x < ∞, we associate to x a type:

• the type 1 if at time τ x one of its neighbours has been visited more than N times; • the type 2 if x is not of type 1 and if every neighbour of x has at least one of its neighbours which has been visited more than N times before τ x ; • the type 3 otherwise.

We also associate two sets of vertices, C 1

x and C 2 x : when x is of type 1 and on E x (N), C 1 x = ∅, otherwise C 1 x is the set of all neighbours of x that have not been visited by the walk at time τ x . Thus C 1

x contains all the vertices that may be visited for the first time after a jump from x.

Define next C 2 x := ∪ y∈C 1 x C 2 x,y , with C 2 x,y as follows. When y has a neighbour that has been visited more than N times at time τ x and on E y (N), C 2

x,y = ∅, otherwise C 2 x,y is the set of all neighbours of y that have not been visited by the walk at time τ x . Thus C 2

x contains all the vertices that may be visited for the first time after a jump from a vertex in C 1

x . Observe that when x is of type 3, conditionally to F τx , the walk has a probability bounded below by some constant p > 0, depending only on N, in particular independent of x and F τx , to be stuck on {x, y} for some y ∼ x forever after τ x . So the conditional Borel-Cantelli lemma ensures that only finitely many x's can be of type 3. Now we define inductively a growing sequence of subgraphs (G n ) n≥0 ⊂ G, an increasing sequence of random times (τ n ) n≥0 and a sequence of vertices (x n ) n≥0 as follows. First G 0 = {x 0 } ∪ C 1

x 0 and τ 0 = 0. Note that C 1

x 0 = {y ∼ x 0 }. Now assume that G k , τ k and x k have been defined for all k ≤ n, for some n ≥ 0. If the walk never exists the set G n , then set G n+1 = G n and τ n+1 = ∞. Otherwise let τ n+1 be the first exit time of G n , x n+1 be the position of the walk at time τ n+1 and set

G n+1 = G n ∪ {x n+1 } ∪ C 1 x n+1 . For all n ≥ 0 with τ n < ∞, set O n = ∪ n k=0 C 2
x k \ G n , so that τ n+1 is the first entrance time of the walk in O n . Observe that if for some n, O n = ∅, then τ n+1 = ∞ and thus the walk will visit only a finite number of sites. Note also conversely that if the walk visits an infinite number of vertices, then τ n < ∞, for all n.

Define now a filtration (G n ) n≥0 by G n = σ(ξ x : x ∈ G n ). Then, we have that σ(X k : k ≤ τ n+1 ) ⊂ G n , and that x n+1 and its type are G n measurable. Likewise the number R n of sites in O n is also G nmeasurable. Moreover, since x n+1 ∈ O n , we have R n+1 ≤ R n -1 + |C 2

x n+1 | (where if A is a set we denote by |A| its cardinality). Set, for n ≥ 1, ℓ n = -1 if x n is of type 1 and on E xn (N) or if x n is of type 2 and on ∩ y∈C 1 xn E y (N), and set ℓ n = d 2 -1 otherwise. Thus ℓ n is G n -measurable and for n ≥ 0, R n+1 -R n ≤ -1 + |C 2

x n+1 | ≤ ℓ n+1 . Now it is easy to see that if x n+1 is of type 1,

E[ℓ n+1 | G n ] ≤ -1 + ǫd 2 < 0. Similarly if x n+1 is of type 2, E[ℓ n+1 | G n ] ≤ -1 + (1 -(1 -ǫ) d )d 2 ≤ -1 + ǫd 3 < 0.
Thus, setting A n := {x n is of type 1 or 2}, we get that L n := n k=1 ℓ k 1 A k is a supermartingale. Therefore, a.s. on the event A n occurs an infinite number of times, lim inf n→∞ L n = -∞ (using that on this event, L n cannot converge since on A n , |ℓ n+1 | ≥ 1). Therefore a.s., if the walk visits an infinite number of vertices, then since x n is of type 3 for only a finite number of n, a.s. on the event A n occurs an infinite number of times, lim inf n→∞ R n = -∞, which is absurd since, R n is nonnegative by definition. This proves the lemma.

Acknowledgements. We acknowledge financial support from the Swiss National Foundation Grant FN 200021-138242/1 and the french ANR project MEMEMO2 2010 BLAN 0125.

as their last Nk coordinates). For v ∈ E k , we also set t(v) = v N /v 1 . We have the Lemma 4.4. Assume that α ≥ (N -1)/(N -2), and let v ∈ E k , with

Proof. It follows from Lemma 3.7 that for any i < j ≤ k, D e j -e i F (v) = λ 1 (e je i ),

with

Thus if any of the hypotheses of the lemma is satisfied, there DF (v) has at least one positive eigenvalue, and so v is linearly unstable.

On the other hand we have the following:

then v is linearly unstable.

Proof. Following our previous notation, set u 1 := v 1 and u 2 := v N , and recall that u 1 = u 2 , since v is not equal to the center of ∆. Recall also that t(v) = u 2 /u 1 . Note that since ku 1 + (Nk)u 2 = 1, we have u 1 = 1/(k + (Nk)t). Now the fact that v is an equilibrium means that F (v) = 0, which is equivalent to say that the function ϕ defined by

vanishes at point t(v). We now study the function ϕ. First ϕ ′ (t) = t α-2 ψ(t), with

In particular ψ is strictly concave, ψ(0) < 0 and lim t→∞ ψ(t) = -∞. Now two cases may appear. Either ψ vanishes in at most one point, in which case ϕ is nonincreasing, thus vanishes only in 1. But this case is excluded, since t(v) = 1 by hypothesis. In the other case ψ vanishes in exactly two points, which means that there exist t 1 < t 2 such that ϕ is decreasing in (0, t 1 ) ∪ (t 2 , ∞), and increasing in (t 1 , t 2 ). Now consider first the case when k = 1, which implies ϕ(0) = 0.