Draft:Random utility model

A basic assumption in classic economics is that the choices of a rational person choices are guided by a preference relation, which can usually be described by a utility function. When faced with several alternatives, the person will choose the alternative with the highest utility. The utility function is not visible; however, by observing the choices made by the person, we can "reverse-engineer" his utility function. This is the goal of revealed preference theory.

In practice, however, people are not rational. Ample empirical evidence shows that, when faced with the same set of alternatives, people may make different choices.{{Cite journal |last=Camerer |first=Colin F. |date=1989-04-01 |title=An experimental test of several generalized utility theories |url=https://doi.org/10.1007/BF00055711 |journal=Journal of Risk and Uncertainty |language=en |volume=2 |issue=1 |pages=61–104 |doi=10.1007/BF00055711 |s2cid=154335530 |issn=1573-0476}}{{Cite journal |last1=Starmer |first1=Chris |last2=Sugden |first2=Robert |date=1989-06-01 |title=Probability and juxtaposition effects: An experimental investigation of the common ratio effect |url=https://doi.org/10.1007/BF00056135 |journal=Journal of Risk and Uncertainty |language=en |volume=2 |issue=2 |pages=159–178 |doi=10.1007/BF00056135 |s2cid=153567599 |issn=1573-0476}}{{Cite journal |last1=Hey |first1=John D. |last2=Orme |first2=Chris |date=1994 |title=Investigating Generalizations of Expected Utility Theory Using Experimental Data |url=https://www.jstor.org/stable/2951750 |journal=Econometrica |volume=62 |issue=6 |pages=1291–1326 |doi=10.2307/2951750 |jstor=2951750 |s2cid=120069179 |issn=0012-9682}}{{Cite journal |last=Wu |first=George |date=1994-02-01 |title=An empirical test of ordinal independence |url=https://doi.org/10.1007/BF01073402 |journal=Journal of Risk and Uncertainty |language=en |volume=9 |issue=1 |pages=39–60 |doi=10.1007/BF01073402 |s2cid=153558846 |issn=1573-0476}}{{Cite journal |last1=Ballinger |first1=T. Parker |last2=Wilcox |first2=Nathaniel T. |date=1997-07-01 |title=Decisions, Error and Heterogeneity |url=https://academic.oup.com/ej/article/107/443/1090-1105/5065251 |journal=The Economic Journal |language=en |volume=107 |issue=443 |pages=1090–1105 |doi=10.1111/j.1468-0297.1997.tb00009.x |s2cid=153823510 |issn=0013-0133}} To an outside observer, their choices may appear random.

One way to model this behavior is called stochastic rationality. It is assumed that each agent has an unobserved state, which can be considered a random variable. Given that state, the agent behaves rationally. In other words: each agent has, not a single preference-relation, but a distribution over preference-relations (or utility functions).

Block and Marschak{{Citation |last=Block |first=H. D. |title=Random Orderings and Stochastic Theories of Responses (1960) |date=1974 |url=https://doi.org/10.1007/978-94-010-9276-0_8 |work=Economic Information, Decision, and Prediction: Selected Essays: Volume I Part I Economics of Decision |pages=172–217 |editor-last=Marschak |editor-first=Jacob |access-date=2023-11-07 |series=Theory and Decision Library |place=Dordrecht |publisher=Springer Netherlands |language=en |doi=10.1007/978-94-010-9276-0_8 |isbn=978-94-010-9276-0}} presented the following problem. Suppose we are given as input, a set of choice probabilities P_a,B, describing the probability that an agent chooses alternative a from the set B. We want to rationalize the agent's behavior by a probability distribution over preference relations. That is: we want to find a distribution such that, for all pairs a,B given in the input, P_a,B = Prob[a is weakly preferred to all alternatives in B]. What conditions on the set of probabilities P_a,B guarantee the existence of such a distribution?

Falmagne{{Cite journal |last=Falmagne |first=J. C. |date=1978-08-01 |title=A representation theorem for finite random scale systems |url=https://dx.doi.org/10.1016/0022-2496%2878%2990048-2 |journal=Journal of Mathematical Psychology |volume=18 |issue=1 |pages=52–72 |doi=10.1016/0022-2496(78)90048-2 |issn=0022-2496}} solved this problem for the case in which the set of alternatives is finite: he proved that a probability distribution exists iff a set of polynomials derived from the choice-probabilities, denoted Block-Marschak polynomials, are nonnegative. His solution is constructive, and provides an algorithm for computing the distribution.

Barbera and Pattanaik{{Cite journal |last1=Barberá |first1=Salvador |last2=Pattanaik |first2=Prasanta K. |date=1986 |title=Falmagne and the Rationalizability of Stochastic Choices in Terms of Random Orderings |url=https://www.jstor.org/stable/1911317 |journal=Econometrica |volume=54 |issue=3 |pages=707–715 |doi=10.2307/1911317 |jstor=1911317 |issn=0012-9682}} extend this result to settings in which the agent may choose sets of alternatives, rather than just singletons.

Block and Marschak proved that, when there are at most 3 alternatives, the random utility model is unique ("identified"); however, when there are 4 or more alternatives, the model may be non-unique. For example,https://scholar.harvard.edu/files/tomasz/files/lisbon32-post.pdf we can compute the probability that the agent prefers w to x (w>x), and the probability that y>z, but may not be able to know the probability that both w>x and y>z. There are even distributions with disjoint supports, which induce the same set of choice probabilities.

Some conditions for uniqueness were given by Falmagne. Turansick{{Cite journal |last=Turansick |first=Christopher |date=2022-07-01 |title=Identification in the random utility model |url=https://www.sciencedirect.com/science/article/pii/S0022053122000795 |journal=Journal of Economic Theory |volume=203 |pages=105489 |doi=10.1016/j.jet.2022.105489 |arxiv=2102.05570 |s2cid=231861383 |issn=0022-0531}} presents two characterizations for the existence of a unique random utility representation.

There are various RUMs, which differ in the assumptions on the probability distributions of the agent's utility, A popular RUM was developed by Luce{{Cite book |last=Luce |first=R. Duncan |url=https://books.google.com/books?id=ERQsKkPiKkkC&dq=R.+Duncan+Luce.+Individual+Choice+Behavior%3A+A+Theoretical+Analysis.+Wiley%2C+1959.&pg=PP1 |title=Individual Choice Behavior: A Theoretical Analysis |date=2012-06-22 |publisher=Courier Corporation |isbn=978-0-486-15339-1 |language=en}} and Plackett.{{Cite web |url=https://academic.oup.com/jrsssc/article-abstract/24/2/193/6953554 |access-date=2023-11-07 }}

The Plackett-Luce model was applied in econometrics,{{Cite journal |last=D |first=Mcfadden |date=1974 |title=Conditional Logit Analysis of Qualitative Choice Behavior |url=https://cir.nii.ac.jp/crid/1572824500127838080 |journal=Frontiers in Econometrics}} for example, to analyze automobile prices in market equilibrium.{{Cite journal |last1=Berry |first1=Steven |last2=Levinsohn |first2=James |last3=Pakes |first3=Ariel |date=1995 |title=Automobile Prices in Market Equilibrium |url=https://www.jstor.org/stable/2171802 |journal=Econometrica |volume=63 |issue=4 |pages=841–890 |doi=10.2307/2171802 |jstor=2171802 |issn=0012-9682}} It was also applied in machine learning and information retrieval.{{Cite journal |last=Liu |first=Tie-Yan |date=2009-06-26 |title=Learning to Rank for Information Retrieval |url=https://www.nowpublishers.com/article/Details/INR-016 |journal=Foundations and Trends® in Information Retrieval |language=English |volume=3 |issue=3 |pages=225–331 |doi=10.1561/1500000016 |issn=1554-0669}} It was also applied in social choice, to analyze an opinion poll conducted during the Irish presidential election.{{Cite journal |last1=Gormley |first1=Isobel Claire |last2=Murphy |first2=Thomas Brendan |date=June 2009 |title=A grade of membership model for rank data |url=https://projecteuclid.org/journals/bayesian-analysis/volume-4/issue-2/A-grade-of-membership-model-for-rank-data/10.1214/09-BA410.full |journal=Bayesian Analysis |volume=4 |issue=2 |pages=265–295 |doi=10.1214/09-BA410 |s2cid=53559452 |issn=1936-0975}} Efficient methods for expectation-maximization and Expectation propagation exist for the Plackett-Luce model.{{Cite journal |last1=Caron |first1=François |last2=Doucet |first2=Arnaud |date=January 2012 |title=Efficient Bayesian Inference for Generalized Bradley–Terry Models |url=http://www.tandfonline.com/doi/abs/10.1080/10618600.2012.638220 |journal=Journal of Computational and Graphical Statistics |language=en |volume=21 |issue=1 |pages=174–196 |doi=10.1080/10618600.2012.638220 |arxiv=1011.1761 |s2cid=42955305 |issn=1061-8600}}{{Cite journal |last=Hunter |first=David R. |date=February 2004 |title=MM algorithms for generalized Bradley-Terry models |url=https://projecteuclid.org/journals/annals-of-statistics/volume-32/issue-1/MM-algorithms-for-generalized-Bradley-Terry-models/10.1214/aos/1079120141.full |journal=The Annals of Statistics |volume=32 |issue=1 |pages=384–406 |doi=10.1214/aos/1079120141 |issn=0090-5364}}{{Cite book |last1=Guiver |first1=John |last2=Snelson |first2=Edward |title=Proceedings of the 26th Annual International Conference on Machine Learning |chapter=Bayesian inference for Plackett-Luce ranking models |date=2009-06-14 |chapter-url=https://doi.org/10.1145/1553374.1553423 |series=ICML '09 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=377–384 |doi=10.1145/1553374.1553423 |isbn=978-1-60558-516-1|s2cid=16965626 }}

RUMs can be used not only for modeling the behavior of a single agent, but also for decision-making among a society of agents.{{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 }} One approach to social choice, first formalized by Condorcet's jury theorem, is that there is a "ground truth" - a true ranking of the alternatives. Each agent in society receives a noisy signal of this true ranking. The best way to approach the ground truth is using maximum likelihood estimation: construct a social ranking which maximizes the likelihood of the set of individual rankings.

Condorcet's original model assumes that the probabilities of agents' mistakes in pairwise comparisons are independent and identically distributed: all mistakes have the same probability p. This model has several drawbacks:

• 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 $\backslash Theta^P\_2$-complete).{{Cite journal |last1=Hemaspaandra |first1=Edith |last2=Spakowski |first2=Holger |last3=Vogel |first3=Jörg |date=2005-12-16 |title=The complexity of Kemeny elections |url=https://www.sciencedirect.com/science/article/pii/S0304397505005785 |journal=Theoretical Computer Science |volume=349 |issue=3 |pages=382–391 |doi=10.1016/j.tcs.2005.08.031 |issn=0304-3975}}

RUM provides an alternative model: 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.

Walker and Ben-Akiva{{Cite journal |last1=Walker |first1=Joan |last2=Ben-Akiva |first2=Moshe |date=2002-07-01 |title=Generalized random utility model |url=https://www.sciencedirect.com/science/article/pii/S0165489602000239 |journal=Mathematical Social Sciences |series=Random Utility Theory and Probabilistic measurement theory |volume=43 |issue=3 |pages=303–343 |doi=10.1016/S0165-4896(02)00023-9 |issn=0165-4896}} generalize the classic RUM in several ways, aiming to improve the accuracy of forecasts:

• Flexible Disturbances: allowing a richer covariance structure, estimating unobserved heterogeneity, and random parameters;
• Latent Variables: explicitly representing the formation and effects of unseen constructs, such as perceptions and attitudes;
• Latent Classes: capturing hidden segmentation in terms of taste parameters, choice sets, and decision protocols;
• Combining Revealed Preferences and Stated Preferences: to combine advantages of these two data types.

Blavatzkyy{{Cite journal |last=Blavatskyy |first=Pavlo R. |date=2008-12-01 |title=Stochastic utility theorem |url=https://www.sciencedirect.com/science/article/pii/S030440680700136X |journal=Journal of Mathematical Economics |volume=44 |issue=11 |pages=1049–1056 |doi=10.1016/j.jmateco.2007.12.005 |issn=0304-4068}} studies stochastic utility theory based on choices between lotteries. The input is a set of choice probabilities, which indicate the likelihood that the agent choose one lottery over the other.