Uri Rothblum's intellectual legacies

The journal Linear Algebra and its Applications has published an article in memoriam of Uri Rothblum, who passed away in March of this year:   Uriel G. Rothblum (1947–2012) by Raphael Loewy.

The article has discussions of aspects of Uri's work by a number of his collaborators, one of whom is Hans Schneider, a longtime editor of LAA. I recently corresponded with Professor Schneider about the beginning of his long and productive collaboration with Uri, and (with his permission) here is some of that correspondence.

 Dear Professor Schneider: Eric Denardo shared with me the memoir of Uri Rothblum, and encouraged me to write a note to you about his very first interaction with you. My memory of it isn't all that clear.

It must have been in 1974 (the year that he and I graduated from Stanford) that you contacted him about his paper on nonnegative matrices. As I recall, your letter suggested that perhaps his results and some of yours should appear in collaboration. He wasn't sure that his English was up to the task of saying "no" in a diplomatic way, and so he asked me to help draft the letter, which explained that he had a special emotional attachment to that paper since it was a central part of his dissertation.

He valued enormously his subsequent collaboration with you, and never tired of telling me that the letter I had drafted for him might be the most productive piece I have written.

The world is certainly less complete without Uri in it.

All the best,

Al Roth
http://kuznets.fas.harvard.edu/~aroth/alroth.html
http://marketdesigner.blogspot.com/

 From: Hans Schneider [hans@math.wisc.edu]
 Sent: Saturday, September 01, 2012 1:15 PM
 To: Roth, Alvin
 Cc: Eric Denardo
 Subject: Re: Uri's write-up in Linear Algebra and its Applications
 Dear AL,
 Thank you for your very interesting letter and  apologies for my slow reply. 
 ...

 But now to your remarks. You are right, I proposed that Uri and I combine our papers and he turned this  down. I did not know that you were involved until Eric told me this year.

 It was a good decision on his part and I need to thank you for your help to Uri.  The sequence of letters (mine, his) spectacularly achieved what I desired, viz. cooperation with a young mathematician who was interested in the same area as I. I think it is impossible for me to explain how mathematically isolated I felt at the time without sounding like a petulant child.

 BTW, I first saw Uri's paper #3 in early 1975. The correction is worth making for I spent calendar 1974 at  TU Munich and before I left my student Richman had essentially completed results for his Ph.D. which  were  waiting to be writtten up when I saw Uri's paper. That's the paper I offered to combine with Uri's. I recall that Uri said there was room for both papers; I wish I still had his letter. Richman-S finally appeared in LAMA in 1978.

 I have never again offered to make a joint paper of a submission to LAA, even when I felt I could improve it significantly. I got increasingly worried that this is crossing a line for an EIC.  (Full disclosure, there is another paper joint with me that was originally submitted by my co-authors, but it became joint at the suggestion of an editor when he saw my referee's report.)

 Finally , I am very glad to hear from you, AL, that Uri saw the events that brought us together so positively. To my recollection, we never discussed them in any meaningful way.

 best wishes

 hans

 ps The obit is now on line on the LAA site under 'articles in press'. 

******************

Some quick recollections of my own, of an intellectual history sort.

Uri and I were office mates in grad school, and I often benefited from his advice. I recall one time in particular, when I needed to prove that a certain interval was compact, and he showed me a proof that allowed me to complete the theorem that formed the basis for my dissertation. I later realized that a corollary of his proof was that _every_ interval was compact, so unfortunately I had to use another proof (and I recall a tense week between weekly visits to my advisor, at the end of which I was able to say "there was a problem with the proof I outlined last week" instead of "...with the theorem...").

Uri and I didn't collaborate as grad students, but we eventually wrote four papers together:

Roth, A.E. and Rothblum, U. "Risk Aversion and Nash's Solution for Bargaining Games With Risky Outcomes," Econometrica, Vol. 50, 1982, 639‑647.

Roth, A.E., Rothblum, U.G., and Vande Vate, J.H. "Stable Matchings, Optimal Assignments, and Linear Programming," Mathematics of Operations Research, 18, 1993, 803-828. 

 Blum, Y., A.E. Roth, and U.G. Rothblum "Vacancy Chains and Equilibration in Senior-Level Labor Markets," Journal of Economic Theory, 76, 2, October 1997, 362-411.

Roth, A.E. and U.G. Rothblum "Truncation Strategies in Matching Markets--In Search of Advice for Participants," Econometrica, 67, January, 1999, 21-43.
  

The two two-author papers each began when, in the course of a long walk somewhere, I indicated that I was working on a problem that was too hard for me to solve.  The paper with John Vande Vate came about by combining two different such conversations. But the most unusual of the collaborations was initiated by Uri in connection with work he had started with his student Yossi Blum. I believe they figured out that a paper by Blum and Rothblum would look better if they had a third author named Roth.

Readers of this blog may already be familiar with his other papers on matching and market design:

H. Abeledo and U.G. Rothblum, “Stable matchings and linear inequalities,” Discrete Applied Mathematics 54 (1994), pp. 1-27.

H. Abeledo and U.G. Rothblum, “Courtship and linear programming,” Linear Algebra and Its Applications 216 (1995), pp. 111-124.

H. Abeledo and U.G. Rothblum, “Paths to marriage stability,” Discrete Applied Mathematics 63 (1995),  pp. 1-12

H. Abeledo, Y. Blum and U.G. Rothblum, “Canonical monotone decompositions of fractional stable matchings,” The International Journal of Game Theory 25 (1996), pp. 161-176.

Y. Blum and U.G. Rothblum, “ ‘Timing is everything’ and marital bliss,” Journal of Economic Theory 103 (2002), pp. 429-443.

N. Perach, J. Polak and U.G. Rothblum, “Stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion,” The International Journal of Game Theory 36 (2008),
pp. 519-535.

N. Perach and U.G. Rothblum, “Incentive Compatibility for the Stable Matching Model with an Entrance Criterion,” accepted for publication in The International Journal of Game Theory, 17 pages.

Book review: U.G. Rothblum, Two Sided Matchings: A Study in Game-Theoretic Modeling and Analysis (by A.E. Roth and M.A. Oliviera Sotomayor), Games and Economic Behavior 4 (1992), pp.161-165

Here is Uri's listing on Google Scholar.
Here is his list of publications in chronological order.
Here is the obituary by Boaz Golany in INFORMS online.

Special issue of NRL in honor of Uri Rothblum, February 2019

Occasionally an Operations journal can bring memories flooding back: here's a special issue in honor of my old friend Uri Rothblum, who passed away in 2012. (We met in 1971, when we entered the Ph.D. program in Operations Research at Stanford.)

 The Journal Naval Research Logistics 
Volume 66, Issue 1, Special Issue:Uriel Rothblum, Pages: 1-102, February 2019

Here is the introduction, and the first paper, coauthored by Uri...

Introduction

• Michael Katehakis

• Pages: 3
 
• First Published: 26 December 2018

• Full text
 
• PDF
 
• Request permissions

RESEARCH ARTICLES

Free Access

Constant risk aversion in stochastic contests with exponential completion times

• Pelin G. Canbolat
 
• Uriel G. Rothblum

• Pages: 4-14
 
• First Published: 24 January 2017

• Abstract
 
• Full text
 
• PDF
 
• References
 
• Request permissions
• ***************************

The previous issue was in honor of Pete Veinott, Uri's Ph.D. advisor:
Volume 65, Issue 8 Special Issue:Pete Veinott 

************

Here are other posts of mine remembering Uri.

The journal used to be called the Naval Research Logistics Quarterly, and I published three papers there from 1977 to 1982.

Uriel G. Rothblum, 1947-2012

Uri Rothblum in his office at the Technion in 2003

My old friend Uri Rothblum passed away today, after a heart attack. We met when we entered graduate school in 1971. He was a man of many parts: a good friend, a devoted husband, a proud dad of three grown sons, and an important and dedicated and tireless scholar.

Update: there's a website at the Technion where friends can post comments in memoriam.

Operations Research Conference in Memory of Professor Uriel G. Rothblum (June 11, 2013)

I am in Israel to participate in a conference honoring my old friend Uri Rothblum. The instructions to the presenters were to try to present a talk that Uri would have liked to hear...

Matching with Couples - Video of my lecture at the Rothblum conference at the Technion

Here's the talk I gave at the memorial conference for Uri Rothblum at the Technion:
Matching with Couples (55 minutes)

The year in passings

I noted a number of deaths this year (and memorials for earlier passings):

•  Michel Balinski (1933-2019)
•  Alan Krueger (1960-2019)
•  Dr. Oscar Salvatierra, Jr. (1935 - 2019)
•  Special issue of NRL in honor of Uri Rothblum, February 2019
•  Memorial service for Martin Shubik today at Yale
• In Memoriam: Martin Shubik
•  Xenotransplants, Baby Fae, and the complex pioneering efforts of Dr. Leonard Bailey, RIP
• Mark Kleiman (1951-2019)
• Marty Weitzman, 1942-2019
• Ed Green, 1948-2019
• Egon Balas, 1922-2019
•  Who is a refugee? Remembering U.N. High Commissioner for Refugees Sadako Ogata

Designing privacy (differential privacy) at the Institute for Advanced Study

Differential Privacy Symposium

Differential privacy disentangles learning about a dataset as a whole from learning about an individual data contributor. Just now entering practice on a global scale, the demand for advanced differential privacy techniques and knowledge of basic skills is pressing. This symposium will provide an in-depth look at the current context for privacy-preserving statistical data analysis and an agenda for future research. This event is organized by Cynthia Dwork, of Microsoft Research, with support from the Alfred P. Sloan Foundation.

Speakers include:

Helen Nissenbaum, Cornell Tech and NYU
Aaron Roth, University of Pennsylvania
Guy Rothblum, Weizmann Institute
Kunal Talwar, Google Brain
Jonathan Ullman, Northeastern University

Market Design and Operations Research: an interview by the journal Mathematics of Operations Research

The journal Mathematics of Operations Research, where the main paper from my dissertation was published in 1976, has published an interview with me in their Author Spotlight section: In Conversation with...ALVIN E. ROTH.

Here's the first question and answer:

INFORMS:  Your first published paper, “Subsolutions and the Supercore of Cooperative Games,” [2]based on your doctoral thesis, appeared in MOR in 1976. The paper was handled by Nobel winner and MOR Founding Area Editor Robert Aumann. Can you share with us how your first experience with the peer review process went?

ROTH:  I recall that experience vividly. Aumann, in his editor’s letter, told me to ignore the referees, but to revise the paper along the lines he would describe. One revision he wanted had to do with the proof of my main theorem, for which I had used Zorn’s Lemma. He advised me to try to construct a proof which instead used transfinite induction. I didn’t know what transfinite induction was, so I was very skeptical, but I grimly trudged to the math library and got a copy of Hausdorff’s book Set Theory [3] to repair this gap in my education. I still remember how my hopes lifted when I opened the book and saw that it had been translated from the German by…Aumann. It turned out that he knew what he was talking about, and the proof that appears in my published MOR paper uses transfinite induction.

...

At the Author Spotlight page they also link to the several papers I published in MOR:

Roth AE (1976) Subsolutions and the Supercore of Cooperative Games. Math. Oper. Res. 1(1):43–49.  

Roth AE (1977) Individual rationality and Nash’s solution to the bargaining problem. Math. Oper. Res. 2(1): 64–65. 

Roth AE (1982) The economics of matching: Stability and incentives. Math. Oper. Res. 7(4):617–628. 

Roth AE (1985) Conflict and coincidence of interest in job matching: Some new results and open questions. Math. Oper. Res. 10(3):379–389.*  

Roth AE, Rothblum UG, Vande Vate, JH (1993) Stable matchings, optimal assignments, and linear programming. Math. Oper. Res. 18(4): 803–828. 

Since becoming a notorious economist, I've had a number of conversations with operations researchers that begin with a question like "Why did you switch from OR to Economics?"

My usual answer is that I got my Ph.D. in OR in 1974 with a dissertation in game theory, and it looked at that time as if OR would be a natural place for game theory to flourish, particularly since Bob Aumann was the founding game theory editor of MOR. But, as it turned out, game theory grew first and fastest in Economics. So I just stood my ground, while the disciplinary boundaries shifted around me. Today, market design has become the engineering part of game theory, and it's time for OR and Economics to reconnect around market design. And indeed at Stanford, many of the Ph.D. students in our market design classes in the econ department are OR students from our MS&E department or from our Business school, both of which in turn have market designers on their faculty.  So I'm optimistic that my dual identities as an economist and operations researcher may soon seem seamless.
****************



*Beware, my 1985 paper contains an error about the lattice structure of stable matchings, that was noted and corrected by
Charles Blair (1988), "The Lattice Structure of the Set of Stable Matchings with Multiple Partners,"  Mathematics of Operations Research 13(4):619-628. http://dx.doi.org/10.1287/moor.13.4.619
and also by
Jianrong Li, (2013) A Note on Roth's Consensus Property of Many-to-One Matching. Mathematics of Operations Research 38(2):389-392. http://dx.doi.org/10.1287/moor.1120.0576 

"דוקטור לשם כבוד" honorary doctorate at the Technion

When I was in Haifa to attend the conference in memory of Uri Rothblum (where I gave this talk), I was reminded that I used to visit often: for many years I was on the Board of Governors of the Technion.

And so, while I was there, I got an honorary degree, and planted a tree.

In Latin, an honorary doctorate is Doctor honoris causa, in Hebrew "דוקטור לשם כבוד" . (Doctor l'shem cavod, i.e. Doctor for the sake of honor...)

Here's an interview I did by phone with a reporter.
Here's a picture of the assembled cast.

(l-r) Prof. Alvin E. Roth; Elisha Yanay; Alfred J. Bar; Yoram Alster; J. Steven Emerson; Daniel Rose; Prof. Peretz Lavie, president of the Technion; Danny Yamin, Chairman of the Technion Council; Lawrence Jackier, Chairman of the Technion Board of Governors; Melvyn H. Bloom; Ilan Biran; and Prof. Jason L. Speyer.

June 10, 2013 

***************
And here are me and Emilie next to the newly planted tree (the little one on the left, not the big one behind us...)

Update: here's the video of the honorary doctorate ceremonies. (It's long, but I did my best to keep in short, you can see me starting at 1:22:23--most of the applause is for brevity:)

And here is a much shorter video of the tree-planting ceremony, with President Peretz Lavie doing the honors, and Technion chemistry laureate Dan Schechtman and me planting the trees.

Vacancy chains in urban housing

 Vacancy chains occur not just in labor markets, but also in housing markets. (Earlier this week I wrote about housing chains for hermit crabs that result from evictions.)  A vacancy chain in a housing market can be thought of as a moving chain: someone moves into a vacant house or apartment (perhaps a newly constructed one), and someone else moves into the home they vacated, and so on, until the chain ends when a person who was in some different market (e.g. in rental housing, or in a distant location) moves into the last identifiable home in the chain.

Here are two papers that explore what happens when newly constructed housing is relatively expensive. They find that the chain often reaches much more moderately priced housing, i.e. adding to the stock of expensive housing also makes more affordable, existing housing available to new occupants.

The first paper draws on data from a dozen American cities (from Atlanta to San Francisco):

The effect of new market-rate housing construction on the low-income housing market, by Evan Mast, Journal of Urban Economics, Available online 27 July 2021, https://doi.org/10.1016/j.jue.2021.103383

Abstract: I illustrate how new market-rate construction loosens the market for lower-quality housing through a series of moves. First, I use address history data to identify 52,000 residents of new multifamily buildings in large cities, their previous address, the current residents of those addresses, and so on for six rounds. The sequence quickly reaches units in below-median income neighborhoods, which account for nearly 40 percent of the sixth round, and similar patterns appear for neighborhoods in the bottom quintile of income or percent white. Next, I use a simple simulation model to roughly quantify these migratory connections under a range of assumptions. Constructing a new market-rate building that houses 100 people ultimately leads 45 to 70 people to move out of below-median income neighborhoods, with most of the effect occurring within three years. These results suggest that the migration ripple effects of new housing will affect a wide spectrum of neighborhoods and loosen the low-income housing market.

%%%%%%%%%%%

A more recent working paper draws on data from metropolitan Helsinki and reaches similar conclusions:

Bratu, Cristina and Harjunen, Oskari and Saarimaa, Tuukka, City-wide Effects of New Housing Supply: Evidence from Moving Chains (August 31, 2021). VATT Institute for Economic Research Working Papers 146, Available at SSRN: https://ssrn.com/abstract=3929243 or http://dx.doi.org/10.2139/ssrn.3929243

Abstract: We study the city-wide effects of new, centrally-located market-rate supply using geo-coded total population register data from the Helsinki Metropolitan Area. The supply of new market rate units triggers moving chains that quickly reach middle- and low-income neighborhoods and individuals. Thus, new market-rate construction loosens the housing market in middle- and low-income areas even in the short run. Market-rate supply is likely to improve affordability outside the sub-markets where new construction occurs and to benefit low-income people.

**********

Earlier:

Vacancy chains in housing for hermit crabs   

Blum, Y., A.E. Roth, and U.G. Rothblum "Vacancy Chains and Equilibration in Senior-Level Labor Markets," Journal of Economic Theory, 76, 2, October 1997, 362-411.

Computing fairness

One of the areas in which computer science and economics touch each other more than a bit is in understanding what constitutes a fair way of allocating scarce resources.  This was the subject of a recent Northwestern CS workshop:

Quarterly Theory Workshop: Algorithmic Fairness

"Synopsis: As algorithmic systems have increasingly been deployed to make consequential decisions, it is becoming urgent that we grapple with the problem of (un)fairness and discrimination. These are delicate issues — to think rigorously about them, we first need to figure out how to formally define what we want, and then reason about how we might go about achieving our goals algorithmically — and what tradeoffs we will have to manage. This workshop focuses on recent advances in the theory of algorithmic fairness: both on foundational definitional questions, and on algorithmic techniques. The speakers are Nicole Immorlica (MSR), Jon Kleinberg (Cornell), Omer Reingold (Stanford), and Aaron Roth (U. of Pennsylvania).
The technical program of this workshop is organized by Aaron Roth and Jason Hartline."

These were the talks:

Speaker: Jon Kleinberg
Title: Algorithmic Fairness Criteria for Evaluating Individuals and Sets
Abstract: Recent discussion in the public sphere about classification by algorithms has involved tension between competing notions of what it means for such a classification to be fair to different groups. We consider several of the key fairness conditions that lie at the heart of these debates, and discuss recent research establishing inherent trade-offs between these conditions. We also consider a variety of methods for promoting fairness and related notions for classification and selection problems that involve sets rather than just individuals.

This talk is based on joint work with Sendhil Mullainathan, Manish Raghavan, and Maithra Raghu.

Speaker: Aaron Roth
Title: Preventing Fairness Gerrymandering in Machine Learning

Abstract: The most prevalent notions of fairness in machine learning are statistical notions: they fix a small collection of high-level, pre-defined groups (such as race or gender), and then ask for approximate parity of some statistic of the classifier (like positive classification rate or false positive rate) across these groups. Constraints of this form are susceptible to (intentional or inadvertent) fairness gerrymandering, in which a classifier appears to be fair on each individual group, but badly violates the fairness constraint on one or more structured subgroups defined over the protected attributes (such as certain combinations of protected attribute values). Individual notions of fairness avoid this problem, but at the cost of needing to make often unrealistic assumptions about the setting. We propose instead to demand statistical notions of fairness across exponentially (or infinitely) many subgroups, defined by a structured class of functions over the protected attributes. We will show how to achieve this in polynomial time, under the assumption that we are given oracles for solving the unconstrained learning problems (for both the set of classifiers to be learned, and the set of subgroups to be protected). Our algorithm casts the problem as solving for an equilibrium in a zero sum game, and observes that learning oracles are enough to efficiently play no-regret learning dynamics. We then demonstrate experimentally that our proposed algorithms are practical, by investigating their performance on several real datasets when instantiated with learning heuristics in place of oracles.

This talk is based on joint work with Michael Kearns, Seth Neel, and Steven Wu.

Speaker: Omer Reingold
Title: On Algorithmic Fairness Between Groups and Individuals 
Abstract: As algorithms increasingly inform and influence decisions made about individuals, it is increasingly important to address concerns that these algorithms might be discriminatory. Historically, definitions of fairness fell into one of two extremes: (1) broad-strokes statistical guarantees; (2) individual-level protections. Statistical guarantees tend to be much easier to satisfy (information and complexity theoretically), but tend to be much weaker in the protections they provide. We will discuss two recent works towards bridging the gap between statistical and individual protections. These works provide efficient learning algorithms that also ensure every subpopulation within some rich class is protected (according to some fairness notion).

One of the notions we will discuss is that of multicalibration — a new measure of algorithmic fairness that aims to mitigate concerns about discrimination that is introduced in the process of learning a predictor from data. The second notion studies fair classification within the versatile framework of Dwork et al. [ITCS 2012], which assumes the existence of a metric that measures similarity between pairs of individuals. Unlike previous works on metric-based fairness, we study the setting where a learning algorithm does not know the entire metric, but can query similarities between particular pairs of individuals a bounded number of times. We note that we do not make any assumption on the metric and are still able to obtain meaningful protection from systemic discrimination that we refer to as “metric multifairness.”

The talk will be focused on the various ways in which algorithmic fairness can be defined but will also elude to some of the ways in which it can be obtained. It is based on joint works with Úrsula Hébert-Johnson, Michael P. Kim and Guy Rothblum.

Speaker: Nicole Immorlica
Title: Fair Classification and Learning
Abstract:  Classification, learning, and optimization algorithms are increasingly used to make decisions of social consequence. An automated resume reader classifies applicants, deciding which are worth interviewing. A learning algorithm estimates the impact of a drug on health outcomes. A facility location algorithm chooses where to locate new warehouses. For these algorithms to be useful, practitioners strive to maximize their accuracy and optimality. However, this can result in differential treatment across population subgroups, resulting in a sense of inequity. Fairness metrics are used to measure the degree of inequity. In this talk, we explore how to jointly optimize fairness and accuracy using, as a black box, existing algorithms that optimize accuracy or optimality. Our first solution is tailored to classification tasks and proposes decoupling the classification task, using different classifiers for each subgroup. Our second solution can optimize any smooth and continuous function of accuracy and fairness in classification, learning, and optimization settings. It further has the advantage that subgroup membership, while used to train, is not used at run time. This additional power comes with the cost of added computational complexity in training.

Technion honorary doctorate ceremony

The Technion will broadcast its honorary doctorate ceremony here: Honorary Doctors Ceremony - June 10, 2013 – 8:00 pm, 1:00 pm EDT, USA

I don't imagine that it will be gripping to watch, but I will be there. I served for a number of years on the Technion's Board of Governors, and I am in Israel for the memorial conference of my old friend Uri Rothblum.