| This workshop is dedicated to the memory of Yehuda Vardi, Professor of Statistics, Rutgers University. |
Utility functions have a long history in economics and psychology but have recently caught the attention of computer scientists in various applications. Random utility approaches have been extensively used in the social sciences. The fundamental idea is that utilities of agents could be hard or even impossible to precisely assess or elicit, so one should model these utilities as random variables. This modeling approach could turn out to be useful in developing and solving optimization problems and algorithms for which there is no time to or where it is is impossible to assess/obtain input data precisely. Such situations could be of interest in computing tasks with massive input data sets as well as tasks in which data corresponds to agent valuations that have to be elicited (such as pricing data like the willingness to buy/pay at a given price). Discrete choice models, i.e., situations in which utilities of only finitely many objects have to be elicited, are of special interest (and have been studied extensively, for example with regard to transportation systems, consumer choice in marketing, etc. [Baltas and Doyle (2001), Ben-Akiva, McFadden, Abe, Bockenholt, Bolduc, Gopinath, Takayuki, Ramaswamy, Rao, Revelt and Steinberg (1997), Ben-Akiva and Bierlaire (1999), McFadden (2000)]. Many discrete choice models have a natural polyhedral representation [Falmagne (1996), Niederee and Heyer (1997), Regenwetter and Marley (2001), Fishburn (2001)] and these representations have been studied mostly by the mathematical psychology community, e.g., [Falmagne (1978), Koppen (1995), Suck (1997)].
Several interesting discrete choice models give rise to the study of well-known polytopes, with the Binary Choice Polytope [Block and Marschak (1960), as a prominent example. The very same polytope is also well-studied in the operations research community as the feasible set of an optimization problem on rankings (e.g., see [Groetschel, Juenger and Reinelt (1985), Reinelt (1985)]). It was therefore dubbed the Linear Ordering Polytope. Other new polytopes such as the Approval Voting Polytope [Falmagne (1996), Doignon and Regenwetter (1997)] have shown up more recently in studies of random utility models of subset choice and could be of potential interest to the operations research community. In general, the questions of model characterization and of fitting these random utility models to the experimental data are often equivalent to finding complete linear descriptions and optimizing over corresponding polyhedra. On the other hand, it is plausible that some of the well-studied polyhedra in polyhedral combinatorics and combinatorial optimization could be used to design new discrete choice models that could be easily testable.
The three-day workshop will allow for exchange of ideas between researchers in random utility on the one side and polyhedral combinatorics on the other, with inclusion of computer scientists with expertise on algorithmic approaches to such problems as well as computer scientists with an interest in modern applications in IT. The aim is to define a program and general theory of developing random utility models that could be efficiently characterized and tested through experimental data.
Ben-Akiva, M., McFadden D., Abe, M., Bockenholt, U., Bolduc, D., Gopinath, D., Takayuki, M., Ramaswamy, V., Rao, V., Revelt, D., Steinberg, D., "Modeling methods for discrete choice analysis,'' Marketing Letters, 8, 1997, 273-286.
Ben-Akiva, M. and Bierlaire, M., "Discrete choice methods and their applications to short-term travel decisions,'' in R. Hall (ed.), Handbook of Transportation Science, International Series in Operations Research and Management Science, Vol. 23, Kluwer, 1999.
Block, H. D., and Marschak, J., "Random orderings and stochastic theories of responses,'' in Olkin, I., Ghurye, S., Hoeding, H., Madow, W., and Mann, H. (eds.), Contributions to Probability and Statistics, Stanford University Press, Stanford, 1960.
Doignon, J.-P. and Regenwetter, M., "An approval-voting polytope for linear orders, Journal of Mathematical Psychology, 41, 1997, 171-188.
Falmagne, J.-C., "A representation theorem for finite random scale systems,'' Journal of Mathematical Psychology, 18 1978, 52-72.
Falmagne, J.-C., "A stochastic theory for the emergence and the evolution of preference relations,'' Math. Soc. Sci., 31, 1996, 63-84.
Fishburn, P., "Signed orders, choice probabilities, and linear polytopes,'' Journal of Mathematical Psychology, 45, 2001, 53-80.
Groetschel, M., Juenger, M., and Reinelt, G., "Facets of the linear ordering polytope,'' Math. Programming, 33, 1985, 43-60.
Koppen, M., "Random utility representation of binary choice probabilities: Critical graphs yielding critical necessary conditions,'' Journal of Mathematical Psychology, 39, 1995, 21-39.
McFadden, D. and Train, K., "Mixed MNL models for discrete response,'' Journal of Applied Econometrics, 15, 2000, 447-470.
Niederee, R., Heyer, D., "On subjective intensity and its measurement,'' in A.A.J. Marley (ed.), Choice, Decision and Measurement: Essays in Honor of R. Duncan Luce, Mahwah, NJ: Lawrence Erlbaum Associates, 1997.
Regenwetter, M, Marley, A. A. J., "Random relations, random utilities, and random functions,'' Journal of Mathematical Psychology, 45, 2001, 864-912.
Reinelt, G., The Linear Ordering Problem : Algorithms and Applications, Research and Exposition in Mathematics 8, Heldermann-Verlag, Berlin, 1985.
Suck, R., "Polytopes in measurement and data analysis,'' Journal of Mathematical Psychology, 41, 1997, 299-303.
Next: Call for Participation
Workshop Index
DIMACS Homepage