2022 Optimization Days

HEC Montréal, Québec, Canada, 16 — 18 May 2022

Schedule Authors My Schedule

WC10 - Game theory

May 18, 2022 03:30 PM – 05:10 PM

Location: Banque Scotia (blue)

Chaired by Noureddine Toumi

4 Presentations

  • 03:30 PM - 03:55 PM

    Dynamic pricing and advertising in the presence of strategic consumers and social contagion: A mean-field game approach

    • Jafar Chaab, presenter, HEC Montreal

    In this paper, we introduce a framework for new product diffusion that integrates consumer heterogeneity and strategic social influences at individual level. Forward-looking consumers belong to two mutually exclusive segments: individualists, whose adoption decision is influenced by the price and reputation of the innovation, and conformists, whose adoption decision depends on social influences exerted by other consumers and on the price. We use a mean-field game approach to translate consumer strategic interactions into aggregate social influences that affect conformists’ adoption decision. The game is played à la Stackelberg, with the firm acting as leader and consumers as followers. The firm determines its pricing and advertising strategies to maximize its profit over a finite planning horizon. We provide the conditions for existence and uniqueness of equilibrium and a numerical scheme to compute it. Our results suggest that the firm adopts a penetration pricing strategy in the presence of strategic consumers, whereas it decreases the price first and then increases it in face of myopic consumers. Moreover, due to consumer heterogeneity, our results show that as the fraction of one segment increases in the market, the consumers in the other segment have less tendency towards adoption.

  • 03:55 PM - 04:20 PM

    Robustness and sample complexity of model-based MARL for general-sum Markov games

    • Jayakumar Subramanian, Senior Research Scientist
    • Amit Sinha, presenter, McGill University
    • Aditya Mahajan, GERAD, McGill University

    Multi-agent reinforcement learning (MARL) is often modeled using the framework of Markov games (also called stochastic games or dynamic games). Most of the existing literature on MARL concentrates on zero-sum Markov games but is not applicable to general-sum Markov games. It is known that the best-response dynamics in general-sum Markov games are not a contraction. Therefore, different equilibrium in general-sum Markov games can have different values. Moreover, the Q-function is not sufficient to completely characterize the equilibrium. Given these challenges, model based learning is an attractive approach for MARL in general-sum Markov games.

  • 04:20 PM - 04:45 PM

    Can strategical capacity allocation significantly improve students welfare?

    • Federico Bobbio, presenter, Université de Montréal
    • Margarida Carvalho, Polytechnique Montréal
    • Alfredo Torrico, Polytechnique Montréal
    • Andrea Lodi, Polytechnique Montreal

    The college admission problem is a classic mathematical problem that has been addressed from a theoretical and practical perspective for many decades. Indeed, the mathematical methods that have been developed are being used to match thousands of students to schools (or colleges) every year. From a theoretical perspective, this problem relies on two key assumptions: The condition of stability, which ensures a certain degree of fairness in the matching, and the fact that the capacities of the schools are fixed beforehand. We investigate how to improve the fairness of the outcome for the students by applying a variation in the capacities of the schools. From a concrete perspective, this research question addresses an issue that is usually solved manually or without the support of sophisticated mathematical tools: How to allocate scholarships to improve the matching of every student.
    We develop an integer programming exact formulation to solve the problem, which is NP-hard to approximate. To overcome this difficulty, we also propose some heuristics that show how to impact the individual and social welfare of the students by allocating strategically extra capacities.

  • 04:45 PM - 05:10 PM

    A Crowd Evacuation Model with Congestion Effect and Exits Restrictions

    • Noureddine Toumi, presenter,
    • Roland Malhamé, GERAD - Polytechnique Montréal
    • Jérôme Le Ny, GERAD - Polytechnique Montréal

    Crowd evacuation modeling is crucial for improving architectural designs and preventing fatalities in emergencies. Many existing models proceed with nonlinear effects to capture individuals' interactions within the crowd. Such an approach leads to accurate but analytically intractable behavior. Here we propose a non-cooperative linear-quadratic Mean Field Game model that leads to a tractable yet realistic description of crowd behavior. Specificities of our model are: (i) Agents have a limited set of possible exit options depending on their initial locations with respect to destinations; (ii) Congestion avoidance behavior is simulated by introducing a negative definite weight matrix within the cost function; (iii) Agents interact through distinct regional means as opposed the global population mean in other comparable models. Feature (ii) can generically lead to finite escape time phenomena for the associated Riccati equations. Thus we formulate a sufficient condition to ensure the model solvability. The model is analyzed by considering its behavior for an infinite population and subsequently establishing an ε-Nash equilibrium property of the resulting control laws in the more realistic case of a finite population. Simulations results are reported.