On the Linear Programming Model for Dynamic Stochastic Matching and Its Application to Pricing
Chen et al. — 2025
Résumé (FR)
Cet article étudie la fonction de valeur optimale d’un modèle de programmation linéaire pour le matching stochastique dynamique à temps limité, en se concentrant sur ses propriétés de concavité par rapport aux taux d’arrivée de la demande. Les auteurs appliquent ces résultats aux problèmes de tarification dans les marchés de matching centralisés tels que le covoiturage et la livraison. Un algorithme Minorization-Maximization exploitant la structure différence-de-concave est développé et testé sur des données réelles de covoiturage à grande échelle avec des milliers de types de passagers. Les performances sont supérieures aux méthodes de gradient projeté traditionnelles. Cette contribution mathématique fournit des fondements théoriques solides pour la conception de politiques de tarification dans les plateformes de mobilité partagée.
Summary (EN)
This paper examines the optimal value function of a linear programming model for cost-minimizing dynamic stochastic matching under limited time, establishing its concavity properties with respect to demand arrival rates. The results are applied to pricing in centralized matching markets like carpooling and food delivery. A Minorization-Maximization algorithm exploiting the difference-of-concave structure outperforms projected gradient methods on large-scale real-world ridesharing datasets.
Points clés
| Aspect | Détail |
|---|