University of Southern California
Research Group

Welcome 

I am currently a graduate student in Department of Computer Science, University of Southern California. I am a member of TEAMCORE research group directed by Professor Milind Tambe. I received my bachelor degree from Department of Computer Science, Tsinghua University, Beijing, China. My Curriculum Vitae is here.

Research

I have research interests in Algorithmic Game Theory, Optimization, and Decentralized Markov Decision Process.

My primary focus is on game-theoretic modeling and solution techniques for real-world security applications. In particular, I am actively developing models and solutions that are robust to noise and errors for real-world security domains. Recently I developed a robust optimization algorithm for security games to deal with execution and observation errors (check out our RECON paper). I also have a paper submission on solving Bayesian Stackelberg games using linear relaxation and Bender's decomposition.

Previous work

Stackelberg equilibrium v.s. Nash equilibrium in security games. We showed in security games where subset of a schedule is always a valid schedule, the set of defender's Stackelberg equilibrium strategies is a subset of the set of his/her Nash equilibrium startegies (check out the paper).

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 (check out the paper)

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. (check out the paper).

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 (download), and showed the tradeoffs between t-distance optimality and k-optimality in various graph settings (more details in our paper). A generalized local optimal criterion c-region optimality has been proposed recently and tested in our DALO framework (check the paper).

Publications

Under Submission

  •  Zhengyu Yin and Milind Tambe: A Unified Method for Handling Discrete and Continuous Uncertainty in Bayesian Stackelberg Games.

Journals

  •  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, 2010. [link]

Full Conference Papers

  •  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. [link]
  •  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. [link]
  •  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. [link]
  •  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. [link]
  •  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. [link]
  •  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. [link]
  •  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. [link]

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. [link]
  •  Jun-young Kwak, Rong Yang, Zhengyu Yin, Matthew E. Taylor, 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. [link]
  •  Jason Tsai, Zhengyu Yin, Jun-young Kwak, David Kempe, Christopher Kiekintveld, 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). [link]

Symposium and Workshop Papers

  •  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. [link]
  •  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. [link]
  •  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. [link]
  •  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. [link]
  •  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. [link]
  •  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.

Contact Me

Zhengyu Yin
Email: zhengyuy [at] usc [dot] edu
Office phone: (213)740-7231
Office Address:  Powell Hall of Engineering 210, 3737 Watt Way, Los Angeles, CA 90089-0781, USA