Q&A with Christian Kroer, Columbia professor and Fb Fellowship alum
In this monthly series of interviews, we put members of the academic community and their critical research in the spotlight – as thought partners, collaborators, and independent contributors.
For July we have nominated Christian Kroer, professor at Columbia University. Kroer’s relationship with Facebook began in 2016 when he received the Facebook community in business and computer science. During this time, Kroer became an intern on Facebook Core data science (CDS) team that eventually led to a post-doctoral position. While at CDS, Kroer co-authored a number of publications at leading research conferences and journals.
In these questions and answers, Kroer shares more about his background, current research, and experience with Facebook.
Q: Tell us about your role at Columbia and the type of research you specialize in.
Christian Kroer: I am an assistant professor in the Department of Industrial Engineering and Operations Research at Columbia. There I do research that generally draws on ideas from optimization, AI, game theory and market design. Two of my most active areas of research are 1) how to compute game theory equilibria on a large scale, typically using a mix of optimization and AI techniques, and 2) how to use optimization and AI to understand and enable large-scale market design. Market is to be understood here in a broad sense and can mean, for example, Facebook’s advertising auction market, but also things that are normally not viewed as markets, such as: B. a fair large-scale allocation of resources to users or content producers.
In general, I find research that appeals to me, as it allows me to mix theoretical and applied work. Most of my work involves a lot of math – I particularly like convex optimization and online learning – but I usually also want to implement the algorithms I co-author with to see how they work with realistic data. Sometimes the discrepancy between theory performance prediction and practical performance can be very interesting! Most of the research I do at Columbia is done in collaboration with the great PhD students we have in our department. I’ve really enjoyed being a professor so far, and that’s in large part because of you.
In addition to research, I also teach courses. My teaching mainly focuses on AI and machine learning, looking at how these topics are combined with more classic operations research topics.
Q: What have you been working on lately?
CK: I have a number of active research areas that I am working on. I will try to summarize the most important ones briefly. You can find more context on my website.
I worked with my student Yuan Gao on the problem of calculating a so-called market equilibrium. The idea in a market equilibrium is that you have a number of goods, as well as a number of buyers interested in those goods, and each buyer has a currency budget. The aim is to find a set of prices and a corresponding distribution of the goods among the buyers, so that every buyer acquires an optimal bundle of goods at the prices. An interesting note is that the budgets and prices do not have to be in the form of real money; it can also be counterfeit money that we give to every buyer. For example, this idea has been used to fairly distribute course places to students: give each student a wrong budget for buying course places, ask them how much they would appreciate various proposed class schedules, and find a market equilibrium below this wrong economy that you created. Our work in this area has been particularly motivated by Internet-scale applications such as: B. Ad auctions and fair content recommendations, where the scalability of the algorithms is of the utmost importance.
With my student Rachitesh Kumar, I worked with tools from theoretical computer science and economics to analyze the behavior of bidders in Internet advertising auctions. Together with his co-advisor Santiago Balseiro, we examine large auction systems within the framework of first price auctions, where we examine the existence of game-theoretical equilibria and the structure of optimal buyer behavior. This is a very relevant topic as several major ad exchanges have recently switched to this auction format. Together with Columbia University’s Xi Chen, we used tools from Computational Complexity Theory to show that it is most likely difficult (in the strictly formal sense) to compute equilibrium behavior for buyers in a system that uses second price auctions. This is interesting against the background of the switch from second price auctions to first price auctions mentioned above, as our work shows that there is a strong theoretical sense in which first price auctions are easier to handle than second price auctions.
I am still working on the topic on which I spent most of my PhD thesis: Calculating the Nash equilibrium and other solution concepts in large sequential games with imperfect information. To give an idea of what I mean here, the canonical example of such a game is poker. Informally, it can be shown that a Nash equilibrium is the optimal way to play a two-player poker game when no assumptions are made about the opposing player. The catch is that this game is extremely big, and so you have to accept some approximation errors when trying to compute these equilibria. Together with Gabriele Farina and Tuomas Sandholm, I worked on some new ideas to achieve fast theoretical and practical rates of convergence when using gradient descent-like algorithms to solve these games.
Q: When and how did you first come into contact with Facebook?
CK: My relationship with Facebook goes back a long way. I first got into Facebook during my PhD when I received the Facebook Fellowship in Economics and Computation in early 2016 (or maybe late 2015). In the same year I also spent the summer as an intern in the CDS team with Eric Sodomka and Nico Stier. This internship actually had a huge impact on my long-term research interests. Much of the market-driven work I’ve described earlier is inspired by the time I’ve spent with them.
Q: How did your relationship with Facebook develop from then on?
CK: After my internship at CDS, I worked with the group over and over again during the rest of my doctorate. Then, after my doctorate, I also worked as a postdoc in the group for a year. Since then, I have continued to work with various Facebook researchers on projects related to large markets. For example, we’re working on how optimization and AI methods can be used to improve recommendations for people interested in blood donation opportunities.
Q: Where can people find out more about your research?
CK: I post links to all of my work on my research website. I also wrote a number of scripts for a PhD course that I taught in my department; these cover several of the general areas I work in. I also occasionally tweet about research topics @chrkroer.