On testing substitutability

05/19/2018
by   Cosmina Croitoru, et al.
0

The papers hatfimmokomi11 and azizbrilharr13 propose algorithms for testing whether the choice function induced by a (strict) preference list of length N over a universe U is substitutable. The running time of these algorithms is O(|U|^3· N^3), respectively O(|U|^2· N^3). In this note we present an algorithm with running time O(|U|^2· N^2). Note that N may be exponential in the size |U| of the universe.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset