## Abstract

In this paper, we consider the problem of testing substitutability of weak preferences. For this problem, Aziz, Brill, and Harrenstein proposed an O(ℓ ^{3} u ^{2} +ℓ ^{2} u ^{2} s ^{2} )-time algorithm, where u is the size of the ground set, ℓ is the number of acceptable sets, and s is the maximum size of an equivalent class. In this paper, we propose an O(ℓ ^{3} u+ℓ ^{2} u ^{2} s)-time algorithm for this problem. Our algorithm is based on a generalization of the characterization of substitutability of strict preferences given by Croitoru and Mehlhorn.

Original language | English |
---|---|

Pages (from-to) | 1-4 |

Number of pages | 4 |

Journal | Mathematical Social Sciences |

Volume | 99 |

DOIs | |

Publication status | Published - May 2019 |

## All Science Journal Classification (ASJC) codes

- Sociology and Political Science
- General Social Sciences
- General Psychology
- Statistics, Probability and Uncertainty