NSF CAREER: The Symbiosis of Graphical Models and Games
Abstract
Many natural, social and engineered systems exhibit
or facilitate complex behavior. Such behavior often results from the
deliberate actions of, and interactions between, a large number of
individuals. The need to study behavior in complex systems of
network-structured interactions in large populations promotes interest
in computational game-theoretic models.
Graphical games build on classical models in game theory, as well as
compact, structured representations in probabilistic graphical
models. The result is a practical and computationally amenable model
to handle networked large-population systems.
The creation of technology for scientists and policy makers to study
and work with large real-world complex systems of (strategic)
interactions requires further advances in graphical games and
models. The project seeks to fill knowledge gaps by advancing
computational aspects of game theory, graphical models and machine
learning, and laying the foundation for a systematic two-way knowledge
transfer between computational game theory and graphical models.
The research program strengthens the connection between graphical
models and game theory by casting probabilistic inference problems as
equilibrium computation, creating algorithms to learn games from
behavioral data, and characterizing equilibrium structure and
computation.
The current educational program involves two main components: (1) the infusion of the research results into general education, at all levels, via both new course development, and integration into existing courses taught by the PI and others in the Department of Computer and Information Science (CIS) at the University of Michigan – Dearborn (UMD); and (2) a concerted effort to improve collaborations between CIS and other UMD departments in colleges outside the College of Engineering and Computer Science (CECS), of which CIS is part, such as the Public Humanities program in the College of Arts, Sciences, & Letters (CASL), and also at the Ann Arbor campus of the larger University of Michigan system (e.g., through the Michigan Institute for Data Science, or MIDAS for short).
The previous educational program included (1) a concerted effort to
bridge the Departments of Economics and Computer Science at Stony
Brook University (my former institution); and (2) collaborations
through the Center for Game Theory in Economics and the International
Summer Festival on Game Theory, held annually at Stony Brook, which
would serve as conduits for outreach and dissemination.
People
Luis E. Ortiz
(PI)
Current Participants
- Boshen Wang (MS Student in CIS, Michigan - Dearborn)
- Hau Chan (PhD 2015, Stony Brook)
- Ze Gong (MS 2015, Stony Brook)
- Mohammad T. Irfan
(PhD 2013, Stony Brook; Visiting Assistant Professor of Computer Science and Fellow
in Digital and Computational Studies at Bodowin College since Fall 2013)
Former Participants
- Kota Yamaguchi (PhD 2014, Stony Brook; now an Assistant Professor in Tohoku University since Summer 2014)
- Kristen Stewart (BS 2014, Stony Brook; participated Spring 2013-Spring 2014;
REU Fall 2013-Spring 2014; now a PhD student in the
Department of Computer Science at Stony Brook University)
- Jean Honorio (PhD 2012, Stony Brook; Postdoctoral Fellow at MIT
CSAIL, Fall 2012-Summer 2015; Assistant Professor in the Department of Computer
Science at Purdue University since Fall 2015)
- Joshua Belanish (BS 2013, Stony Brook; participated Summer 2013; now at
Diffeo, on leave
from Ph.D. Program in the Department of Computer Science at Stanford
University)
- Nipun Valor (MS Student, participated Spring and Fall 2013;
graduated in December 2013, Stony Brook)
- Chandra Sekar (MS Student, graduated in 2012, Stony Brook)
- Aaron Meltzer (Former Undergraduate Student, Stony Brook; participated Spring 2013)
Relevant
Publications, Preprints, and Poster Presentations
- Luis E. Ortiz and Mohammad
T. Irfan. FPTAS for Mixed-Strategy Nash Equilibria in Tree Graphical Games and Their Generalizations. arXiv:1602.05237
[cs.GT], February 2016.
- Hau Chan and Luis E. Ortiz. Learning Game Parameters from MSNE: An Application to Learning IDS Games.
In The 26th International Conference on Game
Theory, part of the Stony Brook Game Theory Summer Festival
2015, July 2015.
- Jean Honorio
and Luis Ortiz. Learning the
Structure and Parameters of Large-Population Graphical Games from
Behavioral Data. Journal of Machine Learning Research
(JMLR), 16(Jun):1157--1210, 2015.
[Abstract] [PDF]
Preprint: arXiv:1206.3713
[cs.LG]
Other related versions:
- Jean Fausto
Honorio Carrillo. Learning Linear Influence Games. In Tractable Learning of Graphical Model Structures from Data., Chapter 7, pages 80--107. Ph.D. Thesis. Department of Computer Science, Stony Brook
University. 2012.
[PDF]
- A journal-length version: submitted to arXiv on June
16, 2012 (paper [PDF]).
- Last conference version: submitted March 30, 2012 to UAI 2012
(main paper [PDF];
supplementary material [PDF]).
- First conference version: entitled, Learning Influence Games, initially submitted June 1, 2010 to NIPS
2010.
- Mohammad
T. Irfan and Luis E. Ortiz. Causal Strategic Inference
in Networked Microfinance Economies. In, Advances in
Neural Information Processing Systems (NIPS) 27, Z. Ghahramani,
M. Welling, C. Cortes, N.D. Lawrence, and K.Q. Weinberger,
Editors, Pages 1161--1169, 2014. Curran Associates, Inc.
[PDF]
Other related versions:
- Mohammad
T. Irfan and Luis E. Ortiz. Causal Inference in Game-Theoretic Settings with
Applications to Microfinance Markets.
In The 26th International Conference on Game
Theory, part of the Stony Brook Game Theory Summer
Festival 2015, July 2015.
- Mohammad
T. Irfan. Causal Strategic Inference in Economic
Networks. In Causal Strategic Inference in Social and Economic
Networks., Chapter 3, pages 93--129. Ph.D. Thesis. Department of Computer Science, Stony Brook
University. 2013.
[PDF]
- Workshop poster: Mohammad T. Irfan and Luis E. Ortiz. A Game-Theoretic Model of
Microfinance Markets (Poster). In New York Computer Science and
Economics (NYCE) Day, September 2011.
[PDF]
- Mohammad
T. Irfan and Luis E. Ortiz. On
Influence, Stable Behavior, and the Most Influential Individuals in
Networks: A Game-Theoretic Approach. Artificial
Intelligence. Volume 215, Pages 79-119, October 2014.
ISSN 0004-3702,
http://dx.doi.org/10.1016/j.artint.2014.06.004
URL
Preprint as Technical Report: arXiv:1303.2147
[cs.GT], 2013.
Other related versions and workshop presentations:
- Mohammad T. Irfan and Luis E. Ortiz. A Game-Theoretic Approach to Influence in Networks. In AAAI Conference on Artificial Intelligence (AAAI),
2011.
[PDF]
- Mohammad
T. Irfan. Causal Strategic Inference in Social
Networks. In Causal Strategic Inference in Social and Economic
Networks., Chapter 2, pages 25--92. Ph.D. Thesis. Department of Computer Science, Stony Brook
University. 2013.
[PDF]
- Causal Strategic Inference in Networks (Poster). In Workshop on
Information and Decision in Social Networks (WIDS), November 2012.
[PDF]
- A Model of Strategic
Behavior in Networks of Influence (Extended Abstract). In International Conference on Game
Theory, 22nd Stony Brook Game Theory Festival of the Game Theory Society, July 2011.
- A Model of Strategic
Behavior in Networks of Influence (Poster). In Workshop on
Information and Decision in Social Networks (WIDS), May 2011.
[PDF]
- Influence Games with Application to Identifying the Most Influential Nodes in Social Networks (Student "Flash" Presentation). In New York Computer Science and
Economics (NYCE) Day, September 2010.
- Kota
Yamaguchi, Tamara L. Berg, and Luis E. Ortiz. Chic or Social: Visual Popularity Analysis in Online Fashion
Networks. Poster in NYAS 8th Annual Machine Learning
Symposium.
March 28, 2014.
[PDF]
Other related poster presentations:
- Kota
Yamaguchi, Luis E. Ortiz, and Tamara L. Berg. What makes a popular fashion
picture. Poster in 3rd Greater New York Area Multimedia and Vision Meeting.
June 14, 2013.
[PDF]
Other Partially Related Publications
- Luis E. Ortiz. On Sparse Discretization for Graphical Games. Preprint: arXiv:1411.3320 [cs.AI], November 2014.
Original: December 2002.
- Kota
Yamaguchi, M. Hadi Kiapour, Luis E. Ortiz, and
Tamara L. Berg. Retrieving Similar Styles to Parse
Clothing. Pattern Analysis and Machine Intelligence
(TPAMI), IEEE Transactions on, Vol. 37, no. 5, pp. 1028--1040,
May 2015.
URL
Extends and subsumes the following conference version:
- Kota Yamaguchi, M. Hadi Kiapour, Luis E. Ortiz, and
Tamara L. Berg. Parsing Clothing in Fashion Photographs. In IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), 2012.
[PDF]
Some Relevant/Related Invited Talks and Other Presentations
(The following excludes some presentations already mentioned above.)
- On Networks and Behavior: Strategic Inference and Machine
Learning
- University of Puerto Rico, Río Piedras, Oct. 28, 2015
- Economics and Computer Science Research Seminar, EconCS Group,
Harvard University, Oct. 19, 2015
- University of Delaware, May, 2015
- Department of Computer and Information Science, University of Michigan - Dearborn, May, 2015
- Talk, Colloquium Series, Department of Computer Science, Iowa
State University, Apr. 23, 2015
- Talk, Seminar Series, Microsoft Research New York City,
Apr. 14, 2015
- Talk, Seminar Series, Department of Computer Science,
University of North Carolina at Chapel-Hill, Apr. 9, 2015
- Talk, Machine-Learning Seminar Series, Department of Computer
Science, Duke University, Apr. 8, 2015
- Talk, Colloquium Series, Department of Computer Science and
Engineering, University of Minnesota Twin Cities, Mar. 23, 2015
- Colloquium Series, Department of Computer Science, University of Miami, Mar. 19, 2015
- Department of Electrical Engineering and Computer Science,
Wichita State University, Mar. 4, 2015
- Talk, Toyota AI Seminar Series, Computer Science and
Engineering, University of Michigan - Ann Arbor, Dec. 16, 2014
- From Senate Votes to Smoking: Using Game Theory to Find
Influential Individuals
- ¿Estudios Graduados? Orientación General,
Oportunidades y Mi Experiencia Personal
- Undergraduate Student Organization (ACM), Department of Computer Science, University of Puerto Rico, Río Piedras, Oct. 28, 2015
- Undergraduate Student Organizations (Bohique, IIE, and ASQ),
Department of Industrial Engineering, University of Puerto Rico, Mayagüez, Oct. 29, 2015
SOFTWARE (Prototypes)
Most software products/prototypes listed below are currently available only upon request
- Matlab code to learn linear-influence games (LIGs) from
strictly behavioral data [Download]
- Source code to learn LIGs using a sigmoidal approximation (used
to learn game from dataset of U.S. Supreme Court decisions)
- Source-code implementation of web-based system for playing
graphical games
- Source-code implementation of web-based system for playing
fashion games
- Source-code implementation to collect out-of-network data of
fashion popularity votes using Amazon Mechanical Turk
- Source code to study the effect of social vs. content factors
in the (un)predictability of postings in online fashion social
networks
- Source code to find all pure-strategy Nash equilibria
of multiplayer LIGs (exponential in the number of
players, so OK for up to 25 players)
- Source-code to generate interesting random LIGs
- Source-code to generate random Ising Models
- Source-code implementation of no-regret learning algorithms to compute
approximate correlated equilibria in graphical games (used for approximate inference in
probabilistic graphical models)
- Source-code implementation of Survey NashProp
Datasets
Some currently available only upon request
- U.S. Senate Voting [Download]
(then load file 'X.mat' in Matlab)
- U.S. Supreme Court Decisions
- Fashion Social Networks: In-network Data; Out-of-network Data
[Webpage]
Sponsor
National Science Foundation
This material is based upon work supported by the National Science
Foundation under Grant Number 1643006 (transferred from Grant Number
1054541). Any opinions, findings, and conclusions or recommendations
expressed in this material are those of the author(s) and do not
necessarily reflect the views of the National Science Foundation.