2.1. A motivating example

As an example, imagine that we need to construct a garage. Figure 2 shows the tasks needed to complete the construction. The tasks are represented in a task network, where links indicate precedence constraints. The first decision we are faced with is how to sequence the tasks in the RFQ and how much time to allocate to each of them. For instance, we could reduce the number of parallel tasks, allocate more time to tasks with higher variability in duration or for which there is a shortage of laborers, or allow more slack time.

A task network example and a corresponding RFQ.

A sample RFQ is shown in Figure 2. Note that the time windows in the RFQ do not need to obey the precedence constraints; the only requirement is that the accepted bids obey them. We assume that the supplier is more likely to bid, and submit a lower-cost bid, if it is given a greater flexibility in scheduling its resources. It is up to the customer to find a bid combination that forms a feasible schedule.

2.2. Experiences and observations

We have shown (Collins et al., 2001) that the time constraints specified in the RFQ can affect the customer's outcome in two major ways:

1. by affecting the number, price, and time windows of bids. We assume that bids will reflect supplier resource commitments, and therefore larger time windows will result in more bids and better utilization of resources, in turn leading to lower prices (Collins, 2002). However, an RFQ with overlapping time windows makes the process of winner determination more complex (Collins, 2002). Another less obvious problem is that every extra bid over the minimum needed to cover all tasks adds one more rejected bid. Ultimately, a large percentage of rejections will reduce the customer agent's credibility, which, after repeated interactions in the market, will result in fewer bids and/or higher costs.
2. by affecting the financial exposure of the customer agent (Collins et al., 2001). We assume nonrefundable deposits are paid to secure awarded bids, and payments for each task are made as the tasks are completed. The payoff for the customer occurs only at the completion of all the tasks. Once a task is completed in the time period specified, the customer is liable for its full cost, regardless of whether other tasks have failed in the meantime. If a task is not completed by the supplier, the customer is not liable for its cost, but this failure can ruin other parts of the plan. Slack in the schedule increases the probability that tasks will be completed or that there will be enough time to recover if any fail. However, slack extends the completion time and so reduces the payoff. In many business situations, the speed is the key; the value of the final payoff may drop off very steeply with time.

The agent needs to issue the RFQ before having received any bid, so the process of deciding how to schedule the different tasks and how much time to allocate to each task involves a probability of loss, as well as a probability of gain. This requires the decision process to deal with the risk posture of the person or organization on whose behalf the agent is acting.

The agent can use information available from the market on expected costs, probability of completion of tasks within a time window, and expected numbers of bidders to guide its decision on how to sequence the tasks and how much time to allocate to each.

In the next section we propose a principled method for generating RFQs that takes into account the agent's risk posture and available market statistics to produce a schedule that optimizes the agent's expected utility.

3.1. Terminology

A task network (see Fig. 2) is a tuple 〈N, <〉 of a set N of individual tasks and strict partial ordering on them, such that for any i, j ∈ N, i < j implies that task i immediately precedes task j. We also use N to denote the number of tasks where appropriate.

A task network is characterized by a start time (t^s) and a finish time (t^f), which delimit the interval of time when tasks can be scheduled. The placement of task n in the schedule is characterized by task n start time (t_n^s) and task n finish time (t_n^f), subject to the following constraints:

where P₁(n) is the a set of immediate predecessors of n, P₁(n) = {m ∈ N|m < n}, and S₁(n) is defined similarly to be the set of immediate successors of task n.

The probability of task n completion by time t, conditional on the ultimate successful completion of task n, is distributed according to the cumulative distribution function (CDF) Φ_n = Φ_n(t_n^s; t), lim_t→∞ Φ_n(t_n^s; t) = 1. Observe that Φ_n is defined to be explicitly dependent on the t_n^s. To see the rationale, consider the probability of successful mail delivery in x days for packages that were mailed on different days of a week.

There is an associated unconditional probability of success p_n ∈ [0, 1] characterizing the percentage of tasks that are successfully completed given infinite time (see Fig. 3). In the empirical support of work we assumed Weibull probability distribution for Φ_n; however, the form of the distribution is not tied in the theory. In fact, we expect that the success probabilities will be derived from the available market information.

The unconditional distribution for the successful completion probability.

Task n bears an associated cost.¹

There is a single final reward V scheduled at the plan finish time t^f and paid conditional on all tasks in N being successfully completed by that time.

For each cost and reward, there is an associated rate of return²

We associate the rate of return q with the final payoff V.

3.2. Expected utility and certainty equivalent

We represent the customer agent's preferences over payoffs by the von Neumann–Morgenstern utility function u (Mas–Colell et al., 1995). We further assume that the absolute risk-aversion coefficient r := −u′′/u′ of u is constant for any value of its argument; hence, u can be represented as follows:

It is imperative to note here that we do not compare utility values directly; the counterintuitive (i.e., decreasing in monetary terms) form of the utility for r < 0 is a trade-off for simple notation.

We assume that a future state of the world can be described in terms of potential money transfers and the corresponding probabilities. Accordingly, we define gamble to be a set of payoff–probability pairs G = {(x_i, p_i)_i} s.t. p_i > 0, ∀i and [sum ]_i p_i = 1. The expectation of the utility function over a gamble G is the expected utility (EU):

The certainty equivalent (CE) of a gamble G is defined as the single payoff value whose utility matches the expected utility of the entire gamble G, that is, u(CE[G]) := EU[G] . Hence, under our assumptions

Our evaluation criterion is based upon comparing CE values, because they represent money transfers in certain and current money. Because of this interpretation the CE values, unlike utilities, can be compared across various risk aversities and alternative schedules, even between different plans. Naturally, the agent will not be willing to accept gambles with a negative certainty equivalent and higher values of the certainty equivalent will correspond to more attractive gambles.

To illustrate the concept, Figure 4 shows how the CE depends on the risk aversity r of an agent. In this figure we consider a gamble that brings the agent either 100 or nothing with equal probabilities. Agents with positive r values are risk averse; those with negative r values are risk loving. Agents with risk aversity close to zero, that is, almost risk neutral, have a CE equal to the gamble's weighted mean (50).

The CE of a simple gamble as a function of the risk aversity.

3.3. Cumulative probabilities

To compute the certainty equivalent of a gamble we need to determine a schedule for the tasks and compute the payoff probability pairs.

We assume that the c_n for task n is scheduled at t_n^f, so its present value

is

We define the conditional probability of task n success as

We also define the precursors of task n as a set of tasks that finish before task n starts in a schedule, that is,

The unconditional probability that task n will be completed successfully is

That is, the probability of successful completion of every precursor and of task n itself are considered as independent events. The reason this is calculated in such form is because, if any task in

fails to be completed, there is no need to execute task n.

The probability of receiving the final reward V is therefore

3.4. Example and discussion

To illustrate the definitions above, let us return to the task network in Figure 2 and consider the sample task schedules shown in Figure 5. In this figure the x axis is time and the y axis shows both the task numbers and the cumulative distribution of the unconditional probability of completion (compare to Fig. 3). Circle markers show t_n^s. Crosses indicate both t_n^f and success probabilities

(numbers next to each point). Square markers denote that the corresponding task cannot span past this point due to precedence constraints. The thick part of each CDF shows the time allocated to each task.

The CE maximizing time allocations for the plan in Figure 2 for r = −0.01 (left) and r = 0.02 (right).

The customer agent needs a way of collecting the market information necessary to build and use the probability model. The probability of success is relatively easy to observe in the market. This is the reason for introducing the cumulative probability of success Φ_n and probability of success p_n, instead of the average project life span or probability of failure. Indeed, it is rational for the supplier to report a successful completion immediately in order to maximize the present value of a payment. In addition, it is rational not to report a failure until the last possible moment, because of a possibility of earning the payment by rescheduling, outsourcing, or fixing the problem in some way.

3.5. Gamble calculation algorithm and maximization

Given a schedule like the one shown in Figure 5, we need to compute the payoff probability and then maximize the CE for the gamble. Writing an explicit description of the expected utility as a function of gambles is overly complicated and relies on the order of task completions. Instead, we propose a simple recursive algorithm that creates these gambles. We then maximize the CE over the space of all feasible schedules and the corresponding gambles.

In the first call, the algorithm receives a “todo” task list T = N and a “done” task list D = [empty ]. All the subsequent calls are recursive. To illustrate the idea behind this algorithm, we refer to the payoff–probability trees in Figure 6. These two trees were built for the time allocations in Figure 5 and reflect the precursor relations for each case.

Payoff–probability trees for the time allocations in Figure 5.

Considering the more sequential schedule on the right, we note that with probability

ask 1 fails, and the customer agent does not pay or receive anything and stops the execution (path 1 in the right tree). With probability

the agent proceeds with task 3 (path 1 in the tree). In turn, task 3 either fails with probability

, in which case the agent ends up stopping the plan and paying a total of c₁ (path 1 → 3), or it is completed with the corresponding probability

. In the case where both 1 and 3 are completed, the agent starts both 2 and 4 in parallel and becomes liable for paying c₂ and c₄, respectively, even if the other task fails (paths 1 → 3 → 2 → 4 and 1 → 3 → 2 → 4). If both 2 and 4 fail, the resulting path in the tree is 1 → 3 → 2 → 4 and the corresponding payoff–probability pair is framed in the figure.

The algorithm's complexity is O(2^K−1 × N), where K is the maximum number of tasks that are scheduled to be executed in parallel. Reducing the complexity of calcGamble is critical, because it will be executed in the inner loop of any CE maximization procedure, unless we somehow fix precursor relations and, consequently, a tree structure. In commercial projects the ratio K/N is likely to be low, because few of these exhibit a high degree of parallelism. Our preliminary experiments allow us to conclude that the K/N ratio is lower for risk-averse agents (presumably, businesspeople) than for risk lovers (gamblers). These two considerations may reduce the need for a faster algorithm, although additional work to improve the algorithm is planned.

3.6. Experimental results

We have conducted a set of experiments on CE maximization in a variety of task networks. Some of the results for our reference six-task network are summarized in Figure 7. In this figure, the y axis shows 11 different risk-aversity r settings, and the bottom x axis is time t in the plan. The rounded horizontal bars in each of 11 sections denote time allocations for each of six tasks, with task 1 on top. Sections r = −0.01 and r = 0.02 correspond to schedules in Figure 5a and b, respectively. Finally, the vertical bars show the maximum CE values on the top x axis for each r setting.

The CE maximizing schedules and CE values for the plan in Figure 2 and r ∈ [−0.03, 0.07] .

Let us examine the relative placement of time allocations as a function of r. For this example we chose two tasks, 3 and 4, which have similar positions in the task network. Task 3 (black horizontal bars) has a lower probability of success in the infinite horizon than task 4 (white bars), as well as a higher variance of the probability of success distribution. In addition, the cost of task 3 is twice the cost of task 4.

Given this setup, we observed four distinct cases in the experimental data:

1. Risk-loving agents tend to schedule tasks in parallel and late in time in order to maximize the present value of the expected difference between reward and payoffs to suppliers. This confirms the intuitive observation from Figure 4 that risk lovers lean toward receiving high, risky payoffs rather than low, certain payoffs.
2. Risk neutral and minimally risk-averse agents place risky task 3 first to make sure that any failure does not happen too far into the project. Note that they still keep task 2 in parallel so in case 2 fails, they are liable for paying the supplier of task 4 on success. One can consider those agents as somewhat optimistic.
3. Moderately risk-averse agents try to dodge the situation above by scheduling task 3 after task 2 is finished. These agents are willing to accept the plan, but their expectations are quite pessimistic.
4. Highly risk-averse agents shrink the task 1 interval to zero, thus “cheating” to avoid covering any costs. One may interpret this as a way of signaling a refusal to accept the plan. Indeed, the assignment of zero duration to a precursor-less task ensures zero probability of completion and hence zero CE, even in the cases where any nondegenerate schedule has a negative CE value.

4.1. CE Sensitivity to schedule changes

We propose measuring the sensitivity of CE by investigating how CE values change with variations of a single task n start time (t_n^s) in the reasonable schedule. For the sake of brevity the resulting dependency of CE values is denoted by CE(t_n^s). Figure 8 shows CE(t_n^s), n = 1···6 for our six-task sample problem for r = −0.01 and 0.02, respectively. In the figure, the y axis of each horizontal stripe n represents the percentage of the maximum CE value as t_n^s varies, the x axis represents t_n^s, and the horizontal lines with circle and cross ends show the corresponding reasonable schedules.

The CE(tns) graphs for the corresponding reasonable schedules in Figure 5.

Tasks 1, 3, and 5 in the right graph are relatively restrictive to the start times of the bids that can be bundled with the reasonable bids without considerably impairing the resulting bundle's value. However, the fact that task 2 in the right graph is more flexible does not guarantee that it will attract a higher number of bids, because the latter depend both on the size of the corresponding time window and on the market properties of the task: resource availability, number of prospective bidders, seasonal changes, and so forth.

We assert that for the purpose of creating a rational RFQ, it is admissible to choose time windows based on the sensitivity of CE to deviations of a single time constraint from the reasonable schedule. The rationale is that the relations between tasks are already encapsulated in the calculations of CE, so the change of one constraint will approximate the rescheduling of several related tasks in the neighborhood of the reasonable schedule.

4.2. Quality versus quantity

Observe that the time window for the task n, {t_n^s|CE(t_n^s) ≥ x}, grows as the lowest expected CE value (x) decreases. The relation between these two variables for the tasks 3 and 4 of the test problem is shown in Figure 9. The corresponding relation between the lowest expected CE value and the expected number of bids as a function of the window size is shown in Figure 10. In the right graph we assumed, for the sake of example, that the supply of task 3 in the market is higher than task 4, hence the difference in relative positions of task 3 and task 4 graphs in the two figures.

The relationship between the RFQ window size (units of time on x axis) and the lowest admissible percentage of the maximum CE value.

The relationship between the expected number of bids (x axis) and the lowest admissible percentage of the maximum CE value.

The graph in Figure 10 is an example of the relation between the quality and the quantity of bids for which we are searching. Indeed, the only independent variable in this graph is t_n^s. The quantity of bids depends on the size and positions of RFQ time windows that, in turn, depend on the decision about the lowest acceptable CE value. The quality of bids is a function of the RFQ choice and the properties of the plan. Finally, it is expected that the customer agent will prefer a point on the graph to any point below and to the left of it; thus, the best choice should lie on the graph.

4.3. Rational quality–quantity choice and RFQ

We illustrate the decision process of the customer agent in Figure 11, where the customer agent's preferences over quality–quantity combinations are represented by a family of indifference curves and the graph of underlying quality–quantity relationship is as derived in the previous section. Each indifference curve shows quality–quantity pairs that are equivalent from the agent's point of view. In particular, points A, B, and C are considered to be equally attractive. The intuition is that, although in point A the agent receives a much smaller number of bids to compare with C and is exposed to a higher risk of not covering some tasks, this is offset by a positive effect of a lower percentage of bid rejections on the agent's reputation. In addition, the winner determination problem is exponentially easier to solve (Collins, 2002) for the lower expected number of bids in point A.

A quality–quantity graph with three (—) indifference curves; (– – –) the maximum expected quality line.

For all points below the maximum expected quality line (Fig. 11, dashed line) agent's preferences increase in the direction of point M. Thus, a curve through point D is preferred over one through point C and even more so over one through point E. The rational choice belongs to the intersection of the quality–quantity graph and the highest indifference curve (point B).

After the rational choice of the quality–quantity combinations for all tasks in the plan is revealed, we proceed with constructing the RFQ time windows. The choice of early start time (t_n^es) and late start time (t_n^ls) are determined by the value of the reciprocal of the CE(t_n^s) at the minimum admissible CE choice for task n. The late finish time (t_n^lf) is chosen to be at the reasonable time window length distance from t_n^ls. Figure 12 shows two sample RFQs for the garage building example. The start time intervals ([t_n^es, t_n^ls]), late finish time t_n^lf, and the corresponding reasonable schedules are presented in the figure.

The rational RFQs for the corresponding reasonable schedules in Figure 5 and the maximum CE percentages of 80, 95, 50, 70, 50, and 90%. (shaded bar segments) start time intervals, (unshaded bar segments) late finish times, and (○—×) corresponding reasonable schedules.

Our choice of the RFQ may not be optimal in the quantitative sense. However, it is individually rational for the customer agent, fast to compute, and, arguably, easily grasped by a human user of the system. It should be emphasized here that the choice of the RFQ is based on the uncertain market information; hence, any quantitatively “optimal” solution is itself a compromise.

5.1. Multiple local maxima

One of the most important issues related to CE maximization is the presence of multiple local maxima of CE, even in cases where task networks are fairly simple. We argue that this property is partially due to the relative positioning of the tasks off the critical path. Any two tasks that are not ordered by the precedence constraints can be scheduled in three ways: parallel and two sequential. Scheduling tasks in parallel increases the probability of successful completion, whereas sequential scheduling minimizes overall payments in case one of the tasks fails. In cases where extra slack allows for sequential scheduling, it turns out that parallel and sequential positionings of two independent individual tasks lead to similar resulting CE values.

To illustrate the issue, we constructed a sample task network with two parallel tasks. Task 1 has a higher variance of completion time probability and lower probability of success than task 2; everything else is the same. The resulting graph of CE is shown in Figure 13. There are three local maxima with positive CE values in this figure: one that corresponds to task 2 being scheduled first in sequential order, another on the right side corresponding to task 1 being first, and yet another representing both tasks being scheduled at time 0 and executed in parallel. The number of local maxima grows considerably with the number of the tasks that are not restricted by the precedence relationship.

The local maxima for two parallel tasks.

5.1.2. Search algorithm

The proposed search algorithm explores several alternative schedules in parallel. The initial set of alternatives can be generated in many ways: random generation, hill climbing from a random schedule, critical path method, and so forth. The execution of the algorithm proceeds in steps by randomly applying one of the six transformation rules to each alternative schedule. The probabilities of choosing some rule can be adjusted to adjust the algorithm's behavior over a wide range.

Figure 14 illustrates the algorithm for the case of three pairwise independent tasks. In this figure the columns represent three consecutive states of the algorithm, and each column lists several alternative schedules. Arrows and letters next to the columns denote various transformations from the following list:

The two steps of the search algorithm execution.

Distortion alters start and finish times of one or several tasks and adjusts the time windows of all related tasks to maintain precedence constraints (1 → 5, Fig. 14). Distortion mimics the basic step of the simulated annealing algorithm in continuous 2N–dimensional space of task start and finish times.

Gradient following is one or more steps of a generic numerical maximization method (5 → 9). This step is very computationally intensive, because it requires many calls to the calcGamble algorithm in the process of calculating numerical derivatives. By varying the relative probabilities of the distortion and gradient following, we may choose the stochastic properties of the proposed approach.

Shuffling changes relative scheduling of two or more tasks wherever it is permitted by the precedence constraints. It can switch ordering of the tasks (6 → 10), change the sequential ordering to parallel, or reschedule parallel tasks to be executed sequentially (4 → 8). The major role of shuffling is to explore local maxima that have similar CE values due to different scheduling of tasks off the critical path.

Explosion adds a copy of the subject schedule to the list of alternatives (2 → 6, 7). Explosion compliments shuffling by allowing for simultaneous exploration of the groups of similar schedules. We may choose to decrease the rate of explosions with the annealing temperature to focus on improving the current set of solutions after the search space has been explored to some extent.

Implosion merges two similar⁵

Similarity is a function of the distance between two schedules, as between two points in the 2N-dimensional time space.

schedules in one. It helps to reduce computational expenses from crowding several alternative schedules around one maximum (7, 8 → 11). The rate of implosions will change in the direction opposite to the rate of explosions.

Removal eliminates alternatives that do not score well relative to others (3 → [empty ]). This transformation takes care of the schedules that are stuck in local maxima with low CE values. The rate of removals grows as the annealing temperature decreases.

Each of the first five transformations is tested against the simulated annealing temperature rule whenever it leads to a decrease in the CE value. In case it is discarded, other transformations are chosen at random and applied until one of them increases the CE or passes the temperature rule.

The probabilities of transformations and the details of the proposed search algorithm's properties are subject to further research. However, it is reasonable to believe that the comprehensive study of the RFQ generation mechanism is only possible in the dynamic market environment. In the next section we outline the approach to the large-scale testing of the MAGNET system that we are presently researching and that will provide us with the necessary data.

5.2. Evolutionary framework for large-scale testing

We plan to devote efforts to thoroughly test the suggested CE-based approach of rational RFQ generation. In particular, we are interested in testing how well individual agents interact in a populated market. The major goals of this part of the study would be the following:

• to provide the statistical data necessary for the evaluation of the theoretical assumptions and derivations;
• to facilitate the understanding of the nuances of CE-based RFQ generation and suggest improvements to the theory and implementation; and
• to study the relative performance of agents in a simulated market, developing an understanding of the properties of automated and mixed-initiative combinatorial auction-based trading societies.

The most compelling approach would be to gather a rich set of statistical data from a commerce domain. That has not proven to be feasible for two reasons. First, few industrial organizations are sufficiently open to expose the type of data you would need to do that, and we would need data from multiple organizations in a single market. Second, data is gathered to serve a purpose, and our experience tells us that when you attempt to apply existing data to a new purpose, it frequently turns out to be full of inconsistencies and methodological problems.

In lieu of using real industry data, we are designing a large-scale test suite atop an abstract domain with controllable statistics, based on the evolutionary approach to economic simulation. Evolutionary frameworks have been used extensively in economics (Nelson, 1995; Rode, 1997; Tesfatsion, 2001). The framework will allow us to tune the market by tweaking the frequency of issuing RFQs and will allow for the dynamic introduction of new supplier strategies without imposing any assumptions on the nature of strategies. We will later extend the framework to support trade games played by human subjects. This will be an especially useful tool for teaching and a tool to explore strategic behaviors and study the emergence of cooperation (Axelrod, 1984; Axelrod, 1997).

We suggest detailed reasoning behind our choice of the evolutionary approach and describe experimental results from a pilot model of a trading agent society in our related research (Babanov, Ketter, et al., 2002).