数理解析研究所講究録
第 1819 巻 2012 年 89-92

89

Understanding Capacities on a Finite Lattice
Motoya Machida
Department of Mathematics, Tennessee Technological University, Cookeville, TN
mmachida@tntech.edu

This article summarizes the results obtained by the author [4] who explored
a combinatorial approach when capacities are defined over a finite lattice. Let
be a finite lattice with partial ordering , and let and denote the minimum
and the maximum element ofmonotone function on is called a capacity
ifand $\varphi(i)=1$ . Let denote the collection of nonempty dual orderideals in , and let be an -valued random variable on some probability space, distributed as $\mathbb{P}(\mathcal{X}=V)=f(V)$ . Ifthen
$L$

$i$

$\hat{0}$$\leq$$L.$$\varphi(\hat{0})=0$$A$$\varphi$$L$$\mathcal{L}$$L$$\mathcal{X}$$\mathcal{L}$$\mathbb{P}(\hat{0}\in \mathcal{X})=0$$(\Omega, \mathbb{P})$(1)$\varphi(x)=\mathbb{P}(x\in \mathcal{X})$gives a capacity, which is viewed as a marginal condition for . From anotherviewpoint, the collection of capacities on is a convex polytope, every element of
which can be represented as the convex combination$\mathcal{X}$$L$(2)$\varphi(x)=\sum_{V\in \mathcal{L}}f(V)\chi_{V}(x) , x\in L,$

wheredenotes an indicator function of . It should be noted, however, thatthe choice of is not necessarily unique. In the way of formulating (2), the weight$f(V)$ determines a probability mass function (pmf) for, in which (2) is deemed
to be (1). This probabilistic interpretation of a capacity was first considered by
Choquet [1] and independently by Murofushi and Sugeno [6].
$\ldots\in L$ ,For
we define the difference operator
by$V$$\chi_{V}$$f$$\mathcal{X}$$a_{1},$$a_{2},$(3)$\nabla_{a1}$$\nabla_{a}1\varphi(x)=\varphi(x)-\varphi(x\wedge a_{1}) , x\in L,$

and the successive difference operator(4)$\nabla_{a,\ldots,a_{n}}1$

recursively by$\nabla_{a_{1},\ldots,a_{n}}\varphi=\nabla_{a_{n}}(\nabla_{a1,\ldots,a_{n-1}}\varphi) , n=2,3, \ldots.$

The monotonicity of is characterized byfor any $a\in L$ ; furthermore,is called completely monotone (or monotone of order ; see [1]) if$a_{n}\in L$ and for any $n\geq 1.$
for any$\varphi$$\nabla_{a}\varphi\geq 0$$\infty$$a_{1},$$\ldots,$$\varphi$$\nabla_{a1,\ldots,a_{n}}\varphi\geq 0$

90
Let $X$ be an -valued random variable with pmf $f(x)=\mathbb{P}(X=x)$ . If $f(\hat{0})=0$
then$L$(5)$\varphi(x)=\sum_{y\leq x}f(y) , x\in L,$gives a capacity, which is viewed as a cumulative distribution function (cdf), alsoknown as a belief function in [2]. The existence of the cdf (5) for a capacity
is necessary and sufficient for the completely monotonicity of . This crucial
observation, known as Choquet’s theorem, was made by Choquet [1] for the classof compact sets in a topological space, and it has been instrumental in the studiesof random sets. See [5] for a comprehensive review on random sets on topologicalspaces. This result in case of lattices was due to Norberg [7] who studied measureson continuous posets.
The function in (5) is called the M\"obius inverse of , by which the successive
difference operators are fully characterized as follows.
$\varphi$$\varphi$$f$$\varphi$of satisfies

Theorem 1. The M\"obius inverse

$f$

(6)

: $y\leq x,$$\nabla_{a1,\ldots,a_{n}}\varphi(x)=\sum\{f(y)$$\varphi$$y\not\leq a_{i}$for all $i=1,$$\ldots,$$n\}.$Particularly we can show the Choquet’s theorem for a finite lattice via combinatorial techniques.

. Then the M\"obius inverse
Corollary 2. Assume
if and only if is completely monotone.
$\varphi(\hat{0})\geq 0$$f$of$\varphi$

is nonnegative$\varphi$

is itself a distributive lattice when it is equipped with theThe collection
is embedded as the subposet
order relation $U\preceq V$ by $U\supseteq V$ . The latticeof principal dual order ideals. Here we introduce a completely
monotone capacity on , and call it a completely monotone extension of if itsatisfies the marginal condition$\mathcal{L}$$L$$\mathcal{L}_{0}$$:=\{\langle a\rangle^{*}:a\in L\}$$\Phi$(7)$\mathcal{L}$$\varphi$$\varphi(x)=\Phi(\langle x\rangle^{*}) , x\in L.$

The marginal condition (7) is equivalent to (2), in which the weight $f(V)$ determines the M\"obius inverse of . By the same token, (1) and (7) are the samo when
as a cdf for -valued random variable
we express
Kellerer [3] and R\"uschendorf [8] investigated the optimal bounds analogous tothe classical Fr\’echet bounds systematically for various marginal problems. Let
we canbe the space of real-valued functions on . Given
formulate the nonnegative linear functional$\Phi$$\Phi(U)=\mathbb{P}(\mathcal{X}\preceq U)$$R(\mathcal{L})$$\mathcal{X}.$$\mathcal{L}$$\Phi\in M_{\infty}(\mathcal{L})$$\mathcal{L}$$\Phi(g)=\sum_{V\in \mathcal{L}}f(V)g(V) , g\in R(\mathcal{L})$,91
whereis the M\"obius invcrse ofFr\’echet bound$f$(8)$\Phi$.

Assuming $\varphi\in M_{1}(L)$ , we can define the$B_{\varphi}(g)= \min\{\Phi(g);\Pi(\Phi)=\varphi\}$for any. Duality follows from the relationship between primal anddual problem of linear programming, but it is also viewed as a straightforward
application of the Hahn-Banach theorem (cf. Kellerer [3]).
$g\in R(\mathcal{L})$

Theorem 3. The dual problem(9)

satisfies$S^{\varphi}(g)= \max\{\sum_{x\in L}r_{x}\varphi(x)$$B_{\varphi}(g)=S^{\varphi}(g)$for any$g\in R(\mathcal{L})$:$\sum_{x\in V}r_{x}\leq g(V),$$V\in \mathcal{L}\}.$.

In particular we formulate the optimal lower boundat the dual order ideal
generated by a pair $\{a, b\}$ of . Then we apply
the value
to replacein (3) $-(4)$ , and propose the -difference
operatorby$\lambda(\varphi;a, b)=B_{\varphi}(\langle a, b\rangle^{*})$$\langle a,$$L$$b\rangle^{*}$$\lambda(\varphi;a, x)$$\varphi(a\wedge x)$$\lambda$$\Lambda_{a}$(10)$\Lambda_{a}\varphi(x)=\varphi(x)-\lambda(\varphi;a, x) , x\in L,$

and the successive(11)$\lambda$-difference operator recursively by$\Lambda_{a1,\ldots,a_{n}}\varphi=\Lambda_{a_{n}}(\Lambda_{a1,\ldots,a_{n-1}}\varphi) , n=2,3, \ldots.$

Then we consider a stochastic comparison between, and obtain a sufficient condition for$\mathbb{P}(Y\leq y)$$\varphi(x)=\mathbb{P}(x\in \mathcal{X})$and $\psi(y)=$$\mathbb{P}(Y\in \mathcal{X})=1.$

Theorem 4. If(12)$\Lambda_{aa}1,\ldots,k\varphi(i)\leq\nabla_{a_{1},\ldots,a_{k}}\psi(i)$then there exists a joint
marginal conditions.

$cdf\Gamma$

forfor every monotone path$(\mathcal{X}, Y)$satisfying$(a_{1}, \ldots, a_{k})$$\mathbb{P}(Y\in \mathcal{X})=1$,

given theReferences[1] Choquet, G. (1954). Theory of capacities. Ann. Inst. Fourier 5, 131-295.

[2] Grabisch, M. (2009). Belief functions on lattices. Int. J. Intell. Syst. 24, 7695.
[3] Kellerer, H. G. (1984). Duality theorems for marginal problems. Z. Wahrsch.
Verw. Gebiete 67, 399-432.

92[4] Machida, M. (2011). Capacities on a finitc lattice. Submitted for publication,preprint available at arxiv. org.
[5] Molchanov, I. (2005). Theow of Random Sets. Springer-Verlag, London.

[6] Murofushi, T. and Sugeno, M. (1991). A theory of fuzzy measures: Representations, the Choquet integral, and null sets. J. Math. Anal. Appl. 159,532-549.
[7] Norberg, T. (1989). Existence theorems for measures on continuous posetswith applications to random set theory. Math. Scand. 64, 15-51.
[8] R\"uschendorf, L. (1991). Fr\’echet bounds and their applications. In Advances inProbability Distributions with Given Marginals, 151-187. Kluwer Academic
Publishers, Netherlands.