Star-shaped preferences

In social choice theory, star-shaped preferences are a class of preferences over points in a Euclidean space. An agent with star-shaped preferences has a unique ideal point (optimum), where he is maximally satisfied. Moreover, he becomes less and less satisfied as the actual distribution moves away from his optimum. Star-shaped preferences can be seen as a multi-dimensional extension of single-peaked preferences.

Background

Often, society has to choose a point from a subset of an Euclidean space. For example, society has to choose how to distribute its annual budget; each potential distribution is a vector of real numbers. If there are m potential issues in the budget, then the set of all potential budget distributions is a subset of R^m - the m-dimensional Euclidean space.

Different members of society may have different preferences over budget distributions. A preference is any total order over points. For example, a particular agent may state that he prefers the distribution [0.5, 0.3, 0.2] to [0.4, 0.3, 0.3], prefers [0.4, 0.3, 0.3] to [0, 1, 0], and so on.

Often, agents express their preferences in a simplified way: instead of stating their preferred distributions for all infinitely-many pairs of distributions, they state one distribution, which they consider ideal, which they prefer over all other distributions; this distribution is called their optimum or their peak. However, knowing the optimum of an agent is insufficient for deciding which of two non-optimal distributions they prefer. For example, if an agent's optimum is [0.5, 0.3, 0.2], in theory this tells us nothing about his preference between [0.7, 0.2, 0.1] and [0.9, 0.1, 0.0].

We say that an agent has star-shaped preferences if, informally, he prefers points nearer to his optimum to points farther from his optimum. Formally, denote the optimum by p, and denote some other distribution by q. Let r be any distribution on the line connecting p and q (that is, r := t*q + (1-t)*p, for some real number t in (0,1)). Then, star-shaped preferences always strictly prefer r to q. In particular, in the above example, when p=[0.5, 0.3, 0.2], star-shaped preferences always prefer r=[0.7, 0.2, 0.1] to q=[0.9, 0.1, 0.0].

Note that the star-shaped assumption does not say anything about the preferences between points that are not on the same line. In the above example, an agent with star-shaped preferences and optimum [0.5, 0.3, 0.2] may prefer [0.7, 0.2, 0.1] to [0.3, 0.2, 0.5] or vice-versa.

Special cases

Several sub-classes of star-shaped preferences have received special attention.

• Single-peaked preferences are star-shaped preferences in the special case in which the set of possible distributions is a (one-dimensional) line.
• Metric-based preferences. There is a metric d on the Euclidean space, and every agent prefers a point q to a point r iff d(p,q) ≤ d(p,r). Metric-based preferences can be represented by a utility function u(q) := - d(p,q). Metric-based preferences are star-shaped if the metric satisfies the following property: if all coordinates of p move closer to q, then the distance d(p,q) strictly decreases. In particular, this holds for $\ell _{p}$ metrics for all $p\geq 1$.
• Quadratic preferences. There is a matrix A, and the preferences can be represented by a function u(q) := - (q-p)^T * A * (q-p). Note that if A is the identity matrix then u(q) is minus the Euclidean distance $\ell _{2}$, so in this case the preferences are also metric-based.

Alternative definitions

Freitas, Orillo and Sosa define star-shaped preferences as follows: for every point q, the set of points r that are (weakly) preferred to q is a star domain. Every star-shaped preferences according to are also star-shaped according to. Proof: for every point q, and every point r that is preferred to q, all points on the line between r and the optimum (p) are preferred to r, and therefore by transitivity also preferred to q. Hence, the set of all these points is a star domain with respect to the optimum p. It is not clear whether the converse holds too.

Landsberger and Meilijson define star-shaped utility functions. A weakly-increasing function u is called star-shaped w.r.t. a point t, if its average slope [u(x)-u(t)]/[x-t] is a weakly-decreasing function of x on (-∞,t) and on (t,∞). They use this definition to explain the fact that people purchase both insurance and lotteries.

Results

Border and Jordan characterize the strategyproof mechanisms for agents with quadratic preferences - a special case of star-shaped preferences (see median voting rule).

Lindner, Nehring and Puppe and Goel, Krishnaswami, Sakshuwong and Aitamurto study agents with metric-based preferences with the $\ell _{1}$ metric.