Postdoctoral research project
INRIA Lille - INOCS team
Supervisors: Luce Brotcorne, Bernard Fortz, Martine Labbé.
Duration: 1 year.
Contact: Luce.Brotcorne@inria.fr
In the class of games known as Stackelberg games, one agent, the leader,
must commit to a strategy that can be observed by several other agents,
the followers, before he/she commits to a strategy of his/her own. The
leader wishes to find an optimal payoff-maximizing mixed strategy to
commit to, under the assumption that the followers will have knowledge
of the leader's mixed strategy and will best-respond to it. The problem
in such games consists thus in finding a payoff-maximizing mixed
strategy for the leader and corresponds to a bilevel problem with
bilinear objectives.
Stackelberg games can be modeled as a bilinear bilevel optimization
problem that can be reformulated as a single level mixed integer
nonlinear program (MINLP) (Conitzer and Sandholm 2006; Paruchuri et al.
2008; Kiekintveld et al. 2009). Recently, new stronger models have been
proposed by members the INOCS team (Casorran-Amilburu et al. 2016).
In this project, we will consider a specific application of Stackelberg
games in the context of fare evasion avoidance in transportation
systems. Many transportation system require passengers to purchase
tickets before entering, but they are not physically forced to do so
because the lack of infrastructure (e.g. no automatic doors to grant
access). Therefore, to avoid fare evasion, patrol units move in the
transit system to inspect passengers. One objective for the authority
organizing the patrols is to catch the maximum number of fare evaders
(and to collect a maximum amount of fines), while passengers have to
make a choice between buying a ticket or taking the risk of paying the
fine if they are controlled.
The problem can be seen as a Stackelberg game in which the leader has to
establish a mixed (randomized) strategy for the patrols, and the
passengers, observing this strategy, decide to buy a ticket or not,
maximizing their cost (depending on the probability of being fined).
To the best of our knowledge, the only approach to the problem using
mixed integer programming tool provides a heuristic solution that
overestimates the objective of the leader (Yin et al. 2012). In this
research proposal, we plan to
- establish the computational complexity of the problem;
- propose extended formulations to model exactly the objective of the
leader;
- develop decomposition methods based on column generation to solve
the problem effectively.
Research environment
The INOCS team aims to develop new models, algorithmic techniques and
implementations for optimization problems with complex structure (CS).
More precisley, we consider that an optimization problem presents a CS
when for example it involves some hierarchical leader-follower structure
(bilevel optimization). Luce Brotcorne and Martine Labbé are specialists
in bilevel optimization with a particular expertise to solve Stackelberg
games, while Bernard Fortz has also a strong experience in decomposition
methods that will be at the core of algorithms developed in the project.
This joint experience was already applied in the context of pricing
problems (Fortz, Labbé, and Violin 2013).
Contact.
If you are interested by the position, please send your CV and a motivation letter to Luce.Brotcorne@inria.fr
References
Casorran-Amilburu, Carlos, Bernard Fortz, Martine Labbé, and Fernando
Ordóñez. 2016. "Novel Formulations for General and Security Stackelberg
Games." Université libre de Bruxelles.
Conitzer, Vincent, and Tuomas Sandholm. 2006. "Computing the Optimal
Strategy to Commit to." In _Proceedings of the 7th Acm Conference on
Electronic Commerce_, 82–90. ACM.
Fortz, Bernard, Martine Labbé, and Alessia Violin. 2013. "Dantzig-Wolfe
Reformulation for the Network Pricing Problem with Connected Toll Arcs."
_Electronic Notes in Discrete Mathematics_ 41 (0):117–24.
https://doi.org/http://dx.doi.org/10.1016/j.endm.2013.05.083 .
Kiekintveld, Christopher, Manish Jain, Jason Tsai, James Pita, Fernando
Ordóñez, and Milind Tambe. 2009. "Computing Optimal Randomized Resource
Allocations for Massive Security Games." In _Proceedings of the 8th
International Conference on Autonomous Agents and Multiagent
Systems-Volume 1_, 689–96. International Foundation for Autonomous
Agents and Multiagent Systems.
Paruchuri, Praveen, Jonathan P Pearce, Janusz Marecki, Milind Tambe,
Fernando Ordóñez, and Sarit Kraus. 2008. "Playing Games for Security: An
Efficient Exact Algorithm for Solving Bayesian Stackelberg Games." In
_Proceedings of the 7th International Joint Conference on Autonomous
Agents and Multiagent Systems-Volume 2_, 895–902. International
Foundation for Autonomous Agents and Multiagent Systems.
Yin, Zhengyu, Albert Xin Jiang, Milind Tambe, Christopher Kiekintveld,
Kevin Leyton-Brown, Tuomas Sandholm, and John P Sullivan. 2012. "TRUSTS:
Scheduling Randomized Patrols for Fare Inspection in Transit Systems
Using Game Theory." _AI Magazine_ 33 (4):59.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
