Oxford Journals
tools journals homepage advanced search contact help
Journal of Logic and Computation: Current Issue

OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation

Journal of Logic and Computation

Volume 12, Issue 1, February 2002: pp. 13-53

Operators and Laws for Combining Preference Relations

Hajnal Andréka1, Mark Ryan2 and Pierre-Yves Schobbens3

1Mathematical Institute, Hungarian Academy of Science, Budapest Pf. 127 H-1364, Hungary. E-mail: andreka@math-inst.hu
2School of Computer Science, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK. E-mail: mdr@cs.bham.ac.uk
3Institut d'Informatique, Facultés Universitaires de Namur, Rue Grandgagnage 21, 5000 Namur, Belgium. E-mail: pys@info.fundp.ac.be

The paper is a theoretical study of a generalization of the lexicographic rule for combining ordering relations. We define the concept of priority operator: a priority operator maps a family of relations to a single relation which represents their lexicographic combination according to a certain priority on the family of relations. We present four kinds of results.

[bull] We show that the lexicographic rule is the only way of combining preference relations which satisfies natural conditions (similar to those proposed by Arrow).

[bull] We show in what circumstances the lexicographic rule propagates various conditions on preference relations, thus extending Grosof's results.

[bull] We give necessary and sufficient conditions on the priority relation to determine various relationships between combinations of preferences.

[bull] We give an algebraic treatment of this form of generalized prioritization. Two operators, called but and on the other hand, are sufficient to express any prioritization. We present a complete equational axiomatization of these two operators.

These results can be applied in the theory of social choice (a branch of economics), in non-monotonic reasoning (a branch of artificial intelligence), and more generally wherever relations have to be combined.

Keywords: Preference relations; priority relations; default reasoning; lexicographic combination; Arrows theorem; social choice

Table of Contents   Full-Text PDF (424 KB)

Oxford University Press
Published by Oxford University Press
Copyright ©Oxford University Press 2003
Print ISSN: 0955-792X  Online ISSN: 1465-363X.
Oxford University Press Privacy Policy and Legal Statement