Designer path independent choice functions
- Creators
- Johnson, Mark R.
- Dean, Richard A.
Abstract
This paper provides an algorithm for the construction of all PICFs on a finite set of alternatives, V, designed by an a priori given set I of initial choices as well as the determination of whether the initial set I is consistent with path independence. The algorithm is based on a new characterization result for path independent choice functions (PICF) on finite domains and uses that characterization as the basis of the algorithm. The characterization result identifies two properties of a partition of the Boolean algebra as necessary and sufficient for a choice function C to be a PICF: (i): For every subset A of V the set arc(A)={B:C(B)=C(A)}arc(A)={B:C(B)=C(A)} is an interval in the Boolean algebra 2^V. (ii): If A/B is an interval in the Boolean algebra such that C(A) = C(B) and if M/N is an upper transpose of A/B then C(M) = C(N). The algorithm proceeds by expanding on the implications of these two properties.
Additional Information
© 2005 Springer-Verlag. Received: November 5, 2003; revised version: July 20, 2004.Additional details
- Eprint ID
- 102107
- DOI
- 10.1007/s00199-004-0544-y
- Resolver ID
- CaltechAUTHORS:20200325-130629354
- Created
-
2020-03-25Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field