Page 23 - 33-3

NTU Management Review Vol. 33 No. 3 Dec. 2023

Kang et al. (2023) proposes a way to transform the benefit evaluation problem
to a maximum flow problem. We now show how to extend this method to incorporate
time dependency, which is not considered in his work. Given a construction plan y, we
construct a directed acyclic graph whose structure is similar to that in Figure 1. For each

customer location i, we add a customer node C into the graph. A source node S is created
i
and connected to customer node C with capacity d for all i ∈ I. For facility j, if under
i
i
the given construction plan it is built at scale level k (i.e., y =1), we add a node F for
jk
jt
each of activity session t. A destination node D is created and linked from node F with
jt
capacity q . Finally, a link from node C to node F is added with infinite capacity if p > 0.
jt
ijt
jk
i
Figure 1 is an example for three customers, two activity sessions, and a construction plan
that builds three facilities. According to the way we connect C and F , we find customer
jt
i
1 is unwilling to visit facility 2 in activity session 1. Once the graph is constructed, its
maximum flow may be solved. For the maximum flow instance made from a construction
plan y, we denote the maximized flow value as w(y).
Note that the information about preference levels p is largely omitted in the
ijt
constructed maximum flow problem: It only matters whether p > 0 or not. It is thus not
ijt
surprising that the solutions to the two problems are not the same. Nevertheless, as for the
benefit evaluation problem all we need is the objective value, the constructed maximum
flow problem is enough. We now show in Theorem 1 that the maximized flow value of the
maximum flow problem constructed given a construction plan y is always identical to z(y),

the objective value of the benefit evaluation problem.
Theorem 1: For any construction plan y, we have z(y)=w(y).

Proof. Given any construction plan y, each flow on the graph we constructed is
bounded by the demand of customers and capacity of facilities. Therefore, the capacity
constraints in benefit evaluation problem are obeyed. For every node C , if the maximum
i
flow flows out according to the preference levels in equilibrium, the customers’ decisions
in graph are exactly the same as that in the benefit evaluation problem. It turns out

z(y)=w(y). Based on this maximum flow instance, assume that there is at least one flow
flowing out some node C changes to the less preferred edge. If this change does not
i
decrease w(y), i.e., does not make any edge out of capacity, z(y)=w(y). If it does, this new

instance is impossible to be an outcome of the maximum flow problem. In conclusion,

15