Christophe Gonzales

Patrice Perny

Sergio Queiroz

Preference aggregation in combinatorial domains using GAI-nets

Keywords: GAI-nets, Preference Modelling, Preference Aggregation

come

Introduction

The development of decision support systems and web recommender systems has stressed the need for models that can handle users preferences and perform preference-based recommendation tasks. In this respect, current works in preference modeling and decision theory aim at developing compact preference models achieving a good trade-off between two conflicting aspects: i) the need for models flexible enough to describe sophisticated decision behaviors; and ii) the practical necessity of keeping the elicitation effort at an admissible level as well as the need for fast procedures to solve preference-based optimization problems on large sets of alternatives. As an example, let us mention interactive decision support systems on the web where the preferred solution must be found among a combinatorial set of possibilities. This kind of application motivates the current interest for qualitative preference models and compact representations like CP-nets [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF][START_REF] Boutilier | Preference-based constraint optimization with CP-nets[END_REF] and mCP-nets [START_REF] Rossi | mCP nets: Representing and reasoning with preferences of multiple agents[END_REF], their extension to the multiagent case. Such models are deliberately simple and flexible enough to be integrated efficiently in interactive recommendation systems; the preferences of the agents must be captured using only a few questions so as to perform a fast preference-based search over the possible items.

In other applications (e.g. configuration system, fair allocation of resources, combinatorial auctions), more time can be spent in the elicitation stage in order to get a finer description of preferences. In such cases, utilities can significantly outperform qualitative models due to their higher descriptive power [START_REF] Boutilier | UCP-networks; a directed graphical representation of conditional utilities[END_REF]. Moreover, the use of cardinal utilities in the multiagent setting allows to escape the framework of Arrow's impossibility theorem which considerably restricts aggregation possibilities [START_REF] Pini | Aggregating partially ordered preferences: Impossibility and possibility results[END_REF].

In the literature, different quantitative models based on utilities have been developed to take into account different preference structures. The most widely used model assumes a special kind of independence among attributes called "mutual preferential independence" which ensures that the preferences are representable by an additive utility [START_REF] Krantz | Foundations of Measurement (Additive and Polynomial Representations[END_REF]. Such decomposability makes the elicitation process very fast and simple. However, in practice, preferential independence may fail to hold as it rules out any interaction among attributes. Some generalizations have thus been investigated. For instance utility independence on every attribute leads to a more sophisticated form called multilinear utilities [START_REF] Bacchus | Graphical models for preference and utility[END_REF]. The latter are more general than additive utilities but they still cannot cope with many interactions between attributes. To increase the descriptive power of such models, GAI (generalized additive independence) decompositions have been introduced by [START_REF] Fishburn | Utility Theory for Decision Making[END_REF], that allow more general interactions between attributes [START_REF] Bacchus | Graphical models for preference and utility[END_REF] while preserving some decomposability. Such a decomposition has been used to endow CP-nets with utility functions (UCP-nets) both under uncertainty [START_REF] Boutilier | UCP-networks; a directed graphical representation of conditional utilities[END_REF] and under certainty [START_REF] Brafman | On generalized additive value-function decomposition[END_REF].

In the same direction [START_REF] Gonzales | GAI networks for utility elicitation[END_REF][START_REF] Braziunas | Local utility elicitation in GAI models[END_REF] propose a general procedure to assess GAI utilities in decision under risk. This one is directed by the structure of a graphical model called a GAI-network and consists in a sequence of questions involving simple lotteries that capture efficiently the basic features of the agent's attitude towards risk. Recently the elicitation of GAI models has been investigated in the context of decision making under certainty. [START_REF] Gonzales | GAI networks for decision making under certainty[END_REF] thus proposes elicitation procedures relying on simple comparisons of outcomes (e.g. questions involve only a subset of attributes or outcomes varying in only few attributes). They also suggest efficient choice procedures to find the GAI-optimal element in a product set, using classical propagation techniques used in the Bayesian net literature.

In this paper, we address group decision making problems in similar contexts and we focus on the determination of a good compromise solution between agents. As usual in works on preferences, we assume that the alternatives to be compared belong to a product set the size of which prevents exhaustive enumeration. We assume that a GAI utility has been elicited for each agent and we tackle the problem of performing efficient choices for the group of agents. The paper is organized as follows: In Section 2, we discuss individual and collective preference representation. After recalling some elements about GAI models and their graphical representation we consider various aggregation criteria to define the notion of compromise between agents. In Section 3, we provide efficient algorithms to determine the best compromise solution for the group of agents. Finally Section 4 reports numerical results obtained on multiagent aggregation problems.

GAI utilities: from individual preference modeling to collective decision making

Before describing GAI models, we shall introduce some notations. Throughout the paper, denotes an agent's preference relation (a weak order) over some set X . x y means that x is at least as good as y. ≻ refers to the asymmetric part of and ∼ to the symmetric one. In practice, X is often described by a set of attributes. For simplicity, we assume that X is the product set of their domains, although extensions to general subsets are possible. In the rest of the paper, uppercase letters (possibly subscripted) such as A, B, X 1 denote attributes as well as their domains. Unless otherwise mentioned, (possibly superscripted) lowercase letters denote values of the attribute with the same uppercase letters: x, x 1 (resp. x i , x 1 i ) are thus values of X (resp. X i ). Subsection 2.1 concerns the representation of the preference of a single agent. We will consider the multiagent decision problem in Subsection 2.2.

Individual Preference Modeling

Under mild hypotheses [START_REF] Debreu | Continuity properties of paretian utility[END_REF], it can be shown that is representable by a utility, i.e., there exists a function u : X → R such that x y ⇔ u(x) ≥ u(y) for all x, y ∈ X . As preferences are specific to each individual, utilities must be elicited for each agent, which is impossible due to the combinatorial nature of X . Moreover, in a recommendation system with multiple regular users, storing explicitly for each user the utility of every element of X is prohibitive.

Fortunately, agent's preferences usually have an underlying structure induced by independencies among attributes that substantially decreases the elicitation effort and the memory needed to store preferences. The simplest case is obtained when preferences over X = X 1 × • • • × X n are representable by an additive utility u(x) = n i=1 u i (x i )

for any x = (x 1 , . . . , x n ) ∈ X . This model only requires to store u i (α) for any α ∈ X i , i = 1, . . . , n. However, such decomposition in not always convenient because it rules out interactions between attributes. When agents preferences are more complex, a more elaborate model is needed as shown below:

Example 1 Consider a set X of menus x = (x 1 , x 2 , x 3 ), with main course x 1 ∈ X 1 = {meat(M), fish(F )}, drink x 2 ∈ X 2 = {red wine (R), white wine(W )} and dessert x 3 ∈ X 3 = {cake(C), sorbet(S)}.
First case. Assume the agent's preferences are well represented by an additive utility u characterized by the following marginal utilities:

u 1 (M) = 4; u 1 (F ) = 0; u 2 (R) = 2; u 2 (W ) = 0; u 3 (C) = 1; u 3 (S) = 0.
Then the utilities of the 2 3 possible menus

x (i) follow: u(x (1) ) = u(M, R, C) = 7; u(x (2) ) = u(M, R, S) = 6; u(x (3) ) = u(M, W, C) = 5; u(x (4) ) = u(M, W, S) = 4; u(x (5) ) = u(F, R, C) = 3; u(x (6) ) = u(F, R, S) = 2; u(x (7) ) = u(F, W, C) = 1; u(x (8) ) = u(F, W, S) = 0;
which yields the following ordering: 6) ≻ x (7) ≻ x (8) .

x (1) ≻ x (2) ≻ x (3) ≻ x (5) ≻ x (4) ≻ x (
Second case. Assume that another agent's ranking is: 6) . This can be explained by: i) a high priority granted to matching wine with main course (red wine for meat, white one for fish); ii) at a lower level of priority, meat is preferred to fish; and iii) cake is preferred to sorbet (ceteris paribus).

x (1) ≻ x (2) ≻ x (7) ≻ x (8) ≻ x (3) ≻ x (4) ≻ x (5) ≻ x (
Although not irrational, such preferences are not representable by an additive utility because x (1) ≻ x (5) ⇒ u 1 (M) > u 1 (F ) whereas x (7)

≻ x (3) ⇒ u 1 (F ) > u 1 (M).

However, this does not rule out less disaggregated forms of additive decompositions such as

: u(x) = u 1,2 (x 1 , x 2 ) + u 3 (x 3 ). For example, u 1,2 (M, R) = 6, u 1,2 (F, W ) = 4, u 1,2 (M, W ) = 2, u 1,2 (F, R) = 0, u 3 (C) = 1, u 3 (S) = 0 would represent .
Third case. Assume that the ranking of a third agent is: (6) . Her preference system is actually a refinement of the previous one. She prefers cake to sorbet when the main course is fish but the opposite obtains when the main course is meat.

x (2) ≻ x (1) ≻ x (7) ≻ x (8) ≻ x (4) ≻ x (3) ≻ x (5) ≻ x
In this case, using similar arguments, it can be shown that the previous decomposition does not fit anymore due to the interaction between attributes X 1 and X 3 . However it is interesting to remark that preferences can still be represented by a decomposable utility of the form: u(x) = u 1,2 (x 1 , x 2 ) + u 1,3 (x 1 , x 3 ), setting for instance:

u 1,2 (M,R) = 6; u 1,2 (F ,W ) = 4; u 1,2 (M,W ) = 2; u 1,2 (F ,R) = 0; u 1,2 (M,C) = 0; u 1,2 (M,S) = 1; u 1,2 (F ,C) = 1; u 1,2 (F ,S) = 0.
Such a decomposition over overlapping factors is called a GAI decomposition [START_REF] Bacchus | Graphical models for preference and utility[END_REF]. It includes additive and multilinear decompositions as special cases, but it is much more flexible since it does not make any assumption on the kind of interactions between attributes. GAI decompositions can be defined more formally as follows:

Definition 1 (GAI decomposition) Let X = n i=1 X i . Let Z 1 , . . . , Z k be some subsets of N = {1, . . . , n} such that N = ∪ k i=1 Z i . For every i, let X Z i = j∈Z i X j . Utility u(•) representing is GAI-decomposable w.r.t. the X Z i 's iff there exist functions u i : X Z i → R such that: u(x) = k i=1 u i (x Z i ), for all x = (x 1 , . . . , x n ) ∈ X
, where x Z i denotes the tuple constituted by the x j 's, j ∈ Z i .

GAI decompositions can be represented by graphical structures we call GAI networks [START_REF] Gonzales | GAI networks for utility elicitation[END_REF] which are essentially similar to the junction graphs used for Bayesian networks [START_REF] Jensen | An introduction to Bayesian Networks[END_REF][START_REF] Cowell | Probabilistic Networks and Expert Systems[END_REF]:

Definition 2 (GAI network) Let X = n i=1 X i . Let Z 1 , .
. . , Z k be a covering of N = {1, . . . , n}. Assume that is representable by a GAI utility u(x) = k i=1 u i (x Z i ) for all x ∈ X . Then a GAI network representing u(•) is an undirected graph G = (V, E), satisfying the following properties:

1.

V = {X Z 1 , . . . , X Z k }; 2. For every (X Z i , X Z j ) ∈ E, Z i ∩ Z j = ∅. For every X Z i , X Z j s.t. Z i ∩ Z j = T ij = ∅, there exists a path in G linking X Z i and X Z j s.t.

all of its nodes contain all the indices of T ij (Running intersection property). Nodes of

V are called cliques. Every edge (X Z i , X Z j ) ∈ E is labeled by X T ij = X Z i ∩Z j and is called a separator.
Cliques are drawn as ellipses and separators as rectangles. In this paper, we shall only be interested in GAI trees, i.e., in singly-connected GAI networks. As mentioned in [START_REF] Gonzales | GAI networks for utility elicitation[END_REF], this is not restrictive as general GAI nets can always be compiled into GAI trees. For any GAI decomposition, by Definition 2 the cliques of the GAI network should be the sets of variables of the subutilities. For instance, if u(a, b, c, d, e, f, g) = u 1 (a, b) + u 2 (c, e) + u 3 (b, c, d) + u 4 (b, d, f) + u 5 (b, g) then, as shown in Figure 1, the cliques are: AB, CE, BCD, BDF , BG. By property 2 of Definition 2 the set of edges of a GAI network can be determined by any algorithm preserving the running intersection property (see the Bayesian network literature [START_REF] Cowell | Probabilistic Networks and Expert Systems[END_REF]).

Collective Decision Making

We consider now a multiagent decision problem involving a set A = {1, . . . , m} of agents. We assume that, for each agent j ∈ A, a GAI utility u j representing her preferences over X has been elicited. For simplicity, we assume that each agent use the same absolute utility scale, so as to have commensurability. Then, a classical way of defining the best compromise solution for the group of agents is to define an overall utility u(x) which gives, for any x ∈ X , the value of x for the group. Thus we consider u(x) = h(u 1 (x), . . . , u m (x)) where h is an aggregation function implicitly defining the type of compromise seek in X . The best compromise solution is obtained by optimizing u over X . When h is nondecreasing in each component, u-optimal solutions are weakly Pareto-optimal (i.e. there is no other solution improving the satisfaction of all the agents). Moreover, if h is strictly increasing in each component then u-optimal solutions are Pareto-optimal (i.e. there is no other solution improving the satisfaction of an agent without decreasing the satisfaction of another).

If h is linear, then u is the sum of GAI utilities and, as such, is itself a GAI utility. Then the problem reduces to a monoagent decision problem with a GAI utility. However, linear aggregation functions are not good candidates as they may lead to choose a solution having a very ill-balanced utility profile. For example, consider a problem with 3 agents and assume that X = {x, y, z, w} with u 1 (x) = 0, u 2 (x) = u 3 (x) = 100, u 2 (y) = 0, u 1 (y) = u 3 (y) = 100, u 3 (z) = 0, u 1 (z) = u 2 (z) = 100, u 1 (w) = u 2 (w) = u 3 (w) = 65. All solutions except w are unacceptable for at least one agent. Thus w is the only possible compromise solution; yet it cannot be obtained by maximizing a linear combination (with positive coefficients) of agent utilities. To find better compromise solutions, the following non-linear criteria seem more adequate:

The maximin criterion: u(x) = min j∈A u j (x), to be maximized over X . This criterion amounts to maximize the satisfaction of the least satisfied agent.

The minimax Regret criterion: u(x) = max j∈A r j (x), where r j = u(x j )u j (x), and x j = Argmax x∈X u j (x) (i.e. x j denotes the optimal solution for agent j). This criterion is to be minimized over X . It represents the maximal regret among agents, the regret r j of agent j being defined as the utility gap between x and x j .

The Tchebycheff criterion: u(x) = max j∈A w j r j (x) where w j are positive coefficients. This criterion is to be minimized over X . It represents the distance (w.r.t. a weighted Tchebycheff norm) between two utility profiles: (u 1 (x), . . . , u n (x)) obtained with solution x, and the ideal utility profile (u 1 (x 1 ), . . . , u m (x m )) corresponding to a fictitious ideal situation (generally not feasible) in which all agents are optimally satisfied simultaneously. This ideal point is an upper bound of the set of Pareto non-dominated solutions. Tchebycheff criterion is a standard tool for generating compromise solutions in multiobjective optimization [START_REF] Steuer | An interactive weighted Tchebycheff procedure for multiple objective programming[END_REF]. It can be seen as a sophistication of the minimax regret criterion using coefficient defined by w j = ω j /(u(x j )-u j * ) where ω j is the weight attached to agent j and u j * = min k∈A u k (x j ). The term 1/(u(x j )u j * ) is a normalization factor. It can be used as a correcting factor when the range of utility values attached to solutions significantly varies from an agent to another. It can also be useful when the agents'utilities are not commensurate. The weights allow to modulate the importance of agents and to control the type of compromise. As shown in [START_REF] Wierzbicki | On the completeness and constructiveness of parametric characterizations to vector optimization problems[END_REF], any Pareto optimal solution can be obtained by optimizing the Tchebycheff criterion with appropriate choices of ω j .

The above aggregation functions are weakly increasing w.r.t. each component, which only ensures weak-Pareto optimality. However, they might be slightly modified to become strictly increasing (so as to generate Pareto-optimal solutions). For example, it is sufficient to add (resp. subtract) ǫ i∈A u i (x) for maximization (resp. minimization), ǫ being an arbitrarily small positive value. We discuss in the next section the optimization of each of the above functions to determine the better compromise solutions between agents.

Algorithms

The ranking approach for compromise search

Determining the optimal compromise solution among agents using a function of type u(x) = h(u 1 (x), . . . , u m (x)) is not trivial because we face two difficulties: the combinatorial nature of X and the possible non-decomposability of function u (h is not linear). For example, if h = min (maximin utility), the determination of the best compromise solution is NP-hard as soon as there are n ≥ 3 attributes, m ≥ 2 agents, each having a GAI utility function including at least one factor of size greater than or equal to 3. This can be proved using a reduction from 3-SAT. Indeed, consider an instance of 3-SAT with n variables and m clauses. To each variable, we associate a Boolean attribute X i and to any clause C j over variables we associate an agent with Boolean function u j . For instance C j = x ∨ y ∨ ¬z will be represented by function u j (x, y, z) = 1 -(1x)(1y)z. Hence, the optimal value of the maximin optimization problem over X = X 1 × • • • × X n with functions u 1 , . . . , u m is 1 if and only if the initial 3-SAT problem is feasible. Similar reductions might be proposed for minimax regret and Tchebycheff criteria which establish the complexity of the search of a good compromise solution. To overcome the problem and be able to optimize a non-decomposable function f on X , we suggest resorting to a ranking approach based on the following 3-stage procedure:

Step 1: scalarization. we reformulate the problem as a monoagent problem, using an overall criterion g(x) defined as a linear combination of individual utilities. Such a function is easier to optimize than f since, as the sum of GAI functions, it is also a GAI function.

Step 2: ranking. we enumerate the solutions of X from best to worst using function g(x). Here, an efficient ranking algorithm exploiting the GAI structure of g to speed-up enumeration is needed. This point will be the core of subsection 3.2.

Step 3: stopping condition. we need to stop enumeration as early as possible due to the size of set X . This can be done efficiently using the following proposition.

Proposition 1 Consider two functions f and g defined from R n into R, to be minimized over X , and such that f(x) ≥ g(x) for all x ∈ X . Let x 1 , ..., x k be the ordered sequence of k-best solutions generated during Step 2 with function g,

if g(x k ) ≥ f(x * ) with x * = Argmin i=1,...,k f(x k ) then x * is optimal for f, i.e. f(x * ) = min x∈X f(x). Proof. For any i > k, we have, by construction, f(x i ) ≥ g(x i ) ≥ g(x k ). Since g(x k ) ≥ f(x * ) by hypothesis we get f(x i ) ≥ f(x *
) which shows that no solution found after step k in the ranking can improve the current best solution x * . 2

This simple result can be applied to criteria introduced in the previous section. The following table gives g, the GAI approximation to be used, for any criterion f considered: criterion f(x) g(x) maximin min j (u j (x)) -1/m j u j (x) minimax regret max j (r j (x))

1/m j r j (x) Tchebycheff max j (w j r j (x)) 1/m j w j r j (x)

Since 1/m j r j (x) only differs from -1/m j u j (x) by a constant term, the same ranking algorithm can be used for maximin and minimax regret criteria. Tchebycheff is just an extension using weights w j and does not raise additional issues. Let us now explain how to proceed to rank elements of X with a GAI function g (step 2).

Ranking using a GAI function

The ranking procedure we present in this subsection heavily relies on another one designed to answer choice queries, that is, to find the preferred tuple over X . To avoid exhaustive pairwise comparisons which would be too prohibitive due to the combinatorial nature of X , both procedures take advantage of the structure of the GAI network to decompose the query problem into a sequence of local optimizations, hence keeping the computational cost of the overall ranking task at a very admissible level. We first briefly present the choice algorithm and, then, derive the general ranking procedure. The former corresponds to solving:

max x∈X u(x 1 , . . . , x n ) = max x∈X i u i (x Z i ). (1)
The optimum can be found efficiently by exploiting the following properties:

1. the max over X 1 , . . . , X n of u(X 1 , . . . , X n ), can be decomposed as max X 1 . . . max Xn u(X 1 , . . . , X n ), and the order in which the max's are performed is unimportant;

2. if u(X 1 , . . . , X n ) can be decomposed as f() + g() where f() does not depend on X i , then max X i [f() + g()] = f() + max X i g();

3. in a GAI-net, the running intersection ensures that a variable contained in an outer clique C (i.e. a clique with at most one neighbor) but not contained in C's neighbor does not appear in the rest of the net.

Properties 2 and 3 suggest computing the max recursively by first maximizing over the variables contained only in the outer cliques as only one factor is involved in these computations, then adding the result to the factor of their adjacent clique, remove these outer cliques and iterate until all cliques have been removed. This leads to the following algorithm:

Function Collect(clique C i , F )
01 for all C j in {cliques adjacent to C i }\F in the GAI-net do 02 let S ij = C i ∩ C j be the separator between C i and C j 03 let u * j be defined on S ij by Collect(C j , {C i })

04 substitute u i (x C i ) by u i (x C i ) + u * j (x S ij ) for all x C i 's 05 done 06 if F = ∅ then 07 let C j be the only clique ∈ F and let S ij = C i ∩ C j 08 let M * i (x S ij ) = Argmax{u i (y C i ) : y S ij = x S ij } and let u * i (x S ij ) = u i (M * i (x S ij )) for all x S ij in X k ∈S ij X k 09 store matrix M * i in separator S ij and return u * i 10 endif
This function recursively reduces Eq. ( 1) by removing one by one all the subutilities (by extracting their max). Thus, calling function Collect on any clique returns the value of the utility of the most preferred element. For instance, on the example of Figure 1, applying Collect(BCD, ∅) results in the message propagations described in Figure 2, where: As for ranking, consider the example of Fig. 2. Assume that Optimal choice returned x * =(â, b, ĉ, d, ê, f, ĝ). Then, the next best tuple, say x 2 , differs from x * by at least one attribute, i.e. there exists a clique C i such that the projection of x 2 on C i differs from that of x * . As we do not know on which C i the difference occurs, we can test all the possibilities and partition the feasible space into: The construction of the above sets follows the decomposition advocated by [START_REF] Nilsson | An efficient algorithm for finding the M most probable configurations in probabilistic expert systems[END_REF]: the cliques in which the attributes are constrained to be different from those of x * are enumerated in the order in which the cliques are called by function Collect within the call to Optimal choice. Sets 1 to 5 above thus correspond to a collect phase encountering successively cliques (B, C, D), (B, D, F ), (B, G), (C, E) and(A, B). Finding the best element in a given Set is essentially similar to finding the optimal choice except that lines 02 and 06 in function Instantiate need be modified to avoid some instantiations (like ( b, ĉ, d)).

Assume now that the second best tuple, say x 2 = (a 2 , b 2 , ĉ, d 2 , ê, f, g 2 ), is the optimal choice of Set 1. Then the next tuple, x 3 , is the best tuple that is different from both x * and x 2 . It can be retrieved using the same process. As x 2 is in Set 1, we should substitute Set 1 by the sets below to exclude x 2 and, then, iterate the same process: functions with the same structure. We generated test data for variables of domain sizes 2, 5 and 10, resp. giving problems with 2 20 , 5 20 and 10 20 possible configurations.

Results

The As it can be seen, we obtained average times ranging from 0.1 to 4.7 seconds, depending on the compromise criterion and the attributes domain size. Finding the maximin compromise solution required the enumeration of more solutions than minimax Regret and Tchebycheff. However, we can see that the most prominent factor is the attributes domain size. Fortunately, the number of elements that need be enumerated before returning the solution increases at a much lower rate than the problem size. For instance, from 20 attributes of domain size 5 to 20 attributes of domain size 10, the number of configurations is multiplied by over 10 6 while, at the same time, the average number of solutions enumerated increased by a factor less than 3. We also ran experiments where each agent had a different GAI decomposable preference structure. In these cases, to generate the aggregated GAI network we triangulated the Markov graph induced by the subutilities of all the agents. The more the discrepancy between the agents structures, the larger the cliques, and the less efficient our algorithm. Whenever the GAI network structures were very different, it turned out to be impossible to conduct the ranking procedure due to the too large amount of memory required to fill the cliques. However, there are many practical situations where interacting attributes are almost identical for all agents, the difference between individual utilities being mainly due to discrepancies in utility values.

Conclusion

In this paper we have shown how GAI-networks could be used not only to efficiently perform individual recommendations (choice and ranking) on combinatorial sets, but also to solve collective recommendation requests for multiagent decision problems. The proposed procedure allows the determination of various types of compromise solutions and remains very efficient provided the number of agents is not too important. It might be used in many real-world situations like preference-based design of an holidays-trip for a

Figure 1 :

 1 Figure 1: A GAI tree

Figure 3 :

 3 Figure 3: The Instantiation phase

Set 1 :

 1 (B, C, D) = ( b, ĉ, d) Set 2: (B, C, D) = ( b, ĉ, d) and (B, D, F ) = ( b, d, f) Set 3: (B, C, D, F ) = ( b, ĉ, d, f) and (B, G) = ( b, ĝ) Set 4: (B, C, D, F, G) = ( b, ĉ, d, f, ĝ) and (C, E) = (ĉ, ê) Set 5: (B, C, D, E, F, G) = ( b, ĉ, d, ê, f, ĝ) and (A,B) = (â, b)

  average results (t: times in ms and #gen: number of generated solutions) over 100 runs are summarized below:

	Domain	maximin	minimax Regret Tchebycheff
	size	t(ms) #gen t(ms) #gen t(ms) #gen
	2	371 9145 118 2437	96	1916
	5	2784 60020 1100 22364 1052 21640
	10	4703 99709 3934 78518 3104 60479

Consequently, the optimal tuple can be obtained by propagating recursively the attributes instantiations (the M i 's) from clique BCD toward the outer cliques, as shown on Figure 3. This leads to the following algorithm:

This justifies the following algorithm:

01 let x * be the tuple resulting from Optimal choice 02 let S = {Sets i} as described above and let kbest = ∅ 03 for each Set i, let opt(Set i) be the optimal choice in Set i 04 for i = 2 to k do 05 let Set j be an arbitrary element of {Set j ∈ S : opt(Set j) ≥ opt(Set p), Set p ∈ S} 06 let x i , the ith best element, be opt(Set j) 07 add x i to kbest and remove Set j from S 08 substitute Set j in S by sets ⊇ {x i } as described above 10 return kbest

Numerical Tests

To evaluate our approach in practice, we have performed experiments on various instances of the multiattribute multiagent search problem. We have recorded computation times and the number of solutions generated before returning the optimal compromise solution for each of the three criteria discussed in the paper. The experiments were performed on a 3.2GHz PC with a Java program.

Test data

To run the experiments, we generated synthetic data for GAI-decomposable preferences. All GAI decompositions involved 20 variables, with 10 subutilities u i (x Z i ) of domain size |x Z i | randomly drawn between 2 to 4. It does not seem realistic to consider higher-order interactions as far as human preference modeling is concerned (such complex interaction might actually be very difficult to assess in practice). Each u i 's domain variables were randomly selected from the set of all variables. For variables that were not selected in any subutility function, we created unary subutilities. Next, we created 5 different utility functions for the structure previously generated, representing the preferences of 5 agents. For each subutility function u j i of an agent j, we first generated its maximum value max(u j i ), in the interval [0, 1]. Then we uniformly generated the utility values for all configurations of u j i in the interval [0, max(u j i )]. This gave us 5 different GAI-decomposable utility group, preference-based configuration of a car for the family, or for content-based movie recommendation tasks for a group of friends.

Further sophistication of our approach are possible, for instance using AND/OR trees [START_REF] Dechter | AND/OR search spaces for graphical models[END_REF][START_REF] Marinescu | AND/OR tree search for constraint optimization[END_REF] within the GAI structure instead of computing the whole u * i 's during the collect phases and performing substitutions of whole utility tables. The ranking algorithm can therefore be improved using a dynamic selection of the clique passed in argument to the collect/instantiation phases (depending on the tuples ranked so far). This is left for further research.


Jean-Bernard Chatelain
email: jean-bernard.chatelain@u-paris10.fr

Explicit Lagrange Multiplier for Firms Facing a Debt Ceiling Constraint

Keywords: JEL Classification: D92, G32 Investment, Credit Rationing

This paper provides the explicit expression of investment facing a binding debt ceiling and the explicit expression of the Lagrange multipliers related to the binding debt ceiling constraint. This result allows to check for misspecification of the parameterizations of these Lagrange multipliers used in Euler investment equations tests during the 1990's.

Introduction

Recent papers tested the Euler equation for capital of the neoclassical model of investment for an infinetely living firm facing quadratic adjustment costs, taxation, imperfect competition on the goods market and an exogenous debt ceiling constraint (see e.g. [START_REF] Gertler | Interest Rate Spreads, Credit Constraints, and Investment Fluctuations: An Empirical Investigation[END_REF], [START_REF] Whited | Debt, Liquidity Constraints and Corporate Investment : Evidence from Panel Data[END_REF] and subsequent papers surveyed in Schiantarelli [1996]). In his Journal of Economic Literature survey on the economics of investment, [START_REF] Chirinko | Business Fixed Investment Spending: A Critical Survey of Modeling Strategies, Empirical Results, and Policy Implications[END_REF] pp. [1902][1903][1904] mentioned that, in these Euler equation tests, "the endogenous variables that parameterize the Lagrange multiplier related to this [borrowing] constraint (such as cash flow and net worth) are not accounted for explicitly in specifying the econometric equation, thus blurring econometric interpretations of the statistical tests. It remains uncertain whether significant liquidity and net worth variables are capturing a structural element heretofore missing in the investment equation or are merely reflecting general misspecification." This Lagrange multiplier is parameterized in an ad hoc fashion in the belief that "the first order conditions do not provide an analytical answer" [START_REF] Whited | Debt, Liquidity Constraints and Corporate Investment : Evidence from Panel Data[END_REF](Whited [ , p. 1435]]). In this note, we provide the analytical answer which was missing. This Lagrange multiplier is related to the gap between the standard neoclassical investment behaviour and the (explicit) credit constrained investment. Both expressions are derived in this note, which allows to check for misspecification in these empirical works.

Explicit Lagrange Multiplier

The standard partial equilibrium neoclassical model of investment begins with an expression for the value of the firm, which in turn stems from the arbitrage condition governing the valuation of shares. The after-tax return to the owners of the firm at time t reflects capital appreciation and current dividends. In equilibrium, if the owners are to be content holding their shares, this return must equal (1m t )r 0 t the after tax nominal return on riskless (government) bonds between period t and period t + 1 (r 0 t represents the nominal return before income tax and m t is the personal income tax on dividends and interest income in period t):

(1 -c t ) (E t [V i,t+1 -S i,t+1 ] -V it ) + (1 -m t )θ t E t [d i,t+1 ] V it = (1 -m t )r 0 t (2.1)
where V it is the value of the firm i at time t, S it denotes the value of new shares issued at time t+1, c t is the accrual-equivalent capital gains tax rate, θ t is the dividend received by the shareholder when the firm distributes one unit of post-corporate tax earnings 1 . Therefore, the taxe rate on dividends is (1m t )θ t . E t is the expectation operator conditional on information known at time t. The after-tax capital gain of the current shareholders thus consists of the change in the market value of the firm less the component of this change due to new share issues. The tax discrimination parameter γ t = (1m t )θ t / (1c t ) determines the relative tax advantage of dividend income against capital gains. The dividends of the firm i at time t are d it . In the absence of bubbles, solving the capital market arbitrage condition yields the following expression for the firm's market value at time zero:

max {p it ,I it ,L it ,d it ,S it, K it ,B it } ∞ t=0 V i,t=0 = E t t=+∞ X t=0 Ã s=t-1 Y s=0 β is ! (γ t d it -S it ) (2.2)
where the firm's one period nominal discount factor is:

β it = 1 1 + ³ 1-m t 1-c t ´r0 t (2.3)
The entrepreneur in firm i chooses dividends, investment, labour and price of output in maximizing the present value of dividends d i,t on date t in a infinite horizon, with the discounted rate of the opportunity cost of internal funds, subject to several constraints. The "flow of funds" constraint defines firm dividends. Cash inflows include sales, new share issues, and net borrowing, while cash outflows consist of dividends, factor and interest payments, and investment expenditures:

d it = (1 -τ ) (p it F (K i,t-1 , N it ) -p it Ψ(I it , K i,t-1 ) -w t N it -i t-1 B t-1 ) +S it + B it -B i,t-1 -p I it I it , (2.4)
where I it is its investment at time t, K it is capital, N it a vector of variable factors of production for firm i at time t, F

(K i,t-1 , N it ) the firm's revenue function (F K > 0,F KK < 0), Ψ(I it , K i,t-1
) the cost of adjusting the capital stock (Ψ I 0, Ψ II > 0, Ψ K < 0, Ψ IK < 0), w t a vector of nominal factor prices at time t, i it the nominal interest rate on debt at time t, B it = the value of net debt outstanding for firm i at time t, p it = the price of final goods at time t, p I it = the price of capital goods at time t (incorporating tax considerations); τ = the corporate income tax rate, against which interest payments are assumed to be deductible.

The firm faces the capital accumulation constraint (with a related Lagrange multiplier λ K it ):

K it = I it + (1 -δ) K i,t-1
where δ a constant rate of economic depreciation, an exogenous debt ceiling constraint (B it ≤ B * it , related Lagrange multiplier λ B it ), and a positivity of dividends constraint (d it ≥ 0, related Lagrange multiplier λ d it ). The firm also faces a downward sloping demand function ϕ (p it ) for its product with an absolute value of the elasticity denoted e = -ϕ 0 (p it ) p it /ϕ (p it ). Demand is equal to supply, i.e. output net of adjustment costs, so that the value of sales is the following function of inputs after inversion of the demand function:

ϕ -1 (F (K i,t-1 , N it ) -Ψ(I it , K i,t-1 )) [F (K i,t-1 , N it ) -Ψ(I it , K i,t-1 )
]. The derivative of sales with respect to an input X is therefore:

" 1 + [F (K i,t-1 , N it ) -Ψ(I it , K i,t-1 )] p it h ϕ -1 i 0 # p it [F X (K i,t-1 , N it ) -Ψ X (I it , K i,t-1 )]
(2.5) I denote the inverse of the markup factor µ = 1 -1 e > 0. The case of a price taker perfect competitor is given by setting the parameter µ to unity each time it appears before the output price in the following equations.

Dividends are substituted directly in the Lagrangean, using the flow of funds constraint as well as investment by the capital accumulation equation. The first order conditions for capital K it (Euler equation) is:

E t β it [ γ t+1 + λ d i,t+1 γ t + λ d it [µp i,t+1 F K (K it , N it+1 ) -µp i,t+1 Ψ K (I i,t+1 , K it ) + (1 -δ)µp i,t+1 Ψ I (I i,t+1 , K i,t ) + (1 -δ)p I i,t+1 1 -τ t+1 ]] = p it µΨ I (I i,t , K i,t-1 ) + p I it 1 -τ t (2.6)
In the Euler equation for capital, the discount factor turns to be "corrected" by a multiplicative factor

Γ it = ³ γ t+1 + λ d i,t+1
´/ ³

γ t + λ d i,t
´. The marginal condition for debt is:

E t β it Γ it = 1 - λ B it γt+λ d it 1 + [1 -τ t+1 ] i it (2.7)
It reveals that the "corrected" discount factor β it Γ it is equal to a discount factor using the net of tax marginal cost of debt as a discount rate if λ B it = 0, and else that the discount factor decreases with the Lagrange multiplier of the debt ceiling constraint (i.e. the discount factor should use the shadow interest rate that would have accepted the firm if she was not facing a quantitative constraint).

Γ it has been parameterized in an ad hoc manner in several papers following the first ones surveyed by [START_REF] Chirinko | Business Fixed Investment Spending: A Critical Survey of Modeling Strategies, Empirical Results, and Policy Implications[END_REF]. The aim of this note is to find its explicit form, which amounts to find the explicit form for λ d it . The Lagrange multiplier related to a quantitative constraint is generally an increasing function of the gap between the "notional" denoted I UC it and the "constrained" control variable (investment for the firm facing credit rationing) denoted I C it . The expression γ t + λ d it is given by the marginal condition on investment in the credit rationing regime:

γ t + λ d it = λ K it p I it + µp it (1 -τ t ) Ψ I (I C it , K i,t -1 ) (2.8)
where the marginal costate variable λ K it is given by the marginal condition on investment in the unconstrained regime (λ d it = 0):

λ K it = γ t h p I it + µp it (1 -τ t ) Ψ I (I UC it , K i,t-1 ) i
It is a function of the investment rate I UC it that would have chosen the firm in the absence of financial constraint. A structural specification of Γ it is therefore given by:

Γ it = p I it + µp it (1 -τ t ) Ψ I (I C it , K i,t-1 ) γ t [p I it + µp it (1 -τ t ) Ψ I (I UC it , K i,t-1 )] γ t+1 h p I i,t+1 + µp i,t+1 (1 -τ t+1 ) Ψ I (I UC i,t+1 , K it ) i p I i,t+1 + µp i,t+1 (1 -τ t+1 ) Ψ I (I C i,t+1 , K it ) (2.9)

The case of quadratic adjustment costs

I parameterize the adjustment cost function with its usual quadratic form [START_REF] Whited | Debt, Liquidity Constraints and Corporate Investment : Evidence from Panel Data[END_REF]), so that Ψ I (I it , K i,t-1 ) = α ´.

Ψ(I it , K i,t-1 ) = α 2 ³ I i,t K i,t-1 -ν ´2 K i,t-1
³ I i,t K i,t-1 -ν ´.
On the one hand, when the firm does not face a debt constraint, the usual form is derived by a local approximation near the equilibrium, on the unique stable path. The standard textbook result is that current investment net of long run investment (which has only to replace the depreciation of the long run capital stock) is a linear function of the wedge between the current capital stock and the long term capital stock:

I UC it = δK * it + (σ -1) (K it -K * it ) ( 3 . 1 )
K * it is the long run stock of capital, defined by the Euler equation with stationary values (it depends on the marginal cost of capital on date t corrected by the marginal adjustment costs of long term investment). σ is the eigenvalue of the linearised dynamical discrete time system with an absolute value below one:

σ = 1 2     1 + 1 β it E t p i,t+1 p it - v u u u t   1 - 1 β it E t p i,t+1 p it   2 - 4K * it F KK (K * it , N * it ) α     (3.2)
On the other hand, when the firm faces a binding debt ceiling constraint, the flow of funds equation can be written in the binding debt ceiling regime on date t (B it = B * it ), with no dividends (d it = 0) and with no new share issues (S it = 0):

0 = (1 -τ )   p it F (K i,t-1 , N t ) -p it α 2 Ã I i,t K i,t-1 -ν ! 2 K i,t-1 -w t N t -i i,t-1 B t-1   +B * it -B i,t-1 -p I it I it (3.3)
Dividing the flow of funds equation by the capital stock p I i,t-1 K i,t-1 and using the capital accumulation relation (K it = I it +(1-δ)K i,t-1 ), it follows a quadratic equation for the ratio of the investment rate j it = I it /K i,t-1 depending on the ceiling of the debt/capital ratio

x * it = B * it /p I it K it : 0 = (1 -τ ) µ π(K i,t-1 , N it ) -p it α 2 (j it -ν) 2 -i i,t-1 x i,t-1 ¶ +x * it p I it p I i,t-1 [j it + 1 -δ] -x i,t-1 - p I it p I i,t-1 j it (3.4) π(K i,t-1 , N it ) = [p it F (K i,t-1 , N t ) -w t N t ] /p I it K it
represents the profit rate. The investment rate is an explicit solution of the quadratic equation:

0 = -(1 -τ )p it α 2 j 2 it + " (1 -τ )p it α 2 2v + p I it p I i,t-1 (x * it -1) # j it + C it (3.5)
where :

C it = -(1 -τ )p it α 2 v 2 + (1 -τ )π(K i,t-1 , N it ) +x * it p I it p I i,t-1 [1 -δ] -[1 + (1 -τ )i i,t-1 ] x i,t-1 (3.6) so that 2 : j C it (B * it ) = v + p I it p I i,t-1 x * it -1 (1 -τ )αp it + v u u t " v + p I it p I i,t-1 x * it -1 (1 -τ )αp it # 2 -2 C it (1 -τ )αp it (3.7)
The first term of the Taylor development of this expression with respect to α, the adjustment cost parameter, which is reasonably below one and small, leads to the following expresssion (it corresponds to the case α = 0, i.e. there are no adjustment costs):

j C it (B * it ) = (1 -τ ) (p it F (K i,t-1 , N t ) -w t N t -i i,t-1 B t-1 ) p I it K i,t-1 + B * it -B i,t-1 p I it K i,t-1 (3.8)
Investment depends on after tax cash-flow from operating activities and on the variation of debt. Squared terms of these variables could be added if one takes into account the second order Taylor development with respect to α.

Explanatory variables of Γ it are the explanatory variables of the financially constrained investment and of the unconstrained investment function. Γ it can also be linearised for a small adjustment cost parameter. Then, explanatory variables are the first differences of the variables determining investment facing credit rationing (cash flow from operating activities and the variation of debt) and of the variables related to the unconstrained investment level (the current size of capital of the firm K it and the cost of capital, which determines the long run stock of capital K * it ). This explicit Lagrange multiplier suggests specifications closer to the structural one for Euler equation tests of financial constraints. For example, [START_REF] Whited | Debt, Liquidity Constraints and Corporate Investment : Evidence from Panel Data[END_REF] intuitions for the choice of the financial variables were right. But these variables ought to have appeared in first difference in Γ it . Then, variables related to the unconstrained investment such as the current size of the capital stock and the cost of capital were omitted. Finally, the estimated parameters related to these extra financial variables were not constrained whereas they cannot be anything else than a combination of the parameters to be estimated in the optimization model written at the very beginning, i.e. the mark-up rate µ and the coefficient of adjustment costs α.

Conclusion

This note derives the explicit expression of investment facing a debt ceiling and of the Lagrange multiplier related to a binding debt ceiling constraint. These two results may 2 If the adjustment cost parameter α is small enough, then one obtains v + p I it p I i,t-1

x it -1

(1-τ )αp it < 0, (the ceiling of the debt/capital ratio x it is necessarily below one). The second solution for investment is negative, and therefore irrelevant for the behaviour of a firm facing a debt ceiling constraint.

  The next step is to solve for the investment solution facing a binding debt constraint ³

Under an imputation relationship between corporate and personal taxes, the parameter θ t = 1/ (1 -s t ) where s t is the rate of imputation. Under a classical relationship, θ t is simply unity.


Jean-Bernard Chatelain
email: jean-bernard.chatelain@u-paris10.fr

Mark-up and Capital Structure of the Firm facing Uncertainty

Keywords: capital, pricing, capital market imperfections. JEL Numbers: D42, D24, G32

This note shows that, with pre-set price and capital decisions of firms facing uncertainty and financial market imperfections, price, mark up and the expected degree of capacity utilization (resp. capital) decreases (resp. increases) with the firm internal net worth.

Introduction

In a recent paper, Chevallier et Scharfstein [1996] provided empirical evidence of a relationship between mark up and leverage and proposed a theoretical underpinning based on the "consumer switching cost" model of [START_REF] Klemperer | Markets with Consumer Switching Costs[END_REF]. A complementary approach is proposed in this note. I show that a relationship between price, capital and financial structure obtains when the firm faces uncertainty with ex post risk of excess capacity, as in [START_REF] Kahn | Why is production more volatile than sales? Theory and Evidence on the Stockout-Avoidance Motive for Inventory-Holding[END_REF] and [START_REF] Karlin | Prices and Optimal Inventory Policy[END_REF]. In this model, price depends on expected "tensions" in the goods markets. The higher the probability of excess demand, the higher the market power which determines the markup. Optimal capital depends on the ratio of the mark-up to the cost of capital. The two decisions are linked.

Therefore, introducing [START_REF] Kiyotaki | Credit Cycles[END_REF] incentive problem leading to a liquidity constraint affects not only investment but also price behaviour. The rise of external finance constraint limits capital and increase the probability of excess demand. Simultaneously, the firm rises the price, which lowers expected demand and the probability of excess demand. In so doing, the loss of investment due to the agency problem is partially offset by an increase of market power.

The paper is organized as follows. Section 2 presents the model. Section 3 solves the perfect capital market case. Section 4 solves the financially constrained case. Section 5 concludes.

The model

The production function is clay-clay, with constant returns to scale for capital and labour. Capital is chosen ex ante and defines productive capacities Y C = K/k. The ratio capital /capacity is k. The cost of capital is denoted c. The output market is cleared ex post by an adjustment of hours worked, except if demand is higher than productive capacities:

L = aY for 0 ≤ Y ≤ Y C (2.1)
The productivity of labour is 1/a. The manager is a price-taker for labour and the unit cost of labour is denoted w. The price of capital is taken as numeraire and may be different of the output price.

The entrepreneur faces uncertainty on demand. g(p) is the firm's expected demand. It satisfies the standard general requirements for an unique optimal monopoly price in the certainty case. It is a decreasing function of price p (g(p) ≥ 0, g p (p) < 0 with a price-elasticity e (p) = pg p (p) /g (p) < -1). Demand is zero (g (p) = 0) for all prices such that p ≥ p max . The requirement for a positive production is that the maximal price p max is over the marginal costs of production p max > wa + ck > 0. I assume the function

h(p) = (p -wa -ck) g p (p) + g (p) ( 2 . 2 )
to be continuous and to have a unique zero being the price p c such as wa + ck ≤ p c < p max . If the maximal price p max is infinite (g (p) > 0 for all prices p ≥ 0, I assume that lim p→+∞ g (p) = lim p→+∞ pg (p) = 0 and that the function h(p) is continuous and presents a unique zero for the price p c such as wa + ck ≤ p c . Demand is ug(p), where u is a non-negative random variable of cumulative distribution F , and of a continuous density f , with a mean equal to one (E [u] = 1 where E represents the expectation operator).

Ex-post, firm production is set at the minimum of production capacity and of demand, Y = min(ug(p), Y C). This is based on the following assumption on short run rigidities: ex-post goods market price rigidity, the second-hand market for excess investment does not work, investment and hours worked are not substitutable ex-post [START_REF] Kahn | Why is production more volatile than sales? Theory and Evidence on the Stockout-Avoidance Motive for Inventory-Holding[END_REF] and [START_REF] Karlin | Prices and Optimal Inventory Policy[END_REF]).

The entrepreneur sets ex ante price and capital while maximizing expected profits denoted π(K, p):

2 (K, p) ∈ Argmax π(K, p) = (p -wa)E [Y ] -cK (2.3)
with K ≥ 0 and p ≥ 0. Expected production is:

E[Y ] = E[min(Y C, ug(p))] = g(p) Z x 0 u • dF (u) + Y C Z +∞ x dF (u) (2.4)
where x = Y C/g (p) is the capacity/expected demand ratio, measuring the expected "tensions" on the goods market. By integration by parts, as E[u] = 1 and as u ≥ 0 (so that

R +∞ 0 [1 -F (u)] du = 1
), one has:

E[Y ] = g(p)I(x) where I(x) = Z x 0 1 -F (u) • du (2.5)
I(x) represents the sum of the probabilities of excess demand up to the level of capital related to x.

Following [START_REF] Kiyotaki | Credit Cycles[END_REF], I add two critical assumptions. First the entrepreneur's technology is idiosyncratic: once his production started at date 0, he is the only agent to have the skill necessary for production to occur. If he withdraws his firm specific labour L between date 0 and date 1, there would remain only durable capital K. Second, he cannot precommit to work. He may therefore threaten his creditors by withdrawing his firm specific labour and repudiate his debt contract. Creditors protect themselves from the threat of repudiation. [START_REF] Hart | A Theory of Debt based on the Inalienability of Human Capital[END_REF] give an argument to suggest that the entrepreneur may be able to negotiate the debt (gross of interest) down to the liquidation value of capital, which eventually incurs a transaction cost τ . At the initial date, the entrepreneur can borrow an amount of external finance K -W , where W represents the firm internal net worth, as long as the repayment does not exceed the market value of capital:

(1 + r) (K -W ) ≤ (1 -δ) K ⇔ K ≤ 1 + r r + δ W (2.6)
r represents the real interest rate, δ represents the depreciation rate. The cost of capital c is equal to r + δ.

The Perfect Capital Market Case

In the perfect capital market case, the first order condition with respect to capital is:

(p -wa)(1 -F (x)) -ck = 0. (3.1)
The marginal cost of capital is equal to the marginal profits at full capacity utilisation, corrected by the probability of use of this capacity. The price p has to be strictly over the sum of marginal costs wa + ck to have a strictly positive optimal capital (else 0 < p ≤ wa + ck ⇒ K * = 0).

The first order condition with respect to price is:

0 = " E [Y ] + (p -wa) ∂E [Y ] ∂g (p) g p (p) # p g (p) g (p) E [Y ] (3.2) ⇒ p = η (x) e (p) η (x) e (p) + 1 wa for x > η -1 Ã - 1 e (p) ! (3.3)
where:

0 ≤ η(x) = g (p) E [Y ] ∂E [Y ] ∂g (p) = 1 - xI x (x) I(x) ≤ 1. (3.4)
The elasticity of expected output with respect to price is the chained elasticity of expected output with respect to expected demand η(x) times the the elasticity of expected demand with respect to price. In the certainty case, the elasticity of output with respect to expected demand is indeed equal to 1.

The optimal solution is found by solving the system of the first order conditions. A proof of the existence of optimal price and capital (and therefore of an optimal capacity/expected demand ratio x) for any continuous distribution based on the intermediate value theorem is given in the appendix. Eliminating price provides the optimal ratio x * in an implicit function form:

j (x * ) = 1 -F (x * ) + ck wa η (x * ) e (p) + ck wa = 0 (3.5)
As there exist at least a solution for x, if the function j (x * ) is strictly monotonic for

x > η -1 ³ -1 e(p)
´, then this solution is unique according to the intermediate value theorem. The derivative j x = ck wa e (p) η x (x * )f (x * ) is strictly negative if η x (x * ) > 0. A sufficient condition on the distribution of demand to guarantee η x (x) > 0, that we assume to be fulfilled in what follows, is:

1 ∀x ∈ [0, +∞[ f (x) 1 -F (x) ≥ η(x) x (3.6)
Differentiating the function j leads to:

(-Ae (p) η x (x * ) + f (x * )) | {z } >0 dx * + (-e (p) η(x * ) -1) | {z } >0 dA+ (-Aη(x * )) | {z } <0 de (p) = 0 (3.7)
where A = ck wa represents the relative cost of factors corrected by their productivity. The ratio x * a decreasing function of the real interest rate and of the depreciation of capital and an increasing function of the real wage and of the price elasticity of the demand curve.

The optimal price p * is:

p * = e (p * ) η ³ x * ³ ck wa , e (p)
It decreases with the ratio x * and therefore increases with the cost of capital and decreases the price-elasticity of demand and has an ambiguous dependance on the real wage.

The optimal level of capital K * is:

K * = kg (p * ) x * Ã ck wa , e (p * ) ! . ( 3 . 9 )
It depends negatively on the cost of capital, positively on the real wage and ambiguously on the elasticity of demand.

The Financially Constrained Case

When the finance constraint is binding, the condition giving the optimal stock of capital is now:

K f * = 1 + r r + δ W < K * ⇒ x f = 1 + r r + δ W kg (p f ) < x * (4.1)
Capital depends negatively on the interest rate, on the depreciation of capital and positively on the firm internal net worth.

The marginal condition on price is unchanged. Eliminating price provides the optimal ratio x f in the financially constrained regime (by definition of x, one has:

p = g -1 ³ K kx ´): l (x) = e (p) η (x) e (p) η (x) + 1 wa -g -1 Ã K f kx ! = 0. (4.2)
It is easy to prove with the intermediate value theorem that the solution for x is unique as lim x→η -1 ( -1 e(p) ) l (x) > 0 , lim x→+∞ l (x) < 0 and l x (x) < 0 (with η x (x) > 0). Differentiating totally l (x) leads to:

0 = à e (p) η x (x) wa [e (p) η (x) + 1] 2 + g -1 p à K f kx ! K f kx 2 ! | {z } <0 dx f -g -1 p à K f kx ! 1 kx | {z } >0 dK f + e (p) η (x) a e (p) η (x) + 1 | {z } >0 dw+ η (x) wa [e (p) η (x) + 1] 2 | {z } >0 de (p)
As in the perfect capital market case, the ratio x f is a decreasing function of the real interest rate and of the depreciation of capital and an increasing function of the real wage and of the price elasticity of the demand curve. But in the financially constrained regime, it is also an increasing function of the firm internal net worth.

The price when the financial constraint binds, denoted p f , is:

p f = e ³ p f ´η ³ x f é (p f ) η (x f ) + 1 wa (4.3)
Price is a decreasing function of the ratio x. As x f < x * , the price when the finance constraint is binding is higher than the price chosen in the perfect capital market case. It is a decreasing function of the price elasticity of the demand curve and of the firm internal net worth and an increasing function of the real interest rate and of the depreciation of capital. Its dependance on the real wage is ambiguous. 2The optimal expected degree of capacity utilisation E [Y ] /Y C = I(x * )/x * is also a decreasing function of the ratio x, due to the concavity of the function I(x). Therefore, it is an increasing function of the real interest rate and of the depreciation of capital and a decreasing function of the real wage and of the price elasticity of the demand curve, in the perfect capital market case. When the financial constraint binds, it is also a decreasing function of the firm internal net worth.

The condition on financial structure for a shift of regimes is obtained as by the solution (x, p, W ) of the system of the two first order conditions and of the binding financial constraint. For a sufficiently high level of the firm internal net worth (an implicit function W * (r, w)), the firms shifts to the uncontrained regime.

Conclusion

This note shows that with pre-set price and capital decisions of firms facing uncertainty and financial market imperfections, price, mark up and the expected degree of capacity utilization (resp. capital) decreases (resp. increases) with the firm internal net worth. Further research could consider dynamic general equilibrium extensions of this model to investigate the cyclical properties of mark-up, capital or inventories, the degree of capacity utilization and financial structure.

Unimodal distributions such as the lognormal distribution, the uniform distribution and the exponential distribution fulfill this condition.

The dependance of the mark up p f /(wa + ck) on the cost of capital is also ambiguous.

Appendix: Existence of the optimal solution (K, p)

The second order necessary and sufficient condition with respect to capital is always fulfilled except if the density of the distribution is zero for the ratio x * :

We maximize profit with respect to price incorporating the marginal condition on the choice of capital : p * ∈ Arg max π(K * , p). The intermediate value theorem applied to the first order derivative of expected profits with respect to price π p helps to prove that this derivative presents at least a zero which is a local maximum.

First, when p = wa + ck, optimal capital is zero (x * = F -1 (0) = 0) so that expected profits are zero. Second, when the price tends to infinity, expected profits tend to be negative: as

and knowing the hypotheses lim p→+∞ g (p) = lim p→+∞ pg (p) = 0, one has:

To apply the intermediate value theorem, it is now only sufficient to prove that π p (K, p = wa + ck) > 0, which is done as follows:

(5.4)

is the derivative of profits where there is no uncertainty. By assumption, it is zero for the optimal monopoly price p c . Therefore, h (p) > 0 for values of the price such that: wa + ck < p < p c . Hence, π p (K * , p) > 0 for values of the price such that: wa + ck < p < p c . QED.

One remarks that price under certainty is lower than price under uncertainty: π p (K c , p c ) > 0. When the random shock is multiplicative, increasing the price implies a lower standard error on sales:

There may be n local maxima (and n -1 local minima) which may be related to the modes of the density function f . A sufficient condition for unicity is to have a monotonous elasticity η(x).


Hervé Herbin

Dr Nathalie Picqué
email: nathalie.picque@ppm.u-psud.fr

Guy Guelachvili

Evgeni Sorokin

Irina T Sorokina

N 2 O weak lines observed between 3900 and 4050 cm -1 from long path absorption spectra

Previously unobserved nitrous oxide transitions around 2.5 µm are measured by intracavity laser absorption spectroscopy (ICLAS) analyzed by time-resolved Fourier transform (TRFT) spectrometer. With an accuracy of the order of 10 -3 cm -1 , measured positions of 1637 assigned weak transitions are provided. They belong to 42 vibrational transitions, among which 33 are observed for the first time. These data are believed to be useful in particular to monitoring atmosphere purposes.

In this note, intracavity laser absorption spectroscopy (ICLAS) coupled (1) with timeresolved Fourier transform (TRFT) spectrometer is applied to the measurement of previously unobserved N 2 O transitions around 2.5 µm. High resolution absorption spectra of N 2 O in natural isotopic abundance are recorded around 4000 cm -1 with kilometric absorption path lengths. Their analysis reveals the observed weak transitions belong to 42 vibrational transitions, among which 33 are observed for the first time. These data are believed to be useful in particular for atmospheric applications.

The laser, installed in a vacuum chamber, is made of Cr 2+ : ZnSe amplifying medium inserted in X-fold cavity. It is optically pumped with an Er 3+ fiber doped laser emitting at 1.6 µm. The pumping beam is chopped by an acousto-optic modulator. The laser build-up is recorded with a TRFTS equipped with two InSb detectors cooled at 77 K. More details on the experimental setup may be found in the instrumentally oriented paper (2) and in (3) where new data measurements and analysis for 23 C 2 H 2 molecular bands located around 4000 cm -1 are also reported.

Three N 2 O time-resolved spectra (numbered 508, 509, 510) have been recorded ( 4) with natural sample pressures respectively equal to 3.49, 70.62, 70.58 hPa (2.62, 53.0, and 52.9 Torr). The gas was inserted in the vacuum chamber. This provides, with the elimination of the parasitic atmospheric absorption, the advantage of a laser cavity filling ratio practically equal to unity. All TRFT spectra of the laser emission were recorded with 64 time samples, 1.6 µs time resolution and 32 co-additions. Unapodized spectral resolutions and recording times were respectively 0.037, 0.037, 0.007 cm -1 and 5, 5, and 25 minutes.

Figure 1 displays the general temporal behavior of the spectrum nb. 510 with restricted spectral resolution. The laser line is narrowing with increasing generation times reaching at most 120 µs. With 7.1 km absorption path length the spectrum covers 150 cm -1 , approximately from 3900 to 4050 cm -1 . With 33.5 km absorption path length the spectral coverage is restricted to 60 cm -1 , from 3955 to 4005 cm -1 . As in Ref. (3), it has been checked that no deviation to the linear evolution versus the generation time of the peak absorbance is observed. No attempt was made to tune the Cr 2+ : ZnSe laser.

Wavenumber scale of the spectra have been calibrated against lines from residual water vapor in the laser chamber, using [START_REF] Toth | [END_REF]. Line positions reported here were measured in the 3 temporal samples of spectrum 510. Their sequence number is 6, 16, 26 corresponding to the equivalent absorption paths 7, 12, 17 km. Their respective wavenumber scales were first checked to be consistent within an average of 4 10 -4 cm -1 . Full width at half maximum of the N 2 O profiles in spectrum 510 (pressure: 70.58 hPa) is of the order of 20 10 -3 cm -1 , revealing as expected contribution of collisional broadening. The accuracy of the line position measurements is of the order of 10 -3 cm -1 . Only well-resolved and unsaturated lines were taken into account. Line sequences detected with a Loomis-Wood program (6), were left unprocessed and are not reported in this note, when at least 15 lines were not fitting the selection criteria. Altogether, 42 bands are observed. Among them, 32 belong to 14 N 2 16 O, 4 to 14 N 15 N 16 O, 4 to 15 N 14 N 16 O, and 2 to 14 N 2 18 O. The 14 N 2 16 O energy level is observed for the first time. In order to appreciate the validity of our measurements, least-squares fits of individual bands were performed using the polynomial expression : 4 with X = J(J+1) The lower state constants were held fixed in the fits to the excellent values given in (7) and (8). Only the lines measured in our spectra were processed in the fits.

16 O bands consist of 1 Σ-Σ, 11 Σ-Π, 2 Σ-Φ, 2 Π-Φ, 4 Π-Π, 8 Π-∆
E(v,J) = G +BX -DX² +HX 3 + LX
The 42 observed bands are summarized with their assignments and calculated band centers in Table 1. A full resolution small part of the temporal sample n° 6 already shown in Figure 1 is given on Figure 2 with spectral assignments of the resolved lines. In the Journal supplementary material, 3 additional tables are given. Table 2 reports for 14 N 2 16 O the effective parameters obtained from our calculations and their corresponding values taken in (7) and (8). Table 3 reports similar results for the isotopologues 14 N 15 N 16 O, 15 N 14 N 16 O, and 14 N 2 18 O. Table 4 is aimed to be a convenient tool. It provides in increasing order 1637 measured line positions, with their corresponding "observed -calculated" values and their isotopologue and rovibrational assignments.

The work has been supported by the French-Austrian exchange program Amadeus and the FWF project P17973.

  and 4 ∆-Φ transitions. All the 14 N 15 N 16 O, 15 N 14 N 16 O, and 14 N 2 18 O bands are Σ-Π transitions. Practically all the observed lines are transitions between already known energy levels. Only the 13312 14 N 2

Figure 2 :

 2 Figure 2: Limited portion of the time-component n° 6 shown on Figure 1. Spectral resolution is 7.1 10 -3 cm -1 . For the sake of clarity all assignments are not given.

Table 1 :

 1 N 2 O bands observed in the present TRFT-ICLAS spectra between 3901 and 4050 cm -1 . Energy level notation is v 1 v 2 l v 3 x. The v's and l are the usual vibrational quantum numbers. x = 1 or 2 stand for the usual e and f notations. Numbers in parentheses after the band center values give one standard deviation in units of the least significant digits. N is the total number of observed lines. RMS : Root Mean Square of the polynomial fit. On the plot, two consecutive components, at an intermediate 0.071 cm -1 apodized resolution, are 8 µs from each other. This corresponds to a 2.4-kilometer increase of the equivalent absorbing path L.

	isotop. a )	Transition	Band center ν 0	N lines Observed J max	RMS
		upper lower	(cm -1 )		P	Q	R (x 10 4 cm -1 )
	446	03111 00001	3931.247641(20)	70	25	-	64	0.4
	446	40001 02001	3937.54475(17)	64	15	-	65	6
	446	03311 00001	3948.28416(28)	31	27	-	51	7
	446	41101 03301	3955.91156(29)	30	43	-	54	6
	446	41102 03302	3955.91221(42)	30	46	-	52	7
	446	41101 03101	3973.75842(18)	55	44	-	63	5
	446	41102 03101	3973.75843(33)	17	-	51	-	4
	446	41101 03102	3973.75850(46)	13	-	46	-	6
	446	41102 03102	3973.75863(14)	65	61	-	66	5
	446	14011 03301	3995.46032(27)	27	36	-	40	6
	446	14212 03302	4005.71059(31)	33	51	-	37	8
	446	14211 03301	4005.71088(36)	37	55	-	37	9
	446	22011 11102	4007.83943(31)	21	-	47	-	6
	446	22011 11101	4007.84067(27)	28	48	-	43	6
	446	14011 03102	4013.30713(25)	18	-	51	-	4
	446	14011 03101	4013.30735(15)	42	51	-	38	5
	446	13111 02202	4023.03477(69)	16	-	31	-	6
	446	13112 02202	4023.03632(22)	25	48	-	10	4
	446	13112 02201	4023.03636(43)	17	-	34	-	6
	446	13111 02201	4023.03638(29)	35	41	-	21	5
	446	14212 03102	4023.55756(24)	31	53	-	20	5
	446	14211 03101	4023.55819(15)	29	64	-	16	4
	446	13112 02001	4032.64887(37)	28	-	55	-	5
	446	13111 02001	4032.64889(20)	47	61	-	8	5
	446	21111 10001	4034.27055(17)	46	66	-	2	5
	446	21112 10001	4034.27081(30)	19	-	56	-	5
	446	12011 01101	4041.393297(50)	50	58	-	17	0.7
	446	13312 02202	4044.72530(41)	27	61	-	-	6
	446	13311 02201	4044.72566(30)	25	60	-	-	6
	446	12211 01101	4053.694338(28)	62	26	-	59	0.7
	446	12212 01102	4053.694361(20)	64	27	-	63	0.6
	446	11111 00001	4061.9795930(58)	111	66	-	45	0.3
	456	12011 01102	3981.33317(18)	39	-	46	-	6
	456	12011 01101	3981.33378(16)	49	63	-	34	6
	456	11112 00001	3998.571578(94)	47	-	64	-	6
	456	11111 00001	3998.57184(23)	57	47	-	34	8
	546	12011 01101	4000.35765(22)	41	43	-	29	6
	546	12011 01102	4000.35946(50)	16	-	33	-	4
	546	11112 00001	4022.28933(29)	38	-	66	-	7
	546	11111 00001	4022.29036(16)	53	63	-	14	7
	448	11111 00001	4014.33116(20)	54	62	-	10	7
	448	11112 00001	4014.33169(29)	30	-	57	-	6
	a ) Isotopologues: 446: 14 N 2 16 O, 456: 14 N 15 N 16 O, 546: 15 N 14 N 16 O, 448: 14 N 2 18 O

Generation time : 24 µs Equivalent absorbing path : 7 km

								14 N 2	16 O (41102)-(03102)
								14 N 2	16 O (41101)-(03101)
								H 2 O
	(12211)-(01101) (12212)-(01102)	P(J) 55 53 P(J)	54 52			53 51	52 50	14 N 2	16 O	51
	Q(J)	27		20	10	7	(11112)-(00001) 14 N 15 N 16 O
	100%
	transmission
	0%
			3996	3997	3998		3999	4000	(cm	-1 )	4001