The problem of choice decomposition (Q810341)

Let A be a discrete set of ``variants''. A choice function is a function c: \(U\subseteq 2^ A\to 2^ A\). It is usually difficult to find the value c(X) of some \(X\in {\mathcal U}:\) this motivates decomposition methods. An example is the Path Independence condition \(c(U_ iZ_ i)=c(U_ ic(Z_ i))\). A choice function c satisfies Path Independence iff it satisfies simultaneously (a) Heritage: for any S,T\(\in {\mathcal U}\), if \(S\subseteq T\) then c(T)\(\cap S\subseteq c(S)\) and (b) Independence: for any S,T\(\in {\mathcal U}\), if c(T)\(\subseteq S\subseteq T\) then \(c(T)=c(S)\). The paper introduces a ``hierarchical'' decomposition of a choice function c at a given \(X\in {\mathcal U}.\) Given a set \(X\in {\mathcal U}=2^ A\setminus \{\emptyset \}\), let \(X_ 0=X\), \(X_ 1,...,X_ k,...,X_ m\), \(X_ k\subseteq 2^{X_{k-1}}\). Along with the function c consider functions \(c_ 0,c_ 1,...,c_ k,...,c_ m\), \(c_ k:\) \({\mathcal U}_ k=2^{X_ k}\setminus \{\emptyset \}\to 2^{X_ k}\), \(c_ o\) being the projection of c on \({\mathcal U}_ 0=2^ X\setminus \{\emptyset \}\). The decomposition \((X_ k,c_ k)^ m_{k=1}\) is coordinated with the choice problem (X,c) if for every \(k=m,...,1\), \(c_ k\) is such that, given the correspondances \(F_ k: X\to X_ k\), for any \(Z\in {\mathcal U}_ k\), \(c_ 0(F_ k^{- 1}(Z))\subseteq F_ k^{-1}(c_ k(Z))\). The main result of the paper relies on the following procedure: \[ X^*_ m=c_ m(X_ m),\quad X^*_ k=c_ k(f^{-1}_{k+1}(X^*_{k+1})),\quad k=m-1,...,1 \] using the correspondances \(f_ k: X_{k-1}\to X_ k\) (the correspondances \(F_ k\) are compositions of the correspondances \(f_ 1,...,f_ k\) and we have: \(F_ k^{-1}(f^{- 1}_{k+1}(X^*_{k+1}))=F^{-1}_{k+1}(X^*_{k+1}))\). The main result of the paper states that for a decomposition which is coordinated with a choice problem (X,c), i) if \(c_ 0\) satisfies the Heritage condition, then \(c_ 0(X)\subseteq c_ 0(X^*)\) for \(X^*=F_ 1^{- 1}(X_ 1^*)\), and ii) if \(c_ 0\) satisfies the Path Independence condition then \(c_ 0(X)=c_ 0(X^*).\) When the choice functions \(c_ k=c_{\beta_ k}\) are generated by binary relations \(\beta_ k\) on \(X_ k:\) (i.e. \(c_{\beta_ k}(Z)=\{z\in Z\); \(\exists x\in Z\); \(x\beta_ kz\}\), \(Z\subseteq X_ k)\) for a decomposition to be coordinated with the choice problem it is necessary that the \(\beta_ k\) be ``homomorphic'' with a relation \(\beta\) on \(2^ X\) such that \(c_{\beta}(S\cup T)\subseteq S\), S,T\(\subseteq X\). In some case the condition is also sufficient.