Recent content in Nick Arnosti on b
In the past year or two, I have gotten more into running. For whatever reason, I have taken to tracking my distance and pace primarily in kilometers. But if I tell my wife I went for a 11 km run, that’s meaningless to her. So it’s useful to be able to convert between kilometers and miles. Of course, there’s a well-defined way to do this. 1 mile \(\approx\) 1.61 km, and 1 km \(\approx\) 0.
Earlier this month, I had a conversation with a reporter for the Toronto Globe and Mail, Canada’s newspaper of record. She wanted to talk to me about campsite reservation systems. She came prepared with a lot of different ideas to discuss, and we had a very enjoyable conversation. A few quotes from this conversation appear in her article, which focuses primarily on the concern that AI could make…
Best Paper Stochastic optimization and coupling. Best Paper with a student lead author: Personalized Recommendations without Inducing Congestion: Mitigating Disparities in the NYC High School Match. Presenter (Erica) was employed at NYCPS over the last year (insider access). Goal is personalized recommendations of students to high-performing schools where they are likely to be admitted. Exemplary…
I just attended MATCHUP 2026 in Paris. There, I learned of the paper “Matching with Attributes” by Aytek Erdil and Battal Dogan (also accepted to EC 2026). This paper gives a creative and satisfying resolution to a longstanding research question: in many-to-one matching with contracts (for concreteness of language, imagine matching doctors to hospitals), what are minimal conditions on hospital…
This post collects a few papers on dynamic matching. Gupta gives a sum-of-squares greedy algorithm for multiway matching with bounded regret (Gupta 2024). Wei, Xu, and Yu propose a primal-dual policy for multi-way dynamic matching (Wei, Xu, and Yu 2023). Dynamic Matching Without Departures Kerimov, Ashlagi, and Gurvich have two papers which consider a very similar model, in which agents do not…
In a previous post, I looked at scores from the National Assessment of Educational Progress (NAEP), which is a set of tests administered every two years. In that post, I focused on national trends, which show that reading and math scores are falling – especially among the lowest-performing students. I pointed out that while this is important to know, it’s not particularly actionable. In this post,…
As an educator, I hear it all the time. Students are less prepared than they used to be. Curriculum is less rigorous. But is there any data to back this up? As it turns out, there is! The National Assessment of Educational Progress (NAEP) is a set of tests given every two years to 4th, 8th and 12th graders across the country.1 These tests are sometimes called “The Nation’s Report Card,” and the…
As an educator, I hear it all the time. Students are less prepared than they used to be. Curriculum is less rigorous. But is there any data to back this up? As it turns out, there is! In a previous post, I took a look at nationwide reading and math scores for 4th and 8th graders. These scores are falling, especially among the bottom quartile of students. This post will look at a report from the…
Kelsey Piper
Kelsey Piper
Yesterday, I attended a presentation where I learned various facts about the undergraduate student body in the College of Science and Engineering at the University of Minnesota. Here are a few that seemed worth knowing, presented in quiz form. Questions. Origin. What percentage of the CSE entering class comes from the Twin Cities metro area? From Minnesota? From the United States? Gender. What…
In my previous post, I described the lottery for the Western States Endurance Run, which uses a weighted lottery to allocate \(m\) identical prizes among \(n\) participants. Each participant \(i\) has \(t_i\) tickets, and tickets are drawn in a uniformly random order until \(m\) distinct participants have been selected. The point of the previous post was that it’s not so easy to calculate the…
Running Marathons and Ultramarathons This year, I ran my first marathon! The Twin Cities Marathon passes 2 blocks from my house (we are at mile 22). I enjoyed the training and race day, and ended the race feeling surprisingly good. It turns out, some people enjoy running further than a marathon! The most famous ultramarathon in the United States is the Western States Endurance Run, which covers…
Saint Paul just approved an increase in property taxes to provide an additional $37 million per year for public schools. This is approximately $1,100 for each student in the district. This made me wonder, what is the current budget? How does this compare to historical budgets, and to budgets of other nearby districts? And how is this money being spent? I knew almost nothing about the Saint Paul…
A key idea from calculus – used frequently in optimization – is that we can use linear functions to locally approximate complicated non-linear functions. This post will illustrate the effectiveness of this approach for a very specific function, the square root (maintaining some continuity with my previous post). Estimating Square Roots to the Nearest Integer Let’s start with the following goal:…
The number \(\sqrt{2}\) is famously irrational: it cannot be expressed as a fraction (ratio of two integers). However, we can use fractions to approximate it. Here is one simple algorithm to do so, which uses only elementary operations. Let our initial estimate be \(x_0 = 1\). From there, we generate the next estimate using the following procedure: Add one to the current estimate. Invert the…
Ashlagi, Kanoria and Leshno Azevedo and Leshno This is really from my paper “Lottery Design for School Choice.” (Do a separate post for Probabilistic Predictions in Random Matching Markets.) Note that I have a chip on my shoulder. Without my work, this would be a dissertation. With my work, it becomes a class exercise for a PhD student. (Reference “which markets lead to stark effect of…
In
Ashlagi, Kanoria and Leshno Azevedo and Leshno This is really from my paper “Lottery Design for School Choice.” (Do a separate post for Probabilistic Predictions in Random Matching Markets.) Note that I have a chip on my shoulder. Without my work, this would be a dissertation. With my work, it becomes a class exercise for a PhD student. (Reference “which markets lead to stark effect of…
In
My wife is a middle-school math teacher, and this spring, she is teaching geometry to some of her students. This gave me a chance to learn some geometry! Her upcoming unit is different notions of the center of a triangle. She gave me a quick primer on a few definitions, and then I went to think about things on my own. This post is what resulted from that thinking, and is not endorsed for use on…
I recently wrote about a flawed analysis of the hot hand in shooting data, which revealed some potentially counter-intuitive phenomena involving coin flips. Continuing in that vein, here are some more fun facts about fair coin flips! Let’s start with an exercise for the reader. Suppose we repeatedly flip a fair coin. Which of the following statements are correct? There is a 50% chance that the…
Although I am not as invested in professional sports as I used to be, I still enjoy following along, and sometimes get a chance to put some math skills to use. This post will analyze a high-profile decision by Lions coach Dan Campbell at the end of their game against the Packers. The situation: tie game, Lions have the ball on the Packers’ 22 yard line. It’s 4th and inches with 43 seconds left,…
Harry and Tom decide to play a game. They flip a fair coin \(n\) times. Each time the coin comes up heads, there is an opportunity to score. Harry scores a point if the next flip is heads, and Tom scores if the next flip is tails. A player wins if after all \(n\) tosses, their score is higher than their opponents. Who is more likely to win? A natural instinct is that because each flip is fair (and…
I recently attended MATCH-UP 2024 at Oxford, where I saw Julius Goedde present the paper “Pricing in markets without money: Theory and evidence from home exchanges”. I found it quite interesting! The paper considers platforms that enable home exchange – examples include Trade to Travel, People Like Us, and Home Exchange. The idea behind all of these sites is, you let strangers stay in your home,…
This post is about using data to detect bias in systems that allocate public resources. For example, in the US there are approximately 90,000 people waiting for a kidney transplant. When kidneys from a deceased donor become available, the Organ Procurement and Optimization Network (OPTN) must decide which of these waiting patients to make offers to. As another example, in Hennepin County there are…
Suppose you are playing Bingo. The caller reads a number, and someone in the room shouts out, “BINGO!” Are they more likely to have a complete row, or a complete column? Surprisingly, the answer is a complete row. This is has been referred to as The Bingo Paradox, and I will explore it in this post. Rules of Bingo Let’s start with the rules of Bingo. Each Bingo card is a 5x5 square.
I’m enjoying EC this week, and had two thoughts. First, interesting math problems are often buried deep in a paper that is nominally on another topic. Second, there are lots of bright people who might know how to solve these math problems, but never see them! Inspired by these thoughts, I am sharing one open problem from my work Lotteries for Shared Experiences with Carlos Bonet, which involves…
Mortgages are confusing! Suppose you wish to borrow money, and pay it back in monthly intallments using a fixed rate mortgage. How much will your monthly payment be? How much will you pay in interest over the lifetime of the loan? If you refinance or move partway through the mortgage, how large will your remaining balance be? Even very mathematically inclined people like me often struggle to have…
Today, my wife and I dropped my daughter off with grandma, so that we could have a “date morning.” My mom asked what our plans were. We said that we were going to a cafe, order some drinks, and talk about math. And that is exactly what we did. It was great. (I love my wife.) More specifically, I taught Amanda about linear programming, in a way that I wish I had been taught.
Note: this post is closely related to my video The Virtues of Random Priority and blog post Famous Open Question Resolved… since 2014?!?!, although it is written to be self-contained. Motivation When giving away resources, two natural goals are to allocate these resources efficiently and fairly. Achieving these goals requires asking people about their preferences, so a third goal is to allocate in…
I recently got the opportunity to play the game “Great Zimbabwe.” I found it to be a very interesting game, with several mechanics that I hadn’t really seen in other games. I don’t think it will ever be a top game for me (for reasons outlined below), but I did find myself thinking about it for days after playing, so I figured I’d share my thoughts. An important caveat to all of the below is that I…
One of the most elegant matching algorthms out there is the Top Trading Cycles algorithm, introduced by Shapley and Scarf in their 1974 paper “On cores and indivisibility”, and attributed to David Gale. This algorithm finds the unique core allocation, and its outcome is therefore individually rational and pareto efficient. In addition, this algorithm makes truth-telling a dominant strategy for all…
Introduction There have been a number of attention-grabbing advancements in the AI space recently, including large language models (i.e. Chat GPT) and image generation (i.e. Dall-E). I think that these developments are going to end up being very significant. While I am not a very experienced user of these services, I am trying to give myself more practice with them, to better understand their…
Note: this post assumes knowledge of the definition of stability in two-sided matching markets. If you aren’t familiar with this definition, you should first learn about that. If you are familiar with the definition of stability, please consider providing a public good by amending the Wikipedia page on the stable marriage problem. When writing this post, I noticed that this page assumes a balanced…
Motivation Suppose I have a set of objects to give away. What goals should I have? Of course, the answer depends on the setting, but two natural goals are efficiency and fairness. If I don’t know people’s preferences, I also need to design a system that incentivizes people to tell me their true preferences. Skipping over the mathematical definitions of efficiency, fairness, and truthfulness (more…
In this post, I want to share a paper that I learned about at EC 2023 in July: Feature Based Dynamic Matching, by Yilun Chen, Yash Kanoria, Akshit Kumar, and Wenxin Zhang. After hearing this work presented, I immediately told my wife about it on a walk in Saint James’ park. No, my wife is not an academic, but the paper is just that great (and she is even greater!
I recently read the working paper “Design on Matroids” by Isa Hafalir, Fuhito Kojima, Bumin Yenmez, and Koji Yokote. There has been a surge of recent papers looking at matching with distributional constraints. I am trying to stay abreast of this literature, so I was excited to take a look. Disclaimer. This is part of a series of posts in which I discuss others’ work. My goal with these posts is to…
I recently read the working paper “Efficient Market Design” by Isa Hafalir, Fuhito Kojima, and Bumin Yenmez. There has been a surge of recent papers looking at matching with distributional constraints. I am trying to stay abreast of this literature, so I was excited to take a look. In this post, I briefly summarize the paper, and then offer some thoughts on the applicability of the model.…
Motivation One recent trend in hiring is for companies to use machine learning models to sort through piles of job applications. This has the obvious advantage (to the company) of reducing the number of hours that recruiters need to spend reading resumes. Algorithmic assessment may also avoid certain biases that human recruiters have, although it is likely to be biased in other ways. Noise or bias…
One of the delights of being married to a teacher is vacationing together over the summer. One of the delights of being married to an adventurous teacher is vacationing in Albania. And one of the delights of being married to an adventurous math teacher is talking about math while vacationing in Albania. This post is inspired by discussions during our recent trip. It uses dynamic programming and…
New York City faces a lawsuit alleging that its “Community Preference” policy creates a disparate racial impact. In previous videos on this topic, examined the plaintiff’s and defendant’s analysis. In this video, I conduct my own analysis. The slides accompanying this lecture are available here. My main conclusion is that the current implementation of the Community Preference policy has large…
The New York Post recently reported on a “lottery glitch” in the application process for New York City Public Schools. Basically, parents could see their child’s lottery number, and could get a new lottery number by cancelling and re-starting their application. This creates an obvious issue, as applications can be repeatedly canceled until the child receives a good lottery number. What I want to…
Today I’m writing about the allocation of H2B visas. This can be thought of as a sister post to my previous writing on H1B visas, although the technical content is quite different. I describe how the H2B allocation procedure evolved from first-come first-served to a lottery. I examine the rules of the current lottery, and propose and analyze several alternative designs. I also look into recent…
New York City faces a lawsuit alleging that its “Community Preference” policy creates a disparate racial impact. In a previous video, I examined the plaintiffs’ analysis. In this video, I look at the city’s rebuttal, presented by Bernard Siskin. While Siskin does a good job of highlighting flaws in the plaintiffs’ analysis, his own report uses uninformative outcome measures and some questionable…
New York City faces a lawsuit alleging that its “Community Preference” policy creates a disparate racial impact. In this video, I explain why the analysis conducted by the plaintiffs’ “expert witness” does not address this claim. The slides accompanying this lecture are available here.
I’ve decided to try a video blog! My first video is on an amazing and fundamental open question, and is intended for a general audience. I’d love to hear any thoughts you have on this new format! Note: Since this video was created, I have learned of a paper by Aytek Erdil which resolves this question for a particular definition of truthfulness. The question remains open if we use a slightly…
The 10th Mountain Division Huts in Colorado are amazing. I’ve done two winter hut trips, which involve backcountry skiing through beautiful terrain, and arriving at lovely cabins stocked with lots of firewood and equipped with all the cooking gear you can imagine. These photos from three years ago make me want to return immediately: . I know what you’re wondering: how do I book my own trip to this…
I was recently looking at the page of the Minnesota Fringe Festival. This is an 10+ day event where artists can perform original work. However, there are not enough spots to accommodate all interested artists. Rather than raising fees or using auditions, they have decided to select artists by lottery! Of course, I had to read more. While selecting by lottery sounds simple, there are often many…
Unlike most of my posts, this one is very personal. In it, I reflect on my research journey, and insights about the research process that I’ve gained over the past five years. Three Components of Research Success Many PhD students suffer from imposter syndrome, and wonder whether they are “good enough” to belong. I never had this problem. Coming out of my PhD, I felt confident that I was good at…