Yair ZICK

Assistant Professor
Ph.D. (Mathematics, Nanyang Technological University)
B.Sc. (Mathematics, "Amirim" Honors Program, Hebrew University of Jerusalem)
COM2-02-60
660 11731

Research Areas

  • Algorithms & Theory
  • Artificial Intelligence

Research Interests

  • Algorithmic Game Theory
  • Algorithmic Transparency
  • Algorithmic Fair Division
  • Cooperative Games
  • Computational Social Choice

Profile

Yair Zick is an assistant professor at the Department of Computer Science at the National University of Singapore. He obtained his PhD (Mathematics) from Nanyang Technological University, Singapore in 2014, and a B.Sc (Mathematics, "Amirim" Honors program) from the Hebrew University of Jerusalem. His research interests include computational fair division, computational social choice, algorithmic game theory and algorithmic transparency. He is the recipient of the 2011 AAMAS Best Student Paper award, the 2014 Victor Lesser IFAAMAS Distinguished Dissertation award, the 2016 ACM EC Best Paper award, and the 2016 Singapore NRF Fellowship.

Current Projects

  • Algorithmic Fair Collaboration - I am deeply interested in theories of economic collaboration and resource allocation; I have spent a lot of time thinking about cooperative games, a mathematical model of agent collaboration, and using algorithmic means to find solutions for them. Some recent works along this line involve exploring collaboration under uncertainty: how can we decide which coalitions should form and how payoffs should we allocate, given that we only observe specific coalitions and their values? In another line of work, we study the classic economic problem of rent division: a group of roommates needs to decide how to allocate rooms and divide rent. How should they do this in a fair manner? In a 2016 EC paper we provide theoretical and emprical answers to this question, as well as confirm our findings with user studies on real data!
  • Algorithmic Transparency - Big data and machine learning techniques are being increasingly used to make decisions about important, and often sensitive, aspects of our lives, such as healthcare and finance. These algorithms often learn from data; that is, they try to predict someone's income levels based on various features, such as their age, salary or marital status. These algorithms are often very, very good at their job (hence their popularity): they are able to process a huge amount of data and offer accurate predictions that would have otherwise been made by human decision makers with only very partial, biased data (and would certainly require much more time). It is often thought that algorithms are unbiased, in the sense that they do not hold any prior opinions that affect their decisions. In particular, we would not like our algorithms to base their predictions on sensitive features - such as ethnicity or gender. So, did a big data algorithm base its decisions on "protected" user features? The problem is that in many cases it is very hard to tell: big data algorithms are often extremely complex, so we cannot be sure whether an algorithm used a protected feature (say, gender), or based its prediction on a correlated input (say, weight lifting ability). Our research aims at developing formal methods that offer some transparency into the way that the algorithms use their inputs. Using tools from game theory, formal causality analysis and statistics, we offer influence measures that can indicate how important was a feature in making a decision about an individual, or a protected group. Our IJCAI 2015 paper offers some theoretical insights as to how such influence measures should be designed, whereas our 2016 Oakland paper studies how such measures can be used to generate user readable transparency reports

Selected Publications

  • The Price of Diversity in Public Housing Allocation Problems
    Nawal Benabbou, Mithun Chakraborty, Vinh Ho Xuan, Jakub Sliwinski and Yair Zick

  • Learning What You Like by Knowing Who You Know
    Ayumi Igarashi, Jakub Sliwinski and Yair Zick

  • A Characterization of Monotone Influence Measures for Data Classification
    Martin Strobel, Jakub Sliwinski and Yair Zick

  • Learning Hedonic Games
    Jakub Sliwinski and Yair Zick
    Conference Paper: The 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017

  • How to Form Winning Coalitions in Mixed Human-Computer Settings
    Moshe Mash, Yair Zick, Yoram Bachrach, and Kobi Gal
    Conference Paper: The 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017

  • Voting Rules as Error-Correcting Codes
    Ariel D. ProcacciaNisarg Shah and Yair Zick
    Journal Paper: Artificial Intelligence Volume 231, February 2016, Pages 1-16

  • Which is the Fairest (Rent Division) of them All?
    Kobi Gal, Moshe Mash, Ariel D. Procaccia and Yair Zick
    Conference Paper: The 17th ACM Conference on Economics and Computation (EC), 2016, Pages 67-84

  • Analyzing Power in Weighted Voting Games with Super-Increasing Weights
    Yoram BachrachYuval FilmusJoel Oren and Yair Zick
    Conference Paper: The 9th International Symposium on Algorithmic Game Theory (SAGT), 2016, pages 169-181

  • A Characterization of Voting Power for Discrete Weight Distributions
    Yoram BachrachYuval FilmusJoel Oren and Yair Zick
    Conference Paper: The 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016, pages 74-80

  • Misrepresentation in District Voting
    Yoram BachrachOmer LevYoad Lewenberg and Yair Zick
    Conference Paper: The 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016, pages 81-87

  • Optimal Interdiction of Illegal Network Flow
    Qingyu Guo, Bo AnYair Zick and Chunyan Miao
    Conference Paper: The 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016, pages 2507-2513

  • Algorithmic Transparency via Quantitative Input Influence: Theory and Experiments with Learning Systems
    Anupam DattaShayak Sen and Yair Zick
    Conference: The 37th IEEE Symposium on Security and Privacy (Oakland), 2016, pages 598-617

  • Tracking Performance and Forming Study Groups for Prep Courses Using Probabilistic Graphical Models (Extended Abstract)
    Yoram BachrachYoad LewenbergJeffrey S. Rosenschein and Yair Zick
    Short Paper: The 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2016, pages 1359-1361

  • Incentivizing Peer Grading in MOOCS: an Audit Game Approach
    Alejandro Carbonara, Anupam DattaArunesh Sinha and Yair Zick
    Conference Paper: The 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015, pages 497-503

  • Learning Cooperative Games
    Maria F. BalcanAriel D. Procaccia and Yair Zick
    Conference Paper: The 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015, pages 475-481

  • Non-Myopic Negotiators See What's Best
    Yair ZickYoram BachrachIan Kash and Peter Key
    Conference Paper: The 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015, pages 2047-2053

  • Influence in Classification via Cooperative Game Theory
    Amit DattaAnupam DattaAriel D. Procaccia and Yair Zick
    Conference Paper: The 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015, pages 511-517

  • Voting Rules as Error-Correcting Codes
    Ariel D. ProcacciaNisarg Shah and Yair Zick
    Conference Paper: The 29th AAAI Conference on Artificial Intelligence (AAAI), 2015, pages 1000-1006

  • Arbitration and Stability in Cooperative Games with Overlapping Coalitions
    Yair ZickEvangelos Markakis and Edith Elkind
    Journal Paper: Journal of Artificial Intelligence Research Volume 50, 2014, Pages 847-884

  • Arbitration and Stability in Cooperative Games
    Yair Zick and Edith Elkind
    Journal Paper: SigEcom Exchanges 12.2, 2014, Pages 847-884

  • On Random Quotas and Proportional Representation in Weighted Voting Games
    Yair Zick
    Conference Paper: The 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2013, pages 432-439

  • Bounding the Cost of Stability in Games Over Interaction Networks
    Reshef Meir, Yair ZickEdith Elkind and Jeffrey S. Rosenschein
    Conference Paper: The 27th AAAI Conference on Artificial Intelligence (AAAI), 2013, pages 690-696

  • Dynamic Weighted Voting Games
    Edith ElkindDmitrii V. Pasechnik and Yair Zick
    Conference Paper: The 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2013, pages 515-522

  • Taxation and Stability in Cooperative Games
    Yair ZickMaria Polukarov and Nicholas R. Jennings
    Conference Paper: The 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2013, pages 523-530

  • On Manipulation in Multi-Winner Elections Based on Scoring Rules
    Svetlana Obraztsova, Yair Zick and Edith Elkind
    Conference Paper: The 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2013, pages 359-366

  • Stability via Convexity and LP Duality in Games with Overlapping Coalitions
    Yair ZickEvangelos Markakis and Edith Elkind
    Conference Paper: The 26th AAAI Conference on Artificial Intelligence (AAAI), 2012, pages 1506-1512

  • Overlapping Coalition Formation Games: Charting the Tractability Frontier
    Yair ZickGeorgios Chalkiadakis and Edith Elkind
    Conference Paper: The 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012, pages 787-794

  • The Shapley Value as a Function of the Quota in Weighted Voting Games
    Yair ZickAlexander Skopalik and Edith Elkind
    Conference Paper: The 22nd International Joint Conference on Artificial Intelligence (IJCAI), 2011, pages 490-496

  • Arbitrators in Overlapping Coalition Formation Games
    Yair Zick and Edith Elkind
    Conference Paper: The 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2011, pages 55-62

Awards & Honours

  • The 2017 NRF Fellowship (2017)
  • The ACM EC Best Paper Award (2016)
  • The IFAAMAS Victor Lesser Distinguished Dissertation Award (2014)
  • The AAMAS 2011 Pragnesh Jay Modi Best Student Paper Award (2011)
  • The Singapore International Graduate Award (2010-2014)
  • “Amirim” Scholarship (2007-2009)

Teaching (2019/2020)

  • CS5461: Algorithmic Mechanism Design
  • CS3243: Introduction to Artificial Intelligence
  • CS4261: Algorithmic Mechanism Design