/* dynamic programming and epistemic logic (1): backward induction puzzle */
% file: bcwrd1.pl, surprise1.pl
% 14,26 Dec 2002.
% a surprising test.

/*�u�����ł��e�X�g�w���v�B����A�[�̔w���I�p�Y���̗L���ȗ��B�j���[�J�����Ɨގ����A���S�\���̉��ł̍����I�I���ɂƂ��Ȃ��񌈒萫�������B*/
/* a prolog based model of the `surprising test' paradox a famous backward induction puzzle, such like as the Newcomb problem or the sequential rationality with common knowledge hypothesis in game theory.
*/

weekday([mon,tue,wed,thur,fri]).
day(D):- weekday(W), member(D,W).
plan(test_on_the_day(X)):- day(X).
surprise_test_on(X):- 
	plan(test_on_the_day(X)), 
	\+ predictable(test_on_the_day(X)).
predictable(test_on_the_day(X)):-
	predictable(test_on_the_day(X),by(mon),if_no_test([])).

/*
% an informal argument of backward induction.
predictable(test_on_the_day(fri),by(fri),if_no_test([mon,tue,wed,thur])).
predictable(test_on_the_day(thur),by(thur),if_no_test([mon,tue,wed])).
predictable(test_on_the_day(wed),by(wed),if_no_test([mon,tue])).
predictable(test_on_the_day(tue),by(tue),if_no_test([mon])).
predictable(test_on_the_day(mon),by(mon),if_no_test([])).
*/

% a semi-formalization.
impossible(surprise_test_on(D)):-
	predictable(test_on_the_day(D),_,_).
impossible(surprise_test_after(X),if_no_test(P)):-
	duration(P,X,F),
	forall(member(Y,F),impossible(surprise_test_on(Y))).
forall(A,B):-
	\+ (A,
	  (
	   \+ B
	  )
	).
predictable(test_on_the_day(X),by(X),if_no_test(P)):- 
	duration(P,X,[]).
predictable(test_on_the_day(X),by(X),if_no_test(P)):-
	impossible(surprise_test_after(X),if_no_test(P)).

% timing and duration: temporal structure
duration(Past,Y,Future):-
	weekday(W),
	append(Past,[Y|Future],W).
past(Past,Y):-
	duration(Past,Y,_Future).
future(Y,Future):-
	duration(_Past,Y,Future).
before(A,B):-past(A,B).
thereafter([Y|Future],Y):-
	duration(_Past,Y,Future).
from_now_on(A,B):-thereafter(A,B).
until(Z,Y):-
	duration(Past,Y,_Future),
	append(Past,[Y],Z).
up_to_now(Z,Y):-until(Z,Y).
% a meta predicate to trace goal:-conditions.
show(P):-
	clause(P,true),
	P,
	tab(2),write(fact(P)),nl.
show(P):-
	clause(P,Q),
	P,
	\+ Q = true,
	tab(2),write(rule(P)),
	write(':-'),nl,
	tab(4),write(Q),nl.


% post script

/*
 note:
 It is ambiguous in the pair of interactive mental states that is 
 the notion of `predictable', the cognitive state of an agent, and 
 of `surprise',  the emotional one.

 1) prediction (uodating) given information
 It is ambiguous whether we admit a value of `partial' information or not.
 However apparently this problem is not affected by the question
 since we (latently) assume the case of perfect information. 
  an alternative:

     predictable(test_on_the_day(X)):-
	predictable(test_on_the_day(X),by(D),if_no_test(P)).
	% predictable(test_on_the_day(X),by(mon),if_no_test([])).

 2) surprise --- an emotional reaction to the predictability?
 Surprise is a state of mind which reflects the 'impossibility' as well as the 'unpredictability'.
 Unpredicability mostly entails a fail of prediction. Other than a surprise, probably an unpredicable event that has occurred actually brings about an emotional state, such like as a regret, a disappointment, or an interestingness.
 In this problem, although a unique solution by backward induction argument exsists, however it is not stable with respect to the epistemic process (i.e., an interactive cognition-emotion oriented mental models) of the agent who has deductive ability equipped to support the argument of rationality as well as of a mere backward induction. I will explain this phenomena informally as follows.
 By the above pogram `predictable', using the backward argument brings about a unique solution `mon'. 
 But if the agent (i.e., student) can deduce the solution, then it can not be done on Monday because the teacher has ability of imitate his / her reasoning and therefore it can not be a surprise test.
 If the student concludes that the test can not be done, then it is obiously true that an unpredictable test can be made and it makes the student surprise when a test on Monday. Thus the process apparently instable.
 Instead of the deterministic argument like above, we may think that the student has some degree of, or a strength of beliefs (i.e., subjective probabilities) about a `surprise' test on each day. 
 By the way, probably a student who had no idea of prediction (i.e., the most vague belief) will not be so surprised by the actually occurred test anyway. Analogically we may infer that the degree of surprise caused by a belief of corresponding degree.
 Thus, the teacher must have a thought that his / her students have at least some prediction about the day of test. 
 Hum... We probably must reformulate the student's prediction strategy space, such like as ..., a partition, or a nest, i.e., a tree ....


*/

%end 

return to front page.