Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments

Traditionally, supervised machine learning algorithms are trained based on past data under the assumption that the past data is representative of the future. However, machine learning algorithms are increasingly being used in settings where the output of the algorithm changes the environment and hence, the data distribution. Indeed, online labor markets (Anagnostopoulos et al., 2018; Horton, 2010), predictive policing (Lum and Isaac, 2016), on-street parking (Dowling et al., 2020; Pierce and Shoup, 2018), and vehicle sharing markets (Banerjee et al., 2015) are all examples of real-world settings in which the algorithm's decisions change the underlying data distribution due to the fact that the algorithm interacts with strategic users. To address this problem, the machine learning community introduced the problem of performative prediction which models the data distribution as being decision-dependent thereby accounting for feedback induced distributional shift (Brown et al., 2020; Drusvyatskiy and Xiao, 2020; Mendler-Dünner et al., 2020; Miller et al., 2021; Perdomo et al., 2020). With the exception of (Brown et al., 2020), this work has focused on static environments. In many of the aforementioned application domains, however, the underlying data distribution also may have memory or even be changing dynamically in time. When a decision-making mechanism is announced it may take time to see the full effect of the decision as the environment and strategic data sources respond given their prior history or interactions. For example, many municipalities announce quarterly a new quasi-static set of prices for on-street parking. In this scenario, the institution may adjust parking rates for certain blocks in order to to achieve a desired occupancy range to reduce cruising phenomena and increase business district vitality (Dowling et al., 2017; Fiez et al., 2018; Pierce and Shoup, 2013; Shoup, 2006).