Rohit Vaish — CMU Visit

Rohit Vaish (Ph.D. student advised by Prof. Shivani Agarwal) talks about new interests spurred by a recent visit to CMU.

This post is about my research visit to Carnegie Mellon University (in Pittsburgh, Pennsylvania) during Fall 2015 semester. The visit was organized under the Indo-US Joint Center for Advanced Research in Machine Learning, Game Theory and Optimization supported by the Indo-US Science and Technology Forum. My host faculty for this visit was Prof. Avrim Blum.

The broad theme of our work was designing algorithms for joint-decision making in multiagent systems. In particular, we focused on the problem of kidney exchange. This problem arises in settings where patients with kidney disease manage to find a friend/relative/spouse who is willing to donate a kidney to them but is medically incompatible (say due to blood-type or tissue-type mismatch). In such a scenario, a transplant can still be carried out via a 2-way exchange, i.e. bringing together two such willing-but-incompatible donor-patient pairs (that happen to be cross-compatible) and having the donor from each pair donate a kidney to a patient from the other pair. In this case, all four surgeries (one each for the donor and patient from each pair) need to be conducted simultaneously in order to keep any of the donors from backing out. Nowadays, more complex cyclic exchanges (like 3-way and 4-way) are fast becoming common.

In its early stages, the task of matching donor-patient pairs was performed either by individual hospitals or by a team of locally connected hospitals. Recent years, however, have seen the emergence of centrally organized exchanges such as APKD, NKR and UNOS in the US, NLDKSS in the UK, ACCORD in the European Union etc. In a centralized kidney exchange, incompatible donor-patient pairs are revealed to the central exchange by the participating hospitals. A matching mechanism then operates on this pool of revealed donor-patient pairs to find as many opportunities for 2-way (or 3 or 4-way) exchange as possible, thereby maximizing social welfare (and the number of lives saved). Hospitals might find it in their selfish interest to conceal certain easy-to-match donor-patient pairs and perform the surgeries in-house, thereby benefiting both from internal matches and the matches suggested by the centralized exchange. There is growing theoretical and empirical evidence to suggest that strategic behavior on the part of the hospitals leads to significant inefficiencies in the overall social welfare. Besides, even in the absence of strategic considerations, the matching problem itself tends to become computationally intractable when 3-way (or larger) exchanges are allowed. The challenge facing an algorithm designer, therefore, is threefold – namely, to design a matching mechanism that (a) incentivizes the agents (in this case, the hospitals) to reveal complete information about their donor-patient pairs, (b) is computationally efficient and (c) minimizes the loss in efficiency. This thread was the subject of our research.

Pioneered by South Korea in 1991, kidney exchange has grown immensely ever since. In fact, the eminent Stanford economist Prof. Alvin E. Roth was awarded the Nobel Memorial Prize in Economic Sciences 2012 (along with Lloyd S. Shapley) in part for his pioneering contributions to the theory and practice of kidney exchange. Check out his talk at Simons Institute (where he discusses the above mentioned issues in greater detail) and his ever active blog.

A recent innovation in the practice of kidney exchange is that of altruistic donation. This refers to the situation when a generous donor simply wants to donate a kidney without any particular recipient in mind. Such donors are extremely valuable in kickstarting an altruistic donor chain, where the altruistic donor donates a kidney to a patient in need, whose willing-but-incompatible donor can in turn donate to another patient in need and so on. These chains are especially useful since they bypass the requirement of conducting all the surgeries simultaneously as with cyclic exchanges. The longest chains till date have been sixty humans long or more!

If you would like to know more, feel free to get in touch!

Advertisements

Pankaj Dayama — AAMAS 2015

Ph.D. student, Pankaj Dayama, gives us our second report on AAMAS 2015.

I travelled to Istanbul, Turkey to attend the AAMAS 2015 conference. I had a paper (“Truthful Interval Cover Mechanisms for Crowdsourcing Applications”) to present in the conference and also attended several talks/poster sessions. Overall the experience was very good. It was very diverse conference with many different tracks, so it was really difficult to shortlist the talks to attend.  I found the following ones very interesting:

  1. “Learning Submodular Functions with Applications to Multi-Agent Systems”, Invited talk by Maria Florina Balcan. This talk focused on use of machine learning in understanding submodular functions. In particular, it discussed recent work on studying the learnability of submodular functions with applications to the analysis of multi-agent systems. She discussed few general algorithms for learning such functions. Further, application of these algorithms for learning influence function in social networks was presented and empirical studies showed that it outperforms existing approaches.
  2. “Dynamic Influence Maximization Under Increasing Return to Scale”, H. Zhang, A. Procaccia, and Yevgeniy Vorobeychik. This paper addressed the algorithmic question of maximizing the total number of adopters of a product at the end of finite time horizon T, where the decision maker faces a budget constraint B. They formulate a dynamic influence maximization problem under increasing return to scale and show that the optimal policy has a simple structure. It must spend the entire budget in single stage (“Best-Stage”). In the setting where time dependency of the cost function is  replaced by cumulative adoption, they propose “Best-K-Stage” heuristic algorithm and show that it significantly outperforms the “Best-Stage” algorithm.

I also got a chance to go around Istanbul and really loved the city. My hotel was very close to the conference venue near Taksim Square. It was just a few miles from old part of the city which has several museums and mosques. I did visit a few places:

  • Blue Mosque (also known as Sultan Ahmed Mosque)  with blue domed exterior
  • Suleymaniye Mosque (largest mosque in Istanbul)
  • Grand Bazaar (with over 3000 shops selling leather goods, carpets, ceramic, etc): Any shopping here will be a test of your bargaining skills)
  • Spice Bazaar (with shops selling spices, nuts, dried fruit, Turkish Coffee, Turkish Delight,etc.)
  • Boat tour down the Bosphorus
  • Dolmabache Palace (new palace built towards the end of Ottoman period after Topkapi Palace)
  • Galata Bridge
  • Basilica Cistern: One of the largest underground ancient water cistern.

Regarding travel and food, the local commute in Istanbul is very efficient and cheap. I had some challenge finding good vegetarian food, but I did like the Aryan drink, Turkish tea, and sweets (Turkish Delight and Baklava).

Palash Dey — AAMAS 2015

For our first report, Ph.D. student Palash Dey describes his visit to Istanbul, Turkey to attend AAMAS 2015, one of the leading conferences in the area of intelligent systems. His papers at the conference are linked from here.

May 4: On the first day, I attended the Workshop on Exploring Beyond the Worst Case in Computational Social Choice (EXPLORE 2015). A prominent and long-pursued research thread in computational social choice (comsoc) theory is to study the use of computational intractability for protecting election systems against various manipulative attacks. However, some recent works expose the weakness of this approach – the intractability results hold only in the worst case! After that, it became very important to study intractability results beyond worst case guarantees. This was the focus of the workshop. On a related note, we had a paper in this conference where we show that although the classical manipulation problem is known to be NP-complete, they are not very hard to solve in the sense that they admit what is known as a polynomial kernel in the context of parameterized complexity.

May 5: The whole day was the doctoral consortium. This event was meant to be for guiding senior Ph.D. students in their future career (but many junior Ph.D. students including me also attended the program). It had interviews of a few established researchers, and they were sharing their own Ph.D. experiences. The session was really an interactive one, and I enjoyed it very much. In the second part, I presented my Ph.D. work. It was a ten-minutes talk. The mistake I made was that I intended to present all of my works and thus I really had to hurry! Choosing any one of my works and explaining it would have surely made people understand better.

May 6: I had a paper presentation that day. I also presented the corresponding poster.

May 7: I bunked the whole day!

May 8: Again I had two papers to present. During the poster session, I explained my work to Edith Elkind and Toby Walsh. Both of them are leading researchers in comsoc. After the presentation, I had a chat with Jerome Lang who is again a leading figure in comsoc.

Favourite papers

I found two papers at the conference particularly interesting.

  1.  “Complexity of Mechanism Design with Signaling Costs”, by Andrew Kephart and Vincent Conitzer: This paper proposes a notion of mechanism design in a restricted setting in the following sense. The set of actions of the players are fixed. The mechanism designer has to choose from a set of utility matrices (possibly exponential) to implement a social choice function. The question is does there exist a game which implements that choice function.
  2. Controlling Elections by Replacing Candidates or Votes“, by Andrea Loreggia, Nina Narodytska, Francesca Rossi, K. Brent Venable, Toby Walsh: This paper introduces a notion of candidacy game in the context of an election. This is particularly interesting since we are still finding a suitable notion of equilibrium in the context of voting. They proposed in
    this paper (and also a series of paper before!) a behavioral dynamics on the behavior of voters and candidates and showed some existential results.

Local Travel and Food

Bus and metro were very accessible and cheap (compared to other European countries). I was staying in the area called Taksim which was very nearby to the historical places namely Aya Sofia, Topkapi Palace, several museums, Blue mosque and so on. I just used to go to Eminuno by bus, and all the above mentioned places are at a walkable distance away. Also the ferry ride in Bosphorus channel is something one should not miss.

Regarding food, there were lots of (quite cheap) restaurants selling doner, hamburgers, and kebabs (both beef and chicken were available).

Bosphorus The Blue Mosque