Building User Journey Games from Multi-party Event Logs

In a competitive market, a good user experience is crucial for the survival of service providers [1]. User journeys model the interaction of a user (or customer) with a company’s services (service provider) from the user’s perspective. One of the earliest works to map user journeys was proposed by Bitner et al. in the form of service blueprinting [2]. Current tools can model and analyse individual journeys with the aim to improve services from the customers’ point of view [3, 4].

User journey analysis methods based on event data exploit events recording the user interactions with a service and its underlying information systems. Due to the sequential nature of user-service interactions, process mining techniques that assume grouped sequences of events as input, have been used to analyse user journeys [5‐8]. For example, Bernard et al. explore and discover journeys from events [7] and Terragni and Hassani use event logs of user journeys to give recommendations [5]. Input events are treated in the same way as for the analysis of business processes: each journey is an instance of a process (case) recorded in a sequence of events (trace) where each event represents an activity occurrence.

In contrast to a business process, which may include numerous actors and systems, a user journey is a sequence of very specific interactions between two parties: the user, and one or more service providers. This invites a specific view on the source event log, where some events are controlled by the user and others by service providers. At the end of the journey, some events represent desirable outcomes for the service provider (positive events) whereas others represent undesirable outcomes (negative events). Such partition of the event log into desired and undesired cases or process outcomes has been explored before. Deviance mining classifies cases to investigate deviations from expected behaviour [9]. A binary partition of the event log into positive and negative cases was used in, e.g., logic-based process mining [10, 11] and error detection [12]. Outcome prediction aims to predict the outcome of a process case based on a partial trace [13, 14]. However, these works do not consider the interactions between user and service providers in user journeys as interactions between independent parties. Results of game theory have previously been used by Saraeian and Shirazi for anomaly detection on mined process models [16] and by Galanti et al. for explanations in predictive process mining [17]; in contrast to our work, these works do not use game theory to account for multiple independent parties in the process model.

In this paper, we propose a multi-party view for user journeys event logs and present a model reduction based on game theory. We have recently shown how to model and analyse a user journey as a two-player weighted game, in a small event log (33 sequences) from a real scenario that could be manually analysed [15]. However, in scenarios with a large number of complex user journeys, the resulting game can be challenging for manual analysis. This paper introduces a k-sequence transition system extension on the directly follows graph of the multi-party game approach presented in [15], and proposes a novel method to automatically detect decision boundaries for user journeys. The method can be useful for the analysis of the journeys since it identifies the parts from where the game becomes deterministic with respect to the outcome of the journey, i.e., the service provider has no further influence on the outcome afterwards. We apply our method to the BPIC’17 dataset [18] as an example of complex user-service interactions, which is available in a public dataset. BPIC’17 does not include information on which activities are controlled by the user (a customer is applying for a loan) and which are controlled by the service provider (a bank). We add this information based on domain knowledge and define multi-party event logs as an extension of event logs with party information for user journeys. The application on BPIC’17 demonstrates the feasibility and usefulness of our approach. Our results show that we can automatically detect the most critical parts of the game that guarantees successful and, respectively unsuccessful, user journeys. This analysis could be extended with automated methods targeting predictive and prescriptive analysis, e.g., recommendations for process improvement.

The outline of our paper is illustrated in Fig. 1. Section 2 introduces necessary definitions and summarizes user journey games. These are extended with a novel game theoretical reduction method in Sects. 3 and 4. Section 5 illustrates our reduction method and the results on BPIC’17 and Sect. 6 concludes the paper.

This section provides background on our previous work on user journey games [15]. The input to the user journey analysis is an event log [19] storing records of observations of interactions between a user and one or more service providers. An event log L is a multiset of observed traces over a set of actions [19]. Given a universe \(\mathscr {A}\) of actions, traces \(\tau \in L\) are finite, ordered sequences \(\langle a_0, \dots , a_n \rangle \) with \(a_i \in \mathscr {A}\), i.e., \(L \in \mathcal {B}(\mathscr {A}^*)\). Given an event log L, we introduce the concept of a multi-party event log \(\mathcal {L}=\langle L,P,I\rangle \) in which each event belongs to a party, where P is the set of parties and the function I extends the traces \(\tau \in L\) with information for each event about the initiating party from P.

Transition systems \(S=\langle \varGamma , A, E, s_0, T \rangle \) have a set \(\varGamma \) of states, a set A of actions (or labels), a transition relation \(E \subseteq \varGamma \times A \times \varGamma \), an initial state \(s_0\in \varGamma \) and a set \(T \subseteq \varGamma \) of final states. A weighted transition system \(\mathcal {S}\) extends a transition system S, with a weight function w indicating the impact of every event [20]. Weighted games partition the events and consider them as actions in a weighted transition system, controllable actions \(A_c\) and uncontrollable actions \(A_u\) [21]. Only actions in \(A_c\) can be controlled. Actions in \(A_u\) are decided by an adversarial environment. When analysing games, we look for a strategy that guarantees a desired property, i.e. winning the game by reaching a certain state. A strategy is a partial function \(\varGamma \rightarrow A_c \cup \{\lambda \}\) deciding the actions of the controller in a given state (here, \(\lambda \) denotes the “wait” action, letting the adversary move).

User journeys capture how a user moves through a service by engaging in so-called touchpoints, which are either actions performed by the user or a communication event between the user and a service provider [3]. User journeys are inherently goal-oriented. Users engage in a service to reach a goal, e.g. receiving a loan or visiting a doctor. If they reach the goal, the journey is successful, otherwise unsuccessful. This can be modelled by a transition system with final states T, and successful goal states from a subset \(T_s \subseteq T\): every journey ending in \(t \in T_s\) is successful. A journey’s success does not only depend on the actions of the service provider—the journey can be seen as a game between service provider and user, where both parties are self-interested and control their share of actions. We define user journey games as weighted transition systems with goals and self-interested parties [15]:

The analysis of services with a large number of users requires a notion of user feedback [3]: Questionnaires provide a viable solution for services with a limited number of users, but not for complex services with many users. In a user journey game, the weight function w denotes the impact that an interaction has on the journey. A user journey game construction is described in [15]. When building user journey games from event logs, we used Shannon entropy [22] together with majority voting to estimate user feedback without human intervention. The more certain the outcome of a journey becomes after an interaction, the higher the weight of the corresponding edge. Gas extends weights to (partial) journeys so they can be compared. Given an event log L and its corresponding weighted transition system \(\mathcal {S}\), the gas \(\mathcal {G}\) of a journey \(\tau \in L\) accumulates the weights when replaying \(\tau \) along the transitions in \(\mathcal {S}\), \(\mathcal {G}(\tau )~{:}{=}~\sum _{a_i \in \tau }~w(a_i)\).

Formal statements about user journey games can be analysed using a model checker such as Uppaal  Stratego  [23]. Uppaal  Stratego extends the Uppaal system [24] by games and stochastic model checking, allowing properties to be verified up to a confidence level by simulations (avoiding the full state space exploration). If a statement holds, an enforcing strategy is computed. To strengthen the user-focused analysis of user journeys, we assume that an adversarial environment exposes the worst-case behaviour of the service provider by letting the service provider’s actions be controllable and the user’s actions uncontrollable. For example, let us define a strategy \({\texttt {pos}}\) for always reaching a successful final state. Define two state properties \({\texttt {positive}}\) for a successful and \({\texttt {negative}}\) for an unsuccessful final state. The keyword control indicates a game with an adversarial environment and \({\texttt {A<>}}\) searches for a strategy where the flag \({\texttt {positive}}\) eventually holds at some state in all possible paths of the game:

If the strategy \(\texttt {pos}\) exists, it can be further analysed and refined to, e.g., minimize the number of steps or gas to reach a final state within an upper bound time \({\texttt {T}}\):

Strategies can be stochastically evaluated using a number of runs \({\texttt {X}}\), e.g., evaluate the minimal gas of the refined strategy within an upper bound time \({\texttt {T}}\):

A decision boundary abstracts a game to focus on crucial parts from where the future outcome is decided. Finding the decision boundary in a complex game can be useful; e.g., there might be no guarantee to find a successful game strategy \(\texttt {pos}\) (see Sect. 2). Such a strategy can only be found for certain states in the game, which may be scattered around and therefore hard to analyse when using non-automatic methods. Moreover, detecting the decision boundary that lead to outcomes in the game from where there is no possibility of recovery can be used to propose further recommendations for service improvement. Figure 1b and  1c illustrate the game abstraction using decision boundaries. The red and green marked parts of the game in Fig. 1b display guaranteeing areas. Once the journey reached a state within those areas, the outcome becomes deterministic. Since all reachable states from a red or green state share the same outcome, they can be abstracted away (Fig. 1c).

Algorithm 1 computes the decision boundary for a game G. The mapping R, from states s to Boolean, stores whether there exists a successful strategy \(\texttt {pos}\) that starts from each state \(s \in \varGamma \) (Lines 2–6). The algorithm computes a reachable sub-game \(G'\) for every state s using the function \(\textsc {Descendants}(s)\), which computes the parts of G which are reachable from s by path exploration. Function \(\textsc {Acyclic}(G',n)\) unrolls n times all loops in \(G'\), e.g. by a breadth-first search strategy. An example of loop-unrolling in games is displayed in Fig. 2. The resulting acyclic game \(G''\) is then model checked with \(\textsc {Query}(G'')\) to look for a successful strategy \(\texttt {pos}\). The result is stored in R(s).

Furthermore, some states are segregated into two sets, \(\varGamma _P\) and \(\varGamma _N\), based on the results from the previous computation (Lines 7–8). States from which it is only possible to reach positive, respectively negative, results are assigned to \(\varGamma _P\), respectively \(\varGamma _N\). States in these sets guarantee the outcome of the game. The game is simplified by abstracting all states in \(\varGamma _P\), respectively \(\varGamma _N\), into one state \(s_{pos}\), respectively \(s_{neg}\), using the function \(\textsc {Merge}\) (Lines 9–12). Once one of these states is reached, the journey becomes deterministic; the service provider has no further influence on the final outcome. The states which point to \(s_{pos}\) and \(s_{neg}\) form the decision boundary (Lines 13–15).

Event logs obtained from user journeys record actions performed by several parties. A user can send messages to a service offered by a service provider and a service provider can send messages to a user currently using the service. It is common practice that artefacts of these actions are recorded in the service provider’s event logs, particularly the order of actions. However, knowledge about which party has triggered which action is commonly ignored while collecting such logs.

In this paper, we approximate multi-party event logs \(\mathcal {L}\) by pre-defining a party function I mapping actions a in event log L to a party in \(P = \{C, U\}\), where C denotes the service provider and U the user. For simplicity, we assume that different service provider parties are captured by the same party C.

We can now build a user journey game from a multi-party event log following [15] (see Fig. 1 for an overview). We then extend the obtained directly follows graph to a k-sequence transition system \(S_L^k= \langle \varGamma , A, E, s_0, T \rangle \) [25], which considers states that record the last k actions happening in the traces of L and stores them in a single state; e.g., the 2-action states of trace \(\langle a, b, c \rangle \) are \(\{\langle a \rangle , \langle a, b \rangle , \langle b, c \rangle \}\). This abstraction captures more information in the game, improving the precision of the game and the alignment between game and log.

We insert an initial state \(s_0\) at the beginning of each trace \(\tau \in L\), and a final state \(t \in T\) at the end of each trace \(\tau \in L\). Let H denote the set of states corresponding to the k-sequence abstraction for all traces in L, then the states are defined by \(\varGamma \subseteq \{s_0\} \cup T \cup H\). The transition relation E is constructed over adjacent actions in all traces \(\tau \in L\). An edge \((s_i, a_{i+1}, s_{i+1})\) is in E if there is a trace \(\tau \in L\) where the last action in state \(s_{i}\) is followed by the last action \(a_{i+1}\) in \(s_{i+1}\). A transition with action \(a_{i+1}\) in \(S_L^k\), means that the corresponding action has also been performed in \(\tau \).

The constructed transition system \(S_L^k\) is transformed into a user journey game by computing the weights on the transitions (see Sect. 2), and applying function I to compute the set \(A_c = \{a \mid I(a) = C \}\) of actions controlled by the service provider and the set \(A_u = \{a \mid I(a) = U \}\) of actions controlled by the user. The user journey game is used to compute its decision boundary (Sect. 3). States behind the decision boundary are merged into successful and unsuccessful states (Fig. 1c). The result is a strongly reduced game preserving all information on the decision structure.

The BPI Challenge 2017 (BPIC’17) [18] provides an event log recording actions in loan applications from a Dutch financial institute. Since this event log has records of interactions between users and a service provider, including calls, it is a suitable event log for user journey analysis. However, we needed to make assumptions to complete the missing information for our scenario, e.g., which journeys are successful or unsuccessful and infer the party function I with knowledge about which actions are triggered by which party.

The event log contains activities from the following groups: Application (A), Offer (O) and Workflow (W) [26]. Recorded journeys in the log can end with three different states: (1) an offer is accepted, (2) the application is declined, or (3) the application is cancelled. We define a party function I, based on domain knowledge and official information given in the BPIC’17 forum.¹ We assume that only users can cancel, submit or complete an application, and that users decide whether calls take place. We further assume that accepted offers are successful journeys, cancellations are unsuccessful journeys: both parties would prefer a different outcome since the user spent time in the service and the bank invested resources, and declined applications are neither successful nor unsuccessful journeys: users followed the whole process without achieving their goal (the bank has to decline certain offers to protect the users, e.g., from unsustainable debt). We exclude declined application journeys from the analysis, given their ambiguity.

BPIC’17 is known to include a substantial change in the service provider’s process, called a concept drift [27], in July 2016. To investigate how this change impacts the user journey game, we split the log at this month and investigate both parts separately. The first part contains traces until 30.06.2016, while the second part contains traces after 01.08.2016.

This paper proposes a novel view on user journey event logs by introducing multi-party event logs that differentiate between the actors of actions leading to events. To promote a user-centric view, the service provider is modelled as controllable and the user as uncontrollable. Based on such a multi-party event log, we show how to use user journey games to model the interaction between user and service provider, and use model checking to find strategies with guaranteed outcomes.