Content deleted Content added
No edit summary |
m Open access bot: doi updated in citation with #oabot. |
||
Line 23:
There are various random utility models, which differ in the assumptions on the probability distributions of the agent's utility, A popular random utility model was developed by Luce<ref>{{cite book |last1=Luce |first1=R. Duncan |title=Individual Choice Behavior: A Theoretical Analysis |date=2012 |publisher=Courier Corporation |isbn=978-0-486-15339-1 }}{{pn|date=November 2023}}</ref> and Plackett.<ref>{{cite journal |last1=Plackett |first1=R. L. |title=The Analysis of Permutations |journal=Applied Statistics |date=1975 |volume=24 |issue=2 |pages=193–202 |doi=10.2307/2346567 |jstor=2346567 }}</ref> They assume that the random utility terms are generated according to [[Gumbel distribution]]s with fixed shape parameter. In the Plackett-Luce model, the likelihood function has a simple analytical solution, so [[maximum likelihood estimation]] can be done in polynomial time.
The Plackett-Luce model was applied in [[econometrics]],<ref>{{cite book |last1=McFadden |first1=Daniel |chapter=Conditional Logit Analysis of Qualitative Choice Behavior |pages=105–142 |editor1-last=Zarembka |editor1-first=Paul |title=Frontiers in Econometrics |date=1974 |publisher=Academic Press |isbn=978-0-12-776150-3 }}</ref> for example, to analyze automobile prices in [[market equilibrium]].<ref>{{cite journal |last1=Berry |first1=Steven |last2=Levinsohn |first2=James |last3=Pakes |first3=Ariel |title=Automobile Prices in Market Equilibrium |journal=Econometrica |date=1995 |volume=63 |issue=4 |pages=841–890 |doi=10.2307/2171802 |jstor=2171802 }}</ref> It was also applied in [[Machine learning in earth sciences|machine learning]] and [[information retrieval]].<ref>{{cite journal |last1=Liu |first1=Tie-Yan |title=Learning to Rank for Information Retrieval |journal=Foundations and Trends® in Information Retrieval |date=2007 |volume=3 |issue=3 |pages=225–331 |doi=10.1561/1500000016 }}</ref> It was also applied in [[Social choice theory|social choice]], to analyze an opinion poll conducted during the [[1997 Irish presidential election|Irish presidential election]].<ref>{{cite journal |last1=Gormley |first1=Isobel Claire |last2=Murphy |first2=Thomas Brendan |title=A grade of membership model for rank data |journal=Bayesian Analysis |date=June 2009 |volume=4 |issue=2 |doi=10.1214/09-BA410 |s2cid=53559452 |doi-access=free }}</ref> Efficient methods for [[expectation-maximization]] and [[Expectation propagation]] exist for the Plackett-Luce model.<ref>{{cite journal |last1=Caron |first1=François |last2=Doucet |first2=Arnaud |title=Efficient Bayesian Inference for Generalized Bradley–Terry Models |journal=Journal of Computational and Graphical Statistics |date=January 2012 |volume=21 |issue=1 |pages=174–196 |doi=10.1080/10618600.2012.638220 |arxiv=1011.1761 |s2cid=42955305 }}</ref><ref>{{cite journal |last1=Hunter |first1=David R. |title=MM algorithms for generalized Bradley-Terry models |journal=The Annals of Statistics |date=February 2004 |volume=32 |issue=1 |doi=10.1214/aos/1079120141 |doi-access=free }}</ref><ref>{{cite book |doi=10.1145/1553374.1553423 |chapter=Bayesian inference for Plackett-Luce ranking models |title=Proceedings of the 26th Annual International Conference on Machine Learning |date=2009 |last1=Guiver |first1=John |last2=Snelson |first2=Edward |pages=377–384 |isbn=978-1-60558-516-1 |s2cid=16965626 }}</ref>
Azari, [[David C. Parkes|Parkes]] and Xia<ref name=":4">{{Cite journal |last1=Azari |first1=Hossein |last2=Parks |first2=David |last3=Xia |first3=Lirong |date=2012 |title=Random Utility Theory for Social Choice |url=https://proceedings.neurips.cc/paper/2012/hash/a512294422de868f8474d22344636f16-Abstract.html |journal=Advances in Neural Information Processing Systems |publisher=Curran Associates, Inc. |volume=25|arxiv=1211.2476 }}</ref> extend the Plackett-Luce model: they consider random utility models in which the random utilities can be drawn from any distribution in the [[Exponential family]]. They prove conditions under which the log-likelihood function is concave, and the set of global maxima solutions is bounded for a family of random utility models where the shape of each distribution is fixed and the only latent variables are the means.
Line 34:
* It ignores the strength of agents' expressed preferences. An agent who prefers a "much more than" b and an agent who prefers a "a little more than b" are treated the same.
* It allows for cyclic preferences. There is a positive probability that an agent will prefer a to b, b to c, and c to a.
* The maximum likelihood estimator - which is the [[Kemeny–Young method]] - is hard to compute (it is <math>\Theta^P_2</math>-complete).<ref>{{cite journal |last1=Hemaspaandra |first1=Edith |last2=Spakowski |first2=Holger |last3=Vogel |first3=Jörg |title=The complexity of Kemeny elections |journal=Theoretical Computer Science |date=December 2005 |volume=349 |issue=3 |pages=382–391 |doi=10.1016/j.tcs.2005.08.031 |doi-access=free }}</ref>
Random utility models provides an alternative: there is a ground-truth vector of utilities; each agent draws a utility for each alternative, based on a probability distribution whose mean value is the ground-truth. This model captures the strength of preferences, and rules out cyclic preferences. Moreover, for some common probability distributions (particularly, the Plackett-Luce model), the maximum likelihood estimators can be computed efficiently.
| |||