Showing posts with label mathematics. Show all posts
Showing posts with label mathematics. Show all posts

Monday, September 23, 2024

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."

Sunday, August 4, 2024

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


Saturday, May 11, 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.


Thursday, April 18, 2024

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. Top trading cycles

    In Press, Journal Pre-proof, Available online 16 April 2024
    Article 102984
    View PDF
  2. Bubble economics

    April 2024
    Article 102944
    View PDF
  3. Stable outcomes in simple cooperative games

    April 2024
    Article 102960
    View PDF
  4. Fifty years of mathematical growth theory: Classical topics and new trends

    April 2024
    Article 102966
    View PDF
  5. Housing markets since Shapley and Scarf

    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

Monday, February 12, 2024

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...

Monday, October 30, 2023

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.

Thursday, April 6, 2023

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

Tuesday, November 8, 2022

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, 2022https://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:)


Wednesday, July 6, 2022

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: citationvideowrite-upCV/publicationsproceedingsinterviewPlus magazine! article

Readers of this blog may be interested in these papers:

Optimization-friendly generic mechanisms without money

"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. "

Wednesday, December 23, 2020

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

Friday, August 3, 2018

Nevanlinna Prize winner Constantinos Daskalakis, and the Fields medalists (and one of the Fields medals)

Here's a video that touches on his work on computational complexity of Nash equilibria, and auctioning multiple items.



Here's some more on that from AFT, focusing as well on the Fields medalist Alessio Figalli

THE 2018 FIELDS MEDAL AND ITS SURPRISING CONNECTION TO ECONOMICS!



And here's more still, from Quanta:

2018 Fields Medal And Nevanlinna Prize Winners


And in case less is more, here's a short announcement from Science:
Five superstars win ‘math’s Nobel Prize’

And then there's this, from the prize ceremony in Rio...
Winner of top mathematics prize has medal stolen from him minutes later

Friday, October 21, 2011

Tomorrow, Oct 22 I'll be teaching NYC math teachers about stable matching and NYC school choice

Stable Matching with Application to School Choice with Al Roth

If you are a NYC high school or middle school math teacher you can register at the link above to attend a class I'll give on October 22, sponsored by Math for America, on the topic

"Stable Matching with Applications to School Choice"

Abstract: "Matching" is the name economists give to the ways we get the many things we choose in life that also have to choose us, from spouses to jobs to places in NYC high schools. Some simple models of matching will be discussed, along with some powerful organizing ideas, like whether a particular matching is stable or unstable. The session will include a detailed description of the current system of matching students with NYC high schools.

When: 10/22/11 9:30 AM EDT
Duration: 6 Hours 
Location: 160 5TH Avenue, 9th floor, Entrance on 21st between 5th and 6th
New York, NY, 10010
Type: General Public and All MfA
Register here

Monday, December 20, 2010

Mathematics and medicine: a cautionary tale

Mathematics is valuable in many areas of application, including medicine, but there are hazards to having doctors diagnose their own mathematical needs. A hilarious example was just brought to my attention; a well-cited medical paper that reinvents one of the first lessons of high school calculus (which the author goes on to name after himself):
A mathematical model for the determination of total area under glucose tolerance and other metabolic curves. by M M Tai, Diabetes Care February 1994 vol. 17 no. 2 152-154 .

Here's the abstract in its entirety:
"OBJECTIVE--To develop a mathematical model for the determination of total areas under curves from various metabolic studies. RESEARCH DESIGN AND METHODS--In Tai's Model, the total area under a curve is computed by dividing the area under the curve between two designated values on the X-axis (abscissas) into small segments (rectangles and triangles) whose areas can be accurately calculated from their respective geometrical formulas. The total sum of these individual areas thus represents the total area under the curve. Validity of the model is established by comparing total areas obtained from this model to these same areas obtained from graphic method (less than +/- 0.4%). Other formulas widely applied by researchers under- or overestimated total area under a metabolic curve by a great margin. RESULTS--Tai's model proves to be able to 1) determine total area under a curve with precision; 2) calculate area with varied shapes that may or may not intercept on one or both X/Y axes; 3) estimate total area under a curve plotted against varied time intervals (abscissas), whereas other formulas only allow the same time interval; and 4) compare total areas of metabolic curves produced by different studies. CONCLUSIONS--The Tai model allows flexibility in experimental conditions, which means, in the case of the glucose-response curve, samples can be taken with differing time intervals and total area under the curve can still be determined with precision. "

Google Scholar reveals that this paper is Cited by 137, most of which appear to be un-ironic.

Incidentally, while scholars like to properly reference things, who knows if the world would be better if the author had cited a calculus textbook, and pointed out that this method had been well known for hundreds of years. Very likely the medical journal would have declined to publish it if they had realized it wasn't new. (It says something about the difficulty a medical journal faces in evaluating mathematical ideas that none of the referees recognized this.) And the citations the paper has received suggest that at least to some subsequent researchers, this elementary calculus lesson, delivered in a medical journal, filled a gap in their education and proved useful. On the other hand, if the paper had instead pointed out that there is lots of widely available software to do numerical integration, it might have been even more useful to docs who needed to find areas under curves.

One of the delights of interdisciplinary work is how fruitful it can be. This is particularly true in market design, which almost always involves work between economists and experts in other things who are  directly involved in some market.

One of the frustrations of interdisciplinary work is that it involves translation between different cultures. For example, parts of market design are fairly mathematical, or involve ideas from economics (e.g. about incentives) that may be unfamiliar to non-economists.

My work on kidney exchange has had more than its share of both the delights and the frustrations, in part because the non-economist experts involved--kidney surgeons--are so very expert at what they do. I've had the good fortune to be part of teams of market designers and surgeons who work really well together.

But the translation barrier to the rest of the medical profession is formidable, particularly because matching for kidney exchange is quite mathematical, and doctors are mostly selected for their talents in other things. This makes for great complementarities when you find the right docs, but it's always hard for the medical journals to evaluate contributions that have an element of mathematics, and things can go badly wrong when a doctor overestimates the breadth of his competency, which is an occupational hazard for people whose daily work involves giving advice to patients whose lives depend on it.

HT: Assaf Romm