This example shows that, in general, the Mobius transform of a coherent lower probability cannot be used to calculate its natural extension.
>>> import itertools
>>> import random
>>> from improb.lowprev.lowprob import LowProb
>>> from improb.lowprev.belfunc import BelFunc
>>> random.seed(10)
>>> n = 4
>>> events = [list(event) for event in itertools.product([0, 1], repeat=n)]
>>> gambles = [[random.randint(0,2) for i in range(n)] for j in range(20)]
>>> for i in range(20):
... # construct belief function from lower probability
... lpr = LowProb.make_random(pspace=n, division=2, number_type='fraction')
... lpr.extend()
... bel = BelFunc(lpr)
... # check for incoherence
... for gamble in gambles:
... if lpr.number_cmp(lpr.get_lower(gamble), bel.get_lower(gamble)) != 0:
... print('lpr (lower probability):')
... print(lpr)
... print('bel.mobius (basic belief assignment):')
... print(bel.mobius)
... print("lpr.get_lower({0})={1}".format(gamble, lpr.get_lower(gamble)))
... print("bel.get_lower({0})={1}".format(gamble, bel.get_lower(gamble)))
... break
... else:
... # no incoherence found! try another one
... continue
... break
... else:
... raise RuntimeError("no counterexample found")
lpr (lower probability):
: 0
0 : 0
1 : 0
2 : 0
3 : 0
0 1 : 0
0 2 : 1/2
0 3 : 1/2
1 2 : 1/2
1 3 : 1/2
2 3 : 0
0 1 2 : 1/2
0 1 3 : 1/2
0 2 3 : 1/2
1 2 3 : 1/2
0 1 2 3 : 1
bel.mobius (basic belief assignment):
: 0
0 : 0
1 : 0
2 : 0
3 : 0
0 1 : 0
0 2 : 1/2
0 3 : 1/2
1 2 : 1/2
1 3 : 1/2
2 3 : 0
0 1 2 : -1/2
0 1 3 : -1/2
0 2 3 : -1/2
1 2 3 : -1/2
0 1 2 3 : 1
lpr.get_lower([2, 0, 1, 1])=1
bel.get_lower([2, 0, 1, 1])=1/2
Quick check:
lpr.get_lower([2,0,1,1]) >= lpr([1,0,1,0])+lpr([1,0,0,1])=1
bel.get_lower([2,0,1,1]) = 0.5*(1+1+0+0+0+0-1+0+0)=0.5
However, it seems that the Mobius transform of a 2-monotone lower probability can be used to calculate its natural extension. The following simulation seems to confirm this for a space of size 3 (all coherent lower probabilities on such space are 2-monotone).
>>> import itertools
>>> import random
>>> from improb.lowprev.lowprob import LowProb
>>> from improb.lowprev.belfunc import BelFunc
>>> random.seed(10)
>>> n = 3
>>> gambles = [[random.randint(0,5) for i in range(n)] for j in range(20)]
>>> for i in range(20): # increase at will...
... # construct a coherent lower probability
... lpr = LowProb.make_random(pspace=n, division=2, number_type='fraction')
... lpr.extend()
... bel = BelFunc(lpr)
... # check for incoherence
... for gamble in gambles:
... if lpr.number_cmp(lpr.get_lower(gamble), bel.get_lower(gamble)) != 0:
... print('lpr (lower probability):')
... print(lpr)
... print('bel.mobius (basic belief assignment):')
... print(bel.mobius)
... print("lpr.get_lower({0})={1}".format(gamble, lpr.get_lower(gamble)))
... print("bel.get_lower({0})={1}".format(gamble, bel.get_lower(gamble)))
... break
... else:
... # no incoherence found! try another one
... continue
... break
... else:
... raise RuntimeError("no counterexample found")
Traceback (most recent call last):
...
RuntimeError: no counterexample found
>>> from fractions import Fraction
>>> import itertools
>>> import random
>>> from improb.lowprev.linvac import LinVac
>>> from improb.decision.opt import OptLowPrevMax
>>> random.seed(40)
>>> n1 = 2
>>> n2 = 2
>>> ndec = 3
>>> pspace = [tuple(omega)
... for omega in itertools.product(list(range(n1)), list(range(n2)))]
>>> for i in range(20):
... # construct a linear vacuous mixture
... lprob = [0.8 / len(pspace) for omega in pspace]
... lpr = LinVac(pspace, lprob=lprob) # no need for randomness
... opt = OptLowPrevMax(lpr)
... # construct gambles:
... # gambles[w1][d][w2] gives the gain of the w1-d-w2 path
... gambles = [[[random.randint(0, 2) + 0.01 * d + w1 * 0.005
... for w2 in range(n2)]
... for d in range(ndec)]
... for w1 in range(n1)]
... # construct strategies:
... # strats[i][w1] gives decision of i'th strategy, after observing w1
... strats = [tuple(strat)
... for strat in itertools.product(list(range(ndec)), repeat=n1)]
... # construct normal form gambles:
... # normgambles[strat][omega] gives the gain of the i'th strategy
... normgambles = dict(
... (strat, dict(
... (omega, gambles[omega[0]][strat[omega[0]]][omega[1]])
... for omega in pspace))
... for strat in strats)
... # construct extensive form gambles:
... # extgambles[w1][d][omega] gives the gain of decision d after observing w1, as a function of omega
... extgambles = [[dict((omega, gambles[w1][d][omega[1]] if omega[0] == w1 else 0)
... for omega in pspace)
... for d in range(ndec)]
... for w1 in range(n1)]
... #print(gambles)
... #print(strats)
... #print([[normgambles[strat][omega] for omega in pspace] for strat in strats])
... #print([[[extgambles[w1][d][omega] for omega in pspace] for d in range(ndec)] for w1 in range(n1)])
... # calculate normal form solution of subtrees after observing w1
... local = {}
... for w1 in range(n1):
... event = set(w for w in pspace if w[0] == w1)
... local[w1] = list(opt([extgambles[w1][d] for d in range(ndec)], event))
... #print(w1, event)
... #print(local[w1])
... # calculate full solution by combining all local solutions
... normlocal = set()
... for localgambles in itertools.product(*[local[w1] for w1 in range(n1)]):
... #print localgambles
... normlocal.add(tuple(sum(localgamble[w] for localgamble in localgambles) for w in pspace))
... #print(normlocal)
... # calculate full normal form solution
... norm = opt([normgambles[strat] for strat in strats])
... norm = set(tuple(normgamble[w] for w in pspace) for normgamble in norm)
... #print(norm)
... # calculate corresponding strategies
... localstrats = set()
... normstrats = set()
... for strat in strats:
... normgamble = tuple(normgambles[strat][omega] for omega in pspace)
... if normgamble in norm:
... normstrats.add(strat)
... if normgamble in normlocal:
... localstrats.add(strat)
... # convert normal form to extensive form
... normstrats2 = set(itertools.product(*[set(strat[w1] for strat in normstrats) for w1 in range(n1)]))
... # check if solutions differ
... if localstrats != normstrats:
... for w1 in range(n1):
... for d in range(ndec):
... print(
... "w1={0}, d={1}: ".format(w1, d)
... + " ".join("{0:.3f}".format(x) for x in gambles[w1][d]))
... print("lpr=" + " ".join(str(x) for x in lprob))
... print(sorted(normstrats))
... print(sorted(localstrats))
... #print(sorted(localstrats - normstrats))
... #print(sorted(normstrats - localstrats)) # should be empty!
... #print(sorted(normstrats2))
... break
... # stronger violation... never occurs??
... #if localstrats != normstrats2:
... else:
... raise RuntimeError("no counterexample found")
w1=0, d=0: 1.000 2.000
w1=0, d=1: 0.010 0.010
w1=0, d=2: 2.020 1.020
w1=1, d=0: 0.005 1.005
w1=1, d=1: 2.015 1.015
w1=1, d=2: 0.025 2.025
lpr=0.2 0.2 0.2 0.2
[(0, 1), (2, 1), (2, 2)]
[(0, 1), (0, 2), (2, 1), (2, 2)]
Does subtree imperfectness persists after converting the normal form into an extensive form?
>>> import itertools
>>> import random
>>> from improb.lowprev.lowprob import LowProb
>>> from improb.decision.opt import OptLowPrevMax
>>> random.seed(10)
>>> n1 = 2
>>> n2 = 3
>>> ndec = 3
>>> pspace = [tuple(omega)
... for omega in itertools.product(list(range(n1)), list(range(n2)))]
>>> for i in range(20):
... # construct a lower prevision
... lpr = LowProb.make_random(pspace=pspace, zero=False)
... # construct gambles:
... # gambles[w1][d][w2] gives the gain of the w1-d-w2 path
... gambles = [[[random.randint(0, 5) for w2 in range(n2)]
... for d in range(ndec)]
... for w1 in range(n1)]
... # construct strategies:
... # strats[i][w1] gives decision of i'th strategy, after observing w1
... strats = [tuple(strat)
... for strat in itertools.product(list(range(ndec)), repeat=n1)]
... # construct normal form gambles:
... # normgambles[strat][omega] gives the gain of the i'th strategy
... normgambles = dict(
... (strat, dict(
... (omega, gambles[omega[0]][strat[omega[0]]][omega[1]])
... for omega in pspace))
... for strat in strats)
... # construct extensive form gambles:
... # extgambles[w1][d][omega] gives the gain of decision d after observing w1, as a function of omega
... extgambles = [[dict((omega, gambles[w1][d][omega[1]] if omega[0] == w1 else 0)
... for omega in pspace)
... for d in range(ndec)]
... for w1 in range(n1)]
... #print(gambles)
... #print(strats)
... #print([[normgambles[strat][omega] for omega in pspace] for strat in strats])
... #print([[[extgambles[w1][d][omega] for omega in pspace] for d in range(ndec)] for w1 in range(n1)])
... # calculate normal form solution of subtrees after observing w1
... local = {}
... for w1 in range(n1):
... event = set(w for w in pspace if w[0] == w1)
... local[w1] = list(opt([extgambles[w1][d] for d in range(ndec)], event))
... #print(w1, event)
... #print(local[w1])
... # calculate full solution by combining all local solutions
... normlocal = set()
... for localgambles in itertools.product(*[local[w1] for w1 in range(n1)]):
... #print localgambles
... normlocal.add(tuple(sum(localgamble[w] for localgamble in localgambles) for w in pspace))
... #print(normlocal)
... # calculate full normal form solution
... norm = opt([normgambles[strat] for strat in strats])
... norm = set(tuple(normgamble[w] for w in pspace) for normgamble in norm)
... #print(norm)
... # calculate corresponding strategies
... localstrats = set()
... normstrats = set()
... for strat in strats:
... normgamble = tuple(normgambles[strat][omega] for omega in pspace)
... if normgamble in norm:
... normstrats.add(strat)
... if normgamble in normlocal:
... localstrats.add(strat)
... # convert normal form to extensive form
... normstrats2 = set(itertools.product(*[set(strat[w1] for strat in normstrats) for w1 in range(n1)]))
... # check if solutions differ
... # stronger violation!!
... if localstrats != normstrats2:
... for w1 in range(n1):
... for d in range(ndec):
... print(
... "w1={0}, d={1}: ".format(w1, d)
... + " ".join("{0:.2f}".format(x) for x in gambles[w1][d]))
... for (gamble, event), (lprev, uprev) in lpr.iteritems():
... print("lpr({0})={1:.2f}".format(gamble, lprev))
... print(sorted(normstrats2))
... print(sorted(localstrats))
... break
... else:
... raise RuntimeError("no counterexample found")
Traceback (most recent call last):
...
RuntimeError: no counterexample found