Zhengyu Yin

I have research interests in artificial intelligence, algorithmic game theory and optimization and decision making under uncertainty.

My research focuses on addressing various types of uncertainty in Stackelberg games arising from real world security applications. The use of game-theoretic concepts has allowed security forces to exert maximum leverage with limited resources. Indeed, the leader-follower Stackelberg game model is at heart of many deployed applications. Due to the adversarial environment and the nature of law enforcement activities, many types of uncertainty, such as execution, observation, and preference uncertainty, must be taken into account in game-theoretic modeling for practical security applications.

In particular, I seek to address two major challenges. First, I am interested in mathematical modeling of uncertainty that may arise in real world deployments. Second, I am interested in developing compact game representation and efficient solution techniques so that solving the uncertainty model of interest is computationally feasible (check out my RECON paper and HUNTER paper). I have applied game-theoretic solutions to the problem of fare evasion deterrence in public transit networks. The project is carried out in collaboration with the Los Angeles Sheriff's Department and is currently under evaluation for the Los Angeles Metro Rail system. (check out the original paper and its extension.)

  • Stackelberg equilibrium v.s. Nash equilibrium in security games. We showed in Stackelberg games motivated by various security appliactions, the leader is best-responding regardless of her ability to commit (and therefore the follower's ability to observe). In particular, we showed in these security games where subsets of a schedule are always valid, the set of defender's Stackelberg equilibrium strategies is a subset of the set of her Nash equilibrium startegies.
  • Urban security -- graph-based seucrity games. In this game, the attacker can pick one node from the set of sources and choose a path to attack a target, while the defender can set up checkpoints on edges to stop the attacker. We compressed the action space for both players and proposed a Linear Programming appoach combined with various sampling method to solve the game approximately.
  • Continuous-time decentralized Markov decision process. We studied a class of decentralized Markov decision process operating in a continuous time horizon with temporal constraints among agents. The model is motivated by the ocean sampling domain where autonomous underwater vehicles collect water samples from biological hotspots near the coast. We propose an efficient local-optimal solver for such problems, exploiting transition independence among agents.
  • Local optimal algorithms for DCOP. We proposed a new solution concept t-distance optimality and derived quality bound of it. We designed an asynchronous decentralized local search algorithm (DALO) that is guaranteed to monotonically converge to a local optimum. We implemented and tested DALO for k-optimality and t-distance optimality on an asynchronous simulation framework, and showed the tradeoffs between t-distance optimality and k-optimality in various graph settings. A generalized local optimal criterion c-region optimality has been proposed recently and tested in our DALO framework.

Journals

  •  Zhengyu Yin, Albert Xin Jiang and Milind Tambe, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, and John P. Sullivan: TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems using Game Theory, AI Magazine, 33(4):59-72, 2012.
  •  Dmytro Korzhyk*, Zhengyu Yin*, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe (*Korzhyk and Yin are both first-authors of this publication): Stackelberg vs. Nash in Security Games: Interchangeability, Equivalence, and Uniqueness, Journal of Artificial Intelligence Research, 41:297-327, 2010. 

Full Conference Papers

  • Albert Xin Jiang, Zhengyu Yin, Chao Zhang, Milind Tambe, and Sarit Kraus: Game-theoretic Randomization for Security Patrolling with Dynamic Execution Uncertainty, (To Appear) In Proceedings of Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Saint Paul, USA, June, 2013.
  •  Zhengyu Yin, Albert Xin Jiang, Matthew P. Johnson, Milind Tambe, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, and John P. Sullivan: TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems In Proceedings of Twenty-Fourth Conference on Innovative Applications of Artificial Intelligence (IAAI), Toronto, Canada, July 2012. 
  •  Zhengyu Yin and Milind Tambe: A Unified Method for Handling Discrete and Continuous Uncertainty in Bayesian Stackelberg Games In Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Valencia, Spain, June 2012.
  •  Ondrej Vaneky, Zhengyu Yin, Manish Jain, Branislav Bosansky, Milind Tambe, and Michal Pechoucek: Game-theoretic Resource Allocation for Malicious Packet Detection in Computer Networks, In Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Valencia, Spain, June 2012.
  •  Zhengyu Yin, Manish Jain, Fernando Ordonez and Milind Tambe: Risk-Averse Strategies for Security Games with Execution and Observational Uncertainty, In Proceedings of Twenty-Fifth Conference on Artificial Intelligence (AAAI), San Francisco, USA, August, 2011.
  •  Zhengyu Yin and Milind Tambe: Continuous Time Planning for Multiagent Teams with Temporal Constraints, In Proceedings of Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI), Barcelona, Spain, July, 2011.
  •  Meritxell Vinyals, Eric Shieh, Jesus Cerquides, Juan Antonio Rodriguez-Aguilar, Zhengyu Yin, Milind Tambe, and Emma Bowring: Quality Guarantees for Region Optimal DCOP Algorithms, In Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Taipei, Taiwan, May, 2011.
  •  Jason Tsai, Zhengyu Yin, Jun-young Kwak, David Kempe, Christopher Kiekintveld, and Milind Tambe: Urban Security: Game-Theoretic Resource Allocation in Networked Physical Domains, In Proceedings of the National Conference on Artificial Intelligence (AAAI), Altanta, USA, July 2010.
  •  Zhengyu Yin, Dmytro Korzhyk, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe: Stackelberg vs. Nash in Security Games: Interchangeability, Equivalence, and Uniqueness, In Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Toronto, Canada, May 2010.
  •  Christopher Kiekintveld, Zhengyu Yin, Atul Kumar and Milind Tambe: Asynchronous Algorithms for Approximate Distributed Constraint Optimization with Quality Bounds, In Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Toronto, Canada, May 2010.
  •  Emma Bowring, Zhengyu Yin, Rob Zinkov, Milind Tambe: Sensitivity analysis for distributed optimization with resource constraints, In Proceedings of the Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Budapest, Hungary, May 2009.

Short Conference Papers

  •  Jun-Young Kwak, Rong Yang, Zhengyu Yin, Matthew E. Taylor, and Milind Tambe: Towards Addressing Model Uncertainty: Robust Execution-time Coordination for Teamwork, In Proceedings of the 2011 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT), Lyon, France, 2011.
  •  Jun-young Kwak, Rong Yang, Zhengyu Yin, Matthew E. Taylor, and Milind Tambe: Teamwork in Distributed POMDPs: Execution-time Coordination Under Model Uncertainty, In Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Taipei, Taiwan, May 2011.
  •  Jason Tsai, Zhengyu Yin, Jun-young Kwak, David Kempe, Christopher Kiekintveld, and Milind Tambe: How to Protect a City: Strategic Security Placement in Graph-Based Domains, In Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Toronto, Canada, May 2010 (Extended Abstract).

Demo Papers

  •  Michal Jakob, Zbynek Moler, Antonin Komenda, Zhengyu Yin, Albert Xin Jiang, Matthew P. Johnson, Michal Pechoucek, and Milind Tambe: AgentPolis: Towards a Platform for Fully Agent-based Modeling of Multi-Modal Transportation (Demonstration), In Proceedings of the Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Valencia, Spain, June 2012.

Symposium and Workshop Papers

  •  Albert Xin Jiang, Zhengyu Yin, Matthew P. Johnson, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, Milind Tambe: Towards Optimal Patrol Strategies for Fare Inspection in Transit Systems, AAAI Spring Symposium on Game Theory for Security, Sustainability and Health, Palo Alto, USA, March, 2012.
  •  Zhengyu Yin, Kanna Rajan, and Milind Tambe: Solving Continuous-Time Transition-Independent DEC-MDP with Temporal Constraints, In AAMAS Workshop on Multiagent Sequential Decision Making in Uncertain Domains (MSDM), Taipei, Taiwan, May, 2011. 
  •  Jun-young Kwak, Rong Yang, Zhengyu Yin, Matthew E. Taylor, and Milind Tambe: Robust Execution-time Coordination in DEC-POMDPs Under Model Uncertainty, In AAMAS Workshop on Multiagent Sequential Decision Making in Uncertain Domains (MSDM), Taipei, Taiwan, May, 2011.
  •  Jun-young Kwak, Rong Yang, Zhengyu Yin, Matthew E. Taylor, and Milind Tambe: Teamwork and Coordination under Model Uncertainty in DEC-POMDPs, In AAAI Workshop on Interactive Decision Theory and Game Theory (IDTGT), Atlanta, USA, July, 2010.
  •  Jason Tsai, Zhengyu Yin, Jun-young Kwak, David Kempe, Christopher Kiekintveld, Milind Tambe: Strategic Security Placement in Network Domains with Applications to Transit Security, In IJCAI 2009 Workshop on Quantitative Risk Analysis for Security Applications (QRASA), Pasadena, United States, July 2009.
  •  Zhengyu Yin, Christopher Kiekintveld, Atul Kumar and Milind Tambe: Local Optimal Solutions for DCOP: New Criteria, Bound, and Algorithm, In AAMAS 2009 Workshop on Optimization in Multi-Agent Systems (OptMAS), Budapest, Hungary, May 2009.
  •  Lei Shi, Bin Liu, Changhua Sun, Zhengyu Yin, Laxmi Bhuyan, H. Jonathan Chao: Flow-slice: a novel load-balancing scheme for multi-path switching systems, In Symposium on Architectures for Networking and Communications Systems (ANCS), Orlando, Florida, USA, December 2007.

Book Chapters

  •  Milind Tambe, Jun-young Kwak, Matthew Taylor, Manish Jain, Chris Kiekintveld, Zhengyu Yin, and Rong Yang: Two Decades of Multiagent Teamwork Research: Past, Present, Future, Book chapter in Proceedings of the Second International Workshop on Collaborative Agents -- Research and Development (CARE), 2010.

Reprinted Papers in Edited Volumes

  •  Zhengyu Yin*, Dmytro Korzhyk*, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe (*Korzhyk and Yin are both first-authors of this publication): Stackelberg vs. Nash in Security Games: Interchangeability, Equivalence, and Uniqueness, In Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned (Edited by Milind Tambe), Cambridge University Press, 2011.