Error in the Euclidean Preference Model
This work highlights a fundamental limitation in spatial preference models used in recommender systems and multiagent systems, indicating that high-dimensional embeddings may be necessary for accurate approximation, which is incremental as it extends prior theoretical results.
The paper tackles the problem of representing ordinal preferences with Euclidean vector embeddings, showing that in many cases almost all preference profiles cannot be accurately represented, and derives a theoretical lower bound on the expected error when using such models.
Spatial models of preference, in the form of vector embeddings, are learned by many deep learning and multiagent systems, including recommender systems. Often these models are assumed to approximate a Euclidean structure, where an individual prefers alternatives positioned closer to their "ideal point", as measured by the Euclidean metric. However, Bogomolnaia and Laslier (2007) showed that there exist ordinal preference profiles that cannot be represented with this structure if the Euclidean space has two fewer dimensions than there are individuals or alternatives. We extend this result, showing that there are situations in which almost all preference profiles cannot be represented with the Euclidean model, and derive a theoretical lower bound on the expected error when using the Euclidean model to approximate non-Euclidean preference profiles. Our results have implications for the interpretation and use of vector embeddings, because in some cases close approximation of arbitrary, true ordinal relationships can be expected only if the dimensionality of the embeddings is a substantial fraction of the number of entities represented.