Robust Reward Placement under Uncertainty

Petros Petsinis, Kaichen Zhang, Andreas Pavlogiannis, Jingbo Zhou, Panagiotis Karras

Introduction

Strategically placing reward-generating facilities—such as retail stores, billboards, or charging stations—within a city is a high-stakes decision. To maximize "reward" (e.g., customer footfall or ad impressions), stakeholders typically rely on urban mobility patterns. However, these patterns are rarely static; they fluctuate based on external factors like weather, holidays, or special events. A placement optimized for a "sunny day" might perform poorly during a "rainy day" storm.

Mobility patterns change significantly under different environmental conditions, such as sunny versus rainy weather.

This paper addresses the Robust Reward Placement (RRP) problem: finding a facility configuration that performs competently across a set of potential Markov Mobility Models (MMMs). Instead of simply maximizing the average or minimum reward, the authors propose a "max-min ratio" objective. This approach maximizes the worst-case ratio between the reward achieved and the theoretical optimum for any specific scenario, ensuring the solution is competitive regardless of which environment manifests.

Methodology

The authors demonstrate that RRP is NP-hard and generally inapproximable within a constant factor under standard budget constraints. To tackle this complexity, they propose several algorithmic frameworks:

  • $Ψ$-Saturate: A bicriteria approximation algorithm that uses binary search on the objective value. It provides a theoretical guarantee of being within $ε$ of the optimum, though it may slightly exceed the specified budget.
  • DP-RRP (Dynamic Programming for RRP): A specialized dynamic programming approach derived from the Max-Min 0–1 Knapsack problem. While the optimal version scales exponentially with the number of scenarios, the authors' implementation is optimized for practical efficiency.
  • Heuristics: Several baseline strategies were evaluated, including All Greedy (picking the best individual scenario solution), Myopic (iterative marginal gain), and Best-Worst Search (BWS) (maximizing the absolute minimum reward).

Experimental Evaluation

The algorithms were tested on both synthetic networks (Erdős-Rényi and Scale-Free) and real-world mobility data from Baidu Map in Nanjing, China. The real-world dataset comprised over 51,000 nodes and 13 distinct mobility models representing various environmental settings.

Computational efficiency of various RRP algorithms across different network topologies and parameters.

Key Results

  • Performance and Robustness: On the Nanjing dataset, DP-RRP consistently outperformed other heuristics and the $Ψ$-Saturate algorithm across different budget levels. The experiments confirmed that larger budgets allow for better "hedging" against uncertainty, though the ratio-based objective can sometimes exhibit non-monotonic behavior.
  • Efficiency: As shown in the scaling experiments, while $Ψ$-Saturate is theoretically grounded, it is computationally intensive. Best-Worst Search (BWS) emerged as the most time-efficient heuristic, making it suitable for massive networks where speed is prioritized over absolute precision.
  • Topology Impact: In Scale-Free networks—which closely mirror the hub-and-spoke nature of real cities—the DP-RRP heuristic proved exceptionally effective.

Discussion and Future Work

A key insight of this work is the mathematical analogy between expected rewards in MMMs and PageRank scores, allowing the use of power-iteration methods for rapid reward precomputation. The "max-min ratio" objective also proves superior to "max-min reward," as the latter can lead to "lazy" placements that are mediocre in all settings rather than competitive in each.

Future research could extend this model to dynamic placement, where facilities like mobile food trucks or digital billboards can be redeployed as conditions change. Additionally, incorporating content features—tailoring the type of reward to the specific demographics of passing agents—could further enhance the utility of robust placement strategies.

Summary updated

BibTeX
@inproceedings{petsinis2024robust,
  author = {Petros Petsinis and Kaichen Zhang and Andreas Pavlogiannis and Jingbo Zhou and Panagiotis Karras},
  title = {{Robust Reward Placement under Uncertainty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure