extfieldsofstudy:
Mathematics
Computer Science

text:
Quadrilateral Meshing by Circle Packing

We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types: (1) the elements form the cells of a Voronoi diagram, (2) all elements have two opposite right angles, (3) all elements are kites, or (4) all angles are at most 120 degrees. In each case the total number of elements is O(n), where n is the number of input vertices.

Introduction
We investigate here problems of unstructured quadrilateral mesh generation for polygonal domains, with two conflicting requirements. First, we require there to be few quadrilaterals, linear in the number of input vertices; this is appropriate for methods in which high order basis functions are used, or in multiblock grid generation in which each quadrilateral is to be further subdivided into a structured mesh. Second, we require some guarantees on the quality of the mesh: either the elements themselves should have shapes restricted to certain classes of quadrilaterals, or the mesh should satisfy some more global quality requirements.
Computing a linear-size quadrilateralization, without regard for quality, is quite easy. One can find quadrilateral meshes with few elements, for instance, by triangulating the domain and subdividing each triangle into three quadrilaterals [15]. For convex domains, it is possible to exactly minimize the number of elements [13]. However these methods may produce very poor quality meshes. High-quality quadrilateralization, without rigorous bounds on the number of elements, is an area of active practical interest. Techniques such as paving [7] can generate high-quality meshes for typical inputs; however these meshes may have many more than O(n) elements. Indeed, if the requirements on element quality include a constant bound on aspect ratio, then meshing a rectangle of aspect ratio A will require Ω(A) quadrilaterals, even though in this case n = 4.
We provide a first investigation into the problem of finding a suitable tradeoff between those two requirements: for which measures of mesh quality is it possible to find guaranteed-quality meshes with guaranteed linear complexity? The results-and indeed the algorithms-of this paper are analogous to the problem of nonobtuse triangulation [2,4,6]. Interestingly, for quadrilaterals there seem to be several analogues of nonobtuseness.
Our algorithms are based on circle packing, a powerful geometric technique useful in a variety of contexts. Specifically, we build on a circle-packing method due to Bern, Mitchell, and Ruppert [6]. In this method, before constructing a mesh, one fills the domain with circles, packed closely together so that the gaps between them are surrounded by three or four tangent circles. (Circle packings with only three-sided gaps form a sort of discrete analogue to conformal mappings [18]. However for most domains some foursided gaps are necessary, and in some of our algorithms four-sided gaps are actually helpful since they lead to degree-four mesh vertices.) One then uses these circles as a framework to construct the mesh, by placing mesh vertices at circle centers, points of tangency, and within each gap. Earlier work by Shimada and Gossard [17] also uses approximate circle packings and sphere packings to construct triangular meshes of 2-d domains and 3-d surfaces. Other authors have introduced related circle packing ideas into meshing via conforming Delaunay triangulation [14], conformal mapping [8,16], and decimation [11,12]. Circle packing ideas closely related to the algorithms in this paper have also been applied in origami design [3,10].
We use circle packing to develop four new quadrilateral meshing methods. First, in Section 3, we show that the Voronoï diagram of the points of tangency of a suitable circle packing forms a quadrilateral mesh. Although the individual elements in this mesh may not have good quality, the Voronoï structure of the mesh may prove useful in some applications such as finite volume methods. Second, in Section 4, we overlay this Voronoï mesh with its dual Delaunay triangulation; this overlay subdivides each Voronoï cell into quadrilaterals having two opposite right angles. Note that any such quadrilateral must have all four of its vertices on a common circle. Third, in Section 5, we show that a small change to the method of Bern et al. (basically, omitting some edges), produces a mesh of kites (quadrilaterals having two adjacent pairs of equal-length sides). The resulting mesh optimizes the cross ratio of the elements (a measure of the aspect ratio of the rectangles into which each element may be conformally mapped): any kite can be conformally mapped onto a square. Finally, in Section 6, we subdivide these kites into smaller quadrilaterals, producing a mesh in which each quadrilateral has maximum angle at most 120 • . This is optimal: there exist domains for which no mesh has angles better than 120 • .

Circle Packing
Let us first review the nonobtuse triangulation method of Bern et al. [6]. This algorithm is given an n-vertex polygonal region (possibly with holes), and outputs a triangulation with O(n) new Steiner points in which no triangle has an obtuse angle. In outline, it performs the following steps: 2. Connect holes of the polygon by placing nonoverlapping circles, tangent to edges of the polygon or to previously placed circles, so that the domain outside the circles forms one or more simply connected regions with circular-arc sides.
3. Simplify each region by packing it with further circles until each remaining region has three or four circular-arc or straight-line sides (Figure 1(b)).

4.
Partition the polygon into 3-and 4-sided polygonal regions by connecting the centers of tangent circles (Figure 1(c)).
Our quadrilateralization algorithms will be based on the same general outline, and in several cases the quadrilaterals we form can be viewed as combinations of several of the triangles formed by this algorithm.
Steps 1, 4, and 5 are straightforward to implement. Eppstein [9] showed that step 2 could be implemented efficiently, in time O(n log n), as independently did Mike Goodrich and Roberto Tamassia, and Warren Smith (unpublished). We now describe in some more detail step 3, simplification of regions, as we will need to modify this step in some of our algorithms. Proof: Compute the Voronoï diagram of the circles within this region; that is, a partition of the region into cells, each of which contains points closer to one of the circles than to any other circle ( Figure 2). Because the region is simply connected, the cell boundaries of this diagram form a tree. We choose a vertex v of this tree such that each of the subtrees rooted at v has at most half the leaves of the overall tree, and draw a circle centered at v and tangent to the circles having Voronoï cells incident at v. This splits the region into simpler regions. We continue recursively within these regions, stopping when we reach regions bounded by only four arcs (in which no further simplification is possible). Adding each new circle to the Voronoï diagram can be done in time linear in the number of arcs bounding the region, so the total time to subdivide all regions is O(n log n). 2 We call the region between circles of this packing a gap. We now state without proof two technical results of Bern et al. about these gaps.

Lemma 2 (Bern et al. [6]) The points of tangency on the boundary of a gap are cocircular.
A three-sided gap is one bounded by three circular arcs. A good four-sided gap is a gap bounded by four arcs, such that the circumcenter of its points of tangency is contained within the convex hull of those points. A bad four-sided gap is any other four-arc gap.

Lemma 3 (Bern et al. [6]) Any bad four-sided gap can be split into two good four-sided gaps by the addition of a circle tangent to two of the bad four-sided gap's circles. (Figure 3.)
In some cases two opposite circles bounding one of the new gaps created by Lemma 3 may overlap, but this poses no problem for the rest of the algorithm.

Voronoï Quadrilateralization
We begin with the quadrilateralization procedure most likely to be useful in practice, due to its low output complexity and lack of complicated special cases.
The geodesic Voronoï diagram of a set of point sites in a polygonal domain is a partition of the domain into cells, in each of which the geodesic distance (distance along paths within the domain) is closest to one of the given sites. We now describe a method of finding a point set for which the geodesic Voronoï diagram forms a quadrilateral mesh. One potential application of this type of mesh would be in the finite volume method, as the dual of this Voronoï mesh could be used to define control volumes for that method (see e.g. Miller et al. [12]). The angle between each primal and dual edge pair would be 90 • , causing some terms in the finite volume method to cancel and therefore saving some multiplications [2,5]. Our mesh will also have the possibly useful property that all Voronoï edges will cross their duals.
We modify the initial circle packing of Bern et al. [6], as follows. We start by protecting vertices, as before; but in this case that protection consists of a circle centered at each domain vertex. Then, as before we fill the remainder of the domain by tangent circles; however we do not attempt to create tangencies with the domain boundary; instead the circle packing should meet the boundary at circles with their centers on the boundary. Further, no tangent point between two circles should lie on the domain boundary, although circles centered on the boundary may meet in the domain interior. (Some circles may cross or be tangent to the boundary, however we ignore these incidences, instead treating these circles as part of three-sided gaps.) It is not hard to modify the previous circle packing algorithms to meet these conditions. The result will be a packing with, again, three-sided and four-sided gaps. However, the gaps involving boundary edges are all four-sided and have right-angled corners rather than points of tangency on those edges.

Theorem 1
In O(n log n) time we can find a circle packing as above, such that the geodesic Voronoï diagram of the points of tangencies of the circles forms a quadrilateral mesh.
Proof: The vertex protection step can be performed in O(n) time using circles with radius half the minimum distance between vertices. (This minimum distance is an edge of the Delaunay triangulation and can be found in O(n log n) time.) Next we find a set of O(n) circles to add to our packing, so that any remaining gaps are simply connected [9]. If in this step we ever add a circle c tangent to the boundary, we replace it by a set of circles: a circle with radius ǫ centered on the boundary at the point of tangency, circles with radius ǫ/2 tangent to c at each of its other points of tangency, and one circle concentric to c with radius reduced by ǫ; this replacement is depicted in Figure 5.
Finally, as in the algorithm of Bern et al. [6] we repeatedly find the Voronoï diagram of the circles bounding any remaining gap and place a circle on a Voronoï vertex so as to divide the gap into two smaller parts of roughly equal complexity. However, in order to avoid placing circles tangent to the boundary in this step, we change their method by using only the circles around a gap as Voronoï sites, omitting any diagram edges that may bound the gap. Our Voronoi diagram's edges (together with any boundary edges of the gap) form a tree, so we can find a vertex which splits the tree's leaves roughly evenly. Placing a circle at that vertex produces two simpler gaps and does not cause essential tangencies with the domain boundary. Unlike Bern et al. [6], we do not bother eliminating bad four-sided gaps. We form a mesh by connecting each center of a circle in the packing to the circumcenters of adjacent gaps ( Figure 4). In the four-sided gaps along the domain boundary, we place an additional edge from the boundary to the center of the opposite circle, bisecting the chord between the tangencies with the two other circles. These edges form a quadrilateral mesh since each face surrounds a point of tangency, and each point of tangency is surrounded by the vertices from two circles and two gaps. Each mesh element is the Voronoi cell of the point of tangency it contains; its boundary is composed of perpendicular bisectors of dual Delaunay edges. Each dual Delaunay edge has a circumscribing circle from the circle packing as witness to the empty-circle property of Delaunay graphs. 2 Curiously, this mesh is not only a certain type of generalized Voronoï diagram; it is also another type of generalized Delaunay triangulation! The power of a circle with respect to a point in the plane is the squared radius of the circle minus the squared distance of the point to the circle's center. The power diagram of a set of (not necessarily disjoint) circles is a partition of the plane into cells, each consisting of the points for which the power of some particular circle is greatest. Like the usual kind of Voronoï diagram, the power diagram has convex cells, since the separator between any two circles' cells is a line (if the two circles overlap, their separator is the line through their two intersection points). We can restrict the power diagram to a polygonal domain by defining the power only for points visible to the center of the given circle.
From the construction above, define a family F of circles by including the original packing and a "dual" collection of circles through the tangencies surrounding each gap, centered at the gap's site. As we now show, the power diagram of this family (depicted in Figure 6) is the planar dual to our mesh.

Theorem 2 The quadrilateral mesh defined above includes an edge between two points if and only if the corresponding circles' cells share an edge in the power diagram of F.
Proof: F has one circle centered at each vertex; the two circles corresponding to the endpoints of an edge overlap in a lune. The lune's two corners are points of tangency in the original circle packing (or, if the edge is on the domain boundary, the corners are one such point of tangency and its reflection) and are contained in the two quadrilaterals on either side of the edge. These corners have power zero with respect to the two circles, and are not interior to any other circles; therefore they have those two circles (and possibly some others) as nearest power neighbors. Since power diagram cells are convex, those two circles must continue to be the nearest neighbors to each point along the center line of the lune; in other words this center line lies along an edge in the power diagram corresponding to the given mesh edge.
Conversely, we must show that every power diagram adjacency corresponds to a mesh edge. But the power diagram boundaries described above form a convex polygon completely containing the center of the cell's circle; therefore there can be no other adjacencies than the ones we have already found, which correspond to mesh edges. 2 Since quadrilaterals in this mesh typically correspond to eight triangles in the nonobtuse triangulation algorithm of Bern et al., the constant factors in the O(n) bound above should be quite small in practice. Bern et al. [6] observed that their method typically generated between 20n and 30n triangles, so we should expect between 3n and 4n quadrilaterals in our mesh.

Opposite Right Angles
As we now show, the Voronoï triangulation above can be used to find another quadrilateral mesh, in which each quadrilateral has two opposite right angles. Such a quadrilateral must be cyclic (having all four vertices on a common circle); further, the circumcenter bisects the diagonal connecting the two remaining vertices.
Our algorithm works by overlaying the power diagram defined above onto the quadrilaterals of Theorem 1, resulting in their subdivision into smaller quadrilaterals. In order to perform this subdivision, we may need to place a few additional circles into our packing. On the boundary of the domain, the gaps between circles will be formed by chains of three tangent circles, the two ends of which are circles centered on the domain boundary. The center circle in this chain is allowed to cross the boundary; we ignore this crossing. Reflecting such a chain across the domain boundary edge produces a four-sided gap partially outside the domain; like Bern et al. [6] we say that this gap is good or bad if the convex hull of its points of tangency contains or doesn't contain their circumcenter respectively. The algorithm of this section requires these gaps to be good. As in the method of Bern et al. [6], any bad four-sided gap can be subdivided into two good four-sided gaps by the addition of another circle which by symmetry can be placed with its center on the domain boundary.

Theorem 3 In O(n log n) time we can partition any polygon into a mesh of O(n) quadrilaterals, each having two opposite right angles.
Proof: We form the Voronoï quadrilateralization of Theorem 1, and subdivide each quadrilateral Q into four smaller quadrilaterals by dropping perpendiculars from the Voronoï site contained in Q to each of Q's four sides. On edges where two cells of the Voronoï quadrilateralization meet, the two perpendiculars end at a common vertex because they are the two halves of a chord connecting two tangent points on the same circle. For the same reason, each perpendicular meets the edge to which it is perpendicular without crossing any other cell boundaries first. 2 The same procedure of dropping perpendiculars will work whenever we have a Voronoï diagram in which the site generating each cell can be connected by a perpendicular to each cell edge. Therefore, some heuristic simplification can be applied to the mesh above, reducing its complexity further: after forming the Voronoï quadrilateralization of Theorem 1, remove sites one by one from the set of generators as long as this condition is met.

Kites
The next type of quadrilateralization we describe is one in which all quadrilaterals are kites (convex quadrilaterals with an axis of symmetry along one diagonal). Although kites may have bad angles (very close to 0 • or 180 • ), they have some other nice theoretical properties. In particular, the cross ratio of a kite is always one.
The cross ratio of a quadrilateral with consecutive side lengths a, b, c, and d is the ratio ac : bd. Since this ratio is invariant under conformal mappings, a conformal mapping from the quadrilateral to a rectangle (taking vertices to vertices) can only exist if the rectangle has the same cross ratio; but the cross ratio of a rectangle is just the square of its aspect ratio. Therefore, kites are among the few quadrilaterals that can be conformally mapped onto squares.  Proof: As in the algorithm of Bern et al., we find a circle packing; however as discussed below we place some further constraints on the placement of circles. We then connect pairs of tangent circles by radial line segments through their points of tangency, and apply a case analysis to the resulting set of polygons. As shown in Figure 7, all interior gaps can be subdivided into kites: three-sided gaps result in three kites, good four-sided gaps result in four, and bad four-sided gaps result in seven. Also shown in the figure are three types of gaps on the boundary of the polygon: three-sided gaps along the edge, reflex vertices protected by two equal tangent circles, and convex vertices packed by a single circle.
There are two remaining cases, in which one or two of the sides of a four-sided gap are portions of the domain boundary, and the four-sided gap has a high aspect ratio preventing these boundary edges from being covered by a small number of three-sided gaps. In the simpler of these cases, two opposite sides of the four-sided gap are both boundary edges. Such a gap is necessarily good. If it has aspect ratio O(1), we can line the domain edges by O(1) additional circles, as in the next case. Otherwise, our construction is illustrated in Figure 8. We find a mesh using an auxiliary set of circles, perpendicular to the original packing. We first place at each end of the four-sided gap a pair of identical circles, tangent to each other and crossing the boundary edges perpendicularly at their points of tangency. These are the medium-sized circles in the figure. We next place two more circles, each perpendicular to one of the boundary edges and crossing it at the same points already crossed by the previously added circles; these are the large overlapping circles in the figure. Finally, each end of the original four-sided gap now contains a gap formed by four circles, but two of these circles cross rather than sharing a tangency. We fill each gap with an additional circle; these are the small circles in the figure. The resulting set of eight circles forms six three-sided gaps and one good four-sided gap, and can be meshed as shown in the figure.
The final case consists of four-sided gaps (not necessarily good) involving one boundary edge. To make this case tractable, we restrict our initial placement of circles so that, if we place a circle C within a gap involving boundary edges, then C is either tangent to those edges or separated from them by a distance of at least ǫ times its radius, for some sufficiently small value ǫ. Then, any remaining four-sided boundary gap must have bounded aspect ratio, and we can place O(1) small circles along the boundary edge leaving only three-sided gaps on that edge ( Figure 9). The interior of the gap can then be packed with O(1) additional circles leaving only the previously solved three-and four-sided internal gap cases. 2

No Large Angles
The maximum angle of any triangle has been shown to be one of the more important indicators of triangular mesh quality [1], and it is believed that the maximum angle is similarly important in quadrilateral meshes. For triangular meshes, a maximum angle of 90 • can be achieved [6], but for quadrilaterals this would imply that all elements are rectangles, which can only be achieved when the domain has axis-parallel sides. Indeed, as we now show, some domains require 120 • angles.

Theorem 5
Any simple polygon with all angles at least 120 • cannot be meshed by quadrilaterals having all angles less than 120 • .
Proof: Suppose we have such a simple polygon, and a quadrilateral mesh on it. Let x denote the number of mesh vertices on the boundary of the polygon, i denote the number of interior vertices, e denote the number of mesh edges, and q denote the number of mesh quadrilaterals. Then, since each quadrilateral has four edges, each interior edge appears twice, and there are x boundary edges, we have the relation 4q = 2e − x. Combining this with Euler's formula x+ i+ q− e = 1 and cancelling q leaves e = 2i+ (3/2)x− 2. However, if all interior vertices of the mesh were incident to four or more edges, and all exterior vertices were incident to three or more edges, we would have e ≥ 2i + (3/2)x (since each edge contributes two to the sum of vertex degrees), a contradiction. So, the mesh has either an interior vertex with degree three, or an exterior vertex with degree two, and in either case at least one of the angles at that vertex must be at least 120 • . 2 As we now show, this lower bound can be matched by our circle packing methods. and right vertices, and subdivide both of the resulting triangles into three 120 • quadrilaterals (Figure 10(a)). If both angles are large (greater than 60 • ), we can similarly split the kite vertically along a line from top to bottom and again subdivide both of the resulting triangles ( Figure 10(b)). In both of these two cases the subdivisions are axis-aligned or at 60 • angles to the axes. In the final case, the top angle is large (at least 120 • ) and the bottom is sharp (less than 120 • ). In this case, like the second, we partition the kite vertically into two triangles, and again partition each triangle into three; however in this final case the subdivisions are along lines between the bottom of the triangle and the two opposite edge midpoints, and at 60 • angles to those lines. It is easily verified that with the given assumptions on the angles of the original kite, all vertices of the subdivision lie as depicted in the figures and all angles are at most 120 • . 2

Conclusions
We have shown that circle packing may be used in a variety of ways for quadrilateral mesh generation with simultaneous guaranteed bounds on complexity and quality.
Many questions remain open: How small can we make the constant factors in our complexity bounds, both in the worst case and in practice? Can we generate linear-complexity quadrilateral meshes with no small angles? Can we combine guarantees on several quality measures at once? Extensions of the circle packing method to three dimensional tetrahedral or hexahedral meshing would be of interest, but seem difficult due to the inability of three dimensional spheres to partition the domain into bounded-complexity regions. However perhaps our methods can be generalized to guaranteed-quality quadrilateral surface meshes.
Some of the methods we describe are purely of theoretical interest, due to high constant factors or distorted quadrilateral shapes, but we believe circle packing should be useful in practice as well. Among our methods, perhaps the low constant factors and lack of complicated cases in the Voronoï quadrilateralization make it the most practical choice.


extfieldsofstudy:
Computer Science
Physics

text:
General Principles of Learning-Based Multi-Agent Systems

We consider the problem of how to design large decentralized multi-agent systems (MAS's) in an automated fashion, with little or no hand-tuning. Our approach has each agent run a reinforcement learning algorithm. This converts the problem into one of how to automatically set/update the reward functions for each of the agents so that the global goal is achieved. In particular we do not want the agents to ``work at cross-purposes'' as far as the global goal is concerned. We use the term artificial COllective INtelligence (COIN) to refer to systems that embody solutions to this problem. In this paper we present a summary of a mathematical framework for COINs. We then investigate the real-world applicability of the core concepts of that framework via two computer experiments: we show that our COINs perform near optimally in a difficult variant of Arthur's bar problem (and in particular avoid the tragedy of the commons for that problem), and we also illustrate optimal performance for our COINs in the leader-follower problem.

INTRODUCTION
In this paper we are interested in computational problems having the following characteristics: • the agents each run reinforcement learning (RL) algorithms; • there is little to no centralized communication or control; • there is a provided world utility function that rates the possible histories of the full system.
There are many examples of such problems, some of the more prominent being: 1. Designing a control system for constellations of communication satellites or of constellations of planetary exploration vehicles (world utility in the latter case being some measure of quality of scientific data collected); 2. Designing a control system for routing over a communication network (world utility being some aggregate quality of service measure); 3. Construction of parallel algorithms for solving numerical optimization problems (the optimization problem itself constituting the world utility); 4. Control of a large, distributed chemical plant.
These kinds of problems may well be most readily addressed by using a large Multi-Agent System (MAS) [19], where each agent is restricted to communicate with only a few neighbors, and where each agent runs a Reinforcement Learning (RL) algorithm. In such systems, a crucial problem is ensuring that the agents' RL algorithms do not "work at cross-purposes", so that their collective behavior maximizes a provided global utility function. The difficulty in achieving this is that these systems have no centralized control, so the dynamics is governed by the collective effects of the individual agents each modifying their behavior via their (local) RL algorithms.
We are interested in such systems where the agents are "greedy" (i.e., there is no external structure forcing cooperation). However, both the agents reward functions and the overall system structure are automatically set and then updated in a machine learning-like fashion, so as to facilitate the achievement of the global objective.
As opposed to hand-tailored MAS design, these alternative approaches potentially have the following benefits: one does not have to laboriously model the entire system; global performance is "robust"; one can scale up to very large systems; and one can maximally exploit the power of machine learning. We use the term COllective INtelligence (COIN) [21,22,23] to refer to either MAS's designed in this way, or (in the case of naturally occurring MAS's) to MAS's investigated from this perspective.
The COIN framework is related to many other fields. (See [21] for a detailed discussion of these relations, involving several hundred references.) Some of them are: • multi-agent systems; • computational economics; • reinforcement learning for adaptive control; • statistical mechanics; • computational ecologies; • game theory , in particular, evolutionary game theory. Previous MAS's most similar to a COIN include those where agents use reinforcement learning [8,13], and/or where agents actively attempt to model the behavior of other agents [14].
In this paper we introduce some of the concepts from the COIN framework, and then present experiments testing those concepts. The restricted version of the framework presented here is not sufficient to formally guarantee optimal global performance for all multi-agent systems. Rather the experiments recounted below are designed to empirically investigate the usefulness of these concepts in some illustrative domains. In Section 2 we present general background on COINs and the experiments we conducted. In Section 3, we present the portion of the COIN framework investigated in this paper. In Sections 4 and 5, we describe the bar and leader-follower experiments, respectively, and how our approach deals with the many pitfalls encountered in each.

MOTIVATION AND BACKGROUND
A naturally occurring example of a system that can be viewed as COIN is a human economy. For example, one can take the agents to be the individuals trying to maximize their personal rewards. One might then declare that the world utility is a time average of the gross domestic product. ("World utility" per se is not a construction internal to a human economy, but rather something defined from the outside.) To achieve high global utility it is necessary to avoid having the agents work at cross-purposes lest phenomena like the Tragedy of the Commons (TOC) occur, in which individual avarice works to lower global utility [12]. One way to avoid such phenomena is by modifying the agents' utility functions via punitive legislation. A real world example of an attempt to make such a modification was the cration of anti-trust regulations designed to prevent monopolistic practices.
In designing a COIN we have more freedom than antitrust regulators though, in that there is no base-line "organic" local utility function over which we must superimpose legislation-like incentives. Rather, the entire "psychology" of the individual agents is at our disposal when designing a COIN. This freedom is a major strength of the COIN approach, in that it obviates the need for honesty-elicitation mechanisms, like auctions, which form a central component of conventional economics.
We recently investigated the use of the COIN approach for distributed control of network packet routing [22]. Conventional approaches to packet routing have each router run a shortest path algorithm (SPA), i.e., each router routes its packets in the way that it expects will get those packets to their destinations most quickly. Unlike with a COIN, with SPA-based routing the routers have no concern for the possible deleterious side-effects of their routing decisions on the global goal (e.g., they have no concern for whether they induce bottlenecks). We ran simulations that demonstrated that a COIN-based routing system has better throughputs than does an SPA-based system [22].
In this paper we present a more fine-grained investigation of our COIN methodology, in which we disentangle two of the major components of that methodology and examine the real-world usefulness of them separately. In the first set of experiments we investigate how one might initialize a COIN (i.e., initialize each agents' local reward function) to ensure that the agents do not work at cross purposes. The problem we chose for this purpose is a more challenging variant of Arthur's bar attendance problem [1,7,17]. In this problem, agents have to determine which night in the week to attend a bar. The problem is set up so that if either too few people attend (boring evening) or too many people attend (crowded evening), the total enjoyment of the attendees drops. Our goal is to design the reward functions of the attendees so that the total enjoyment across all nights is maximized. (This problem is similar to a number of problems arising in electronic commerce, where agents need to select the "best" markets to trade their wares.) In the second set of experiments we investigate how runtime modification of agent utility functions and/or interagent interactions can improve performance beyond that of the initialized COIN. For this set of experiments we chose a problem where certain "follower" agents mimic the activities of other "leader" agents. The idea is to investigate a scenario where actions that are beneficial to a particular agent have deleterious global effects when copied by other agents.

COIN FRAMEWORK
As applied here, the COIN framework has three main components: 1. The first component investigates various formalizations of the desideratum that whenever the local utility functions increase, then so must the value of the world utility. It implicitly defines equivalence classes of local utility functions that meet those formalizations, for allowed agent interactions of various types. 2. There is little explicit concern for the dynamical nature of the COIN in this first component of the framework; that dynamics is subsumed under the assumption that the agents can achieve large values of their local utility functions, via their RL learning. However due to that dynamics it may be that the agents are all inadvertently "frustrating" each other, so that none of them can achieve large values of their local utility functions. The second component of the COIN framework addresses this problem by means of further restrictions (beyond those of the first component) on the allowed set of local utility functions. We call the design of a system's local utility functions using the two components of the COIN framework the COIN initialization of that system. 3. Successful COIN initialization ensures that if the agents in the system achieve large values of their local utility functions, then the world utility is also large. However due to uncertainties in the type of the agent interactions, in the real world the local utility functions set in the COIN initialization are usually only a good first guess. The third component of the COIN framework addresses this issue by modifying the local utility functions at run-time based on localized statistical information. We call this modifying process macrolearning. In contrast, we call the reinforcement learning that agents perform to optimize their local reward microlearning.
In this paper we consider the state of the system across a set of discrete, consecutive time steps, t ∈ {0, 1, ...}. Without loss of generality, we let all relevant characteristics of an agent at time t -including its internal parameters at that time as well as its externally visible actions -be encapsulated by a Euclidean vector ζ η,t . We call this the "state" of agent η at time t, and let ζ be the state of all agents across all time. World utility, G(ζ), is a function of the state of all agents across all time. Our goal as COIN designers is to maximize world utility.
The following concepts and definitions form the core of the COIN framework: Subworlds: Subworlds are the sets making up an exhaustive partition of all agents. For each subworld, ω, all agents in that subworld have the same subworld utility function gω(ζ) as their local utility functions. Accordingly, consider having each subworld be a set of agents that collectively have the most effect on each other. In this situation, by and large, agents cannot work at cross-purposes, since all agents that affect each other substantially share the same local utility.
Constraint-alignment: Associated with subworlds is the concept of a (perfectly) constraint-aligned system. That is a system in which any change to the state of the agents in subworld ω at time 0 will have no effect on the states of agents outside of ω at times later than 0. Intuitively, a system is constraint-aligned if no two agents in separate subworlds affect each other, so that the rationale behind the use of subworlds holds. (In the real world of course, systems are rarely exactly constraint-aligned.) Subworld-factored: A subworld-factored system is one where for each subworld ω considered by itself, a change at time 0 to the states of the agents in that subworld results in an increased value for gω(ζ) if and only if it results in an increased value for G(ζ). For a subworld-factored system, the side effects on the rest of the system of ω's increasing its own utility do not end up decreasing world utility. For these systems, the separate agents successfully pursuing their separate goals do not frustrate each other as far as world utility is concerned.
The definition of subworld-factored is carefully crafted. In particular, it does not concern changes in the value of the utility of subworlds other than the one changing its state. It also does not concern changes to the states of agents in more than one subworld at once. Indeed consider the following property: any change at time 0 to the entire system that improves all subworld utilities simultaneously also improves world utility. This might seem an appealing alternative desideratum to subworld-factoredness. However one can construct examples of systems that obey this property and yet quickly evolve to a minimum of world utility (for example this is the case in the TOC).
It can be proven that for a subworld-factored system, when each of the agents' reinforcement learning algorithms are performing as well as they can, given each others' behavior, world utility is at a critical point. Correct global behavior corresponds to learners reaching a Nash equilibrium [21]. There can be no tragedy of the commons for a subworld-factored system.
Wonderful life utility: Let CLω(ζ) be defined as the vector ζ modified by clamping the states of all agents in subworld ω, across all time, to an arbitrary fixed value, here taken to be 0. The wonderful life subworld utility (WL) is: (1) When the system is constraint-aligned, so that, loosely speaking, subworld ω's "absence" would not affect the rest of the system, we can view the WL utility as analogous to the change in world utility that would have arisen if subworld ω "had never existed". (Hence the name of this utilitycf. the Frank Capra movie.) Note however, that CL is a purely mathematical operation. Indeed, no assumption is even being made that CLω(ζ) is consistent with the dynamics of the system. The succession of states the agents in ω are clamped to in the definition of the WL utility need not obey the dynamical laws of the system. This dynamics-independence is a crucial strength of the WL utility. It means that to evaluate the WL utility we do not try to infer how the system would have evolved if all agents in ω were set to 0 at time 0 and the system evolved from there. So long as we know ζ extending over all time, and so long as we know G, we know the value of WL utility. This is true even if we know nothing of the dynamics of the system.
Another crucial advantage of the WL utility arises from the fact that in a COIN, each agent, by itself, is operating in a large system of other agents, and therefore may experience difficulty discerning the effects of its actions on its utility. Very often this problem is obviated by using the WL utility; the subtraction of the clamped term in the WL utility removes some of the "noise" of the activity of agents in other subworlds, leaving only the underlying "signal" of how the agents in the subworld at hand affect the utility. This makes it easier for the microlearning to improve the utility of the agents in that subworld. When the system is subworld factored, this property facilitates the improvement of world utility. In many circumstances, this cancelling characteristic of WL also ensures that the utility functions obey the applicable a priori locality restrictions on communications among agents.
The experiments in this paper revolve around the following fact: a constraint-aligned system with wonderful life subworld utilities is subworld-factored. Combining this with our previous result that subworld-factored systems are at equilibrium at critical points of world utility, this result leads us to expect that a constraint-aligned system using WL utilities in the microlearning will approach near-optimal values of the world utility.
No such assurances accrue to WL utilities if the system is not constraint-aligned however. Accordingly our first set of experiments investigates how well a particular system performs when WL utilities are used but little attention is paid to ensuring that the system is constraint-aligned. Our second set of experiments then focus on a macrolearning algorithm that modifies subworld memberships dynamically, so as to increase the degree of constraint-alignment, all while using WL local utility functions.

EXPERIMENTAL METHOD
We conducted two sets of experiments to investigate the COIN framework. The first set is a variant of Brian Arthur's bar-attendance model [1]. Since we are not interested here in directly comparing our results to those in [1,13], we use a more conventional (and arguably "dumber") reinforcement learning algorithm than the ones investigated in [1,13].
There are N agents, each of whom picks one of seven nights to attend a bar the following week, a process that is then repeated. In each week, each agent uses its own reinforcement learning (RL) algorithm to decide which night to attend to maximize its utility.
The world utility is of the form: where "xj (ζ, t)" means the j'th component of x(ζ, t) which is the attendance on night j at week t; γ k (y) ≡ α k y exp (−y/c); c and each of the {α k } are realvalued parameters. Intuitively, this world utility is the sum of the world "rewards" for each night in each week. This G is chosen to reflect the effects in the bar as the attendance profile of agents changes. In the case when there are too few agents, the bar suffers from lack of activity and therefore the world utility should be low. Conversely, when there are too many agents the bar becomes overcrowded and the rewards should also be low. Note that γ k (·) reaches its maximum when its argument equals c.
The α's are used to weight the importance of different nights. Two different choices of the {α k } are investigated. One treated attendance on all of the nights equally, As explicated below, our microlearning algorithms worked by providing a real-valued "reward" signal to each agent at each week t. Each agent's reward function is a surrogate for an associated utility function for that agent. The difference between the two functions is that the reward function only reflects the state of the system at one moment in time (and therefore is potentially observable), whereas the utility function reflects the agent's ultimate goal, and therefore can depend on the full history of that agent across time.
We investigated the following functions specifying the rewards at time t for each of the agents: • Uniform Division Reward: U D(dω(t), ζ, t) ≡ γ dω (x dω (ζ, t))/x dω (ζ, t) • Global Reward: • Wonderful Life Reward: where dω is the night selected by subworld ω. Note the distinction between utilities and rewards. For example, world utility is the sum over all time of global reward. The UD reward is considered a natural "naive" choice of an agent's reward function; the total reward on each night gets uniformly divided among the agents attending that night.
Providing the GR reward at time t to each agent is considered a reasonable way to provide that agent an approximation to the value of world utility that would ensue if the current policies of all the agents were henceforth frozen to their current polices. This reward function results in all agents receiving the same feedback information. For this reward, the system is automatically subworld-factored. However, evaluation of this function requires centralized communication.
Similarly, the WL reward at time t is considered a reasonable approximation to the WL utility. However, in contrast to the GR reward, to evaluate its WL reward each agent only needs to know the total attendance on the night it attended. In addition, as indicated above, one would expect that with the WL reward the microlearners can readily discern the effects of their rewards on their utilities -something not necessarily true if they use the GR reward.
Each agent is its own subworld. Each agent's microlearning algorithm uses a seven dimensional Euclidean vector to represent the expected reward for each night of the week. At the end of each week, the component of this vector corresponding to the night attended is proportionally adjusted towards the actual subworld reward just received. At the beginning of each week, the agent picks the night to attend using a Boltzmann distribution with energies given by the components of the vector of expected rewards. A decaying temperature is used to aid exploration in the early stage of the process. The microlearning algorithms are set to use the same parameters (i.e. learning rate, Boltzmann temperature, decay rates) for all three reward functions. This learning algorithm is equivalent to Claus and Boutilier's [8] independent learner algorithm for multi-agent reinforcement learning. Systems using the WL reward converged to optimal performance. This indicates that the bar problem is sufficiently constraint-aligned so that interactions between subworlds does not diminish performance. Presumably this is true because the only interactions between subworlds occurred indirectly, via the microlearning.

RESULTS
Moreover, since the WL reward is easier for the mi-crolearners to exploit (see above), one would expect the convergence using the WL reward to be far quicker than that using the GR reward. The GR reward does eventually converge to the global optimum. This is in agreement with the results obtained by Crites [9] for the bank of elevators control problem. However, when α = [0 0 0 7 0 0 0] the GR reward converged in 1250 weeks. This is more than 4 times the convergence time for the WL reward. When α = [1 1 1 1 1 1 1] the GR reward took 6500 weeks to converge, which was more than 30 times the time WL reward took to converge. This slow convergence is a result of the reward signal being diluted by the large number of agents in the system. In contrast to the behavior for reward functions based on the COIN framework, use of the UD subworld reward function results in very poor world reward values that deteriorated as the microlearning progressed. For the case where world reward only depends on a single night, this is essentially an instance of the tragedy of the commons; it is in every agent's interest to attend the same night, and their doing this shrinks the world reward "pie" that must be divided among all agents.
Taken together, these experiments demonstrate that the initialization prescriptions of the COIN framework can result in excellent global performance.

EXPERIMENTAL METHOD
In the experiments recounted in the previous section the system was sufficiently constraint-aligned for the WL reward to result in optimal performance. The second set of experiments involving leaders and followers also used WL reward. These experiments investigated the use of macrolearning to make an initially non-aligned system more constraintaligned, and thereby improve the world utility. In this experiment, macrolearning consists of changing the subworld memberships of the agents.
In these experiments the bar problem is modified to incorporate constraints designed to frustrate WL subworld reward. This is done by forcing the nights picked by some agents (followers) to agree with those picked by other agents (leaders). Each leader has two followers. The world utility is the sum, over all leaders, of the values of a triply-indexed reward matrix whose indices are the the nights that the leader and his two followers attend: where li(t) is the night the i th leader attends, and f 1i(t) and f 2i(t) are the nights attended by the followers of leader i, in week t. The system's dynamics is what restricts all the members of each triple (li(t), f 1i(t), f 2i(t)) to equal the night picked by leader i for week t. However, G and R are defined for all possible triples, li(t), f 1i(t) and f 2i(t). So in particular, R is defined for dynamically unrealizable triples that arise in the clamping operation. Because of this, for certain R's there exists subworld memberships such that the dynamics assures poor world utility when WL rewards are used. This is precisely the type of problem that macrolearning is designed to correct.
To investigate the efficacy of the macrolearning, two sets of separate experiments were conducted. In the first one the reward matrix R is chosen so that when leader and follower agents are placed in separate subworlds, leaders maximizing their WL reward results in minimal world reward. In contrast to the bar problem experiments, in these experiments, due to the coupling between leaders and followers, having each agent be its own subworld would mean badly violating constraint-alignment. (The idea is that by changing subworld memberships macrolearning can correct this and thereby induce constraint-alignment.) In the second set of experiments, rather than hand-crafting the worst-case reward matrix, we investigate the efficacy of macrolearning for a broader spectrum of reward matrices generated randomly.
For the worst-case reward matrix, the subworld membership that results in the most constraint-aligned system is when a leader and associated followers belong to the same subworld. The least constraint-alignment occurs when the leader and associated followers are all in separate subworlds. In addition to these two cases we also investigate random subworld membership. We investigate all these cases both with and without macrolearning, and with both worst case and a full spectrum of random reward matrices. The microlearning in these experiments is the same as in the bar problem. All leader-follower experiments use the WL subworld reward.
When macrolearning is used, it is implemented after the microlearning has run for a specified number of weeks. The macrolearning works by estimating the correlations between the nights picked by the agents. This is done by examining the attendances of the agents over the preceding weeks. The agents estimated to be the most correlated with one another are grouped into the same subworld, with the restriction that the number of agents per subworld is always three. Figure 2 presents performance averaged over 50 runs for world reward as a function of weeks using the worst case reward matrix. For comparison purposes, the top curve represents the case where the leaders and their followers are placed in the same subworld so that there is perfect constraintalignment. The bottom curve represents the other extreme where the leaders and their followers are placed in different subworlds resulting in minimal constraint-alignment. In both plots, the middle curve shows the performance of randomly initialized subworlds with (right) and without (left) macrolearning.

RESULTS
The performance for randomly assigned subworlds differs only slightly from that of having each agent be its own subworld; both start with poor values of world reward that deteriorates with time. However, when macrolearning is performed on systems with initially random subworld assignments, the system quickly rectifies itself and converges to optimal performance. This is reflected by the sudden vertical jump through the middle of the right plot at 500 weeks, the point at which macrolearning changes the subworld memberships. This demonstrates that by changing the subworld memberships macrolearning results in perfect constraint-alignment, so that the WL subworld reward function quickly induces the maximal value of the world reward. Figure 3 presents performance averaged over 50 runs for world reward as a function of weeks using a spectrum of reward matrices selected at random. The ordering of the plots is exactly as in Figure 2. Macrolearning is applied at 2000 weeks, in the right plot. The simulations in Figure 3 were lengthened from those in Figure 2 because the convergence time are longer.
The macrolearning algorithm results in a transient degradation in performance at 2000 weeks followed by convergence to the optimal. Without macrolearning the system's performance no longer varies after 2000 weeks. Combined with the results presented in Figure 2, these experiments demonstrate that the COIN construction of macrolearning works quite well.  Figure 3: Leader-follower problem for full spectrum reward matrices. The ordering of the plots is exactly as in Figure 3.
Macrolearning is applied at 2000 weeks, in the right plot.

CONCLUSION
For MAS's to fulfill their full potential, even when used in large systems having strong limitations on inter-agent interactions and communication, a way is needed to automatically configure/update the system to achieve the provided global goal. One approach to this problem is to have each agent run a reinforcement learning algorithm and then configure/update the associated reward functions (and other characteristics) of the agents so as to facilitate achievement of the global goal. This is the central concept embodied in COINs.
In this paper we presented a summary of (a portion of) the mathematical framework of COINs. We then presented two sets of experiments empirically validating the predictions of that framework. The first set of experiments considered difficult variants of Arthur's famous El Farol Bar problem. These experiments showed that even when the conditions required by the theorems of how to initialize a COIN do not hold exactly, they often hold well enough so that they can be applied with confidence. In those experiments, the COINs quickly achieved optimal performance despite the local nature of the information available to each agent, and in particular the COINs automatically avoided the tragedy of the commons that was designed into those experiments. This was not true when the reward functions were either set in a "naive" manner or were all set to equal the global reward.
The second set of experiments considered leader-follower problems that were hand-designed to cause maximal difficulty for those COIN initialization theorems. These experiments explicitly tested the run-time updating procedures of the COIN framework for overcoming such initialization problems. Here, as expected, the initial performance of the COIN was quite poor. However once the updating procedures were brought online, performance quickly rose to optimal. Again, this was in contrast to the case where the reward functions were either set in a "naive" manner or were all set to equal the global reward.
The conclusion of these experiments is that the prescriptions of the COIN framework for how to configure a large MAS often apply even when the exact conditions required by the associated theorems do not hold. Moreover, in those relatively unusual circumstances when the initialization prescriptions of the COIN theorems do not result in optimal global performance, the run-time updating component of the framework can rectify the situation, so that optimal performance is achieved.


extfieldsofstudy:
Computer Science
Mathematics

text:
A Hybrid Approach to Reasoning with Partially Elicited Preference Models

Classical Decision Theory provides a normative framework for representing and reasoning about complex preferences. Straightforward application of this theory to automate decision making is difficult due to high elicitation cost. In response to this problem, researchers have recently developed a number of qualitative, logic-oriented approaches for representing and reasoning about references. While effectively addressing some expressiveness issues, these logics have not proven powerful enough for building practical automated decision making systems. In this paper we present a hybrid approach to preference elicitation and decision making that is grounded in classical multi-attribute utility theory, but can make effective use of the expressive power of qualitative approaches. Specifically, assuming a partially specified multilinear utility function, we show how comparative statements about classes of decision alternatives can be used to further constrain the utility function and thus identify sup-optimal alternatives. This work demonstrates that quantitative and qualitative approaches can be synergistically integrated to provide effective and flexible decision support.

INTRODUCTION
Within the field of automated decision making, similar to the early days when probability theory was consid ered epistemologically inadequate, utility theory these days faces several epistemological problems of its own. In particular, it is often quite difficult to elicit the re quired utility function, especially when the outcomes of the decisions are complex. While  for eliciting a complete utility function from a user, doing so may be neither practical nor desirable. First, a large elicitation overhead may not be commensurate with the task at hand. Second, since people's prefer ences tend to change over time, we may wish to repre sent only that core of preferences that is relatively sta ble over some desired time period. Thus we would like to develop techniques for partially eliciting preferences and for reasoning with partially specified preferences in order to eliminate suboptimal decision alternatives.
Practitioners of decision theory have addressed the issue of eliciting utility functions by developing a comprehensive framework, generally known as multi attribute utility theory (MAUT) [10]. Lying at the heart of MAUT is the notion of utility independence, one of the first notions introduced to exploit qual itative, structural aspects of preference. Suppose that decision outcomes can be described by a set X = {XI> X2, ••• ,X,.} of attributes, meaning that an outcome x is a value assignment (X1 = Xt . X 2 = x 2 , ... ,X,. = X n ) to the attributes, a set Y C X is said to be utility independent of its complement X-Y, or Ul for short, if the preference over probability distribu tions P whose marginals over X-Y are a fixed, degen erate distribution Px-Y does not depend on Px_y.
Utility independence occurs quite often in real-life de cision making situations, and in general can be de tected easily. When a set of attributes Y is UI, a simple theorem shows that we can write the utility function u(x) as an expression that consists of two functions over X -Y and one function over Y, achieving a re duction of dimensionality (and hence complexity). In particular, if every subset Y of X is UI, a condition called mutual utility independence (M UI), then we can write u(x) either in a multiplicative form: n u(x) = IT (1 + k;u;(x;)), i=l or in an additive form: n u(x) = L k;u;(x;), i=l where u; are so-called sub-utility functions that cap ture the decision maker's preference with regard to attribute X; when holding the attributes X;,i "# i at some fixed level, and k; are constants that ensure proper global scaling 1 • Whenever MUI is applicable, the utility function can be obtained in the following two steps:  2In fact, in the case when there are more than 3 at tributes, assessment of MLUFs is usually abandoned [10].
placing a sizable elicitation burden on herself and on the decision maker.
Our perception is that in real-world applications of decision theory, decision analysts often choose the for mer option: to assume MUI. In this paper, we pro pose to study MLUFs 3 . Because complete elicitation of MLUFs is impractical, we set out to develop tech niques to reason with partially elicited MLUFs. In particular, these techniques are designed to identify sub-optimal decision alternatives without assessing all the 2n -1 scaling coefficients (expected utilities thus are not explicitly computed). The premises of these techniques are the following:  In Section 2, we show that the above assumptions can be captured by a polyhedral cone that constrains the unknown scaling coefficients ky. We then use standard optimization techniques to deduce further preferential information such as induced dominance and potential op timality from this constraint. An inherent benefit of these techniques is that they can be used to detect inconsistency in the prefence information elicited from the user. (We note that previously, Hazen presented a preference cone approach for reasoning with partially specified additive or multiplicative utility functions (9), which is similar to the approach presented in this pa per.) The key assumption in this approach is (iii), which ass umes that the decision maker can provide prefer ential comparisons between (real or fictious) decision consequences. This assumption is an integral part of interactive approaches to decision making (12,9,11).
The rationale for making this assumption is that there are certain circumstances where it might be easier for the decision maker to express preferences among de cision consequences than to introspect about the at tributes describing each one. For example, in express ing preferences about movies, most people can readily express their preferences over two films they have seen in the past but may have difficulty describing prefer ences over attributes like director, leading actor, or costum designer. In fact, most people would not even recognize the names of the costume designers, even when they may have a preference for films with nice costumes.
The more comparisons the decision maker can provide, the more conclusive inference can be made. In partic ular, if the decision maker can provide a succint, qual itative statement about her preference that implicitly encoded a set of comparision statements, then we may be able to quickly identify a large set of sub-optimal alternatives.
To capture such preferential statements and derive ef ficient inference mechanisms using them is one of the aims of the field of qualitative decision theory. Recent work from this fi eld has attempted to address the elici tation problem by providing formal languages in which partial preference information can be conveniently ex pressed [5,6,15,3,1]. For example, the languages pro posed by Doyle and Wellman [6] and by Tan and Pearl [15] attempt to provide a semantic to ceteris paribus (all else being equal) comparative statements. These are preferential statements concerning classes of deci sion consequences.
While these languages have successfully addressed a number of expressiveness issues, the inferential mech anisms available have not been sufficiently powerful for building practical decision making systems. In Section 3, we propose using ceteris paribus comparative state ments, as presented in [6], as a means to represent com parative statements made by the decision maker, to be used in conjunction with the assumptions (i), (ii), and (iii) described above. This combination provides us with a fl exible representation for eliciting preferences and an inferrential mechanism to effectively eliminate decision alternatives. The resulting hybrid framework is intended to strike a balance between logic-oriented (generally too weak), and numeric-oriented (generally too cost-intensive) approaches.
The rest of this paper is organized as follows. In Sec tion 2, we develop the preference cone framework to reason with partial MLUF and pairwise comparisions.
In Section 3, we propose to intergrate qualitative pref erential comparisons to the this framework and provide an example to illustrate this idea. We finish with dis-Reasoning with Partial Preference Models 265 cussion of related work and future research issues.

REASONING WITH PARTIALLY ELICITED MULTI-LINEAR UTILIT Y FUNCTIONS USING POLYHEDRAL CONES
In this section we explore the idea of using explicit pairwise comparisons of decision consequences to iden tify sub-optimal alternatives, as outlined in the Intro duction. The premises of this analysis are assumptions (i), (ii), (iii).

LINEAR CONSTRAINTS ON THE SCALING COEFFICIENTS OF MLUFS
First, note that the multilinear form of the utility func tion, as formalized in Equation (1) does not fully cap ture the assumption that the attributes X; are UI; the multilinear form is only a necessary but not sufficient condition for X; to be UI. We need to add constraints on the scaling coefficients ky in order to obtain a nec essary and sufficient condition.
Ta ke, for example, the assumption that X; is UI. Let Thus to say that X; is UI is equivalent to say that the coefficient for u; ( x;) in this linear function must be non-negative. Formally, this means L k {x;}uz tz(x);::: 0. (2)

Z�X-{X;}
Moreover, this inequality must be satisfied for any value assignment to the attributes in the set X-{X;}. Inversely, if this constraint is satisfied, then X; is UI. In other words, the utility independence of the attributes X; is precisely captured by the multilinear form as in Equation ( 1), with the additional linear, homogeneous constraints about the scaling constants, as expressed in Inequality ( 2).
To further simplify the expositions, we introduce the following notations. Let k denote the &-dimensional ( d = 2n -1) vector with components ky, 0 f. Y � X. For any i = 1, 2, ... , n, let s' denote the same dimension vector whose components are functions s� : X -t !R, 0 f. Y � X, defined as: Note that the functions s�(x) do not depend on x;, the i-th component of x. Inequality ( 2) can thus be written as (k, s'(x)) ::; 0, Vi= 1, 2, ... , n; x, where (., .) denotes the inner product of two vectors.
One may at first think that these constraints are by themselves strong enough to imply non-trivial prefer ences over decision alternatives. However, the results that we were able to obtain in our previous work [7], presented in the theorem below, suggest that further preferences can be deduced in only very special cases. (a) the utility junction is additive, or (b) in the probability distributions p and q, the attributes X;, when viewed as random variables, are probabilistically independent.
Furthermore, the inference is not sound if the utility junction is multiplicative.

LINEAR CONSTRAINTS FOR PAffiWISE COMPARISONS
In order to be able to infer a pairwise preference, we need to impose very strong conditions, either about the form of the utility function (it must be additive), or about alternatives (they must be probabilistically independent}, in addition to having the local domi nances. When these conditions do not hold, we need other sources of preferential information in order to be able to identify sub-optimal alternatives and to nar row down the set of candidate alternatives. One such source is pairwise comparison statements made by the decision maker. Note that the statement p ::$ q translates into the fol lowing inequalities: where tp (respectively tq) denotes the (2n -I) dimensional vector whose components are ty(p) (re spectively t11(q)). This last inequality is also a linear, homogeneous constraint over the unknown constants ky.

SOME BASIC CONCEPTS OF CONVEX CONE ANALYSIS
Before we continue our analysis, we provide a brief review of some basic concepts of convex cone analysis.

Polyhedra, Cones, and Polyhedral Cones
The d-dimension Euclidean Space is the vector space !Rd equipped with the inner product(). Given a vector n, and a E !R, the set 11a = {x/(n,x) =a} is called a hyperplane, the set n;; = { x/ (n, x) :::; a} is called a closed hal/space with outward normal n. For simplicity of notations, the subscript a is omitted when a = 0.
The intersection of a finite number of closed halfspaces is called a polyhedron.
with apex 0. In this paper, cones are all 0-apexed, unless indicated otherwise. Given a set W � !Rd, the set of all points that can be expressed as non-negative linear combinations of points of W can be shown to be a convex cone, and is denoted by Cw. This cone is called the convex cone generated by W and can be equivalently defined as the smallest convex cone con taining W. A cone that is also a polyhedron is called a polyhedral cone. It is well-known that polyhedral cones are precisely convex cones generated by finite sets of points, and can be shown to be closed.

Dual Cones
Given a set w � �. let w· be defined as w· := {YI(x,y) $ 0, 'v'x E W}. W* is easily shown to be a convex cone and is refered to as the dual cone of W. For example, if W contains a single point n, then the dual cone of W is n-, the closed halfspace with outward normal n.
The following theorem is standard in convex cone anal ysis. Assuming that the domain of each attribute X; is fi nite, the above inequalities are equivalent to a finite set of linear homogeneous constraints over the scaling coefficients ky. From now on, we denote these con straints as follows { (k, w;) ::; Olj = l..m}, and denote W = {w;li = l..m}. Thus, the utility function u, when represented as a vector k with coordinates ky, must lie in the intersection of the closed halfspaces with outward normal w;: m kEK:= n w j .

j= l
This intersection is a polyhedral cone, which is the dual cone K = W* of W. Using Theorem 2, we have that K* = w•• = Cw, i.e., the dual cone of K, the set of admissible k, is the polyhedral cone generated by the constraint vectors w; (see Figure 1).

Induced Dominance
The above analysis i=ediately leads to the following result that can be used to test for induced dominance.
Reasoning with Partial Preference Models 267 Figure 1: A 2-dimensional illustration of Theorem 3.

Here W = {wbw2}·
Theorem 3 Given a pair of alternatives (p, q), we can deduce p ::5 q iff tp -tq E Cw. The "only if " part means that if tp -tq ¢ Cw, then there exists k E K such that (k, tp -tq) > 0, i.e. p >-q under such k.
Below is an algorithm for testing induced dominance. This "inference rule" is sound and complete based on the above theorem.

Complexity Analysis
The complexity of Algorithm 1 is determined by the complexity of determining the generators {k 1 ll} of the polyhedral cone K (step 1). These vectors are out ward normal vectors of the ( d-1 )-dimension facets of the polyhedron Cw. This problem is essentially the same problem as finding the facet normals of the con vex hull of a set of points in the (d-I)-dimension space, which can be solved in time O(m r d /21 -1 ) using algorithms from computational geometry [14). Here, m is the number of the elements of W, and d = 2" -1 is the dimension of the space (which is the number of the scaling coefficients).
To conclude this section, we note that in complex de cision making problems, the decision maker may easily exhibit inconsistent preferences. For example, she may assert a set of comparative statements that results in an empty preference cone (K = 0). In sucll situa tions, we would like the system to restore consistency by eliminating one or more "problematic" compara tive statements. But how to identify sucll problematic statements is an open question and needs further re search and experiment. 3

INTERGRATING QUALITATIVE COMPARATIVE STATEMENTS
In the previous section we have shown how compar ative statements about decision consequences can be exploited to test for induced dominance and potential optimality. Since there are 2" -1 unknown scaling coefficients, cllances are that we would need an inor dinately large number of pair-wise comparisions from the decision maker in order to make useful inferences.
Qualitative preference logics such as those proposed by Doyle and Wellman [5,6) and Tan and Pearl [15) provide languages that can express comparative state ments about classes of decision consequences. Sucll a qualitative expression of preferences gives us a large number of pair-wise preferences among individual de cision conequences, which can be used to effectively constrain the space of utility functions.
In this section we give an example to illustrate this idea. In this example, the state space has three propo sitional attributes {X1,X2,X3} with domains {0,1}. Suppose also that the attributes are utility indepen dent in sucll a way that for eacll attribute, 1 is the prefered value. This means that the sub-utility func tions u;(x;) for the attributes are given by u;(x;) = x;. The overall utility function can be written as u(x1,x2,xa) = k1x1 + k2x2 + kaxa + k12X1X2 + k13X1X3 + �3X2X3 + k123X1X2X3.
Next, we translate the assumption about utility inde pendence of the attributes into constraints about the scaling constants. Let us consider attribute X1. To say that X1 is UI is equivalent to say that the overall utility function u(x1, x2, xa) = (k1 + k12X2 + k1axa + k123X2xa)x1 + �x2 + kaxa + k2ax2xa, when viewed as a linear function of x1 must have pos itive coefficient for X1, i.e.
Considering all value assigments for x2 and x3, the UI ass umption for xl implies the following inequalities involving the scaling constants: The utility independence for X2 and Xa can be ex pressed similarly: Note that the inequality k1 > 0 is equivalent to the comparison statement (0, 0, 0) -< (1, 0, 0), and the in equality k1 +k12 > 0 is equivalent to (0, 1, 0) -< (1, 1, 0). Now suppose that the decision maker states that she prefers to have (x1 = 1, X2 = 0) to (x1 = 0, x2 = 1), all else being equal, i.e. regardless of the value of x3. This statement is equivalent to the following constraints: (6) Using Algorithm 1 with the Constraints ( 3), (4), (5), and (6), we will be able to obtain that, for example, In contrast, in this paper, the consequences of deci sions are uncertain. Furthermore, in work in MCDM, the value function is usually assumed to have some tractable form such as (in increasing order of gener ality) linear (16], quasiconcave (12,13], or monotonic (11]. In this paper, the decision maker's utilty func tion is assumed to have multi-linear form. Since multi linear functions can be non-monotonic (see Theorem However, the inference mechanisms offered by these languages remain rather weak.
It is thus highly desirable to develope a framework that can exploit different strengths of these different quantitative and qualitative approaches. In this paper, we attempt to provide such a framework. Assuming a multi-linear utility function with known sub-utility functions, we show how ceteris paribus comparative statements by the decision maker can be used to infer further preferential information such as induced pair wise preference and sub-optimality.

269
There are several issues that we plan to address in this framework. The first issue is efficiency. Note that the time complexity of Algorithm 1 is exponen tial (O(mf"/21-I )). The base of this upper bound, which is the number of the constraint vectors w;, can be large. A possible solution for this is to investi gate ways to effectively use sets of comparisions, repre sented by qualitative logical constructs. For example, a ceteris paribus comparison, which is equivalent to a set of comparisions between individual decision conse quences, can sometimes be captured by a single linear inequality involving certain (but not all) scaling coef ficients. This would result in fewer constraint vectors.
With regard to the exponent of the upper bound, since in practice, the number of attributes ( n) is usually very small (3-8), we expect the exponent (rd/21-1) not to exceed 127. We can also try to exploit further util ity independencies, if applicable, to reduce the num ber of scaling coefficients and to reduce the exponent.
For example, if Y is UI of X -Y and IYI = r, then the number of scaling coefficients can be reduced to 2r + 2n-r+I -4. If both Y and X -Y are UI of the other, then the number can be reduced to 2r + 2n-r-2 (Keeney & Raiffa 1976 (10], Chapter 6.10.3). Finally, we point out that since the motivation of our work is to reduce the elicitation time, which in most cases is much larger than the computation time, this approach to reasoning with partial preference information could sometimes provide an attractive option despite the in volved computational complexity.
Second, instead of working with only the supplied pref erences, we may want the system to take the initiative and ask the user to make comparisons between deci sion consequences, or sets of decision consequences (us ing some qualitative logical constructs). To this end, the most interesting issue is identifying the questions whose answers would lead to the most conclusive infer ence, e.g., induced optimality of a particular decision alternative, or induced sub-optimality of a large num ber of decision alternatives 5• A difficulty with this approach is that the user may not be able to answer some of those queries.
Finally, it is interesting to see if this approach to rea soning with partially elicited preference information can be intergrated into the case-based framework to preference elicitation advocated in our recent work [8] (see also (4]). In this framework, the system maintains a population of users with their preferences partially or completely specified in a given domain. When en countering a new user, called A, the system first elicits some preference information from A, and then deter mines which user in the population has the preference 50ur previous work [7] has addressed this issue in a special case when the utility function is additive. structure that is closest to A's. The preference struc ture of that user will be used to determine an initial default representation (or working model) of A's pref erences. We can use the techniques presented in this paper to elicit some initial preference information from the decision maker and to eliminate some sub-optimal decision alternatives. If the set of remaining decision candidates is still large, the system can use the case based approach to make recommendations for the de cision maker.