Thursday
Friday
Presented under the auspices of the Special Focus on Computation and the Socio-Economic Sciences.
*********************************************************************
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).
Several interesting discrete choice models give rise to the study of well-known polytopes, with the Binary Choice Polytope, 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. It was therefore dubbed the Linear Ordering Polytope. Other new polytopes such as the Approval Voting Polytope 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.