We were pleased to have Yannai. A. Gonczarowski (Hebrew University of Jerusalem and Microsoft Research) visit our Department recently. During his time with us, he not only gave his excellent seminar on “Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games“, but also generously gave his time to answer a short Q & A, covering everything from resource selection games, to creative thinking in mathematics, to finding the time to perform opera.

Where are you currently working?

I am currently studying toward a PhD at the Einstein Institute of Mathematics, the Rachel and Selim Benin School of Computer Science and Engineering, and the Federmann Center for the Study of Rationality, at the Hebrew University of Jerusalem. My advisors are Profs. Sergiu Hart and Noam Nisan. My studies are supported by an Adams Fellowship of the Israel Academy of Sciences and Humanities. I am also a Research Intern at Microsoft Research. My research interests include game theory, combinatorics, epistemology and multi-agent systems.

You’ve been working in game theory, combinatorics and multi-agent systems. What attracted you to undertake research within these areas?

One of the best things about Academia is that when you start down one road, you never know where you’re going to end up. Since elementary school, I’ve liked combinatoric riddles and, as an undergraduate, Discrete Mathematics / Combinatorics were my favourite topics. One day, in my first undergrad semester, as part of a Discrete Mathematics course, we were taught Gale and Shapley’s Stable Matching Algorithm, and were given an example of how it can be manipulated. This fascinated me like nothing I had learnt before, and a casual observation that I made to the lecturer, Prof. Ehud Friedgut, eventually spawned my first scientific paper (co-authored with him – Gonczarowski, Y.A., Friedgut, E. (2013) Sisterhood in the Gale-Shapley Matching Algorithm. The Electronic Journal of Combinatorics. 20 (2). #P12). For my Master’s degree, I searched for a combinatorial problem to work on, and by happenstance bumped into Prof. Yoram Moses, who told me about a combinatorial problem he came upon in his research at the time. This problem, drawing from multi-agent systems in distributed computing, quickly pulled me into the fascinating world of logic and epistemology in multi-agent systems (epistemology is useful also beyond game theory!), which eventually became the field of study of my thesis (under his co-supervision, alongside Prof. Gil Kalai – Gonczarowski, Y.A., 2012. Timely Coordination in a Multi-Agent System. MSc thesis, Hebrew University of Jerusalem). When starting my PhD, I decided that I might as well work in game theory to begin with, since I was likely to be drawn into it yet again in the future anyway… Every now and then, I find myself stumbling upon combinatorial questions arising from game theory, and looking at those is always great fun as well.

You’ve recently been working on computing equilibria in resource selection games; could you tell us a little about that?

Thanks for asking! Resource selection games are games in which each player must choose exactly one resource out of a list (lists may vary across players), and the player’s payoff depends (usually in a decreasing fashion) on the load on the chosen resource, i.e. the amount of other players choosing the same resource. Such games are ubiquitous, and in fact any reader plays such a game whenever asking themselves questions such as “taking which highway would allow me to arrive at my destination as fast as possible this morning?”, “using which computer server would complete my computing jobs the quickest?”, and even (this is for a few friends of mine from back home!) “shopping at which fashion store would make my clothes as unique as possible?”. Nonatomic resource selection games (games where each of the continuum of players has, by itself, negligible contribution to the load on any resource) have been central to the interplay between computer science and economics (the field commonly referred to as ‘algorithmic game theory’), but from a purely game-theoretic perspective, not as much is known about them as is about atomic games. In our paper (co-authored with Prof. Moshe Tennenholtz – Gonczarowski, Y.A., Tennenholtz, M. (2014) Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games. Hebrew University of Jerusalem Center for the Study of Rationality. Discussion Paper 673), we provide a novel construction, drawing intuition from a (physical) hydraulic system, and apply it to such games in order to both strengthen old results about such games, and prove a gamut of new results. One of the benefits of our analysis is that all our existence proofs for equilibria are constructive (no fixed point theorems / minimax / potential / linear programming needed), giving rise to explicit formulae for equilibria, and even to calculation of equilibria without even using a computer, but merely a few containers, pipes, pistons, and water (don’t let the animations accompanying the proofs fool you, though — the mathematics behind these proofs is completely formal and rigorous, of course!).

A mathematical proof that uses pipes and vessels of liquid is quite unusual. How did you come up with this idea? Is this sort of creative thinking something one can be trained to do?

Thanks! Well, it all started with a very special case of the problem, for which I was a bit too lazy to write down all the equations to solve, and when I tried to envision the qualitative behaviour of the solution, an analogy to a hydraulic system came to mind. (I recently learnt that it was Bill Gates who once said “I choose a lazy person to do a hard job, because a lazy person will find an easy way to do it.”) After that, we started asking ourselves how to extend the system to cover scenarios that are increasingly more generic. You know, for many of the most beautiful proofs that I know, a great deal of creative thinking was needed, and how this can be taught is perhaps one of the key questions in training a researcher. Specifically regarding our hydraulic analogy, before starting to circulate it we were a bit anxious as to whether we could mathematically generate strong-enough results from our construction, which, fortunately, I believe we were able to do. Unfortunately, if this were ‘simply’ another way of obtaining existing results in a more intuitive manner, then I doubt that it would have received as much attention; perhaps encouraging such physical analogies and unconventional proofs, even if they ‘only’ simplify known proofs or make them more intuitive, may have the effect of increasing the amount of unconventional proofs out there, which in turn may train readers to think more in such directions. After all, arguably the best way to train someone to use certain mathematical tools, concepts or directions is simply to expose them to enough known proofs that use these, so that one hopefully gets the idea.

Do you see applications for this research? Is that something you think about when choosing a project?

This question seems to be asked more and more in all academic fields. The reality is that some of the most profound applications have come from research that seemed at one point quite detached from any practical use. Any electrical engineer would tell you that complex analysis is invaluable in their line of work; I can’t help but wonder: had the question of applicability been raised when complex analysis was developed, would it still have been developed? Probably even more alarming is that had this been the case, humanity would probably never have known that it missed out on something that could find applicable use. Personally, I tend to choose projects based on how much they captivate me, and how much I find myself obsessing over them when I’m driving, eating, sleeping, etc. — this way I know that I will have fun regardless of the outcome. I hope at least some of these either find use, be it theoretical or practical, or inspire research of use, sometime in the future.

You mentioned working with top mathematicians, computer scientists and game theorists during your Bachelor’s and your Master’s, and now as a PhD. Would you recommend young students to do the same: approach their professors and talk about their ideas? What is it about the academic atmosphere where you grew up that fostered such openness?

I was indeed, and still am, fortunate to work with great advisors and co-authors. First, I must emphasise that Israel is not as formal as many other countries. It’s perfectly acceptable, for instance, for a PhD student, to, unscheduled, pop by the office of any professor and ask if they have a few minutes to listen to an idea that the student has, and the professor would agree if she or he has the time. For a BSc student this would be more risky — personally, I had some ‘chutzpah’ and was fortunate with the responses I got (and, apparently, the ideas weren’t bad!). Would I recommend this to young students? That depends on the professor and on the idea, I guess… on the one hand, you’ll never know unless you try (and if you try, it could be well worth it), and on the other hand, no one wants a reputation of being a nag with bad ideas… I guess my advice would be: always be extremely polite, and make sure you’ve invested a significant amount of your own time thinking at home before asking for the time of others. To any faculty member who would be kind enough to listen to my junior advice, I would recommend always being willing to listen to ideas, no matter whom they come from.

You are also a serious musician, is that right? Do you still find the time to perform, alongside the progression of your mathematical career?

I am indeed a professionally-trained opera singer, having completed a Bachelor’s and a Master’s degree in Classical Singing at the Jerusalem Academy of Music and Dance (one of the top performing arts schools in Israel). I did my BMus in concurrence with my BSc, and my MMus in concurrence with my MSc, and up until that point I somehow managed to find the time for both my mathematical studies and my music studies (including school opera productions, concerts, etc.). Before starting my PhD, I was fortunate enough to perform in some of Israel’s most sought-after venues, receiving praise in our national press. Unfortunately, they don’t tell you when you’re a BSc student that it only gets busier as you progress (especially if you throw having a family into the mix), and they don’t tell you when you’re a music student that any performer spends a significant amount of their time preparing for auditions. To make a long story short, I sadly perform professionally much less than I used to, and when I do perform professionally, it’s usually by invitation of a conductor / composer / producer / etc., which allows me to skip the time-consuming stage of preparing material for endless auditions.