Sophie Thoyer

Atakelty Hailu

Multi-Unit Auctions to Allocate Water Scarcity Simulating bidding behaviour with agent based models

Keywords: enchères multi-unitaires, apprentissage, simulation multi-agent, allocation de l'eau multi-unit auctions, learning, multi-agent models, water allocation

Les enchères multi-unitaires sont un outil potentiellement intéressant de réallocation des droits d'usage de l'eau car elles évitent le problème du « lumpy bid ». En revanche, la théorie sur les enchères multi-unitaires ne permet pas d'identifier les stratégies optimales des enchérisseurs (car il existe une multiplicité des équilibres) et ne fournit donc que des indications partielles sur les formats d'enchère les plus performants. Les études empiriques et expérimentales complètent notre connaissance mais elles sont relativement rares, limitées à des cas simples (deux enchérisseurs, deux unités) et démontrent que les enchérisseurs ont une rationalité limitée et apprennent à améliorer leur stratégie par l'expérience et la répétition. Ce papier construit un modèle de simulation multi-agents pour comparer la performance de différents formats d'enchères inversées (prix uniforme, discriminant et Vickrey généralisé) lorsque les enchérisseurs soumettent des fonctions d'offre continues et apprennent à ajuster leur stratégie pour améliorer leurs gains nets (algorithme d'apprentissage par renforcement de Roth et Erev). Nous démontrons que, conformément à la théorie, le format Vickrey généralisé implique les stratégies les plus sincères et nous confirmons la réduction de demande dans le cas des enchères uniformes et discriminantes. Notre étude démontre les contributions potentielles à la recherche dans ce domaine d'une approche de simulation multi-agents et nous permet de formuler des recommandations sur la mise en place d'enchères multi-unitaires.

Introduction

Preserving minimal instream flows in rivers for environmental and recreational purposes may entail the permanent (when river water is over-allocated) or transitory (in the case of droughts) reduction of water allocation to farmers. It can take the form of compulsory curtailments with a negotiated compensation or it can be voluntarily traded between irrigators and the public agency in which environmental interests are vested. The second option has been implemented in various contexts in the US through auctions to acquire water rights, mostly on a short-term basis [START_REF] Cummings | Using laboratory experiments for policy-making: an example from the Georgia irrigation reduction auction[END_REF]. This article analyses the use of auctions to allocate water scarcity between farmers and explores the scope for multi-unit auctions as an alternative to other existing irrigation auction designs.

Multi-unit or multiple unit auctions are auctions where bidders bid with their demand or supply curves or schedules. The main advantage of multi-unit auctions is that they allow us to avoid the lumpy bid issue [START_REF] Tenorio | Revenue equivalence and bidding behaviour in a multiunit auction market: An empirical analysis[END_REF]. However, there is great uncertainty about the best auction formats when multi-unit auctions are employed [START_REF] Laury | Enhancing and improving designs for auction mechanisms that can be used by the EPD for irrigation auctions --Water policy working paper #2002 -012[END_REF]. The theory can only supply the structural properties of equilibrium strategies; however, the multiplicity of equilibria does not allow for comparisons across auction formats (see [START_REF] Martimort | Enchères multi-unitaires, un survol de la literature récente[END_REF] for a review). Empirical studies [START_REF] Tenorio | Multiple unit auctions with strategic price-quantity decisions[END_REF]Wolfram, 1998, List and[START_REF] List | Demand reduction in multi-unit auctions: evidence from a sportscard field experiment[END_REF] and experiments [START_REF] Kagel | Behavior in multi-unit demand auctions: experiments with uniform price and dynamic Vickrey auctions[END_REF][START_REF] Engelmann | Bidding behaviour in multi-unit auctions -an experimental investigation and some theoretical insights[END_REF] have improved our knowledge of multi-unit auctions but they remain scarce and most experiments are restricted to two bidders and two units.

Moreover, they demonstrate that bidders have limited calculation capacities and learn from experience through repeated play instead of landing on the equilibrium strategies at the outset of the game.

This study builds an agent-based model of a multi-unit auction to study the performance of alternative auction formats. Agent-based modeling (ABM) or agent-based computational economics (ACE) is a tool that is increasingly being used to complement theoretical and experimental studies in economics. [START_REF] Tesfatsion | Agent-Based Computational Economics: Growing Economies from the Bottom Up[END_REF] surveys the economics research areas in which ACE has been applied while [START_REF] Duffy | Agent-based models and human-subject experiments[END_REF] examines the relationship between ACE and human-subject experiments in economics and provides an overview of studies using ACE to examine findings from human subject experiments. ACE is the study of artificial societies of interacting autonomous agents that directly emulate the behaviours of individuals, institutions and environmental components that make up the system being studied [START_REF] Epstein | Growing artificial societies: Social sciences from the bottom up[END_REF][START_REF] Epstein | Growing artificial societies: Social sciences from the bottom up[END_REF][START_REF] Tesfatsion | Agent-Based Computational Economics: Growing Economies from the Bottom Up[END_REF]. Unlike conventional or deductive approaches, the starting point in ACE is the specification of agent attributes and behaviours rather than equations or equilibrium conditions describing the system under study. Therefore, ACE is suited to the study of systems where modelling outcomes can be gainfully enriched through the explicit incorporation of phenomena like agent heterogeneity, local interactions and networking, inductive learning, as well as through the relaxation of other restrictive assumptions that are normally imposed under conventional analysis for tractability purposes [START_REF] Tesfatsion | Agent-Based Computational Economics: Growing Economies from the Bottom Up[END_REF]. Studies applying ACE to the study of auctions include [START_REF] Andreoni | Auctions with Artificial Adaptive Agents[END_REF], Nicolaisen, Petrov and Tesfatsion (2001), [START_REF] Bower | Experimental analysis of the efficiency of uniform price versus discriminatory auctions in the England and Wales electricity market[END_REF], Bunn and Oliveria (2001), Hailu and Schilizzi (2004). In our study, competing bidders submit continuous bid supply functions in the auction and employ reinforcement learning algorithms to update their bidding strategies.

The paper is organized as follows. In the first part, we describe the main issues associated with water auctions which have already taken place and we discuss the advantages of multi-unit auctions. We also review the various auction formats and the structural properties of equilibrium strategies. In the second part, we develop an agent-based model (ABM) where bidders are represented by software agents mimicking their attributes and behaviours [START_REF] Hailu | Assessing the performance of auctions for the allocation of conservation contracts: Theoretical and computational approaches[END_REF]: they have a boundedly rational and learn to improve their bidding strategy through repeated play using the [START_REF] Erev | Predicting how people play games with unique, mixed strategy equilibria[END_REF] reinforcement learning algorithm. In the third part, we conduct a number of computer-based experiments in order to compare equilibrium strategies, costs and efficiency, in the following three alternative sealed-bid auction formats: the uniform-price multi-unit auction; the discriminatory multi-unit auction; and the generalized Vickrey auction [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF].

We demonstrate that under the Ausubel format, simulated bids converge towards truthful bids as predicted by the theory and that bid shading is the rule for the uniform auction. However, the simulated bidding behavior under discriminatory pricing is different from what the theory expects, although it is in accordance with experimental results obtained by other authors. Our study allows us to assess the potential gains from agent-based modeling approaches in the assessment of the dynamic performance of multi-unit procurement auctions. We were able to assess changes in bidding behaviour accompanying changes in competition levels, and to compare the differences in bidding strategies among bidders with different opportunity cost (true supply curve) structures. We then draw some recommendations for the desirable format of water auctions.

Reverse multiple-bid auctions to re-allocate water entitlements

Water auctions

Increasing concerns regarding the environmental consequences of instream water scarcity have led a number of policy-makers to set-up water license buyback schemes. These schemes aim to reduce the consumptive use of water and increase environmental flows in times of drought. In the United States, auctions have been trialed as an alternative to other voluntary schemes such as posted prices. Auctions are expected to improve the efficiency of water curtailment and reduce budgetary expeditures through the minimization of information rents paid to farmers.

The Georgia irrigation auction is one of the most interesting examples. The Flint River Drought Protection Act was enacted in April 2000. It requires that state authorities use an "auction-like process" to pay farmers to suspend irrigation in declared drought years. The Environmental Protection Division is required to assess the risks of an upcoming drought and to determine consequently the number of hectares, which must be taken out of irrigation to maintain acceptable instream flows. An auction is organized whereby farmers may offer to voluntarily forego irrigation of all land covered by a specific water-use permit for the remainder of the cultivation year in exchange for a lump sum payment. There is one single buyer, the State, and multiple sellers, the farmers. Pilot sessions were conducted within an experimental setting to assess and compare different auction designs: a discriminative-price auction, a uniform-price auction, an iterative uniform price auction as well as posted price offers [START_REF] Cummings | Using laboratory experiments for policy-making: an example from the Georgia irrigation reduction auction[END_REF][START_REF] Laury | Enhancing and improving designs for auction mechanisms that can be used by the EPD for irrigation auctions --Water policy working paper #2002 -012[END_REF]. The target acreage is not public knowledge. A real case auction was finally conducted through the Internet in March 2001. It was set up as an iterative discriminative auction in which farmers were allowed to revise their offers after preliminary results were announced. The process continued until no one wished to submit a revised offer. Although the rate of participation was high, it was found that the iterative process had led to a substantial increase of payments to farmers and to inefficiencies, although the contrary was expected. Consequently, a revision of the auction format was planned.

The San-Antonio auction (Texas) is a programme which seeks to acquire additional aquifer pumping rights by purchase or lease from irrigators West of san Antonio. The auction was held in April 2003, with the San Antonio Water Systems being the buyer and seeking to relieve short term scarcity issues. It was an ascending multi-unit auction. The auction was conducted in real-time through the Internet, and bidders could re-evaluate and adjust a bid in response to other bidder's offerings during the auction.

It is also worth mentioning here the Deschutes water exchange in Oregon. The Deschutes Resources Conservancy (DRC) is a private nonprofit organization dedicated to stream flow restoration and water quality improvement in the Deschutes Basin. The water exchange programme was created in 2001 to foster an active market for water rights in order to promote efficient water use and restore depleted stream flows. The DRC started a payment scheme to provide incentives for the right holders to forego the use of all or a portion of their rights on an annual basis (used subsequently for instream use). The 2002 policy was based on a fixed price per acre-foot: participation was secured among small acreage landowners. The exchange considered using a reverse sealed-bid auction mechanism as part of its 2003 program.

These examples highlight two important features about real world auction trials. First, that there is little guidance for policy-makers about the best auction formats. Formats so far employed vary from open format to sealed bid, from ascending uniform price auctions to iterative auctions with discriminatory payments. Second, all the trials share one common feature. All auctions were multi-unit, single-bid auctions: bidders were allowed to submit only one bid for a pre-defined quantity (either an acre of land or a price per cubic meter). They were not offered the option to submit a bid supply curve (i.e. a schedule of incremental quantity-price offers) . This raises the issue of lumpy bids, mentioned by [START_REF] Tenorio | Multiple unit auctions with strategic price-quantity decisions[END_REF] but also illustrated in the case of the auctioning of conservation contracts [START_REF] Chan | The role of auctions in allocating public resources[END_REF]. If a landholder cannot submit several bids in order to obtain different rental fees for different parts of his/her land, and if marginal conservation costs tend to increase with the land area conserved, then landowners will avoid bidding for large areas of land. This is because the landholder would have to increase the bid with the size of the land offered (in order to properly reflect the average opportunity cost of the land), thereby reducing his/her chance of winning. The same problem is likely to arise with water buyback auctions: it is likely that farmers could choose to adopt water saving practices or technologies which could allow them to forego part of their entitlement at a reasonable cost, but that they would be more reluctant to give up irrigation altogether on large pieces of land since it would have a much higher cost in terms of foregone benefits. Therefore, if, say for monitoring reasons, bidders are only allowed to offer only one piece of land for withdrawal from irrigation, then water right holders are unlikely to offer large amounts of land. This phenomenon leads to lower participation, higher cost per unit of water recovered and lower efficiency because the auction exploits only differences in the average costs of individual right holders, but not the differences in the marginal costs of alternative techniques or levels of water curtailment that can be undertaken by a particular right holder.

One way to get around this issue of lumpy bid problem is to organize multi-unit auctions whereby farmers can actually submit a supply schedule rather than a single bid. The focus of this study is to examine the performance of alternative auction formats for auctions where sellers submit supply schedules represented as bid functions.

Multi-unit auctions

The theoretical literature on multi-unit auctions usually distinguishes between sequential and simultaneous auctions of several objects with bidders wanting more than one unit. In the case of water auctions, we concentrate on simultaneous procurement auctions, for multiple identical units, within a symmetric independent private value model. We therefore assume that the whole issue of affiliated or common values is not relevant in the case of water right buybacks since what counts for the farmer is the private cost associated with a reduction of his water entitlements. 1 We also assume that the number of units that the auctioneer wishes to buy is fixed (as opposed to a budget constrained auctioneer or an auctioneer with a downward-sloping demand curve). Since most of the literature on multi-object multiple-bid auctions describes selling auctions, here we describe and summarize briefly what would be the equivalent predictions for a procurement auction in the case of a continuous rather than discrete bid specification. The continuous bid specification can be interpreted as one relating to the purchase of perfectly divisible units and was initially developed by [START_REF] Wilson | Auctions of shares[END_REF] who called it "auctions of shares".

There are two main options for buying multiple units simultaneously: open format auctions or sealed bid auctions. In the sealed bid auction, payments can be discriminatory, uniform or follow the generalized Vickrey rule. In the open format, we can have ascending auctions (discriminatory), descending auctions (uniform) or [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF] auctions. The relation 1 Landholders or farmers will be different in their productivity levels and, therefore, in their values for water. This may not be the case in the rare circumstance where there is scope for alternative resale on a water market between private right-holders or when farmers have heterogeneous expectations concerning the severity of the upcoming drought and the resulting scarcity.

between sealed bid formats and corresponding open formats is theoretically one of outcomeequivalence [START_REF] Krishna | Auction Theory[END_REF]. It therefore implies differential overbidding. Bidders with the same opportunity cost per unit increase their bids by different amounts according to the quantity they are offering to provide: the larger participants bid more than their smaller competitors for units with comparable unit costs.

In sealed bid auctions, each bidder is asked to submit multiple bids indicating the price he is willing to accept for different quantities sold. In effect, these multiple bids are equivalent to an inverse supply function. In certain settings, bidders can be asked to submit a continuous supply schedule rather than discrete bids. To describe the allocation procedures in the different auction formats, we need to define the concept of residual demand. Let's define the supply schedule of { }

) ( , 0 max ) ( b S Q b D i j j d i ∑ ≠ - - = Each bidder is awarded the quantity i Q * at which his supply schedule intersects his residual demand. *) ( *) ( * b S b D Q i i i = = -
However, the three formats differ in the calculation of the payments for the winners (see figure 1 in appendix):

-in a discriminatory auction, each bidder is paid an amount equal to the sum of his actual winning bids (or the area under his supply schedule up to i Q * in the continuous case).

-in a uniform-price auction, all units sold are paid at the market-clearing price equating aggregate supply to demand. Therefore, infra-marginal winners receive payments that are higher than the production costs implied by their bid supply.

-in a generalized Vickrey auction, each bidder is paid for each unit sold the highest value of the corresponding losing bid. If he has won the first unit, he is paid the highest losing bid of his competitors on this first unit. For the second unit, he is paid the highest losing bid of his competitors on this second unit. In a continuous case, where bidders would submit supply schedules rather than discrete bids, each successful bidder is paid the entire area under the residual demand up to i Q * .

Equilibrium strategies, efficiency, and revenue

For multiple-bid auctions, no closed form expressions of the bidding strategies are available in the general case and most authors have therefore focused on the structural properties of the equilibrium strategies. [START_REF] Wilson | Auctions of shares[END_REF], Back and Zender (1993), Englebrecht-Wiggans and Kuhn (1998), [START_REF] Tenorio | Multiple unit auctions with strategic price-quantity decisions[END_REF] and [START_REF] Ausubel | Auctions of divisible goods: on the rationale for the treasury experiment[END_REF], have analysed the outcomes of different multi-unit auction formats and shown that the revenue equivalence theorem does not extend to the case of multiple-bid auctions.

They demonstrate3 , using different but simplified auctions, the issue of bid shading (or demand reduction) associated with a uniform-price multiple-bid selling auction. Their findings agree: although it is a dominant strategy to bid truthfully for the first unit (or, in the continuous case, when quantity tends to zero), it is efficient for the bidders to shade their bids for additional units or quantities. Moreover, the amount of bid shading increases with quantities offered. "The reason for this differential shading is that the incentive to win units at any price below marginal value is offset by the incentive to reduce the price paid on infra-marginal units that are won anyway" (Ausubel and Cramton, 2002, p23). The latter becomes increasingly important when quantities increase, which explains the increasing bid shading. The consequence is that bids no longer correlate with opportunity costs, leading to efficiency losses. All demonstrations can be carried over with no restriction to the procurement case. This phenomenon has been verified empirically by [START_REF] Wolfram | Strategic bidding in a multiunit auction: An empirical analysis of bids to supply electricity in England and Wales[END_REF] who conducted an econometric analysis of "supply inflation" in the electricity procurement auction in England and Whales.

It is also demonstrated that there is an incentive, in a discriminatory format, to submit flatter supply curves than in a uniform price auction. If bidders are risk neutral, submitting entirely flat supply curves is a possible equilibrium (Back and Zender, 1993), although drastic demand reduction is also a possible outcome, especially when the difference in marginal values is high (Englebrecht-Wiggans and Kahn, 1998;[START_REF] Krishna | Auction Theory[END_REF] . Since there are different classes of equilibrium strategies, it is difficult to analyse how bidders coordinate or even compare the efficiency of the two formats. [START_REF] Tenorio | Revenue equivalence and bidding behaviour in a multiunit auction market: An empirical analysis[END_REF] compares the discriminatory and uniform price auction formats in the Zambian foreign exchange market, which successively implemented the two. He demonstrates that the uniform price auction yields higher average revenue to the auctioneer. His case study includes some form of affiliated values, however.

Only in the generalized Vickrey payment or its counterpart in the open format (i.e. the ascending auction with "clinched" quantities designed by [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF]) is truthful bidding a weakly dominant strategy, resulting in efficient allocation. On the other hand, for uniform and discriminatory formats, only increased competition can lead to the reduction of strategic behaviour and to more truthful bidding (Ausubel and Cramton, 1996;[START_REF] Swinkels | Asymptotic efficiency for discriminatory private value auctions[END_REF]. The generalized Vickrey is more complex and has not been employed in practice. It would be very useful to how the familiar formats compare with it and the extent to which the relative performance of the different formats depends on the competition level and other details about the auctions.

Experiments

One way to circumvent the unavailability of predictive analytical results is to turn to experimental methods. Experiments can be designed to confirm theoretical results but their function can also be to carry a problem beyond the analytical capabilities of theoretical analysis or to fill a void when theory is incomplete or not available (Hailu and Schilizzi, 2003).

Given both the weakness of the theory on multiple-bid auctions and the increasing use of such auctions in economic life, a growing number of researchers have tried to investigate bidding behaviour with laboratory experiments. Alemgeest, Noussair and Olson (1998) demonstrate that, in the two unit case, an ascending clock auction generates less revenue than the uniform sealedbid auction, due to strategic bid shading. [START_REF] Kagel | Behavior in multi-unit demand auctions: experiments with uniform price and dynamic Vickrey auctions[END_REF] also compare uniform-price sealed bid and open ascending auctions, with a real player with flat demand for two units playing against a robot with unit demand. Their findings also highlight the issue of demand reduction and show that in the open format, bids converge towards equilibrium values more rapidly than in a sealed bid format, as if "clock could enhance learning". They confirm that the Ausubel format leads to truthful bidding. [START_REF] Engelmann | Bidding behaviour in multi-unit auctions -an experimental investigation and some theoretical insights[END_REF] compare bidding behaviour under five auctions formats and for a case where two bidders with flat demand curves compete to buy two units. Their experiments demonstrate that demand reduction is more acute in uniform open than in uniform sealed bid auctions, and that the Ausubel format eliminates bid shading. They also find that, in clear contrast to the theoretical prediction, bidders in discriminatory auctions place substantially different bids on the first and second unit, even when their valuations for the two units are close. They suspect that it might be due to myopic zero profit aversion of the bidders but do not prove it.

All these experiments are conducted in extremely simplified settings. Human experiments can also be extremely costly and complicated to run when exploring issues such as competition or heterogeneity amongst bidders. One way to deal with these difficulties is to employ computational or in silico experiments, conducted with autonomous "artificial" agents interacting in artificial societies [START_REF] Tesfatsion | Agent-Based Computational Economics: Growing Economies from the Bottom Up[END_REF]. The starting point of such agent-based models is the specification of agent attributes and behaviors rather than equations relating system level variables to describe the dynamics of the system. In the field of auctions, such simulations have already been conducted to study electricity markets [START_REF] Nicolaisen | Market power and efficiency in a computational electricity market with discriminatory double-auction pricing[END_REF]Dunn and Oliveira, 2001;Bower and Dunn, 2001) and to compare learnt and optimal bids in the context of single bid auctions [START_REF] Andreoni | Auctions with Artificial Adaptive Agents[END_REF].

The modelling of bidding strategies

Structure of agent based model

Our auction model has a population of agents selling water in a sealed-bid auction to a single buyer, the government agent. The government agent has a target or demand level for water purchases. Each seller is characterized by a (true) water supply function and a capacity indicating the maximum amount of water it has for sale. The water supply function represents the marginal value or opportunity cost of water to the seller and we assume that it is a non decreasing function of the amount of water given up. In the case of water, this maximum capacity would be equal to the bidders current water entitlement. The government agent does not know the true water supply functions of the different bidders and makes selection based on submitted or declared water supply bid functions. Over time, sellers learn to choose supply bid functions that maximize their expected net incomes.

Each auction round involves two stages. In the first stage, the government collects bid functions from the sellers and calculates the residual demand for each bidder and determines the equilibrium quantities bought from each of them at the intersection of their bid supply and their residual demand. In the second stage, payments to individual bidders are determined according to the auction format in use. See section 1.2 and Figure 1 in appendix for a description of how payments are determined in the different auction types. Sellers use the results of the auction to compute their net incomes and to update the probabilities with which they choose their bid strategies for the next round. The strategy choice probabilities of a bidder therefore depend on his opportunity costs (true water supply function) as well as on the history of choices he has made and rewards obtained for those choices.

For the sake of simplicity, it is assumed that the true water supply function of all a sellers i is linear and can be written as:

i i i i Q b a P 0 0 + = with i i ms Q ≤ ≤ 0
, where ms i is the maximum water capacity of bidder I (equivalent to his water entitlement)

The model is built for a heterogeneous population of eight sellers with the water supply capacity, intercept and slope parameters indicated in Table 2. Capacity takes either of two values, namely, 0.25 and 0.75. The intercept parameter 0 i a can be either 0.25 or 0.75 while the slope parameter 0 i b can be 0.25 or 0.75. No two bidders are identical. The intercept parameter is the entry price, and reflects the fixed cost of giving up water. The maximum price (Max Price) is the price required by the seller when selling his whole entitlement ms i . From table 2, we can see that sellers 7 and 8 have the highest marginal costs of supply for all quantities whereas players 1 and 2 have the lowest marginal costs and will therefore have many more opportunities to be selected in a competitive bidding process.

Seller choice strategies

We make the assumption that the learnt bidding curve is also linear and can therefore be written:

i i i i Q b a P + = with ) ( i i Q β the strategic

bid of player i

There are therefore two dimensions to the seller's choice strategy: intercept choice (a i ) and slope choice (b i ). The learning algorithm described in 2.3 will allow bidders to progressively explore different combinations of a and b and to retain the best values based on the performance of past bids. Intercept and slope choices are discretized into ten steps. For the intercept, for example, the seller has ten choices 0, 0.1, 0.2, … ,1.0. For the slope parameter, there is a choice of ten values equally spaced between 0 and the maximum slope value implied by the constraint discussed below. The true intercept and slope parameters are included in the choice sets to allow for truthful revelation of supply function parameters.

A constraint is imposed on the choice of strategies so that the chosen bid function does not have any section falling below the true cost function. This is guaranteed by restricting the allowed or feasible parameter choices (a and b) as shown in Figure 1. The constraints imposed are: 1) that the learnt supply curve should not fall below the true supply curve; and 2) that the relevant marginal price for any bidder is not more than a certain proportion (maxPF, or maximum price factor) of the marginal cost of supply of the most expensive unit by the most expensive supplier (maxP). In this case, max PF is set to 3 (with maxP the marginal price of the last unit supplied by seller 8, or 1.325) The first constraint was included to ensure that the learnt supply curve does not lead to losses. And the second prevents the relevant strategy space from becoming unnecessarily big.

Figure 1: Seller's feasible strategies of bid function choice.

The learning algorithm

Different learning models have been developed over the last several decades. A typology of learning models presented by [START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF] shows the relationship between these learning algorithms and how certain variants can be obtained as special cases of others. The models differ in terms of their information requirements or assumptions. The reinforcement-learning algorithm is chosen for this study as it is particularly suitable for modelling bidding behaviour without requiring that players be knowledgeable about forgone payoffs associated with strategies that they did not select.

The reinforcement-learning algorithm was developed by [START_REF] Roth | Learning in extensive form games: experimental data and simple dynamic models in the intermediate term[END_REF] based on the reinforcement principle that is widely accepted in the psychology literature. [START_REF] Erev | Predicting how people play games with unique, mixed strategy equilibria[END_REF] extend and use this learning algorithm to model behaviour from 12 experimental studies 4 of repeated games with unique nontrivial equilibria in mixed strategies. They find that the reinforcement learning model's predictions of the choices of experimental subjects generally outperform equilibrium predictions. The Roth-Erev algorithm or modified versions of it have been used in agent-based studies of electricity auction markets (e.g. [START_REF] Nicolaisen | Market power and efficiency in a computational electricity market with discriminatory double-auction pricing[END_REF][START_REF] Bunn | Agent-based simulation: An application to the new electricity trading arrangements of England and Wales[END_REF].

The Roth-Erev learning algorithm is based on the following four principles rooted in the psychology of learning [START_REF] Erev | Predicting how people play games with unique, mixed strategy equilibria[END_REF]: the law of effect, the power law of practice, experimentation and recency. The law of effect asserts that the tendency to choose an action is strengthened (reinforced) or weakened depending upon whether the action produces favourable results or not. This principle implies that choice behaviour is probabilistic. The power law of practice refers to the fact that learning curves tend to be initially steep. Experimentation (or generalization) implies that strategies that are similar to previously chosen successful ones will be employed more often. Experimentation prevents players from quickly being locked into particular choices. Recency (or forgetting) requires that recent experience has more impact on behaviour than past experience.

The main features of the algorithm can be described using the following three equations. If the propensity of player i to choose strategy (a,b)) at time t is denoted by ) ( t q ab i , the propensity updating function can be written as (Erev and Roth 1998, p. 863

): ) 1 ( ) , , ( ) ( ) 1 ( ) 1 ( R b a E t q t q cd ab i ab i + - = + φ
where: φ is the recency parameter, R is the reward or reinforcement from previous choice of strategy (c,d)and is the payment above true supply function obtained by the seller, while E cd (a,b,R) is the following three step generalization function 5 : 4 Eleven of these games were conducted by different researchers in the period between 1960 and 1995. 5 For strategy sets without linear order, the generalization function should be specified as a two-step function. See Erev and Roth (1998, p. 863)

. = R(1-ε) if a = c and b= d E cd (a, b, R) = R. (ε/2) if (a, b) is neighboring strategy of (c,d) = 0 otherwise
where ε is an experimentation parameter (see Figure 2). The probability that player i uses his (c,d) strategy is then given by:

) 3 ( ) ( ) ( ) ( t q t q t p cd i cd i cd i ∑∑ =
Therefore, this learning algorithm has three parameters, namely, the recency parameter, the experimentation parameter as well as a scale parameter (s) that determines the initial propensities 6 . The values of these parameters that provided the best data for the 12 games studied in [START_REF] Erev | Predicting how people play games with unique, mixed strategy equilibria[END_REF] were used in this study. These values are 0.1, 0.2 and 9, respectively.

Our experiments with alternative values for these parameters show that the convergence between theoretical and learnt bids is insensitive to the values of these parameters.

Simulation results, comparative statics and discussion

The model was used to conduct experiments at five different levels of demand, namely, 0.1, 0.5, 1, 2, and 3 units, and for the three auction formats (generalized Vickrey, discriminatory and uniform price). Compared to the aggregate or total capacity of 4.0 units offered by the 8 bidders, these demand levels cover a wide range of competition levels (from 2.5% to 75%). The relative performance of the different auctions depends on the level of this competition as discussed below.

Difference in auction results becomes more important as the demand level increases.

In all the experiments, bidder agents start with randomly selected bids and adjust their bids over the auction rounds. To ensure convergence, 5000 rounds were conducted for each auction. The results converge to their final values much earlier that the 5000 th round. However, discussions below are based on the results form the 5000 th round. For each auction case (demand level and auction format), 100 replication with different random seeds were run. Results discussed here are based on the averages of these replications.

Expected results

As discussed in Section 1.2, the theory helps us characterize the structural properties of equilibrium strategies. These characterizations are summarized in figure 3

Individual learning

Since learning involves two parameters, a good measure of the deviation of the learnt values from the true values is the Euclidean distance between the two pairs. The deviation of learnt from true supply parameter values is smallest in the case of the Vickrey auction, at all demand levels (See Table 3), which confirms the truthful revelation mechanism nature of this format. This deviation is highest under the discriminatory auction where bidders learn to alter their entry prices and supply slopes. Uniform auctions lead to strategic biases but they are less dramatic than in the case of discriminatory auctions.

It is useful to note that for low levels of demand, corresponding to high competition, only the lowest marginal cost bidders (bidders 1 and 2) are selected and are therefore offered an opportunity to learn. Even for a level of demand of 2 (auction presented in table 4), sellers 5 and 6 are rarely selected in the successive bidding processes. This is reflected in table 4d which highlights that highest opportunity cost sellers (sellers 8, 7, 6 and 5) rarely succeed in selling their water in the auction. The range of learnt parameters does not exactly match the theoretical predictions but confirm a number of hypotheses (See Tables 4 and5). First of all, the Vickrey auction and the uniform price auctions lead to comparable results, although on average the generalized Vickrey leads to slightly more sincere bidding than the uniform format. It is interesting to note that in both formats, bidding on the first unit is almost truthful, which is consistent with theory, but that sellers with low capacity display very aggressive overbidding strategies on the following units whereas sellers with a high capacity display almost sincere bidding on all units. This is not predicted by theory and deserves further investigation.

For discriminatory auctions, the average learnt entry price is clearly above the true entry price; however, the phenomenon of the "flatter supply" is not verified. They all display overbidding strategies where both the entry prices and payments required for additional units are inflated. This confirms the results by Englebrecht-Wiggans and Kahn (1998).

These tendencies are more clearly marked when the level of competition declines. Bid shading increases slightly for Vickrey and uniform auctions, although strategies under the Vickrey auction remain closer to sincere bidding than strategies under uniform price. However, the discriminatory auction displays unexpected results: learnt entry prices are very high whereas the overbidding on following units is reduced.

Auction outcomes

The overall outcomes of the auction can be judged using different criteria. From the policy maker's point of view, both budgetary costs and allocative efficiency are important. Table 6 shows that for very high levels of competition, the three auctions perform almost identically.

However, when competition is less acute, we observe larger discrepancies between auctions, with discriminatory auctions displaying bad performance indicators and uniform auctions. When competition is really low (demand = 75% of aggregate supply), the three formats perform equally bad, with high budgetary outlays paid by unit of water..

Table 7 shows the performance of auctions relative to the full information case. The Vickrey auction exhibits least distortion from outcomes obtained under truthful bidding, especially for low levels of competition whereas the uniform and discriminatory auctions might involve substantial misrepresentation of bid functions.

We observe as well that if budgetary outlay is the decisive criterion, then discriminatory auctions perform well for high levels of competition, although it looses its budgetary savings advantage at higher levels of demand. At the highest demand level considered here, even the uniform auction entails payments per unit higher than those required under the Vickery auction.

Conclusions

As management agencies around the world look for better ways of reallocating or allocating water, interest in mechanisms like procurement multiple-bid auctions is likely to grow. There have already been some applications of this mechanism. The potential benefits of alternative auction designs need to be studied.

This paper considered three alternative auction types that could be employed in cases where sellers' bids are in the form of supply schedules or bid functions rather than single quantity-bid pairs. Theoretical predictions regarding three multi-unit auctions, namely, generalized Vickrey, discriminatory and uniform prices, are first discussed. An agent-based model with eight sellers bidding to supply water is then used to study the performance of the three auctions under circumstances where bidders learn to change their bid supplies over time. The bidders learn over a strategy space with dimensions relating to the intercept and slope parameters of bid function.

The comparison is undertaken for five different demand levels, ranging in magnitude from 2.5% to 75% of aggregate supplier capacity.

Learnt bid supply functions are found to be closest to true ones for the Vickrey auction. The uniform auction comes second by this criterion and discriminatory auctions lead to extreme overbidding, especially for low levels of competition.

Misrepresentations in declared (or submitted) bid supply functions mean that water purchase targets are not necessarily met using least cost sources of water. The Vickrey auction leads to reallocation of water with minimum opportunity cost. However, it is important to note that for very high levels of competition or very low levels of competition, the performance of the three auctions are in fact similar and if budget expenditures carry more weight than gains in allocative efficiency, then uniform auctions can be a better choice. Therefore, a careful assessment of the tradeoffs implied by the choice of auction type is necessary. The Vickrey auction is unfamiliar and more complicated. But the potential benefits it offers in minimizing social cost of reallocated water for all demand levels and budgetary outlay makes it an attractive format, especially when competition is not acute. This could happen in the case of very high demand, as would occur, for example, if there is a severe drought or when water can only be bought in a restricted area from a small number of potential suppliers. However, in most cases, auctions are organized to respond optimally to a forecasted deficit of water during the summer months: demand by the policy-maker is usually much lower than the aggregate potential supply of all farmers. In such case, the choice of an auction format is less important. However, agencies in charge of water procurement might need to have standard auction formats in place. The results from our study point to the importance of tailoring the format to the intensity of demand that is likely to be most frequent.

Finally, the model used here has focused on learnt supply curves that are linear. This simplified the modelling process and has allowed us to say more about the performance of alternative auctions than we could be based on the theory alone. However, it would be interesting to investigate in further research the implications of more general or learnt supply curves that are nonlinear.

  per-unit bids. We can then define the residual demand facing bidder i, ) (b D i -, as the total demand Q d less the sum of the amounts offered by other bidders for each level of bid.

  .ms ≤ maxPF.maxP a o ≤ a a + b.ms ≥ a o + b o .ms

Figure 2 :

 2 Figure 2: Generalization (experimentation) with Moore Neighbours.

  below.

Figure 3 :

 3 Figure 3: structural properties of equilibrium strategies under discriminatory and uniform-price formats.

Figure

  Figure 1: Total payments under different auction formats

Table 1 :

 1 Outcome equivalence for various formats of procurement multi-unit auctions and structural properties of equilibrium strategies

	Sealed-bid format	Open format	Structural property of equilibrium strategies
			and efficiency 2
	Discriminatory	Ascending clock	Scope for flat supply and for supply inflation
			Inefficient allocation
	Uniform-Price	Descending clock	Supply "inflation" a : increasing marginal bias with
			quantity supplied b . Inefficient allocation
			Coordination at a high price equilibrium
	Generalized Vickrey	Descending clock with	Truthful bidding is a dominant strategy
		clinched purchase	Efficient allocation
		(Ausubel, 1997)

a Equivalent to demand reduction (or bid shading) in a selling auction b It is a weakly dominant strategy to bid one's true value on the first unit then to start overbidding at an increasing rate.

Table 2 :

 2 Composition of water seller population

	Sellers (Bidders)	Maximum capacity (ms)	True intercept parameter (a 0 ) (true entry price)	True slope parameter(b 0 )	Max price
	Seller 1	0.25	0.25	0.25	0.3125
	Seller 2	0.75	0.25	0.25	0,4375
	Seller 3	0.25	0.25	0.75	0,4375
	Seller 4	0.75	0.25	0.75	0,8125
	Seller 5	0.25	0.75	0.25	0,8125
	Seller 6	0.75	0.75	0.25	0,9375
	Seller 7	0.25	0.75	0.75	0,9375
	Seller 8	0.75	0.75	0.75	1,3125

Table 3a :

 3a Average Euclidian distance of learnt intercept and slope parameter pair from true parameter values when demand is 2 (50% of capacity).

	Sellers	Generalized Vickrey	Discriminatory auction	Uniform auction
	Seller 1	0.83	0.98	1.07
	Seller 2	0.47	0.84	0.62
	Seller 3	0.83	1.35	0.82
	Seller 4	0.42	0.81	0.66
	Seller 5	0.65	1.51	0.62
	Seller 6	0.27	0.73	0.93
	Seller 7	0.92	1.67	0.88
	Seller 8	0.74	1.43	0.97
	Average	0.64	1.17	0.82

Table 3b :

 3b Average Euclidian distance of learnt intercept parameter from true intercept value when demand is 2

	Sellers	Vickrey auction	Discriminatory auction	Uniform auction
	Seller 1	0.11	0.46	0.19
	Seller 2	0.10	0.42	0.17
	Seller 3	0.10	0.46	0.18
	Seller 4	0.11	0.49	0.16
	Seller 5	0.03	0.27	0.06
	Seller 6	0.03	0.31	0.04
	Seller 7	0.02	0.26	0.04
	Seller 8	0.04	0.04	0.04
	Average	0.07	0.34	0.11

Table 3c :

 3c Average of learnt slope parameter from true slope value when demand is 2

	Sellers	Vickrey auction	Discriminatory auction	Uniform auction
	Seller 1	3.51	2.02	4.34
	Seller 2	0.50	0.50	0.65
	Seller 3	3.20	3.48	2.66
	Seller 4	0.39	0.28	0.70
	Seller 5	3.00	6.20	2.84
	Seller 6	0.40	0.38	1.78
	Seller 7	4.17	5.89	3.68
	Seller 8	1.20	2.40	1.54
	Average	2.05	2.64	2.27

Table 3d :

 3d Average quantities supplied by bidders as % of their own capacity when demand is 2 .

	Sellers	Vickrey auction	Discriminatory auction	Uniform auction
	Seller 1	76	88	72
	Seller 2	73.3	84	70.7
	Seller 3	76	80	80
	Seller 4	69.3	62.7	61.3
	Seller 5	60	28	68
	Seller 6	32	24	29.3
	Seller 7	36	28	52
	Seller 8	9.3	26.7	13.3
	Average	54	52.7	55.8

Table 4 :

 4 Learnt versus true supply parameters when demand is 2 (50% of capacity).

		Vickrey auction	Discriminatory auction	Uniform auction
	Sellers	Ratio of learnt to true entry price (a/a 0 )	Ratio of learnt to true supply slope b/b 0	Ratio of learnt to true entry price (a/a 0 )	Ratio of learnt to true supply slope b/b 0	Ratio of learnt to true entry price (a/a 0 )	Ratio of learnt to true supply slope B/b 0
	Seller 1	1.54	4.14	3.49	2.71	1.92	4.05
	Seller 2	1.65	2.05	3.48	1.56	2.03	2.34
	Seller 3	1.57	1.94	3.47	1.56	1.95	1.83
	Seller 4	1.58	1.32	3.52	1.00	1.86	1.50
	Seller 5	1.11	3.30	1.63	4.35	1.14	3.39
	Seller 6	1.12	2.07	1.67	1.07	1.14	4.67
	Seller 7	1.11	1.99	1.62	1.65	1.12	2.24
	Seller 8	1.10	1.94	1.11	2.88	1.11	2.28
	Average	1.35	2.34	2.50	2.10	1.53	2.79
	Expected 1	=1	=1	>1	?	=1	>1
	1 see Table 3.

Table 5 : Learnt versus true supply parameters when demand is 3 (75% of capacity).

 5

		Vickrey auction	Discriminatory auction	Uniform auction
	Sellers	Ratio of learnt to	Ratio of learnt to	Ratio of learnt to	Ratio of learnt to	Ratio of learnt to	Ratio of learnt to
		true entry	true supply	true entry	true supply	true entry	true supply
		price	slope	price	slope	price	slope
	Seller 1	2.80	5.28	5.69	3.09	2.88	6.10
	Seller 2	3.05	2.09	5.85	1.49	3.11	2.43
	Seller 3	2.66	2.50	5.71	1.46	2.87	2.65
	Seller 4	2.63	1.26	5.79	0.67	2.92	1.33
	Seller 5	1.37	3.50	2.24	1.20	1.47	3.93
	Seller 6	1.43	1.98	2.30	0.65	1.54	2.56
	Seller 7	1.33	1.67	2.24	0.67	1.42	1.72
	Seller 8	1.23	1.67	2.28	0.57	1.31	2.04
	Average	2.06	2.49	4.01	1.22	2.19	2.85
	Expected 1	=1	=1	>1	?	=1	>1

Efficiency here refers to the social opportunity cost of reallocated resources or water. An efficient reallocation is obtained when water is obtained from sources with the least opportunity cost for water.

All demonstrations are made for a model where bidders' values are private and independently distributed, and ex-ante symmetric (the distribution of information is uniform across bidders in the pre-auction situation). Since we only consider a private values environment, any equilibrium in the sealed bid format is outcome equivalent to an equilibrium of the corresponding open auction

The initial propensity for any given strategy is set as the product of the scale parameter and an expected profit from bidding. In our case, the latter is set at 10% of the cost of supplying an amount equal to the maximum capacity.


Dmitry Kucharavy
email: dmitry.kucharavy@insa-strasbourg.fr

Roland De Guio

Application of S-Shaped Curves

Keywords: Laws of Technical systems evolution, Resource limitations, Technology Future Analysis, S-shaped curve, S-curve

come

INTRODUCTION

The regularity of systems' evolution as an initial slow change, followed by a rapid change and then ending in a slow change again are observed since statistical observation was established in the mid 18 th century. Various scientists and researchers discovered, reinvented, and adapted the curves of nonlinear growth many times for different domains of knowledge. Therefore, S-shaped curves possess a lot of different names: Logistic curve, Verhulst-Pearl equation, Pearl curve, Richard's curve (Generalized Logistic), Growth curve, Gompertz curve, S-curve, S-shaped pattern, Saturation curve, Sigmoid(al) curve, Foster's curve, Bass model, and many others. Researches all around the world apply S-shaped curves for projecting the performance of technologies, to foresee population changes, for market penetration analyses, for micro-and macro-economic studies, for diffusion mechanisms of technological and social inventions, for ecological modelling, and for many other purposes. What explains such a generic and universal application of logistic S-curves?

HISTORY OF THE S-SHAPED CURVE

Origin of the logistic curve and its basic concept

The logistic function as a model of population growth was first introduced by Belgian mathematician Pierre-Francois Verhulst (1804-1849) in 1838 [START_REF] Weisstein | Logistic Equation[END_REF]. Verhulst derived his logistic equation after he had read 'An essay on the Principle of Population' of English demographer and political economist Thomas Malthus (1766-1834). The logistic equation was introduced to describe the selflimiting growth of a population. This equation sometimes called the Verhulst-Pearl equation according to its rediscovery in 1920 by American zoologist and one of the founders of biometry Raymond Pearl . Early in the 20th century, Alfred James Lotka from John Hopkins University, US and Vito Volterra from the University of Rome, Italy working independently but in parallel, generalized Verhulst's growth equation to model competition among different species. The Volterra-Lotka model, also known as the predator-prey equations, has opened the way to effectively managing competition in biology, ecology and technology domains. Today this model is frequently employed to describe the dynamics of systems [START_REF] Modis | A Scientific Approach to Managing Competition[END_REF].

Different types of competition can be distinguished [START_REF] Modis | A Scientific Approach to Managing Competition[END_REF][START_REF] Modis | Predictions -10 Years Later[END_REF]: • competition of one species for resources; • two competitors: pure competition (loss-loss), predator-prey (win-loss), symbiosis (win-win), parasitic (win-impervious), symbiotic (loss-indifferent), and no competition;

• many competitors at the same time. For example, a population of bacteria grows in a closed bowl of broth. The rate of chemicals in the broth to bacteria transformation is proportional to the number of bacteria present and the concentration of transformable chemicals. Thus, Verhulst's equation for this particular case can be written as:

M N M aN dt dN ) ( - = (1)
Where, N(t) -number of bacteria at time t; M -amount of transformable chemicals at t=0 (before growth starts); aparameter that represents the interaction between the competitors. Solution of equation (1) as a logistic function:

) ( 1 ) ( b at e M t N + - + = (2)
Where, b -is a constant, locating the process in time [START_REF] Modis | Predictions -10 Years Later[END_REF]. The law of natural growth over a period of time can be described through periods of birth, growth, maturity, decline and death for any system. This set of periods is often called the life cycle of system. A bell-shaped curve is usually applied as a template to represent the rate of growth within a time span (see Figure 1). Whereas cumulative growth (cumulative number of "units" until any given points in time) follows an S-curve. Thus the S-curve became a visual symbol of cumulative growth. The simplest mathematical function that produces an S-curve is called a logistic. The essential meaning of this function is 'the rate of growth is proportional to both the amount of growth already accomplished and the amount of growth remaining to be accomplished.' Understanding of that concept helps to catch part of the answer to the question: "Why does the S-curve approach possess forecasting powers?"

We believe the forecasting power of the S-curve is due to the basic concept of limiting resources that lies at the basis of any growth process. In diverse areas, limiting resources are named in different ways: scarcest resources (geochemistry), restricted resources (economy), limitation of resources (TRIZ 1 ), resource constraint (theory of constraints) etc. In most cases, applying an S-curve for forecasting induces the correct measurement of the growth process that in turn can be applied to identify the law of natural growth quantitatively and to reveal the value of the ceiling (upper limits of growth) and steepness of the growth (slope of curve). Obviously, the more precise the data and the bigger the section of the S-curve they cover leads to a lower level of uncertainties [START_REF] Debecker | Determination of the uncertainties in S-curve logistic fits Technological Forecasting and Social Change[END_REF]. In other words, one can identify a more accurate ceiling and steepness with a larger data set. This effect causes some difficulties in applying an S-curve forecast for emerging technologies, which have not yet passed the "infant mortality" threshold (when the ratio of new to old technology has not reached 0.1).

Rate of growth

Application of S-shaped curves

The law of natural growth was derived from research in Economics. The Malthusian growth model is the ancestor of the logistic function of Pierre Verhulst. Benjamin Gompertz in 1825 published work developing the Malthusian growth model further for demographic study (law of mortality). Since those times, S-shaped curves have been applied for studies in population dynamics and economic analyses. In the early 1960s, S-shaped curves and envelop curves were regularly employed for technological forecasting [START_REF] Ayres | Technological Forecasting and Long-Range Planning[END_REF]. The application of the logistic curve in combination with envelop curves for forecasting by extrapolation of trends issued many fascinating results for lightning systems, 1 Theory of inventive problem solving particle accelerators, aircrafts, microelectronics, transportation systems, energy conversion technologies. For instance, the diffusion of innovation theory, formalized by Everett M. Rodgers [START_REF] Rogers | Diffusion of Innovations[END_REF] in 1962 postulated that innovations would spread in society in an S-curve. The law of natural growth seems as simple as it is fundamental. Biologists have applied it to describe the growth of a species under competition. It has been used in medicine to describe the diffusion of epidemic diseases. Market studies of new products, usually based on the law of natural growth in a specific niche, use an S-curve analysis. Fisher J.C. and Pry R.H. in 1971 [START_REF] Fisher | A simple substitution model of technological change[END_REF] have shown that data describing the substitution of a new product or process for an old one can be fitted extremely well by a simple mathematical logistic function that produces an S-curve. There are plenty examples of applying S-curves for studying the future of complex systems. It is simply not within the scope of this paper to count even the major ones.

For instance, at the International Institute for Applied Systems Analysis (IIASA and for many others. The International Journal of Technological Forecasting and Social Change3 published more than 320 articles from May 2002 to May 2007. About 14 articles considered in particular the application of the logistic S-curve of natural growth for forecasting purposes. More than 170 articles within this period mentioned S-curves on their pages. In usual forecasting and strategic planning practice Sshaped curves enter as modular components in many methods and techniques. Table 1 summarizes the observed application of S-curves as a part of various forecasting methods. A study of the application of S-curves, summarized in Table 1, shows that they are most often applied for analysing past data in order to disclose new trends and for proving known ones. From a practical viewpoint, according to the results of various research, the processes of diffusion of novelties, substitution of systems, and competitive growth obey the same law of natural growth. Thanks to its fractal aspects [START_REF] Modis | Fractal aspects of natural growth Technological Forecasting and Social Change[END_REF] the law of natural growth can be applied for almost any scale and complexity of systems from elementary particles up to the evolution of stars and knowledge acquisition.

Method name:

Nature & Application:

Trend Impact Analysis [START_REF]Futures Research Methodology[END_REF] Quantitative. For extrapolation of previously collected data Curve fitting technique [START_REF]Futures Research Methodology[END_REF] Qualitative and quantitative. Qualitative and quantitative. For trend extrapolation.

Text Mining for Technology Forecast [17, pp.194-197] Quantitative.

For analysis of annual publications, to prove informative trends.

Life Cycle Analysis in the framework of strategic analysis

Qualitative.

To identify the stage of a system's evolution.

Theory of Innovation Diffusion [8]

Qualitative and quantitative.

For studying the technology adaptation dynamic.

Emerging issues analysis [START_REF] Molitor | Forecasting Model: Key Dimensions for Plotting the "Patterns of Change[END_REF] Quantitative.

For identifying the issues before they reach the trend of problem phase for engineering and nonengineering fields.

Table 1. Applications of S-shaped curves in the framework of other methods

S-CURVE IN THE FRAMEWORK OF TRIZ

In the scope of TRIZ research, in the mid 1970s it was proposed to employ the S-curve model for the qualitative study of technical systems evolution [START_REF] Altshuller | Creativity as an Exact Science[END_REF][START_REF] Altshuller | About forecasting of technical systems development[END_REF]. In order to facilitate the positioning of the analysed system onto a logistic curve G.Altshuller proposed the application of three supplementary statistical curves: changes of number of inventions, changes of level of inventions, and changes of profitability during time. It was proposed also to apply a concept of three levels of resource limitations during the life cycle of technical systems (Figure 2):

• first level -limitation of working principle (limits of system's resources), • second level -limitation of economic rationality (limits of available resources from the environment), and • third level -physical limits of resources in supersystem (e.g. limitations of fossil resources, limitations of available space, limitations of renewable resources -clean water). In the scope of research into technological forecasting, we are looking for a method for the application of the concept of assessing multi-level resource limitations in order to improve the reliability of the forecast for emerging technologies that do not have enough history of their evolution (lack of data and knowledge). It is necessary to notice that a similar concept of scarce resources was described as a Law of the Minimum by German geochemist Justus von Liebig (1803-1873) in 1840. The Law of the Minimum states 'that growth is controlled not by the total resources available, but by the scarcest resource'. For chemistry, such a concept is known as the rate determining step, in management techniques as the critical path. Derivatives from the law of the minimum can be found in many areas of knowledge from economics, environmental, social and technological sciences. ones following the law of Ideality growth. Why does system 3 conquer system 2? In competition if system 3 shows a better ratio of Performance to Expense it has more chances to survive. Expense is our limiting resource. And this is exactly the meaning of the law of increasing Ideality: 'during their evolution the technical systems tend to improve the ratio between system performance and the expense required for this performance.' The trickiest question is how to calculate Ideality in practice for particular systems [START_REF] Petrov | Progress and Ideality[END_REF]. After analysis of the available sources of knowledge, we did not find any feasible ideas and procedures for computing Ideality (often called the 'Main index of the system'). It is not surprising that the founder of TRIZ first proposed to apply an S-curve analysis for qualitative analysis. Therefore, vertical scales in most TRIZ publications are purely qualitative or apply some arbitrary units. Before presenting some data about TRIZ publications, it is necessary to clarify the different viewpoints on what is a 'forecast'. If someone tells us, "it will rain". Will it be a forecast, a prediction or just a vision of the future? Usually we are interested to know when and where "it will rain." It is important to know how intensive it will be and how the temperature will change afterwards. Frequently observed TRIZ-forecasts resemble "it will rain." For instance, the following assertion: motor vessels will be substituted by water-jet vessels. Yes, they will! However, it is interesting to know when?, were? and for which application? In order to avoid misunderstandings, we would like to present our working definition of the term 'forecast'. We define a technology forecast in the framework of our research as "an explicit description of emergence, performance, features, and impacts of a technology in a particular place at a particular point of time in the future for a definite application." If some of the components of the above definition are omitted, such a description should be considered as a vision of the future rather than as a forecast. Visions of the future merit consideration and study, however, they have another area of application and should not be confused with forecasts. In order to summarise the application of S-curves in the TRIZ community we made an express survey of publications at conferences within the time span 1999-2006 (ETRIA 4 TFC 2001-2006, and TRIZCON 5 ) and publications on the website triz-journal.com 1997-2006 6 . The same articles from different sources where taken into account just once. Unfortunately, we had no opportunity to consider publications from MATRIZ conferences and many other publications in Russian, German, French, Spanish, Japanese, Korean, Chinese, Polish, Czech and others languages. Excerpts from the results of our survey are presented in Tables 2 and3. In total, 137 papers mention S-curve applicability over the reviewed period. Most of them consider pure qualitative analysis of arbitrary parameters. Some of them do not consider any parameters on the vertical scale at all. The authors of only 14 papers during nine years tried to combine qualitative analysis with a quantitative one. Eight papers out of 14 are case studies, concerned with identifying a phase stage of the analysed system or evolutionary trends for a particular technology. The remaining five papers discuss the applicability of S-curve analysis using arbitrary units with some ideas about measurable parameters. Different applications of the S-curve concept in TRIZ publications are presented below (Table 3, Figure 4). Dozens of various applications are grouped into five groups. 4 Annual TRIZ Future Conference of European TRIZ Association, Europe [http://www.etria.net ]. 5 In papers from the first group authors just refer to an Scurve and apply common knowledge (mostly taken from [START_REF] Altshuller | Creativity as an Exact Science[END_REF]) in order to illustrate proposed findings, speculations and particularities. The S-curve concept is applied mainly for educational purposes, in order to illustrate the stages of system evolution, for the illustration of laws of technical systems evolution, to provide information about natural growth. In other words, in order to master the future of technical and non-engineering (business, educational, environmental) systems.

The second group of papers include publications dedicated to the analysis of particular system evolution using an S-curve. They describe the practical experiment of employing quantitative data analysis in order to identify the evolutionary stage of certain technologies.

Unfortunately, such papers are not so numerous even if they attract the attention of many readers. The level of "quantitativeness" in papers varies from data analysis using fitting techniques to quasi-quantitative studies.

Papers from the third group discuss how to define the direction of problem solving activities using an S-curve and systematic technology assessment. Some papers from this group present proposals about the integration of S-curve analysis in several toolboxes for designing new products.

Papers from the fourth group are focused on the forecasting and strategic planning contexts. They propose some rules and recommendations about analysis of systems evolution, history of the system and trend studies using S-curve analysis. The papers discuss the application of the S-curve for engineering and nontechnical systems as well as short-term and long-term perspectives with cascading S-curves. Several papers from this group propose some recommendations for effective evaluation of patents. 3). In the fifth group, several papers that do not fit any group are collected. They represent some authors' speculations, early-ripe hypotheses, and ideas about combining the Scurve concept with other theories and approaches for uncommon needs.

ENVELOPE CURVE EXTRAPOLATION

There is an easy concept behind extrapolation techniques: let past experience be a guide for future expectations. One can distinguish several ways to apply the envelope curve extrapolation in combination with the logistic S-curve of natural growth. One of the better known methods can be named "shift to the super-systems". The main idea is to plot several growth curves for alternative technologies using the same key parameter and to fit the envelop curve for the constructed curves (e.g. see Figure 4.2). The application of envelope curves for long-term technological forecasting started to be popular at the end of the 1950s. This technique is still in use to develop longterm visions. However, today for strategic planning it is more important to foresee technology substitution time and conditions. That is why envelop curve technique results can be found in books, but not in articles and conference papers. There are many pitfalls and particularities of the process for designing the envelop curve extrapolation of this first type. It is commonplace to discuss whether the trend will not continue as before or if it will continue. In fact, this question can be dealt with by means of system dynamic [START_REF] Braun | The System Archetypes[END_REF]. In order to emphasise another pitfall and repeat once again the importance of careful selection the parameters for the vertical scale, Figures 4.1 and 4.2 present two diagrams. These two graphs are taken from the book [START_REF] Ayres | Technological Forecasting and Long-Range Planning[END_REF] to which G.Altshuller referred [START_REF] Altshuller | About forecasting of technical systems development[END_REF] when discussing the applicability of S-curve analysis for inventive problem solving and qualitative technology forecasting. The same parameter was plotted in both graphs. The one in Fig 4 .1 is misleading. because an inappropriate scale is used. Speed of matter, according to the laws of physics cannot exceed 299 792 458 metres per second. The analysis of such examples leads to multiple questions. For instance, how can we be sure about the appropriateness of the chosen scale beforehand? What is a relevant parameter to elaborate an enveloped S-curve for long-term forecasting? For example, should it be the speed of the transportation system or should it be a time to move the load or person from one location to another one? It should be noted, today in Europe high speed trains rise in popularity, because they connect city-centres and the final trip takes less time. Another way to apply the enveloped curve extrapolation can be named "shift to the sub-systems." Several interesting illustrations were presented in paper [START_REF] Modis | Fractal aspects of natural growth Technological Forecasting and Social Change[END_REF] of T.Modis in 1994. By applying qualitative and quantitative analyses of the computer market the author put forward a fractal aspect of natural growth depicted by an S-curve. One of the conclusions that were proved later suggests that "any growth process can be analysed in terms of natural growth sub-processes." It is noticeable how one picture can replace a lot of text explanations. For instance, the link between the slope of the envelop curve and the rhythm of technology substitutions (depicted by sub-S-curves) can be learned from Figure 5 distinctly. Another interesting derivative result from Figure 5 is the hint about shortening life-cycles of technologies (sub-S-curves) when the envelop curve flattens (in the beginning and at the end of natural growth). Due to the limitations of a conference paper, it is impossible to present here all the richness of the application of envelop curves. Here only two of many ways are presented.

SOME FEEDBACK FROM PRACTICE

The target of our research is to improve the process of forecasting for emerging technologies and the quality of the forecasts produced. We next apply the following basic assumptions:

• limitations of resources drive evolution of any technology; • thus, the technology's future can be mapped using knowledge about scarce resources; • application of the law of natural growth with a logistic S-curve, performed in a computable way, can contribute essentially to the accuracy of the long-term forecast. In order to check the above assumptions and hypotheses about reliable forecasting using OTSM-TRIZ 7 knowledge 7 At the end of the 1970s the founder of TRIZ G.Altshuller anticipated the further evolution of TRIZ towards a General Theory of Powerful Thinking, which will be useful two forecasting projects were performed during September 2003 -December 2006 in collaboration with the European Institute for Energy Research (EIFER), Karlsruhe, Germany. Some theoretical and practical results of these projects are described in reports and conference papers [START_REF] Kucharavy | Problems of Forecast[END_REF][START_REF] Kucharavy | Problem Mapping for the Assessment of Technological Barriers in the Framework of Innovative Design[END_REF][START_REF] Gautier | Technological forecasting of Fuel Cells for small stationary applications[END_REF]. In the framework of this paper, we would like only to emphasise the question of measurable parameters for the vertical scale of the S-curve of system evolution. This question is a corner stone of the application of logistic Scurves for medium-and long-term forecasts as we perceive from theoretical and practical studies. According to the law of Ideality increase [START_REF] Altshuller | Creativity as an Exact Science[END_REF], Ideality is defined as a ratio between the system Performances and the Expenses required for these performances.

∑ ∑ = E P I (3)
Where, P -is system performance including all positive results within the life-cycle of the system; E -is the needed expenses of resources including all harmful and undesirable effects within the life-cycle of the system. The practical application of the Ideality concept [START_REF] Gautier | Technological forecasting of Fuel Cells for small stationary applications[END_REF] shows us the necessity of taking into account not only the technical aspects of Ideality (Pt, Et) for analysed systems (see Equation 3), but also Economic, Social and for dealing with non-engineering problems and complex cross disciplinary problems as well. At the beginning of the 1980s G.Altshuller initiated research to develop this theory. OTSM is the Russian acronym usually applied to indicate the General Theory of Powerful Thinking. For details see paper of N.Khomenko et al. [START_REF] Khomenko | A Framework for OTSM-TRIZ Based Computer Support to be used in Complex Problem Management[END_REF].

Environmental factors. Hence, in order to calculate Ideality in practice it is necessary to measure somehow Economic performance and expenses (Pe, Ee), Social performance and expenses (Ps, Es), and Environmental parameters (Pen, Een). Therefore, an instant Ideality can be described as:

) , , , ( Ien Is Ie It f I = (4)
Where, It (technical Ideality) equals the ratio of ΣPt/ΣEt; Ie -is economic Ideality (ΣPe/ΣEe); Is -is social Ideality (ΣPs/ΣEs); Ien -is environmental Ideality (ΣPen/ΣEen). For the purpose of system evolution forecasting it is necessary to consider changes of Ideality over time (within the forecasted timeframe at least). Consequently, changes of Ideality over a time can be described as: Currently, we are working on a practical way to solve this equation or bypass it. There are some practical approaches for measuring the instant technological Ideality. However, it is an open question: "How to quantify Idealities from other contexts using compatible units?" Analysis of technology forecasting practice gives the evidence that it is only the technological context which is not sufficient for reliable forecasting of system evolution. The future state of certain technologies depends on the nearest super-systems (contexts) transformations and intrinsic interactions between super-systems, systems and sub-systems. This processes demands more knowledge which we can get from data about the technical feasibility of emerging technologies and from known technology barriers. In order to handle situations with economic, social and environmental issues a 'proverbial wisdom' is to perform a series of interviews with experts (e.g. kind of Delphi surveys). As we can sum up after the literature reviews, such practice produces qualitative results with many hidden biases [START_REF] Schnaars | Megamistakes: Forecasting and the Myth of Rapid Technological Change[END_REF][START_REF] Schnaars | Five Modern Lessons from 55-Year-Old Technological Forecast[END_REF][START_REF]Principles of Forecasting: A Handbook for Researchers and Practitioner[END_REF]. * * * In the practice of forecasting emerging technologies, there is an inevitable question to be answered: How to forecast the future of emerging technologies using an S-curve and the law of natural growth before systems pass the 'infant mortality' threshold (Figure 2, α point)?

The working hypothesis we are testing actually proposes to measure the process of natural growth of knowledge to predict the future of emerging technologies. Before overcoming the 'infant mortality' threshold and arriving at the exploitation phase of the life-cycle, a new technology passes through exploration and experimentation stages. Each phase has its learning curve of knowledge growth (see Figure 6). Learning curves represent knowledge acquisition in a percentage of solved problems. Problems can be mapped [START_REF] Kucharavy | Problem Mapping for the Assessment of Technological Barriers in the Framework of Innovative Design[END_REF] for emerging technologies using techniques and methods from OTSM-TRIZ [START_REF] Khomenko | A Framework for OTSM-TRIZ Based Computer Support to be used in Complex Problem Management[END_REF]. There are still several questions to be answered and tested through the practice of forecasting. An important one, among others, is How to measure knowledge, obtained within exploration and experimentation phases? How can one calculate the time necessary for decisions about the transition to the next phase (e.g. experimentation)?

SUMMARY

The application of the law of natural growth has imperishable value for the understanding of the transformations of complex systems. Evolution of any kind of system can be represented as successive S-curves of technologies. One can find logistic curves inside S-curves due to the fact that the logistic curves represent fractal aspects. One can also find chaos by getting the logistic equation discrete, especially within technology substitution phases. The logistic S-curve of natural growth is a basic model of the Volterra-Lotka equations, which are reliable for describing and forecasting different forms of competition and technology substitutions. Applied in a discrete form with careful definition of competing 'species', logistic equations would give a picture, where growth in competition, self-organization, complex adaptive behaviour, interactions in fractals can be shown. One of the strongest points of S-curve application is that it is based on nature. It represents a natural law of growth by using simple logistic equations. Thus, quantitative analysis of system transformation contributes essentially to the reliability of forecasting. The weak point of S-curve application is linked to the necessity of applying data about the past of system transformations in order to fill the logistic equation with meaning. The results of studies [START_REF] Modis | Predictions -10 Years Later[END_REF] showed that "the more precise the data and the bigger the section of the S-curve they cover, the more accurately the parameters can be recovered." In other words, when a system is closer to the end of its evolution, it lessens the level of uncertainties and increases the accuracy of the forecast with the Scurve. There is a question: 'When can we use an S-curve?' In other words, 'When should we address cumulative growth?' S-curves and logistic equations depict natural growth in competition. When the analysed process can not be measured as growth (or decline) in competition a simple qualitative application of an S-curve usually produces some misleading results and conclusions. According to our experience and as reported in the results of various literature, it is not trivial to identify appropriate measurement parameters for the vertical scale of the Scurve for medium-and long-term forecasting. Nevertheless, it is unavoidable for getting a forecast, and not only a vague moot vision. The obtained forecast can be dramatically different, depending on the selected parameter for measuring the evolution of the system.

"The ultimate test of the forecaster is an accurate and reliable forecast not the elegant or easily applied method."

Figure 1 .

 1 Figure1. Life cycle bell-shaped curve and S-curve of cumulative growth. In most cases, applying an S-curve for forecasting induces the correct measurement of the growth process that in turn can be applied to identify the law of natural growth quantitatively and to reveal the value of the ceiling (upper limits of growth) and steepness of the growth (slope of curve). Obviously, the more precise the data and the bigger the section of the S-curve they cover leads to a lower level of uncertainties[START_REF] Debecker | Determination of the uncertainties in S-curve logistic fits Technological Forecasting and Social Change[END_REF]. In other words, one can identify a more accurate ceiling and steepness with a larger data set. This effect causes some difficulties in applying an S-curve forecast for emerging technologies, which have not yet passed the "infant mortality" threshold (when the ratio of new to old technology has not reached 0.1).

Figure 2 .Figure 3 .

 23 Figure 2. Styled S-curve of technical systems evolutionand limits of resources The law of natural growth and the S-curve play a key role in the set of height laws of technical systems evolution, postulated in TRIZ. The law of increasing Ideality of technical systems is in fact the derivation of the enveloped curve of successive substitutions of technical systems (see Figure3).

Figure 4 .

 4 Figure 4. Application of S-curve in TRIZ publications (based on data from Table3). In the fifth group, several papers that do not fit any group are collected. They represent some authors' speculations, early-ripe hypotheses, and ideas about combining the Scurve concept with other theories and approaches for uncommon needs.

Figure 4 . 1 .

 41 Figure 4.1. Speed trend curve plotted in 1961. Source [7].

Figure 4 . 2 .

 42 Figure 4.2. Speed trend. Source [7].

Figure 5 .

 5 Figure 5. Styled Envelop curve. An envelop logistic pattern is decomposed into constituent logistics. The horizontal axis represents time (Source [10]).

Figure 6 .

 6 Figure 6. Knowledge acquisition for emerging technology. One can find logistic curves inside S-curves due to the fact that the logistic curves represent fractal aspects. One can also find chaos by getting the logistic equation discrete, especially within technology substitution phases. The logistic S-curve of natural growth is a basic model of the Volterra-Lotka equations, which are reliable for describing and forecasting different forms of competition and technology substitutions. Applied in a discrete form with careful definition of competing 'species', logistic equations would give a picture, where growth in competition, self-organization, complex adaptive behaviour, interactions in fractals can be shown. One of the strongest points of S-curve application is that it is based on nature. It represents a natural law of growth by using simple logistic equations. Thus, quantitative analysis of system transformation contributes essentially to the reliability of forecasting. The weak point of S-curve application is linked to the necessity of applying data about the past of system transformations in order to fill the logistic equation with meaning. The results of studies[START_REF] Modis | Predictions -10 Years Later[END_REF] showed that "the more precise the data and the bigger the section of the S-curve they cover, the more accurately the parameters can be recovered." In other words, when a system is closer to the end of its evolution, it lessens the level of uncertainties and increases the accuracy of the forecast with the Scurve. There is a question: 'When can we use an S-curve?' In other words, 'When should we address cumulative growth?' S-curves and logistic equations depict natural growth in competition. When the analysed process can not be measured as growth (or decline) in competition a simple qualitative application of an S-curve usually produces some misleading results and conclusions. According to our experience and as reported in the results of various literature, it is not trivial to identify appropriate measurement parameters for the vertical scale of the Scurve for medium-and long-term forecasting. Nevertheless, it is unavoidable for getting a forecast, and not only a vague moot vision. The obtained forecast can be dramatically different, depending on the selected parameter for measuring the evolution of the system.

Table 2 .

 2 Annual Altshuller Institute for TRIZ Studies International Conference, USA [ http://www.aitriz.org ]. Ratio of papers mentioning an S-curve in total publications.

	Year	Source	S-curve is mentioned
		1997	triz-journal			13%
		1998	triz-journal			3%
			TRIZCON		15%
			triz-journal		13%
		1999				14%
			TRIZCON		16%
			triz-journal		11%
		2000				12%
			TRIZCON		19%
			ETRIA TFC		13%
			triz-journal		5%
		2001				11%
			TRIZCON		15%
			ETRIA TFC		12%
			triz-journal		12%
		2002				12%
			TRIZCON		27%
			ETRIA TFC		6%
			triz-journal		7%
		2003				10%
			TRIZCON		11%
			ETRIA TFC		14%
			triz-journal		8%
		2004				10%
			TRIZCON		8%
			ETRIA TFC		16%
			triz-journal		7%
		2005				10%
			TRIZCON		12%
			ETRIA TFC		7%
			triz-journal		8%
		2006				8%
	#	Application of S-curve	11/1996 12/1999	01/2000 12/2002	01/2003 12/2006
	1 Just mentioned	11	29	43
	2	Case studies using S-curve	3	3	5
		Maturity of
		technology
	3	assessment in context of	3	6	8
		problem
		solving
		Analysis of
		systems
	4	evolution in	4	8	8
		context of
		forecasting
	5	Non-grouped hypothesis	0	3	3

6

The TRIZ Journal Article Archive [ http://www.trizjournal.com ].

Table 3

 3

. Number of papers in TRIZ publications grouped according to application of S-curve concept.

IIASA is a nongovernmental, multidisciplinary, international research institution; it was founded in October 1972 by academies of science of 12 nations from East and West. The institute now has 18 National full Member Organizations [http://www.iiasa.ac.at/].

ISSN: 0040-1625 "A major forum for those wishing to deal directly with the methodology and practice of technological forecasting and future studies as planning tools as they interrelate social, environmental and technological factors."

ACKNOWLEDGMENTS

We wish to acknowledge the European Institute for Energy Research (EIFER), Karlsruhe for support of the research on Technology forecasting. We also would like to thank our colleagues from the LICIA team of LGECO, INSA Strasbourg for constructive discussions that helped to clarify many points presented in this paper.