Member, IEEE Catherine Douillard

Member, IEEE Claude Berrou

Turbo Codes With Rate-m=(m + 1) Constituent Convolutional Codes

Keywords: Iterative decoding, permutation, rate-( + 1) recursive systematic convolutional

The original turbo codes (TCs), presented in 1993 by Berrou et al., consist of the parallel concatenation of two rate-1/2 binary recursive systematic convolutional (RSC) codes. This paper explains how replacing rate-1/2 binary component codes by rate-( + 1) binary RSC codes can lead to better global performance. The encoding scheme can be designed so that decoding can be achieved closer to the theoretical limit, while showing better performance in the region of low error rates. These results are illustrated with some examples based on double-binary ( = 2) 8-state and 16-state TCs, easily adaptable to a large range of data block sizes and coding rates. The double-binary 8-state code has already been adopted in several telecommunication standards.

I. INTRODUCTION

A CLASSICAL turbo code (TC) [1] is a parallel concate- nation of two binary recursive systematic convolutional (RSC) codes based on single-input linear feedback shift registers (LFSRs).

The use of multiple-input LFSRs, which allows several information bits to be encoded or decoded at the same time, offers several advantages compared with classical TCs. In the past, the parallel concatenation of multiple-input LFSRs had mainly been investigated for the construction of turbo trellis-coded modulation schemes [START_REF] Robertson | Bandwidth-efficient turbo trellis-coded modulation using punctured component codes[END_REF]- [START_REF] Fragouli | Turbo-encoder design for symbol-interleaved parallel concatenated trellis-coded modulation[END_REF], based on Ungerboeck trellis codes. Actually, the combination of such codes, providing high natural coding rates with high-order modulations, leads to very powerful coded modulation schemes.

In this paper, we propose the construction of a family of TCs calling for RSC constituent codes based on -input LFSRs, that outperforms classical TCs. We provide two examples of TCs with reasonable decoding complexity that allow decoding to be achieved very close to the theoretical limit, and at the same time, show good performance in the region of low error rates.

Paper approved by R. D. Wesel, the Editor for Coding and Communication Theory of the IEEE Communications Society. Manuscript received May 1, 2003; revised August 6, 2004.

The authors are with the Electronics Department, GET/École Nationale Supérieure des Télécommunications de Bretagne, CS 83818 -29238 Brest Cedex 3, France (e-mail: catherine.douillard@enst-bretagne.fr; claude.berrou@enst-bretagne.fr).

Digital Object Identifier 10.1109/TCOMM.2005.857165

Section II describes the structure adopted for -input RSC component encoders, along with some conditions that guarantee large free distances, regardless of the value of .

In Section III, we describe the turbo-encoding scheme, and the advantages of this construction compared with classical TCs.

Section IV presents some practical examples of TCs with and their simulated performance. The 8-state family has already been adopted in the digital video broadcasting (DVB) standards for return channel via satellite (DVB-RCS) [START_REF]Interaction Channel for Satellite Distribution Systems[END_REF] and the terrestrial distribution system (DVB-RCT) [START_REF]Interaction Channel for Digital Terrestrial Television[END_REF], and also in the 802.16a standard for local and metropolitan area networks [START_REF]IEEE Standard for Local and Metropolitan Area Networks[END_REF]. Combined with the powerful technique of circular trellises, this TC offers good performance and versatility for encoding blocks with various sizes and rates, while keeping reasonable decoding complexity. Replacing the 8-state component encoder by a 16-state encoder allows better performance at low error rates, at the price of a doubled decoding complexity. Minimum Hamming distances are increased by 30%-50%, with regard to 8-state TCs, and allow frame-error rate (FER) curves to decrease below without any noticeable change in the slope (the so-called flattening effect).

Finally, conclusions and perspectives are summarized in Section V.

II. RATE-RSC ENCODERS BASED ON -INPUT LFSRS

In this section, we will define the constituent RSC codes to be used in the design of the proposed TCs. Fig. 1 depicts the general structure of the RSC encoder under study. It involves a single -stage LFSR, whose -row and -column generator matrix is denoted . At time , the -component input vector is connected to the possible taps via a connection grid represented by a -row and -column binary matrix denoted . The tap column vector at time , , is then given by [START_REF] Berrou | Near-optimum error-correcting coding and decoding: Turbo codes[END_REF] In order to avoid parallel transitions in the corresponding trellis, the condition has to be satisfied, and matrix has to be full rank. Except for very particular cases, this encoder is not equivalent to a single-input encoder fed successively by , that is, the -input encoder is not generally decomposable.

The redundant output of the machine, not represented in Fig. 1, is calculated at time as [START_REF] Robertson | Bandwidth-efficient turbo trellis-coded modulation using punctured component codes[END_REF] where denotes the -component column vector describing the encoder state at time , and is the -component row-redundancy vector. The th component of is equal to one if the th component of is present in the calculation of , and zero, otherwise.

The code being linear, we assume that the "all zero" sequence is encoded. Let us define a return to zero (RTZ) sequence as an input sequence of a recursive encoder, that makes the encoder leave state 0 and return to it again. Calculating the minimum free distance of such a code involves finding the RTZ sequence path with minimum output Hamming weight.

Leaving the null path at time implies that and at least one component of is equal to one. In this case, (2) ensures that the Hamming weight of is at least two when leaving the reference path, since the inversion of one component of implies the inversion of . Moreover, since [START_REF] Benedetto | Parallel concatenated trellis-coded modulation[END_REF] it can be shown that may also be written as [START_REF] Fragouli | Turbo-encoder design for symbol-interleaved parallel concatenated trellis-coded modulation[END_REF] on the condition that [START_REF]Interaction Channel for Satellite Distribution Systems[END_REF] Consequently, if the code is devised to verify condition (5), (4) ensures that if the RTZ sequence retrieves the all-zero reference path at time ( ) because one of the information bits is equal to one, is also equal to one. Hence, relations (2) and (4) together guarantee that the minimum free distance of the unpunctured code, whose rate is , is at least four, whatever . The two codes proposed in this paper for meet this requirement. The minimum Hamming distance of a concatenated code being larger than that of its constituent codes, provided that the permutation function is carefully devised, we can imagine that large minimum distances may be obtained for TCs, for low as well as for high coding rates.

Choosing large values of implies high decoding complexity, because also has to be large, and paths have to be processed for each trellis node. For this reason, only low values of can be contemplated for practical applications for the time being (typically, 2, possibly 3). Up to now, we have only investigated the case in order to construct practical coding and decoding schemes in this new family of TCs. In the following, we call such RSC or turbo encoders double binary. Double-binary RSC codes have a natural rate of 2/3. When higher coding rates are required, a simple regular or quasi-regular puncturing pattern is applied.

The decoding solution calling for the application of the maximum a posteriori (MAP) algorithm based on the dual code [START_REF] Riedel | Symbol-by-symbol MAP decoding algorithm for high-rate convolutional codes that use reciprocal dual codes[END_REF] can also be considered for large values of , since it requires fewer edge computations than the classical MAP algorithm for high coding rates. However, for practical implementations, its application in the log-domain means the computation of transition metrics with a far greater number of terms, and the computation of the (Jacobian) function requires great precision. Consequently, the relevance of this method for practical use is not so obvious when the rate of the mother code is not close to 1.

III. BLOCK TURBO CODING WITH RATE-CONSTITUENT RSC CODES

The TC family proposed in this paper calls for the parallel concatenation of two identical rate-RSC encoders with -bit word interleaving. Blocks of bits, , are encoded twice by this bidimensional code, whose rate is .

A. Circular RSC Codes

Among the different techniques aiming at transforming a convolutional code into a block code, the best way is to allow any state of the encoder as the initial state, and to encode the sequence so that the final state of the encoder is equal to the initial state. The code trellis can then be viewed as a circle, without any state discontinuity. This termination technique, called tailbiting [START_REF] Weiss | Turbo decoding with tailbiting trellises[END_REF], [START_REF] Johannesson | Fundamentals of Convolutional Coding, ser. Digital[END_REF] or circular, presents three advantages in comparison with the classical trellis-termination technique using tail bits to drive the encoder to the all-zero state. First, no extra bits have to be added and transmitted; thus, there is no rate loss, and the spectral efficiency of the transmission is not reduced. Next, when classical trellis termination is applied for TCs, a few codewords with input Hamming weight one may appear at the end of the block (in both coding dimensions), and can be the cause of a marked decrease in the minimum Hamming distance of the composite code. With tailbiting RSC codes, only codewords with minimum input weight two have to be considered. In other words, tailbiting encoding avoids any side effects. Moreover, in a tailbiting or circular trellis, the past is also the future and vice versa. This means that a non-RTZ sequence produces effects on the whole set of redundant symbols stemming from the encoder, around the whole circle. Consequently, the output weights associated with non-RTZ sequences are large, and do not contribute to the minimum Hamming distance of the code.

In practice, the circular encoding of a data block consists of a two-step process [START_REF] Weiss | Turbo decoding with tailbiting trellises[END_REF]. At the first step, the information sequence is encoded from state 0 and the final state is memorized. During this first step, the outputs bits are ignored. The second step is the actual encoding, whose initial state is a function of the final state previously memorized. The double encoding operation represents the main drawback of this method, but in most cases, it can be performed at a frequency much higher than the data rate.

The iterative decoding of such codes involves repeated and continuous loops around the circular trellis. The number of loops performed is equal to the required number of iterations. The state probabilities or metrics, according to the chosen decoding algorithm, computed at the end of each turn are used as initial values for the next turn. With this method, the initial, or final, state depends on the encoded information block and is a priori unknown to the decoder at the beginning of the first iteration. If all the states are assumed to be equiprobable at the beginning of the decoding process, some side errors may be produced by the decoders at the beginning of the first iteration. These errors are removed at the subsequent iterations, since final state probabilities or metrics computed at the end of the previous iteration are used as initial values.

B. Permutation

Among the numerous permutation models that have been suggested up to now, the apparently most promising ones, in terms of minimum Hamming distances, are based on regular permutation calling for circular shifting [START_REF] Dolinar | Weight distribution of turbo codes using random and nonrandom permutations[END_REF] or the co-prime [START_REF] Heegard | Turbo Coding[END_REF] principle. After writing the data in a linear memory, with address ( ), the information block is likened to a circle, both extremities of the block ( and ) then being contiguous. The data are read out such that the th datum read was written at the position , given by [START_REF]Interaction Channel for Digital Terrestrial Television[END_REF] where the skip value is an integer, relatively prime with , and is the starting index. This permutation does not require the block to be seen as rectangular; that is, may be any integer.

In [START_REF] Crozier | Performance of turbo codes with relatively prime and golden interleaving strategies[END_REF] and [START_REF] Berrou | Designing good permutations for turbo codes: Toward a single model[END_REF], two very similar modifications of (6) were proposed, which generalize the permutation principle adopted in the DVB-RCS/RCT or IEEE802.16a TCs. In the following, we will consider the almost regular permutation (ARP) model detailed in [START_REF] Berrou | Designing good permutations for turbo codes: Toward a single model[END_REF], which changes relation ( 6) into [START_REF]IEEE Standard for Local and Metropolitan Area Networks[END_REF] where is an integer, whose value is taken in a limited set , in a cyclic way. , called the cycle of the permutation, must be a divider of and has a typical value of four or eight. For instance, if , the permutation law is defined by

if if if if (8)
and must be a multiple of four, which is not a very restricting condition, with respect to flexibility. In order to ensure the bijection property of , the values are not just any values. A straightforward way to satisfy the bijection condition is to choose all 's as multiples of .

The regular permutation law expressed by ( 6) is appropriate for error patterns which are simple RTZ sequences for both encoders; that is, RTZ sequences which are not decomposable as a sum of shorter RTZ sequences. A particular and important case of a simple RTZ sequence is the two-symbol RTZ sequence, which may dominate in the asymptotic characteristics of a TC (see [START_REF] Benedetto | Design of parallel concatenated convolutional codes[END_REF] for TCs with

). A two-symbol sequence is a sequence with two nonzero -bit input symbols, which may contain more than one nonzero bit. Let us define the total spatial distance (or total span) as the sum of the two spatial distances, before and after permutation, according to (6), for a given pair of positions and ( 9) where [START_REF] Johannesson | Fundamentals of Convolutional Coding, ser. Digital[END_REF] Finally, we denote by the minimum value of , for all possible pairs and [START_REF] Dolinar | Weight distribution of turbo codes using random and nonrandom permutations[END_REF] It was demonstrated in [START_REF] Boutillon | Maximum spread of D-dimensional multiple turbo codes[END_REF] that the maximum possible value for , when using regular interleaving, is

If any two-symbol RTZ sequence for one component encoder is transformed by or into another two-symbol RTZ sequence for the other encoder, the upper bound given by ( 12) is amply sufficient to guarantee a large weight for parity bits, and thus, a large minimum binary Hamming distance. This is the same for any number of symbols, on the condition that both RTZ sequences, before and after permutation, are simple RTZ sequences.

On the other hand, ARP aims at combating error patterns which are not simple RTZ sequences, but are combinations of simple RTZ sequences for both encoders. Instilling some controlled disorder, through the values in [START_REF]IEEE Standard for Local and Metropolitan Area Networks[END_REF], tends to break most of the composite RTZ sequences. Meanwhile, because the value of cycle is small, the good property of regular permutation for simple RTZ sequences is not lost, and a total span close to can be achieved. [START_REF] Berrou | Designing good permutations for turbo codes: Toward a single model[END_REF] describes a procedure to obtain appropriate values for and for the set of parameters.

The algorithmic permutation model described by ( 7) is simple to implement, does not require any ROM, and the parameters can be changed on-the-fly for adaptive encoding and decoding. Moreover, as explained in [START_REF] Berrou | Designing good permutations for turbo codes: Toward a single model[END_REF], massive parallelism, allowing several processors to run at the same time without increasing the memory size, can be exploited.

In addition to the ARP principle and the advantages developed above, the ratecomponent code adds one more The change from binary to double-binary code, though leading to a slight improvement in the distance (18 instead of 16), is not sufficient to ensure very good performance at low error rates. Let us suppose now that couples are inverted (1 becomes 2 and vice versa) once every other time before second (vertical) encoding, as depicted in Fig. 4. In this way, the error patterns displayed in Fig. 2(b) no longer remain error patterns. For instance, 20000002 is still an RTZ sequence for the second (vertical) encoder, but 10000002 is no longer RTZ. Thus, many error patterns, especially short patterns, are eliminated, thanks to the disorder introduced inside input symbols. The right-hand side of Fig. 4 shows two examples of rectangle error patterns that remain possible error patterns after the periodic inversion. The resulting minimal distances, 24 and 26, are large enough for the transmission of short data blocks [START_REF] Berrou | Which minimum Hamming distance do we really need?[END_REF]. For longer data blocks (a few thousand bits), combining this intrasymbol permutation with intersymbol ARP, as described above, can lead to even larger minimum distances, at least with respect to the rectangular error patterns with low input weights we gave as examples.

C. Advantages of TCs With Rate-RSC Constituent Codes

Parallel concatenation of -input binary RSC codes offers several advantages in comparison with classical (one input) binary TCs, which have already been partly commented on in [START_REF] Berrou | The advantages of nonbinary turbo codes[END_REF].

1) Better Convergence of the Iterative Process: This point was first observed in [START_REF] Berrou | Some clinical aspects of turbo codes[END_REF] and commented on in [START_REF] Berrou | Nonbinary convolutional codes for turbo coding[END_REF]. The better convergence of the bidimensional iterative process is explained by a lower error density in each code dimension, which leads to a decrease in the correlation effect between the component decoders.

Let us consider again [START_REF] Heegard | Turbo Coding[END_REF], which gives the maximum total span achievable when using regular or quasi-regular permutation. For a given coding rate , the number of parity bits involved all along the total span, and used by either one decoder or the other, is [START_REF] Crozier | Performance of turbo codes with relatively prime and golden interleaving strategies[END_REF] Thus, replacing a classical binary (

) with a doublebinary (

) TC multiplies this number of parity bits by , though dividing the total span by the same value. Because the parity bits are not a matter of information exchange between the two decoders (they are just used locally), the more numerous they are, with respect to a given possible error pattern (here, the weight-two patterns), the fewer correlation effects between the component decoders.

Raising beyond two still improves the turbo algorithm, regarding correlation, but the gains get smaller and smaller as increases.

2) Larger Minimum Distances: As explained above, the number of parity bits involved in simple two-symbol RTZ sequences for both encoders is increased when using ratecomponent codes. The number of parity bits involved in any simple RTZ sequence, before and after permutation, is at least equal to , regardless of the number of nonzero symbols in the sequence. The binary Hamming distances corresponding to all simple RTZ sequences are then high, and do not pose any problem with respect to the minimum Hamming distance of the TC. This comes from error patterns made up of several (typically, two or three) short simple RTZ sequences on both dimensions of the TC. Different techniques can be used to break most of these patterns, one of them (ARP) having been presented in Section III-B.

3) Less Puncturing for a Given Rate: In order to obtain coding rates higher than , from the RSC encoder of Fig. 1, fewer redundant symbols have to be discarded, compared with an binary encoder. Consequently, the correcting ability of the constituent code is less degraded. In order to illustrate this assertion, Fig. 5 compares the performance, in terms of bit-error rate (BER), of two 8-state RSC codes with the same generator polynomials [START_REF] Benedetto | Design of parallel concatenated convolutional codes[END_REF][START_REF] Crozier | Performance of turbo codes with relatively prime and golden interleaving strategies[END_REF] in octal notation, for

The two-input RSC code displays better performance than the one-input code, for both simulated coding rates.

Raising to three and beyond for this code is not of interest, since there is no full-rank three-column matrix that satisfies [START_REF]Interaction Channel for Satellite Distribution Systems[END_REF]. The choice of a constituent code with parallel transitions in the trellis would lead to a TC with very low minimum Hamming distance.

In Fig. 6, an curve has been introduced for the (23,35) 16-state RSC code with coding rate 3/4. The connection matrices are equal to for for for As expected, we observe that the performance gain between and is smaller than the gain between and . Raising to four and beyond for this 16-state code is not of interest, since there is no full-rank four-column matrix that satisfies (5). 4) Higher Throughput and Reduced Latency: The decoder of an convolutional code provides bits at each decoding step. Thus, once the data block is received, and for a given processing clock, the decoding throughput of a hardware decoder is multiplied by . The latency, i.e., the number of clock periods required to decode a data block, is then divided by , compared with the classical case (

). However, the critical path of the decoder being the Add-Compare-Select (ACS) unit, the decoder with has a lower maximum clock frequency than with . For instance, for , the Compare-Select operation has to be done on four metrics instead of two, thus with an increased propagation delay. The use of specialized look-ahead operators and/or the introduction of parallelism, in particular, the multistreaming method [START_REF] Lin | Algorithms and architectures for concurrent Viterbi decoding[END_REF], makes it possible to significantly increase the maximum frequency of the decoder, and even to reach that of the decoder with . 5) Robustness of the Decoder: Fig. 7 represents the simulated performance in FER, as a function of , of four coding/decoding schemes dealing with blocks of 1504 information bits and coding rate 4/5: binary and double-binary 8-state TCs exhibited in Fig. 2, both with the full MAP decoding algorithm [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol-error rate[END_REF], [START_REF] Benedetto | A soft-input soft-output APP module for iterative decoding of concatenated codes[END_REF], and with the simplified Max-Log-MAP version [START_REF] Robertson | Optimal and suboptimal maximum a posteriori algorithms suitable for turbo decoding[END_REF]. In the latter case, the extrinsic information is less reliable, especially at the beginning of the iterative process. To compensate for this, a scaling factor, lower than 1.0, is applied to extrinsic information [START_REF] Vogt | Improving the max-log-MAP turbo decoder[END_REF]. The best observed performance was obtained when a scaling coefficient of 0.7 for all the iterations, except for the last one, was applied.

In Fig. 7, both codes have ARP internal permutation with optimized span. We can observe that the double-binary TC performs better, at both low and high , and the steeper slope for the double-binary TC indicates a larger minimum binary Hamming distance. These characteristics were justified by 1) and 2) of this section.

What is also noteworthy is the very slight difference between the decoding performance of the double-binary TC when using the MAP or the Max-Log-MAP algorithms. This property of nonbinary turbo decoding actually makes the full MAP decoder unnecessary (or the Max-Log-MAP decoder with Jacobian logarithm correction [START_REF] Robertson | Optimal and suboptimal maximum a posteriori algorithms suitable for turbo decoding[END_REF]), which requires more operations than the Max-Log-MAP decoder. Also, the latter does not need the knowledge of the noise variance on Gaussian channels, which is a nice advantage. The rigorous explanation for this quasi-equivalence of the MAP and the Max-Log-MAP algorithms, when decoding -input TCs, has still to be found.

IV. PERFORMANCE OF DOUBLE-BINARY TCS

This section describes two examples of double-binary TCs, with memory 3 and 4, whose reasonable decoding complexity allows them to be implemented in actual hardware devices for practical applications. Simulation results for transmissions over an AWGN channel with QPSK modulation are provided. From an implemention point of view, the complexity of the corresponding decoder is about twice the complexity of the 8-state decoder.

C. Simulation Results

We have simulated and compared these two codes for two block sizes and three coding rates for transmissions over an AWGN channel with QPSK modulation. The simulation results take actual implementation constraints into account. In particular, the decoder inputs are quantized for hardware complexity considerations. According to our experience, the performance degradation due to input quantization is not significant beyond 5 b. The observed loss is less than 0.15 dB for 4-b quantization, and about 0. We can observe good average performance for this code whose decoding complexity is very reasonable. For a hardware implementation, less than 20 000 logical gates are necessary to implement one iteration of the decoding process when decoding is performed at the system clock frequency, plus the memory required for extrinsic information and input data. Its performance improves predictably with block size and coding rate in relation to the theoretical limit. The reported limits given in Figs. 10 and11, as well as in Fig. 7, take the block size and the target FER into account. They are derived from the Gallager random coding bound on the error probability for binary-input channels, as described in [START_REF] Gallager | Information Theory and Reliable Communication[END_REF]. At FER , the simulated curves lie within 0.6-0.8 dB from the limit, regardless of block size and coding rate. To improve the performance of this code family at FER below , the more powerful 16-state component code has to be selected so as to increase the overall minimum Hamming distance of the composite code. Dotted-line curves in Figs. 10 and 11 show the 16-state TC performance for the same simulation conditions as for the 8-state code. Similar to this code, the permutation parameters are related to the block size, not to the coding rate.

We can observe that the selected code does not lead to a convergence-threshold shift of the iterative decoding process in comparison with the previous 8-state code. For FERs above , 16-state and 8-state codes behave similarly. For lower error rates, thanks to the increase in distance, there is no noticeable floor effect for the simulated signal-to-noise ratio (SNR) ranges, that is, down to a FER of . Again, performance improves predictably with block size and coding rate in relation to the theoretical limit. At FER , the simulated curves lie within 0.7-1.0 dB from the limits, regardless of block size and coding rate, even with the simplified Max-Log-MAP algorithm.

V. CONCLUSION

Searching for perfect channel coding presents two challenges: encoding in such a way that large minimum distances can be reached; and achieving decoding as close to the theoretical limit as possible. In this paper, we have explained why -input binary TCs combined with a two-level permutation can represent a better answer to these challenges than classical one-input binary TCs.

In practice, with , we have been able to design coding schemes with moderate decoding complexity, and whose performance approaches the theoretical limit by less than 1 dB at FER . The 8-state TC with has already found practical applications through several international standards.

Furthermore, the parallel concatenation of RSC circular codes leads to flexible composite codes, easily adaptable to a large range of data block sizes and coding rates. Consequently, as -input binary codes are well suited for association with high-order modulations, in particular -ary quadrature amplitude modulation and -ary PSK, TCs based on these constituent codes appear to be good candidates for most future digital communication systems based on block transmission.

Fig. 1 .

 1 Fig. 1. General structure of a rate-m=(m + 1) RSC encoder with code memory .

Fig. 2 .

 2 Fig. 2. Possible rectangular error patterns. For (a) binary and (b) double-binary TCs with regular permutations.

Fig. 3 .

 3 Fig. 3. Periodicities of the double-binary encoder of Fig. 2(b). Input couples (0,0), (0,1), (1,0), and (1,1) are denoted 0, 1, 2, and 3, respectively.

Fig. 4 .

 4 Fig. 4. Couples in gray spaces are inverted before second (vertical) encoding. 1 becomes 2; 2 becomes 1; 0 and 3 remain unaltered. The three patterns on the left-hand side are no longer error patterns. Those on the right-hand side remain possible error patterns, with distances 24 and 26 for coding rate 1/2.

Fig. 5 .

 5 Fig. 5. Performance in BER of single 8-state RSC codes with m = 1 and m = 2. Encoder polynomials: 15 (feedback) and 13 (redundancy) in octal form (DVB-RCS constituent encoder for m = 2). Coding rates are 2/3 and 6/7 (regular puncturing). Binary/quaternary phase-shift keying (BPSK/QPSK) modulation, additive white Gaussian noise (AWGN) channel, and MAP decoding. No quantization.

Fig. 6 .

 6 Fig. 6. Performance in BER of three single 16-state RSC codes with m = 1, m = 2, and m = 3. Encoder polynomials: 23 (feedback) and 35 (redundancy) in octal notation. Coding rate is 3/4, regular puncturing. BPSK/QPSK modulation, AWGN channel and MAP decoding. No quantization.

Fig. 7 .

 7 Fig. 7. Comparison of performance in FER of two TCs based on both 8-state RSC codes of Fig. 5, with k = 1504, R = 4=5, for MAP and Max-Log-MAP decoding. AWGN channel, QPSK modulation, eight iterations. Scaling factor for Max-Log-MAP decoding: 0.7 for iterations 1-7, 1.0 for iteration 8. No quantization.

Fig. 10 .

 10 Fig. 10. Performance in FER of 8-state and 16-state double-binary TCs for ATM (53 B) blocks and rates 1/2, 2/3, and 3/4. QPSK modulation and AWGN channel. Max-Log-MAP decoding with 4-b input samples and 8 iterations. The theoretical limits on FER are derived from [28].

  4 dB for 3-b quantization. When quantization is applied, clipping extrinsic information at a threshold around twice the maximum range of the input samples does not degrade the performance, while limiting the amount of required memory. Solid line curves in Figs. 10 and 11 show the FER as a function of for the transmission of ATM (53 B) and MPEG (188 B) packets for three different values of coding rate of the 8-state double-binary TC. The component decoders use the Max-Log-MAP algorithm, with input samples quantized on 4 b. Eight iterations were simulated and at least 100 erroneous frames were considered for each point indicated, except for the lowest points, where approximately 30 erroneous frames were simulated.

Fig. 11 .

 11 Fig. 11. Performance in FER of 8-state and 16-state double-binary TCs for MPEG (188 B) blocks and rates 1/2, 2/3, and 3/4. QPSK modulation and AWGN channel. Max-Log-MAP decoding with 4-b input samples and 8 iterations. The theoretical limits on FER are derived from [28].

ACKNOWLEDGMENT

The authors are grateful to the Associate Editor and the reviewers for their valuable comments and suggestions for improving this paper.

A. Eight-State Double-Binary TC

The parameters of the component codes are [START_REF] Berrou | Designing good permutations for turbo codes: Toward a single model[END_REF] The diagram of the encoder is described in Fig. 8. Redundancy vector is only used for coding rates less than 1/2. For coding rates higher than 1/2, puncturing is performed on redundancy bits in a regular periodical way, following patterns that are described in [START_REF]Interaction Channel for Satellite Distribution Systems[END_REF]. These patterns are identical for both constituent encoders.

The permutation function is performed on two levels, as explained in Section III-B.

For , we have the following. • Level 1: inversion of and in the data couple, if .

• Level 2: this permutation level is described by a particular form of ( 8)

Value is added to the incremental relation in order to comply with the odd-even rule [START_REF] Barbulescu | Iterative decoding of turbo codes and other concatenated codes[END_REF]. The disorder is instilled in the permutation function, according to the ARP principle, in two ways.

• A shift by is added for odd values of . This is done because the lowest subperiod of the code generator is one (see Fig. 3). The role of this additional increment is thus to spread to the full the possible errors associated with the shortest error patterns. • , , and act as local additional pseudorandom fluctuations. Notice that the permutation equations and parameters do not depend on the coding rate considered. The parameters can be optimized to provide good behavior, on average, at low error rates for all coding rates, but seeking parameters for a particular coding rate could lead to slightly better performance.

B. Sixteen-State Double-Binary TC

The parameters of the best component code we have found are [START_REF] Boutillon | Maximum spread of D-dimensional multiple turbo codes[END_REF] The diagram of the encoder is described in Fig. 9. Puncturing is performed on redundancy in a periodic way, with identical patterns for both constituent encoders. It is usually regular, except when the puncturing period is a divisor of the LFSR period. For example, for coding rate 3/4, the puncturing period is chosen equal to six, with puncturing pattern [101000].

For this code, the permutation parameters have been carefully chosen, following the procedure described in [START_REF] Berrou | Designing good permutations for turbo codes: Toward a single model[END_REF], in order to guarantee a large minimum Hamming distance, even for high rates. The level-1 permutation is identical to the intrapermutation of the 8-state code. The level-2 intersymbol permutation is given by For The spirit in which this permutation was designed is the same as that already explained for the 8-state TC. The only difference is that the lowest subperiod of the 16-state generator is two, instead of one. That is why the additional shift (by ) is applied consecutively, twice every four values of .

Table I compares the minimum binary Hamming distances of the proposed 8-state and 16-state TCs, for 188-B data blocks and four different coding rates. The distance values were estimated with the so-called all-zero iterative algorithm, a fast computational method described in [START_REF] Garello | The all-zero iterative decoding algorithm for turbo code minimum distance computation[END_REF], which provides distance values with very high reliability for block sizes larger than a few hundred bits. We can observe a significant increase in the minimum distance when using 16-state component codes; the gain varies from 30%-50% depending on the case considered. With this code, we were also able to define permutation parameters leading to minimum distances as large as 33 for , 22 for , and 16 for for ( )-B blocks.

Catherine Douillard (M'01) received the engineering degree in telecommunications from the École Nationale Supérieure des Télécommunications (ENST) de Bretagne, Brest, France, in 1988, and the Ph.D. degree in electrical engineering from the Université de Bretagne Occidentale, Brest, France, in 1992.

In 1991 she joined ENST Bretagne, where she is currently a Professor in the Electronics Department. Her main interests are turbo codes and iterative decoding, iterative detection, and the efficient combination of high spectral efficiency modulation and turbo-coding schemes.

Claude Berrou (M'87) was born in Penmarc'h, France, in 1951. In 1978, he joined the Ecole Nationale Supérieure des Télécommunications (ENST) de Bretagne, where he is currently a Professor in the Electronics Department. In the early 80's, he started up the training and research activities in VLSI technology and design, to meet the growing demand from industry for microelectronics engineers. Some years later, he took an active interest in the field of algorithm/silicon interaction for digital communications. In collaboration with Prof. A. Glavieux, he introduced the concept of probabilistic feedback into error-correcting decoders, and developed a new family of quasi-optimal error-correction codes that he named "turbo codes." He also pioneered the extension of the turbo principle to joint detection and decoding processing, known today as turbo detection and turbo equalization. His current research topics, besides algorithm/silicon interaction, are electronics and digital communications at large, error-correction codes, turbo codes and iterative processing, soft-in/soft-out (probabilistic) decoders, etc. He is the author or co-author of 8 registered patents and about 60 publications in the field of digital communications and electronics.

Dr


Douadia Bougherara
email: douadia.bougherara@inra.fr

Sandrine Costa
email: sandrine.costa-migeon@inra.fr

Gilles Grolleau

Lisette Ibanez
email: lisette.ibanez@inra.fr.

Do positional preferences cause welfare gains?

We examine conditions for which positional preferences for voluntary contribution to a public good can be welfare enhancing in a one-shot public good game, where individuals may also enjoy a return from their contribution ranking. We show that positional preferences are welfare-increasing only under certain conditions. We find that when agents' positional preferences are homogeneous, they overinvest in the public good compared to equilibrium with no positional preferences, resulting in a zero-sum positional race with a higher public good provision. When agents have heterogeneous positional preferences, the overall impact on social welfare is positive when endowments are homogeneous.

Introduction

It is widely recognized that people care for their relative position. But, the co-existence of positional goods1 with non-positional goods may generate a crucial social dilemma. Positional concerns are stronger in some domains than others so that resources are diverted from nonpositional goods to positional goods and lead to a decrease in social welfare [START_REF] Frank | Positional Externalities Cause Large and Preventable Welfare Losses[END_REF]. Because of the very specific nature of positional goods [START_REF] Hirsch | Social Limits to Growth[END_REF], seeking a higher rank is necessarily gained at the expense of other agents, resulting in zero or negative sum games. Each step up the status ladder for one person logically requires a step down for another. Consequently, status seeking agents make expenditures on positional goods to get a higher relative position, but as all agents make the same efforts, all obtain an identical position. In an economy with private consumption goods, positional preferences lead to a welfare loss, which can be aggravated if negative externalities are considered [START_REF] Ng | Relative Income, Aspiration, Environmental Quality, Individual and Political Myopia: Why May the Rat-race for Material Growth be Welfare Reducing[END_REF][START_REF] Brekke | Status-Seeking and Material Affluence: Evaluating the Hirsch hypothesis[END_REF][START_REF] Van Long | Resource-grabbing by Status-Conscious Agents[END_REF][START_REF] Frank | Should Public Policy Respond to Positional Externalities?[END_REF].

Although consumer positional motivations were identified early (e.g., [START_REF] Veblen | The Theory of the Leisure Class[END_REF][START_REF] Hirsch | Social Limits to Growth[END_REF][START_REF] Frank | The Demand for Unobservable and Other Nonpositional Goods[END_REF][START_REF] Alpizar | How Much Do We Care About Absolute versus Relative Income and Consumption?[END_REF], theoretical and empirical investigations about their importance in relation to public goods are scarce (e.g., [START_REF] Holländer | A Social Exchange Approach to Voluntary Cooperation[END_REF][START_REF] Solnick | Are Positional Concerns Stronger in Some Domains than in Others?[END_REF]Hemenway, 2005, Munoz-Garcia, 2011). Contrasting with this literature gap, anecdotal evidence supports the fact that charitable contributions or contributions to public goods may be motivated by positional concerns [START_REF] Wilkinson | Out of Position: Against the Politics of Relative Standing[END_REF]. For instance, Ted Turner inspired the successful idea of the Slate 60 list of the top American donors. Indeed, he argued that the Forbes 400 list of richest Americans was discouraging the wealthy from giving away their money for fear of slipping down the rankings [START_REF] Dowd | Ted's Excellent Idea[END_REF]. School auctions are another example where status seeking concerns can lead to higher private provision of public goods [START_REF] Kuczynski | At School Auctions, Prestige Is the Price[END_REF][START_REF] Pertusini | School Fete Wars -The Rise and Rise of the Lavish PTA fundraiser[END_REF]. Similarly, a recent marketing study showed that status competition can promote pro-environmental behavior, even at a private cost for individuals [START_REF] Griskevicius | Going Green to Be Seen: Status, Reputation and Conspicuous Conservation[END_REF]. The authors argue that 'visible' ecofriendly purchases (by contrasting shopping alone online with shopping in public) are rooted in the idea of competitive altruism, that is people compete for status by trying to appear more altruistic. Gintis et al. (2003, p. 159) state that hyper-fair offers in ultimatum games can reflect Melanesian culture of status-seeking through gift giving.

In this paper, our contribution is to enlarge the analysis of the impact of positional preferences by taking into account, in a single framework, the heterogeneity of endowments, the full range of positional preferences (positive and negative) and the impact on social welfare. Two specific articles are closely related to our work. [START_REF] Holländer | A Social Exchange Approach to Voluntary Cooperation[END_REF], who considers homogeneous agents (both in positional preferences and endowments), shows that, at the equilibrium, the only effect of status orientation is a decrease in social approval through self-assessment. [START_REF] Muñoz-Garcia | Competition for Status Acquisition in Public Good Games[END_REF] compares simultaneous and sequential mechanisms in terms of overall public good contribution, and shows that, in case of heterogeneous positional preferences (supposed to be positive), the sequential mechanism should be preferred. The analytic framework considers a non-linear payoff function, putting higher weight on lower positional preferences. The study only focuses on the impact of positional preferences on public good provision and whether the decision making process (simultaneous or sequential) allows higher contributions. However, the author provides no social welfare analysis.

Adding to the literature, we analyze whether policy makers could promote status races on public goods. Simply put, we explore all the effects on social welfare of such positional concerns, not only in terms of provision of public goods but also in terms of positional externalities. To do so, we use a simple model of a one-shot voluntary contribution to a public good where besides a return to the public good, individuals may enjoy a return from the ranking of their public good contribution. We carry out a comparative statics analysis to determine how positional preferences drive public good provision and impact social welfare. We show that welfare is influenced by the level of two externalities; individual contributions affect the level of public goods (public good externality) but also influence the rank of individuals (positional externality) in the contribution hierarchy. When agents have homogeneous positional preferences over the public good, they overinvest in the positional public good compared to equilibrium with no positional preferences. There is no positional gain (everyone runs to keep the same place), but a higher provision of the public good. Indeed, positional preferences allow public good provision, prevent free rider behavior and thus increase social welfare. When agents differ in their positional preferences over the public good, the overall impact on social welfare is positive when endowments are homogeneous. This paper proceeds as follows. Section 2 presents a basic framework of consumer behavior with positional preferences on public goods contributions and shows that the standard free riding equilibrium is not the only equilibrium. Then, in section 3, we analyze the impact of such positional preferences on social welfare when positional preferences are homogeneous (section 3.1) and when they are heterogeneous (section 3.2). Section 4 concludes.

A model of voluntary contribution with a positional public good

Consider a one-shot public good game where individual i has positional preferences and chooses his public good contribution i x to maximize utility in equation (1). Utility depends on i's own contribution but also on the contributions of others not only because of the nature of the public good but also because of relative standing issues. ( , , ) = + ( , ) + , ,

The utility function is composed of three parts: utility from private consumption , utility from public good consumption , , and utility from relative standing ( , , ).

The first part of equation (1), + , , constitutes the standard payoff function for a voluntary contribution mechanism. For the sake of simplicity and as a first step, we assume this payoff function to be linear both for private as well as public consumption (cf. equation ( 2)); Utility from private consumption, , equals i D (the monetary endowment that i might allocate to public good provision, i.e. disposable income for charitable giving) 2 minus which is the cost of individual i's contribution to the public good. Individual i may contribute any amount of x to the public good such that

       p D x i i , 0
. Public good consumption, 2 We suppose that an individual i with revenue Bi, might allocate a maximum amount of money to charitable giving, Di, such that Bi=D+Di. This amount Di, is exogenously determined and depends on revenue and life expenses (food, housing, etc.). Then, without loss of generality and for sake of simplicity, we set D=0.

, , depends on contributions of all N group members ( + ∑ ≠ ) and group marginal payoff (G). Thus marginal per capita return of the public good equals

N G .
Thus, under the assumption of linear payoff functions, the marginal cost of public good consumption equals p, whereas the marginal benefit equals . We assume that N G p  and that p<G , which corresponds to standard public good dilemma assumptions.

To summarize, the first part of equation ( 1) writes as in equation ( 2).

+ , = -+ ( + ∑ ≠ ) (2)
The last part of equation ( 1),   ,,

i i j i R x x  , represents the positional payoff (cf. equation (3))
where

) 1 (     N x x i j j j
is defined as the average contribution of all other players

    N i j , 1   .     , , i i j i i i j R x x x x     (3)
The positional payoff function is composed of two terms:

-the difference between individual i's contribution and the average contribution of all

other players   j i x x 
, that is i's relative position (as in [START_REF] Brekke | Status-Seeking and Material Affluence: Evaluating the Hirsch hypothesis[END_REF].

-the individual positional parameter a i that measures the nature and strength of positional We would like to stress the role played by the positional parameter. If someone contributes to the public good for the same amount as others on average (i.e., identical relative position), his contribution will not give him benefits other than the monetary payoff. Let us assume a higher relative position for individual i, i.e.   j i x x  >0, that is individual i contributes more than others, on average. Then, if individual i has a positive positional parameter

0 i   (resp. a negative positional parameter 0  i  ), i's positional payoff increases (resp. decreases).
Conversely, assuming a lower relative position for i, i.e.   0

  j i x x
only the individuals that have a negative positional parameter (

0  i 
) will increase their positional payoff. In this particular case, individual i benefits from the public good with a personal contribution lower than the average. He enjoys the pleasure of "making a better deal than other players".

The utility maximizing behavior leads to the following lemma.

Lemma 1: An individual with positive positional concerns contributes all his endowment (respectively nothing) to the public good, if the non-monetary value of his relative position, i  , is higher (respectively lower) than the monetary loss of contributing to the public good, G p N  . An individual with negative positional concerns never contributes to the public good.

Proof: see Appendix

Linearity of payoffs implies equilibrium contributions to be boundary. Thus, there exists two equilibria in this game: player i either donates all his endowment to the public good or submits zero contributions. In an economy where individuals don't possess any positional preferences or where contributions of others are not observable (i.e. individuals don't benefit from any reputational value from public good consumption), and given our assumption N G p  , the unique equilibrium is to contribute nothing. In an economy where individuals possess positional preferences, voluntary contribution may become a dominant strategy, as long as > -

. Our results show that, under the assumption of linear utility functions, status seeking may counter-balance free-riding incentives in a one shot public good game as long as positional preferences are sufficiently high.

The assumption of linear payoff functions might be considered to be restrictive and lack generalization of our results. Especially when arguing that in real life often both "private and public goods are subject to diminishing marginal values" [START_REF] Laury | Voluntary Provision of Public Goods: Experimental Results with Interior Nash Equilibria[END_REF].

So for more generality, we will discuss the way equilibria are modified when linearity is either released at the private consumption level or released at the public good provision level. We still find in both cases that public good contributions increase with positional preferences.

In the case of diminishing returns in private consumption ( ′ > , ′′ < ∀ ), the optimal decision is no longer a corner solution. Indeed, the marginal cost of contributing to the public good is now an increasing function with because the amount of private good becomes rarer. As the optimal voluntary contribution is determined such that the marginal benefit of contributing (i.e. marginal benefit of public good consumption and his/her relative position ) equals the marginal cost, some individuals who value their relative position not necessarily contribute their entire endowment to the public good. We can thus distinguish three different types of behavior. Individuals with don't contribute, individuals with ℎ donate their entire endowment, and individuals with ∈ ] , ℎ [ will contribute only a part of their endowment to the public good.

An illustration is given in Figure 1 supposing a quadratic function for private consumption:

= -+ for any parameter > [START_REF] Laury | Voluntary Provision of Public Goods: Experimental Results with Interior Nash Equilibria[END_REF].

Figure 1. Optimal contribution to the public good as a function of the positional parameter in the case of a quadratic function for private consumption

When considering diminishing marginal returns in public good consumption ( ′ > ; ′′ < ad ′′ < ∀ , there may exist multiple individual equilibria. Diminishing returns may be prevailing in different sectors such as health care, research and development, national defense. An extra contribution does not increase the marginal benefit to all users by the same amount. Under this assumption, private voluntary contribution by an individual will not only depend on his/her personal positional preference but also on the level of others' contributions. The marginal benefit of contribution for individual i decreases with his own contribution level, but also when others contribute more.

For an illustration, we use the quasi-linear function of [START_REF] Laury | Voluntary Provision of Public Goods: Experimental Results with Interior Nash Equilibria[END_REF]

Welfare analysis under positional preferences

According to [START_REF] Frank | Positional Externalities Cause Large and Preventable Welfare Losses[END_REF][START_REF] Frank | Should Public Policy Respond to Positional Externalities?[END_REF], the consumption of positional goods necessarily gives rise to welfare losses. More precisely, the idea is that if one good is more positional than another good, the search for status leads to an increase in consumption of positional goods and a decrease of consumption of non-positional goods. However, as everyone consumes more of the positional good, nobody increases his relative position. Individuals do not get the expected positional benefit. This result is conditional on private positional goods. In the case of public goods, positional concerns may divert some resources from private consumption to private provision of public goods.

We consider now an economy composed of N individuals. Social welfare is the sum of individuals' utility functions.

= ∑ ( , , ) = ∑ + ( , ) + ( , , ) = = (4) Social welfare is thus the sum of the social welfare effects of private good and public good consumption, on one side, and of the social welfare effects of the positions on public good contribution.

= ∑ + ( , ) + ∑ ( , , ) = = (5)
The aim of our paper is to determine the impact of positional preferences on social welfare gains/losses, that is, the impact of a change of the parameters i  on W, and to determine under which conditions positional preferences can be welfare enhancing for the society.

For sake of simplicity, let us assume that all parameters i  increase by .

= ∑ + + ∑ ≠ , ∈[ ,] = + ∑ + ∑ ≠ , ∈[ ,] = (6) x i x -i increase in αi
The first part of this equation represents the sum of individual marginal benefits from both private and public good consumption. It can be assumed without loss of generality, because of the characteristics of a public good, that:

+ + ∑ ≠ ∀
Moreover, section 2 highlights that whatever the assumptions regarding and .

Consequently, the first part of ( 6) is positive. The effect of an increase of the parameters i  on the sum of the positional preferences is more ambiguous and depends on the assumptions on positional preferences.

We consider now positional preferences defined as in equation ( 3).

Homogeneous positional preferences

Proposition 1: If individuals have homogeneous positional preferences, i.e.,  

N j i j i ,..., 2 , 1 ,       
, social welfare increases or remains constant when positional preferences increase.

Proof: see Appendix

If individuals have homogeneous positional preferences, an increase of all positional parameters α by leaves the sum of positional benefits/losses unchanged.

∑ + ∑ ≠ , ∈[ ,]

= if = ∀ , = From (6), it can be deduced that:

= ∑ + + ∑ ≠ , ∈[ ,] =
With homogeneous positional preferences, there is no social welfare gain to status-seeking in public goods as there was none with private goods [START_REF] Frank | Positional Externalities Cause Large and Preventable Welfare Losses[END_REF][START_REF] Frank | Should Public Policy Respond to Positional Externalities?[END_REF]. Positional benefits for some will be counterbalanced by positional losses for others. This result comes from our assumption of homogeneous preferences (all individuals give the same value to their relative position) and our definition of relative position (comparison between individuals and average contribution of all other individuals). However, the public good is overprovided as compared with the benchmark provision level and social welfare increases. In other words, positional preferences can prevent free-rider behavior. Note that the gain in the public good level mainly depends on the group marginal payoff.

Heterogeneous positional preferences

It is clear from section 2 that the individual contribution depends on the individual positional preferences. Without loss of generality, it can be assumed that k individuals will contribute to the public good after an increase of their positional preferences, and that the other individuals will not contribute to the public good, even after an increase of their search for status. Proof: see Appendix

Given our assumption regarding positional preferences (3), the positional component of social welfare is equal to:

∑ + ∑ ≠ = ∑ - ∑ ≠ - = + ∑ -∑ - ≠ = = (7)
The first term of this equation represents the social welfare effect of an increase of all positional tastes by , letting all contributions to public good unchanged. It is always equal to 0, since what some people do gain in terms of positional welfare is equal to what others do lose when all positional tastes increase by .

The second term of this equation is the positional welfare effect of the change of individual contributions due to the change of positional tastes by . If the marginal effect of an increase of positional taste is the same for the k contributors ( = ∀ ∈ [ , ] , then the second term of equation ( 7) is positive :

∑ - ∑ ∈[1,] ≠ - = = - - ∑ -- ∑ = + = > (8)
This proposition shows that when all contributors give the same amount to the public good, social welfare is increased by an increase of positional preferences, not only because of the positive externality on public good consumption, but also because the positional benefit of those who contribute is higher than the positional loss of non-contributors. Indeed those who contribute have a higher positional taste ( i  ) than those who do not contribute. Unlike the results of [START_REF] Frank | Positional Externalities Cause Large and Preventable Welfare Losses[END_REF] on private goods, we show that heterogeneous positional preferences over the public goods with identical contributions can ultimately enhance social welfare.

Let us now consider that the marginal effect on contribution does differ between contributors (the assumption = is not verified) and that contributors do have homogeneous preferences (∀ ∈ [ , ], = ) as non-contributors (∀ ∈ [ + , ], = ). Then:

∑ - ∑ ∈[1,] ≠ - = = - - ( -) ∑ > = (9)
Intuitively, if all contributors have the same positional preferences, the social welfare effect of the comparison between contributors is equal to 0 (the increase of social status of someone is compensated by the decrease of social status by someone else). However, the increase of status of all contributors is higher than the loss of status of non-contributors, since contributors give a higher value to status than non-contributors. This result can be reversed when contributors do not have the same positional preferences. In that case, the social welfare effect of an increase of positional preferences is a sum of the marginal effect on individual contributions ( ) weighted by individual relative positional preferences, which might be either positive or negative ∑ - It should be noticed that, in case of linear payoff functions as assumed in (2), then individual contributions to public good are equal to ; consequently the results depend then on the homogeneity of endowments.

Interestingly, if individuals have heterogeneous positional preferences (and different endowments) and if they compare their contribution to the average contribution of other persons having the same endowment, then the first part of proposition 2 applies and positional preferences in public good provision lead to an increase in social welfare. Indeed, it seems more realistic to assume that people do compare themselves with similar persons. Aristotle argued that 'we envy those who are near us in time, place, age, or reputation' (Rhetoric, 1338a). For instance, Ted Turner is engaged in a competition with the wealthiest Americans, and is careful to maintain his position in this group and far from poor people. In the same vein, [START_REF] Clark | Satisfaction and Comparison Income[END_REF] showed that individuals compare themselves to reference groups including other persons similar to themselves in some dimensions.

Table I. Overall effect of positional preferences for public goods contribution on social welfare

Concluding remarks

While positional races on private goods can be detrimental to social welfare, our results show that positional races on public goods can be conducive to Paretian improvements. Consequently, a major issue for policymakers is to limit positional races in the private goods domain while promoting them in the public goods domain. 'Good' institutions can help to channel status seeking energy in directions conducive to socially desirable outcomes. For instance, it is widely admitted that positional preferences are more likely to remain latent if there is no socially visible way to rank individuals on the considered dimension. From a practical viewpoint, 'social visibility' and the possibility to rank on this dimension can stimulate positional choices in the public goods realm.

A natural extension to our study would be to analyze the overall impact of different combinations of positional preferences regarding public and private goods on the whole economy. Extending the framework to endogenize the positional parameters of individuals as a function of their wealth or/and as a function of the size of their reference group may also provide fruitful insights for future research. Moreover, adding strategic concerns could enrich the analysis. For example, in the case of imperfect information on positional preferences, contribution levels become a strategic variable and constitute signals of individual ranking seeking. Or in the case where charitable contributions cannot be perfectly observed, then expected beliefs on others' contributions will drive individual decision making.

  individual i's utility increases when i contributes less than others, but if 0 i   , individual i's utility increases when i contributes more than others. If 0  i  , individual i does not care about his relative standing and only enjoys the monetary payoff, which corresponds to standard homo economicus preferences.

Figure 2 .

 2 Figure 2. Best response function for individual i in reply to others' contribution level in the case of a quadratic function for public good consumption

Proposition 2 :

 2 Assume that: individuals differ in their positional preferences, that ∀ ∈ [ , ], ∀ ∈ [ + , ] > , and that ∀ ∈ [ + , ] = and = a. An increase of positional preferences leads to an increase in social welfare if its effect on private contribution to the public good is the same for all individuals (

  overall effect is positive.

Table 1 summarizes

 1 Propositions 1 and 2.

We use the terms status and position interchangeably, status being the ultimate positional good.

This work was supported by the ANR-Agence Nationale de la Recherche (French National Research Agency) under the "Programme Agriculture et Développement Durable" [project "ANR-05-PADD-009, Ecolabels"].

Appendix Proof of Lemma 1:

Maximizing earnings, i.e. ax , , results in an equilibrium condition in which the marginal cost of contributing, p, equals the marginal benefit in public good provision, , and in social status, .

From which it can be deduced that:

The optimal contribution to the public good is such that: * = if < -

Proof of proposition 1:

We want to show that (equation ( 6)) is allways positive when individuals have homogeneous positional preferences. The first part of (equation ( 6)) is allways positive, since it is the sum of individual marginal benefits from both private and public good consumption. The second part of is equal to

Under the assumption of homogeneous positional preferences, we have:

Proof of proposition 2 :

Under our assumption of positional preferences (3) the positional component of social welfare variation (second part of equation ( 6)) is equal to :

Simple arithmetic shows that the first term is equal to 0. Next parts analyze the second term.

Part (a)

In case where

Which can be rearranged into:

The hypothesis that > ∀ ∈ [ , ] ad ∀ ∈ [ + , ] can be rewrote into:

, and


Quentin Baert
email: quentin.baert@univ-lille.fr

Anne-Cécile Caron
email: anne-cecile.caron@univ-lille.fr

Maxime Morge
email: maxime.morge@univ-lille.fr

Jean-Christophe Routier
email: jean-christophe.routier@univ-lille.fr

Kostas Stathis
email: kostas.stathis@rhul.ac.uk

Adaptive Multi-agent System for Situated Task Allocation

Keywords:

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

INTRODUCTION

Multi-agent scheduling [1, 2, 4, 8, 10-17, 20, 22-25] has received significant attention in tackling the problem of load balancing and task allocation in distributed systems. Apart from dividing the work through decentralization, we consider dynamicity because allocation of tasks must be concurrent with their execution, and adaptation because tasks must be reallocated when a disruptive event is performed. We will assume that agents are fully distributed and cooperative in order to optimize the global runtime, i.e a systemcentric metric rather than user-centric metrics [10-13, 20, 24]. We will also assume that a task can be performed by any single agent without preemption and precedence order. Moreover, tasks have no deadlines, are indivisible and not shareable.

We follow a market-based approach [10-13, 20, 24] to tackle the multi-agent situated task allocation problem. In order to improve load balancing, agents adopt a locality-based strategy in concurrent one-to-many negotiations for task delegations. The task reallocation is dynamic since the negotiation process is iterated and concurrent with the tasks processing. Moreover, the system is adaptive to disruptive events, e.g. task consumptions. As a practical application, we consider the distributed deployment of the MapReduce design pattern for processing large datasets [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF]. Our preliminary empirical results show that, for such an application, the locality-based strategy improves the runtime.

NEGOTIATION PROCESS

In a multi-agent situated task allocation problem, tasks have different costs (runtime) for different agents due to the resource locality. A task allocation is evaluated by considering the maximum completion time (makespan). In order to locally improve the task allocation, agents consider socially rational task delegations that strictly decrease the local makespan until a stable allocation is reached.

Decentralized task delegation process. Agents operate in concurrent, one-to-many and single-round negotiations for task delegations. Each negotiation, which is based on the Contract Net Protocol [START_REF] Smith | The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver[END_REF], is divided in three steps: 1) the choice of the task to negotiate by the strategy of the initiator; 2) the refusals/bids from the peers based on the social rationality of the task delegation; 3) the selection of the winning bid by the initiator, e.g. the bidder with the smallest workload. Several negotiations may concurrently occur as in [START_REF] Alrayes | Concurrent bilateral negotiation for open e-markets: the CONAN strategy[END_REF] and the responsiveness of the task reallocation can be improved [START_REF] Baert | Negotiation Strategy of Divisible Tasks for Large Dataset Processing[END_REF]. Even if the computation of the local makespan by the initiator of a negotiation is based on its beliefs, that can be inaccurate, a successful negotiation can only reach a socially rational task delegation, and so it tends to improve the makespan.

Concurrent consumptions and delegations. Task delegations and task consumptions are concurrent. Fig. 1 represents their impact on the allocation until all of the tasks are performed (T final = ∅). Starting from the initial allocation P 0 , agents perform socially rational task delegations to improve the makespan (e.g. the path from P 0 to P k ) until a task consumption (e.g. the edge from P k to P ′ 0 ), which eventually interrupts the path toward a stable allocation (e.g. the path from P k to P stable shown in gray). A task consumption may occur when the agents have reached a stable allocation (e.g. P ′ stable ) or not (e.g. P k ). Even if task delegations and task consumptions are concurrent and the two of them tend to decrease the makespan, these processes are complementary since a task removal may allow new socially rational task delegations.

Locality-based strategy. According to a trivial strategy, an agent can perform the largest task in its bundle and negotiate the smallest one in the set of potential socially rational delegations. By contrast, we build the strategy upon the locality since resource fetching consumes time. Intuitively, an agent should perform first the tasks which may cost more for its peers and it should negotiate first the tasks which may cost less for its peers. For this purpose, we define the local availability ratio of an agent for a task as the ratio between the number of local resources for this task with respect to the agent and the total number of resources for the task. According to our strategy, an agent performs first the large local tasks and it negotiates first the large distant ones based on its local beliefs and knowledge, i.e. the local availability ratios and the task costs. This strategy is built on a composite task bundle, called locality-based bundle which is divided in three subbundles as follows.

• The maximum locality bundle contains the tasks s.t. agent owns at least one resource and there is no other agent which owns more resources for this task. The tasks are sorted in decreasing order of cost.

• The intermediate locality bundle contains the tasks which are partially local. The tasks are sorted in decreasing order of local availability ratio and the tasks with the same local availability ratio are sorted in decreasing order of cost.

• The distant bundle contains the tasks which are distant. The tasks are sorted in increasing order of cost.

When an agent looks for a task to perform, it starts from the top of the maximum locality bundle, i.e. the largest local task. When an agent looks for a task to negotiate, it starts from the bottom of the distant bundle (i.e. the largest distant task) and it selects the first one which is a potential socially rational delegation according to its beliefs.

EMPIRICAL VALIDATION

We have implemented a multi-agent system which deploys the MapReduce design pattern in a distributed system setting [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF]. Our agents negotiate the reduce tasks during the job in order to improve the poor load balancing due to data skews [START_REF] Chen | SAMR: A self-adaptive MapReduce scheduling algorithm in heterogeneous environment[END_REF][START_REF] Kwon | Skewtune: mitigating skew in mapreduce applications[END_REF][START_REF] Liroz-Gistau | FP-Hadoop: efficient execution of parallel jobs over skewed data[END_REF], and so the job execution time.

Our experiments1 are based on a 8 Gio dataset (82, 283 keys, i.e. tasks) which has been generated such that the initial task allocation (cf. Fig. 2) is poorly load balanced in order to check that the locality has an impact on the makespan and thus on the job runtime.

We compare the median job execution times when the agents adopt the trivial strategy or the locality-based one with 10 runs for each configuration. We observe that the locality-based strategy significantly improves the runtime, around -7.6%. When there is no negotiation, it corresponds to the Hadoop behaviour where the initial task allocation is never challenged. For comparison, in this case the job runtime is 853 seconds (around +100%). We deduce that the price of the negotiation can be neglected regarding the impact of the load balancing. Moreover, the negotiation allows to decrease the job execution time and even more with the locality-based strategy.

Fig. 2 compares the task allocation when all the tasks have been performed whatever they have been negotiated (or not) between the 16 agents in accordance with the trivial strategy or the localitybased one. We observe that the makespan of the initial allocation is approximately 3.3 10 8 , around 2.5 10 8 (-24%) for the negotiation with the trivial strategy and 2 10 8 (-30.7%) for the locality-based one. We deduce that the negotiation, in particular with the localitybased strategy, allows to improve the load balancing.

CONCLUSION

We have introduced a task reallocation mechanism which is dynamic, since it is concurrent with the tasks processing, and adaptive to disruptive events, i.e. task consumptions. In this context, we have proposed a locality-based strategy adopted by the agents operating in concurrent one-to-many negotiations for task delegations. According to their local beliefs and knowledge, the agents perform first large local tasks and they negotiate first large distant ones. In order to validate our approach, we have developed a proof-of-concept prototype where agents negotiate reduce tasks of the MapReduce design pattern in a distributed setting. Our preliminary empirical results show that, for such an application, the locality-based strategy can improve the load balancing and so the job execution time.

As part of our future work we are currently evaluating our prototype with numerous and representative experiments with real-word datasets in various settings.

Figure 1 :

 1 Figure 1: Concurrent task consumptions (vertical edges) and task delegations (horizontal edges).

Figure 2 :

 2 Figure 2: Initial and ex-post task allocation with the trivial strategy and the locality-based one.

Our experiments have been performed on 16 PCs with 4 cores Intel(R) i7 and 16GB RAM each.