Star-shaped preferences: Difference between revisions
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
| (9 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
In [[social choice theory]], '''star-shaped preferences'''<ref name=":0">{{Cite journal | |
In [[social choice theory]], '''star-shaped preferences'''<ref name=":0">{{Cite journal |last1=Border |first1=Kim C. |last2=Jordan |first2=J. S. |date=1983 |title=Straightforward Elections, Unanimity and Phantom Voters |url=https://www.jstor.org/stable/2296962 |journal=The Review of Economic Studies |volume=50 |issue=1 |pages=153–170 |doi=10.2307/2296962 |jstor=2296962 |issn=0034-6527}}</ref> are a class of [[Preference (economics)|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 == |
== 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 |
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<sup>''m''</sup> - 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. |
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''. 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]. |
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'''.<ref name=":0"/>{{Rp|page=4}} 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]. |
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'''.<ref name=":0"/>{{Rp|page=4}} 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]. |
||
| Line 16: | Line 16: | ||
* '''[[Single-peaked preferences]]''' are star-shaped preferences in the special case in which the set of possible distributions is a (one-dimensional) line. |
* '''[[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|utility function]] u('''q''') := - d('''p''','''q'''). |
* '''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|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 <math>\ell_p</math> metrics for all <math>p\geq 1</math>. |
||
* '''Quadratic preferences'''.<ref name=":0" /> There is a matrix A, and the preferences can be represented by a function u('''q''') := - ('''q'''-'''p''')<sup>T</sup> * A * ('''q'''-'''p'''). Note that if A is the [[identity matrix]] then u('''q''') is minus the [[Euclidean distance]] <math>\ell_2</math>, so in this case the preferences are also metric-based. |
* '''Quadratic preferences'''.<ref name=":0" /> There is a matrix A, and the preferences can be represented by a function u('''q''') := - ('''q'''-'''p''')<sup>T</sup> * A * ('''q'''-'''p'''). Note that if A is the [[identity matrix]] then u('''q''') is minus the [[Euclidean distance]] <math>\ell_2</math>, so in this case the preferences are also metric-based. |
||
== Alternative |
== Alternative definitions == |
||
Freitas, Orillo and Sosa<ref name=":1">{{Cite journal | |
Freitas, Orillo and Sosa<ref name=":1">{{Cite journal |last1=Braga de Freitas |first1=Sinval |last2=Orrillo |first2=Jaime |last3=Sosa |first3=Wilfredo |date=2020-11-01 |title=From Arrow–Debreu condition to star shape preferences |url=https://www.tandfonline.com/doi/full/10.1080/02331934.2019.1576664 |journal=Optimization |language=en |volume=69 |issue=11 |pages=2405–2419 |doi=10.1080/02331934.2019.1576664 |issn=0233-1934}}</ref> 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 <ref name=":0" /> are also star-shaped according to.<ref name=":1" /> ''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.{{Clarify|date=September 2024}} |
||
Landsberger and Meilijson<ref>{{Cite journal |last1=Landsberger |first1=Michael |last2=Meilijson |first2=Isaac |date=1990-10-01 |title=Lotteries, insurance, and star-shaped utility functions |url=https://www.sciencedirect.com/science/article/abs/pii/002205319090064Q |journal=Journal of Economic Theory |volume=52 |issue=1 |pages=1–17 |doi=10.1016/0022-0531(90)90064-Q |issn=0022-0531}}</ref> 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 [[Lottery|lotteries]]. |
|||
== Results == |
== Results == |
||
Border and Jordan<ref name=":0" /> characterize the [[Strategyproof|strategyproof mechanisms]] for agents with quadratic preferences - a special case of star-shaped preferences (see [[median voting rule]]). |
Border and Jordan<ref name=":0" /> characterize the [[Strategyproof|strategyproof mechanisms]] for agents with quadratic preferences - a special case of star-shaped preferences (see [[median voting rule]]). |
||
Lindner, Nehring and Puppe<ref>http://www.accessecon.com/pubs/SCW2008/GeneralPDFSCW2008/SCW2008-08-00132S.pdf</ref> and Goel, Krishnaswami, Sakshuwong and Aitamurto<ref>{{Cite journal | |
Lindner, Nehring and Puppe<ref>http://www.accessecon.com/pubs/SCW2008/GeneralPDFSCW2008/SCW2008-08-00132S.pdf</ref> and Goel, Krishnaswami, Sakshuwong and Aitamurto<ref>{{Cite journal |last1=Goel |first1=Ashish |last2=Krishnaswamy |first2=Anilesh K. |last3=Sakshuwong |first3=Sukolsak |last4=Aitamurto |first4=Tanja |date=2019-07-29 |title=Knapsack Voting for Participatory Budgeting |url=https://dl.acm.org/doi/abs/10.1145/3340230 |journal=ACM Trans. Econ. Comput. |volume=7 |issue=2 |pages=8:1–8:27 |doi=10.1145/3340230 |issn=2167-8375|arxiv=2009.06856 }}</ref> study agents with metric-based preferences with the <math>\ell_1</math> metric. |
||
{{Under construction|placedby=Erel Segal}} |
|||
== References == |
== References == |
||
Latest revision as of 09:03, 29 September 2024
In social choice theory, star-shaped preferences[1] 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
[edit]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 Rm - 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.[1]: 4 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
[edit]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 metrics for all .
- Quadratic preferences.[1] 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 , so in this case the preferences are also metric-based.
Alternative definitions
[edit]Freitas, Orillo and Sosa[2] 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 [1] are also star-shaped according to.[2] 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.[clarification needed]
Landsberger and Meilijson[3] 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
[edit]Border and Jordan[1] characterize the strategyproof mechanisms for agents with quadratic preferences - a special case of star-shaped preferences (see median voting rule).
Lindner, Nehring and Puppe[4] and Goel, Krishnaswami, Sakshuwong and Aitamurto[5] study agents with metric-based preferences with the metric.
References
[edit]- ^ a b c d e Border, Kim C.; Jordan, J. S. (1983). "Straightforward Elections, Unanimity and Phantom Voters". The Review of Economic Studies. 50 (1): 153–170. doi:10.2307/2296962. ISSN 0034-6527. JSTOR 2296962.
- ^ a b Braga de Freitas, Sinval; Orrillo, Jaime; Sosa, Wilfredo (2020-11-01). "From Arrow–Debreu condition to star shape preferences". Optimization. 69 (11): 2405–2419. doi:10.1080/02331934.2019.1576664. ISSN 0233-1934.
- ^ Landsberger, Michael; Meilijson, Isaac (1990-10-01). "Lotteries, insurance, and star-shaped utility functions". Journal of Economic Theory. 52 (1): 1–17. doi:10.1016/0022-0531(90)90064-Q. ISSN 0022-0531.
- ^ http://www.accessecon.com/pubs/SCW2008/GeneralPDFSCW2008/SCW2008-08-00132S.pdf
- ^ Goel, Ashish; Krishnaswamy, Anilesh K.; Sakshuwong, Sukolsak; Aitamurto, Tanja (2019-07-29). "Knapsack Voting for Participatory Budgeting". ACM Trans. Econ. Comput. 7 (2): 8:1–8:27. arXiv:2009.06856. doi:10.1145/3340230. ISSN 2167-8375.