Experimental math (XKCD)

The Unreasonable Effectiveness of Mathematics

 https://xkcd.com/3180/

 

Reputations take a long time to build but can be quickly destroyed

 US support for science is one of the things that will be hard to make reliable again.

Here's a story from the Washington Post, about and including an interview with the mathematician Terence Tao.

 The world’s greatest mathematician avoided politics. Then Trump cut science funding.  Terence Tao, often called the “Mozart of Math,” is focused on fundraising after federal research funding to UCLA was suspended.  By Carolyn Y. Johnson

" What’s hardest to restore is the sense of predictability and stability.

"People who support all the positive aspects of America have to speak out and fight for them now. The things that you took for granted, there was bipartisan support to keep certain things in the U.S. running as they have been more or less for the past 70 years because the system worked. That’s not a safe assumption anymore."

KENNETH ARROW’S LAST THEOREM by Paul Milgrom

 Here's a fitting tribute to Ken Arrow, who died in 2017, in the special issue of the Journal of Mechanism and Institution Design in Hono(u)r of (the still very much alive) Vince Crawford, edited by Alex Tetylboym

KENNETH ARROW’S LAST THEOREM  by Paul Milgrom, in The Journal of Mechanism and Institution Design 9, no. 1 (2024): 7-11.

ABSTRACT: In Kenneth Arrow’s last week of life at age 95, he reported that “I began my research career with an impossibility theorem. If I had time now, my last theorem would be an impossibility theorem about social choice for environmental policy.” This paper completes the formalization, proof, and discussion of the theorem that Arrow then described. 

#########

Some earlier tributes to Ken:

Tuesday, February 21, 2017

Ken Arrow (1921-2017)

Saturday, September 23, 2017

Tributes to Ken Arrow

Monday, October 9, 2017

Celebration of Ken Arrow at Stanford

Friday, October 13, 2017

Pictures from the celebration of Ken Arrow

 

 

 

 

Redesigning the Economics major(s) at Stanford

 At many universities, the undergraduate major in Economics serves several distinct groups of students.  There are students who might want to go on to graduate work in economics, students seeking jobs in business or government or NGOs that require analytical skills, students who would have chosen a Business major if one were available, and students who want to be capable of understanding articles in the WSJ and being thoughtful about public policy.  In general, departments have adopted the view that an education in econ is good for all these groups, from future economists to future educated citizens.

But not all of those groups are equally well served by the same set of required courses.  So Stanford is now offering two different undergrad degrees in Economics.

 Stanford Report has the story

"Economics major expanded to better suit different career paths.
In addition to a Bachelor of Arts degree, the Department of Economics now offers a Bachelor of Science and certificates in several subfields."

 "The Department of Economics in the School of Humanities and Sciences has begun offering students the option of pursuing a Bachelor of Science degree, and the Bachelor of Arts program has been modified. Also, majors can now fine-tune their interests by pursuing certificates in business economics, environmental economics, data science, and finance.  

"One of the most popular majors at Stanford, economics serves a range of students, from those seeking social science insights into decision-making to those seeking specialized quantitative – or “quant” – skills for numbers-heavy careers in finance.

...

“We don’t need them to get through MATH 51 unless they are going in the direction of the more ‘quant’ jobs – in which case we actually want them to have more math,” said Bernheim, who is also director of undergraduate studies in the department. “We decided we could serve both groups better by changing the prerequisite for the BA degree.” 

"Consequently, the new BS pathway’s core requirements, which are more quantitative than the BA’s, include MATH 115: Functions of a Real Variable; STATS 117: Theory of Probability; CS 106B: Programming Abstractions; and math-intensive economics courses on topics such as econometrics and game theory.

...

"Students on either degree path also can now obtain certificates in four areas: business economics, data science, environmental economics, and finance. The certificates allow students to narrow their focus within the major and signal to prospective employers that they’ve learned specific skill sets."

A 40 year old proof about top trading cycles is corrected (by two Berkeley grad students)

 Science (and math) can be self-correcting, sometimes slowly.  Here's an article that corrects the first proof that the top trading cycles algorithm is group strategy proof.  That's a true result, with multiple subsequent proofs.  But apparently the first proof presented wasn't the best one.  That's good to know.

One reason this may have taken a long time to spot is that the result is correct, and that there are subsequent proofs that connect the result to properties of other mechanisms.  

Will Sandholtz and Andrew Tai, the authors, did this work as Ph.D. students at UC Berkeley. (good for them!)

Group incentive compatibility in a market with indivisible goods: A comment  by Will Sandholtz and Andrew Tai

"Highlights

• Bird (1984), first to show top trading cycles is group strategy-proof, has errors.

•We present corrected results and proofs.

•We present a novel proof of strong group strategy-proofness without non-bossiness.

"Abstract: We note that the proofs of Bird (1984), the first to show group strategy-proofness of top trading cycles (TTC), require correction. We provide a counterexample to a critical claim and present corrected proofs in the spirit of the originals. We also present a novel proof of strong group strategy-proofness using the corrected results."

Remembering Jim Simons

 Here's the memorial page from the Simons Institute for the Theory of Computing

Remembering Jim Simons

HT: Vijay Vazirani

###########

Earlier:

Saturday, May 11, 2024

Jim Simons (1938-2024)

Jim Simons (1938-2024)

 Jim Simons, the great investor and philanthropist of math and computer science, died yesterday.

Here's the announcement from the Simons Foundation.

Simons Foundation Co-Founder, Mathematician and Investor Jim Simons Dies at 86

And here's the NYT:

Jim Simons, Math Genius Who Conquered Wall Street, Dies at 86. Using advanced computers, he went from M.I.T. professor to multibillionaire. His Medallion fund had 66 percent average annual returns for decades.

Top Trading Cycles (TTC) and the 50th anniversary of the Journal of Mathematical Economics

 This year marks the 50th anniversary of the Journal of Mathematical Economics, and also of the Top Trading Cycles (TTC) algorithm that was introduced in Volume 1, number 1 of the journal, in the paper by

Shapley, Lloyd, and Herbert Scarf. "On cores and indivisibility." Journal of mathematical economics 1, no. 1 (1974): 23-37. 

TTC was further analyzed in 

Roth, Alvin E., and Andrew Postlewaite. "Weak versus strong domination in a market with indivisible goods." Journal of Mathematical Economics 4, no. 2 (1977): 131-137.

Now the JME is assembling a 50th anniversary collection of papers surveying some of the resulting literatures, with some papers posted online ahead of publication. Here's what they had as of yesterday, including an article on Top Trading Cycles, by Morrill and Roth, and one on Housing markets since Shapley and Scarf, by Afacan, Hu, and Li:

JME’s 50th Anniversary Literature  Edited by Andres Carvajal and Felix Kübler

1. Research articleFull text access

   Top trading cycles

   Thayer Morrill, Alvin E. Roth

   In Press, Journal Pre-proof, Available online 16 April 2024

   Article 102984

   View PDF

2. select article Bubble economics

   Research articleOpen access

   Bubble economics

   Tomohiro Hirano, Alexis Akira Toda

   April 2024

   Article 102944

   View PDF

3. select article Stable outcomes in simple cooperative games

   Research articleFull text access

   Stable outcomes in simple cooperative games

   Gabrielle Demange

   April 2024

   Article 102960

   View PDF

4. select article Fifty years of mathematical growth theory: Classical topics and new trends

   Research articleFull text access

   Fifty years of mathematical growth theory: Classical topics and new trends

   Emmanuelle Augeraud-Veron, Raouf Boucekkine, Fausto Gozzi, Alain Venditti, Benteng Zou

   April 2024

   Article 102966

   View PDF

5. select article Housing markets since Shapley and Scarf

   Research articleFull text access

   Housing markets since Shapley and Scarf

   Mustafa Oğuz Afacan, Gaoji Hu, Jiangtao Li

   April 2024

   Article 102967

   View PDF

##########

At least one of the papers in the (virtual) special issue is already published, I gather that some will be in the June issue:

Monday, March 4, 2024

50th anniversary of Shapley and Scarf (1974), and of the Journal of Mathematical Economics

Is algebra for 8th graders repugnant because it leads to calculus?

 The tide is shifting back towards teaching algebra in San Francisco middle schools.

The WSJ has the story:

In the Battle Over Early Algebra, Parents Are Winning. After schools prevented students from taking algebra before high school to reduce racial inequities, parents in San Francisco and Cambridge, Mass., pushed back. By Sara Randazzo

"San Francisco’s public school district set off a yearslong fight with parents when it decided to prevent students from taking algebra until high school, an attempt to combat racial inequities in math by waiting until more students were ready.

"Parents in favor of letting students start in middle school launched petitions, a ballot measure and a lawsuit, sparring with school officials over questions of equity and privilege.

"Now, it appears the parents who are pushing for eighth-grade algebra are winning.

"The San Francisco Unified School District said Friday that it would reverse its decade-old policy, a move that comes after a similar recent change by the school system in Cambridge, Mass., home to Harvard University.

"When to start students on algebra is a contentious topic because the subject is the gateway to a series of math classes culminating in calculus, which many see as crucial for STEM careers and selective college admissions. Students aspiring to take calculus before graduating have traditionally begun this sequence in eighth grade.

“A lot of the attention to eighth-grade algebra is based upon the feeling that that’s the point at which the race is won,” said Thurston Domina, an education professor at the University of North Carolina.

"In San Francisco, the district long argued that the policy of restricting algebra to high school wasn’t done to hold children back, but to reduce the inequities that result from sorting students by math ability at too young an age.

...

"Nationally, 48% of Asian students reach calculus before graduation, compared with 22% of white students, 14% of Latino students and 11% of Black students.

...

"Last year, California passed a new math framework that de-emphasizes early algebra access. Earlier drafts discouraged any eighth-grade algebra, citing the San Francisco school district’s policy as a more equitable approach. After hundreds of public comments and rounds of revisions, the final framework says students should accelerate in math if they are ready."

#########

I'm reminded of the wisecrack that says that fundamentalists disapprove of pre-marital sex because it leads to dancing, and they don't like dancing.

In this case, education reformers disapproved of 8th grade algebra because it leads to calculus...

Simple Proofs of Important Results in Market Design-- (video of my talk at Berkeley's Simons Institute)

Here's a video of the talk I gave on Friday at the Simons Institute, on simple proofs of important theorems about matching, that have had impact on practical market design.

Introductory workshops to the Mathematics and Computer Science of Market and Mechanism Design semester at Berkeley MSRI

 The semester of Mathematics and Computer Science of Market and Mechanism Design August 21, 2023 to December 20, 2023 at Berkeley will lead off with two introductory sessions:

Connections Workshop: Mathematics and Computer Science of Market and Mechanism Design  September 07, 2023 - September 08, 2023

REGISTRATION DEADLINE: AUGUST 18, 2023

TO APPLY FOR FUNDING YOU MUST REGISTER BY: MAY 17, 2023

Organizers Michal Feldman (Tel-Aviv University), LEAD Nicole Immorlica (Microsoft Research)

"The Connections Workshop will consist of invited talks from leading researchers at all career stages in the field of market design.  Particular attention will be paid to real-world applications.  There will also be an AMA focused on career paths with highly visible individuals in the field, and a social event intended to help workshop attendees network with each other."

and

Introductory Workshop: Mathematics and Computer Science of Market and Mechanism Design  September 11, 2023 - September 15, 2023

REGISTRATION DEADLINE: AUGUST 25, 2023  TO APPLY FOR FUNDING YOU MUST REGISTER BY: MAY 21, 2023  

Organizers Scott Kominers (Harvard Business School), Paul Milgrom (Stanford University), Alvin Roth (Stanford University), Eva Tardos (Cornell University)

"The workshop  will  open  with  overview/perspective  talks  on  algorithmic  game  theory  and  the theory and practice of market design; the afternoon will feature a panel on active research areas in the field (again, at the overview level). The next 2 days will consist of introductory mini-course and tutorials, on topics such as game theory, matching, auctions, and mechanism design. The following day will focus on applicable tools and technology, such as lattice theory, limit methods, continuous optimization, and extremal graph theory. The workshop will conclude with a panel discussion on major open problems."

Earlier announcement:

Tuesday, November 8, 2022

Mathematics and Computer Science of Market and Mechanism Design, at Berkeley MSRI, August 21-December 20, 2023 (applications open)

Market and Mechanism Design, at Berkeley's Simons Laufer Mathematical Sciences Institute, application deadline is Dec. 1

 Here's a new flyer for the 

Mathematics and Computer Science of Market and Mechanism Design, at Berkeley MSRI, August 21-December 20, 2023

Applications are due by December 1.

Notice also that MSRI has new funding and a new name, the Simons Laufer Mathematical Sciences Institute.

Mathematics and Computer Science of Market and Mechanism Design, at Berkeley MSRI, August 21-December 20, 2023 (applications open)

 Apply now to join a semester of interdisciplinary workshops on market and mechanism design, from the point of view of mathematicians, computer scientists, and economists.

Mathematicsand Computer Science of Market and Mechanism Design at the Mathematical Sciences Research Institute in Berkeley, California, August 21, 2023 to December 20, 2023

 Seeking applications for Research Members and Postdoctoral Fellows:

• Research Members are scholars in economics, computer science, operations research, mathematics, or related fields who have a PhD at the time of application and will be in residence for at least 30 consecutive days of the program.
• Postdoctoral Fellows are scholars in those fields who received their PhD on or after August 31, 2018, and will be in residence for the entire program.

Apply here by December 1, 2022: https://www.msri.org/web/msri/scientific/member-application

 Program Summary:

In recent years, economists and computer scientists have collaborated with mathematicians, operations research experts, and practitioners to improve the design and operations of real-world marketplaces. Such work relies on robust feedback between theory and practice, inspiring new mathematics closely linked – and directly applicable – to market and mechanism design questions. This cross-disciplinary program seeks to expand the domains in which existing market design solutions can be applied; address foundational questions regarding our ways of developing and evaluating mechanisms; and build useful analytic frameworks for applying theory to practical marketplace design.

 https://www.msri.org/programs/333

 Program Organizers:

Michal Feldman (Tel-Aviv University); Nicole Immorlica (Microsoft Research); Scott Kominers (Harvard Business School); Shengwu Li (Harvard University); Paul Milgrom (Stanford University); Alvin Roth (Stanford University); Tim Roughgarden (Columbia University); Eva Tardos (Cornell University)

 About MSRI:

Acknowledged as the premier center for collaborative mathematical research, MSRI  organizes and hosts semester-length programs that become the leading edge in that field of study. Mathematicians worldwide come to the Institute to engage in the research of classical fundamental mathematics, modern applied mathematics, statistics, computer science and other mathematical sciences.

 Questions? See attached flyer, or reach out to mcsorgs@msri.org

**********

This could be a nice way to spend a semester--apply now (MSRI loves company:)

Mark Braverman wins Abacus Medal (formerly Nevanlinna Prize)

 Mark Braverman, a computer scientist whose work touches on mechanism design, has won the Abacus Medal of the International Mathematical Union.

Here are some links: citation, video, write-up, CV/publications, proceedings, interview, Plus magazine! article

Readers of this blog may be interested in these papers:

Optimization-friendly generic mechanisms without money

Mark Braverman

"The goal of this paper is to develop a generic framework for converting modern optimization algorithms into mechanisms where inputs come from self-interested agents. We focus on aggregating preferences from n players in a context without money. Special cases of this setting include voting, allocation of items by lottery, and matching. Our key technical contribution is a new meta-algorithm we call \apex (Adaptive Pricing Equalizing Externalities). The framework is sufficiently general to be combined with any optimization algorithm that is based on local search. We outline an agenda for studying the algorithm's properties and its applications. As a special case of applying the framework to the problem of one-sided assignment with lotteries, we obtain a strengthening of the 1979 result by Hylland and Zeckhauser on allocation via a competitive equilibrium from equal incomes (CEEI). The [HZ79] result posits that there is a (fractional) allocation and a set of item prices such that the allocation is a competitive equilibrium given prices. We further show that there is always a reweighing of the players' utility values such that running unit-demand VCG with reweighed utilities leads to a HZ-equilibrium prices. Interestingly, not all HZ competitive equilibria come from VCG prices. As part of our proof, we re-prove the [HZ79] result using only Brouwer's fixed point theorem (and not the more general Kakutani's theorem). This may be of independent interest."

**********

Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations by Itai Ashlagi , Mark Braverman, Yash Kanoria , Peng Shi , Management Science, 2020, 66(5), pp.2163-2193.  https://doi.org/10.1287/mnsc.2018.3265

Abstract: "We study how to reduce congestion in two-sided matching markets with private preferences. We measure congestion by the number of bits of information that agents must (i) learn about their own preferences, and (ii) communicate with others before obtaining their final match. Previous results suggest that a high level of congestion is inevitable under arbitrary preferences before the market can clear with a stable matching. We show that when the unobservable component of agent preferences satisfies certain natural assumptions, it is possible to recommend potential matches and encourage informative signals such that the market reaches a stable matching with a low level of congestion. Moreover, under our proposed approach, agents have negligible incentive to leave the marketplace or to look beyond the set of recommended partners. The intuitive idea is to only recommend partners with whom there is a nonnegligible chance that the agent will both like them and be liked by them. The recommendations are based on both the observable component of preferences and signals sent by agents on the other side that indicate interest."

 ***********

Update: from Quanta.

The Scientist Who Developed a New Way to Understand Communication. Mark Braverman has spent his career translating thorny problems into the language of information complexity.  by Stephen Ornes

"While Braverman continues to guide the theory as his former students and postdocs push it forward, the bulk of his work is done. Now his interests are more focused on a new field called mechanism design, which uses the mathematical approaches of economics and game theory. "

Celebrating Ramanujan's birthday (with some math quotes)

 Yesterday, 22 December, is celebrated every year as National Mathematics Day in India, in honor of the 1887 birthday of the great Indian mathematician Ramanujan.

Here are some quotes about math in honor of the day, in the Indian periodical RepublicWorld.com

Mathematics Day: Here are some of the most inspirational Happy Mathematics Day quotes on Ramanujan's birthday to honour this special occasion.  By Vageesha Taluja

Not included in that collection of quotes is this one, attributed in Wikipedia to Ramanujan himself: "An equation for me has no meaning unless it expresses a thought of God."

I was pleasantly surprised to see included something much more prosaic that I  was quoted as saying, in a 2010 profile in Forbes magazine called Un-Freakonomics, by Susan Adams: 

"I've always been interested in using mathematics to make the world work better." -Alvin E. Roth