Postdoctoral position at INRIA Lille-Nord Europe

Posted by: Bernard FORTZ
Date:2018-03-01
Contact:[email protected]

 

Application of Stackelberg games to avoid fare evasion 
Postdoctoral research project 
INRIA Lille - INOCS team 
Supervisors: Luce Brotcorne, Bernard Fortz, Martine Labbé. 
Duration: 1 year. 
Contact: [email protected] 
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 [email protected] 
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. 

Application of Stackelberg games to avoid fare evasion 

Postdoctoral research position 

INRIA Lille - INOCS team 
Supervisors: Luce Brotcorne, Bernard Fortz, Martine Labbé. 
Duration: 1 year. Contact: [email protected] 

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 [email protected] 


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.