First Date: Singapore's government dating app

The government of Singapore is rolling out a dating site, initially as "A pilot for public officers only."  It infers preferences from questionnaire responses, and uses the deferred acceptance algorithm to produce one match per participant in each match run.

Here it is: FirstDate.
"Start something real.
An initiative to support singles aged 21-35 in their dating journey, verified using Singpass."
"Find your match.  Applications close on 05 Oct 23:59" 

"Swipe fatigue ends here. Receive one match at a time, so you can focus on building a thoughtful connection.

"Designed with your privacy in mind. Only your match sees your profile, and you decide if your contact details are shared. 

...

"What is FirstDate?
"FirstDate started with a question among a group of GovTech officers: does having more potential matches necessarily make it easier to find a suitable match?

"The team shared an interest in exploring some of the challenges people can face when meeting someone new. They wondered whether a different approach that places greater emphasis on compatibility through values and preferences, and offers fewer matches at a time, could give users more space to consider each introduction and decide whether they would like to take the next step. They explored the idea at GovTech Singapore's annual {build} hackathon, where officers develop and test new ideas.

"That idea became FirstDate, a ground-up pilot initiative currently being tested across Public Service.


"How does the matching work?
FirstDate uses your questionnaire responses, including your interests, habits, values and preferences, to understand what you're looking for in a potential partner.

"It then applies the Gale-Shapley Stable Marriage algorithm, an established mathematical approach that generates pairings based on participants' preferences to recommend matches based on compatibility."

#########

Here's some  coverage from Singapore Samizdat:

How Singapore’s government-run dating service works, and why it won’t solve the nation’s dating woes
Here are the 30+ questions in the matchmaking tool that Singapore is deploying to solve the incel problem. 

"Three years after the demise of the Social Development Network, it looks like a new government-run matchmaker is back on the cards for Singapore.

Earlier this month, a pilot progamme by GovTech called FirstDate was announced, with government workers set to be the first batch of daters. If this sounds familiar, that’s because I was the first to report on GovTech testing the waters with this idea all the way back in April for The Straits Times."

#######

Financial Times,
Singapore taps Nobel-winning formula for government dating app 
 

Algorithmic Collusion Without Threats

 Quanta magazine reports on a recent paper on algorithmic collusion (in which a big class of "dumb" strategies can settle on high prices):

The Game Theory of How Algorithms Can Drive Up Prices
Recent findings reveal that even simple pricing algorithms can make things more expensive  by Ben Brubaker 

" how can regulators ensure that algorithms set fair prices? Their traditional approach won’t work, as it relies on finding explicit collusion. “The algorithms definitely are not having drinks with each other,” said Aaron Roth(opens a new tab), a computer scientist at the University of Pennsylvania.

...

" if you want to guarantee fair prices, why not just require sellers to use algorithms that are inherently incapable of expressing threats?

"In a recent paper(opens a new tab), Roth and four other computer scientists showed why this may not be enough. They proved that even seemingly benign algorithms that optimize for their own profit can sometimes yield bad outcomes for buyers. “You can still get high prices in ways that kind of look reasonable from the outside,” said Natalie Collina(opens a new tab), a graduate student working with Roth who co-authored the new study.

...

"“Without some notion of a threat or an agreement, it’s very hard for a regulator to come in and say, ‘These prices feel wrong,’” said Mallesh Pai(opens a new tab), an economist at Rice University. “That’s one reason why I think this paper is important.”

...

"So, what can regulators do? Roth admits he doesn’t have an answer. It wouldn’t make sense to ban no-swap-regret algorithms: If everyone uses one, prices will fall. But a simple nonresponsive strategy might be a natural choice for a seller on an online marketplace like Amazon, even if it carries the risk of regret.

“One way to have regret is just to be kind of dumb,” Roth said. “Historically, that hasn’t been illegal.”

#######

And here's the paper:

Algorithmic Collusion Without Threats 

Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron Roth, Juba Ziani

There has been substantial recent concern that pricing algorithms might learn to ``collude.'' Supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors who refuse to support high prices, and these strategies can be automatically learned. In fact, a standard economic intuition is that supra-competitive prices emerge from either the use of threats, or a failure of one party to optimize their payoff. Is this intuition correct? Would preventing threats in algorithmic decision-making prevent supra-competitive prices when sellers are optimizing for their own revenue? No. We show that supra-competitive prices can emerge even when both players are using algorithms which do not encode threats, and which optimize for their own revenue. We study sequential pricing games in which a first mover deploys an algorithm and then a second mover optimizes within the resulting environment. We show that if the first mover deploys any algorithm with a no-regret guarantee, and then the second mover even approximately optimizes within this now static environment, monopoly-like prices arise. The result holds for any no-regret learning algorithm deployed by the first mover and for any pricing policy of the second mover that obtains them profit at least as high as a random pricing would -- and hence the result applies even when the second mover is optimizing only within a space of non-responsive pricing distributions which are incapable of encoding threats. In fact, there exists a set of strategies, neither of which explicitly encode threats that form a Nash equilibrium of the simultaneous pricing game in algorithm space, and lead to near monopoly prices. This suggests that the definition of ``algorithmic collusion'' may need to be expanded, to include strategies without explicitly encoded threats.

 

 

 

  

Stable Matching with Interviews, by Ashlagi, Chen, Roghani and Saberi

 Job applicants can now easily submit many job applications, and so interviewing applicants, which is time consuming, has become a major source of congestion in many labor markets.  But even in labor markets that use a clearinghouse to process offers and acceptances (like the market for medical residents in the U.S., the NRMP match) interviews are often organized in a decentralized manner. Here's a paper that tackles the question of how to organize an interview match, under some assumptions about what kind of information is obtained in interviews.  Two approaches are considered: an 'adaptive' algorithm that takes into account the results of previous interviews in assigning subsequent interviews, and a 'non-adaptive' algorithm that matches candidates to interviews before any interview results are known.

Stable Matching with Interviews, by Itai Ashlagi, Jiale Chen, Mohammad Roghani, and Amin Saberi (all at Stanford)

Abstract
"In several two-sided markets, including labor and dating, agents typically have limited information about their preferences prior to mutual interactions. This issue can result in matching frictions, as arising in the labor market for medical residencies, where high application rates are followed by a large number of interviews. Yet, the extensive literature on two-sided matching primarily focuses on models where agents know their preferences, leaving the interactions necessary for preference discovery largely overlooked. This paper studies this problem using an algorithmic approach, extending Gale-Shapley’s deferred acceptance to this context. Two algorithms are proposed. The first is an adaptive algorithm that expands upon GaleShapley’s deferred acceptance by incorporating interviews between applicants and positions. Similar to deferred acceptance, one side sequentially proposes to the other. However, the order of proposals is carefully chosen to ensure an interim stable matching is found. Furthermore, with high probability, the number of interviews conducted by each applicant or position is limited to O(log^2 n).
"In many seasonal markets, interactions occur more simultaneously, consisting of an initial interview phase followed by a clearing stage. We present a non-adaptive algorithm for generating a single stage set of in tiered random markets. The algorithm finds an interim stable matching in such markets while assigning no more than O(log^3 n) interviews to each applicant or position. "

Stable matching in Scientific American

 Here's a short article in Scientific American, describing the deferred acceptance algorithm and mentioning some uses for stable matching. (When I was a child, Scientific American opened a window on science for me...)

The ‘Stable Marriage Problem’ Solution Underpins Dating Apps and School Admissions. An elegant matchmaking algorithm called Gale-Shapley can find the best possible pairings for everybody.   By Max Springer

"Let’s create a reality dating show unlike any other in one key aspect. First, we’ll rent a villa on a tropical island. Then we’ll fly in five men and five women, each with their own (heterosexual) dating preferences. Our goal, though, is the exact opposite of the Love Island franchise: we want absolutely zero drama. Can we ensure that everyone pairs off with a partner and sticks with them, without jealousy rearing its ugly head?" 

########

Along the way they briefly quote these luminaries (in the order in which they appear): 

Vijay Vazirani, Jon Kleinberg, Utku Ünver, and Éva Tardos.

Gaming a bike sharing algorithm

 Jacob Leshno points out this NYT story. He writes "The gist of it is that Citi bike pays to deliver bikes to stations with shortages, and someone figured they could make money by creating artificial shortages."

The Hustlers Who Make $6,000 a Month by Gaming Citi Bikes. The bike-sharing program rewards users who help redistribute bikes around New York City. A few riders have figured out how to turn that into profit.  By Christopher Maag (Christopher Maag spent several days in Midtown Manhattan running behind Bike Angels.)

"By monitoring a map of stations on Lyft’s app, they noticed that the algorithm awards points on a sliding scale based on need. Removing a bike from a completely full station: up to four points. Docking at an empty station? That’s worth up to another four. People who move at least four bikes in a 24-hour period get all their points multiplied by a factor of three.

"Lyft pays 20 cents per point. Each ride generates a maximum of 24 points. In perfect conditions, a person on a 3X streak who relocates a bike from a full dock to a completely empty one can earn as much as $4.80 for a single ride.

...

"At 10 a.m. on a Tuesday last month, seven Bike Angels descended on the docking station at Broadway and 53rd Street, across from the Ed Sullivan Theater. Each rider used his own special blue key — a reward from Citi Bike — to unlock a bike. He rode it one block east, to Seventh Avenue. He docked, ran back to Broadway, unlocked another bike and made the trip again.

"By 10:14, the crew had created an algorithmically perfect situation: One station 100 percent full, a short block from another station 100 percent empty. The timing was crucial, because every 15 minutes, Lyft’s algorithm resets, assigning new point values to every bike move.

"The clock struck 10:15. The algorithm, mistaking this manufactured setup for a true emergency, offered the maximum incentive: $4.80 for every bike returned to the Ed Sullivan Theater. The men switched direction, running east and pedaling west."

Automated bidding in auctions

 Part of the future of market design (as artificial intelligence evolves from large language models to something more like general AI) will involve not only the design of marketplace rules, but also design of the marketplace participants.  So a good way to get some sense of that future is to look at parts of it that have already arrived.  And there are lots of algorithms already at work participating in high frequency markets.  Here's a paper surveying automated bidding on ad auctions, by a big group of authors at Google.

Auto-bidding and Auctions in Online Advertising: A Survey by Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R. Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, Jieming Mao, Aranyak Mehta, Vahab Mirrokni, Renato Paes Leme, Andres Perlroth, Georgios Piliouras, Jon Schneider, Ariel Schvartzman, Balasubramanian Sivan, Kelly Spendlove, Yifeng Teng, Di Wang, Hanrui Zhang, Mingfei Zhao, Wennan Zhu, and Song Zuo

Abstract: In this survey, we summarize recent developments in research fueled by the growing adoption of automated bidding strategies in online advertising. We explore the challenges and opportunities that have arisen as markets embrace this autobidding and cover a range of topics in this area, including bidding algorithms, equilibrium analysis and efficiency of common auction formats, and optimal auction design

The Matching Society by Melchior Simioni and Philippe Steiner

"If we put on the glasses of economic sociology, it appears ... that matching corresponds to a specific form of coordination close but distinct from both planning and the market."

That's a sentence that caught my eye (using Google translate) from the recent book by the French sociologists Melchior Simioni and Philippe Steiner

La société du matching (The Matching Society) 

Here's how the publisher's web page introduces it:

"The upheavals brought about by the irruption of matching technology, in all its dimensions, are updating major challenges in our societies. The matching society is not the future of our modern societies, it is its present. The ambition of this essay is to to understand what it changes in our lives.  

"At several decisive stages of our lives, we entrust our fate to algorithms that sort individuals according to a very singular pattern: we choose and we are chosen at the same time. Access to resources as essential as training (with Parcoursup or Affelnet), a romantic partner (Tinder, Meetic and so many others), certain care or a job depends on this technology.

"Unlike the market relationship, where paying is enough, or social benefits, which are paid as a matter of right, matching presupposes a new social relationship: we express our wishes according to the information at our disposal and it is on the basis of the data we provide that the selection is made.

"This principle profoundly changes our relationship with the collective. Because it forces us to tell the truth about ourselves, our hopes, our desires, it accelerates the advent of a singularist society."

########

I've had occasion to blog about the work of Professor Steiner before:

Friday, August 12, 2022

Are sociology and economics coming closer together? Philippe Steiner in Acta Oeconomica

Monday, November 30, 2020

Philippe Steiner on matching and romance, and transplants

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

Algorithmic Mechanism Design With Investment, by Akbarpour, Kominers, Li, Li, and Milgrom,

 Mechanisms that are computationally complex may require approximation in implementation, which can change the incentive properties of the exact mechanism.   But progress can be made...

Algorithmic Mechanism Design With Investment, by Mohammad Akbarpour, Scott Duke Kominers, Kevin Michael Li, Shengwu Li, Paul Milgrom, Econometrica, First published: 07 December 2023, https://doi.org/10.3982/ECTA19559

Abstract: We study the investment incentives created by truthful mechanisms that allocate resources using approximation algorithms. Some approximation algorithms guarantee nearly 100% of the optimal welfare in the allocation problem but guarantee nothing when accounting for investment incentives. An algorithm's allocative and investment guarantees coincide if and only if its confirming negative externalities are sufficiently small. We introduce fast approximation algorithms for the knapsack problem that have no confirming negative externalities and guarantees close to 100% for both allocation and investment.

From the introduction:

"Approximation algorithms can be combined with pricing rules to produce truthful mechanisms, provided that the algorithm is “monotone” (Lavi, Mu'Alem, and Nisan (2003)). In this paper, we study the ex ante investment incentives created by such mechanisms.

"Suppose that one bidder can make a costly investment to change its value before participating in a truthful mechanism. As an initial result, we show that all truthful mechanisms using the same allocation algorithm entail the same investment incentives, so we can regard the investment incentives as properties of the algorithm itself.

"If an allocation algorithm exactly maximizes total welfare, then the corresponding truthful mechanism is a Vickrey–Clarke–Groves (VCG) mechanism. For VCG mechanisms, any single bidder's investment is profitable if and only it improves total welfare (Rogerson (1992)). In this respect, the VCG mechanisms are essentially unique. We find that a truthful mechanism aligns a bidder's investment incentives with welfare maximization only if there is some set of allocations such that, for generic valuation profiles, its allocation algorithm exactly maximizes welfare over that set. Many practical approximation algorithms do not have this structure and, as a result, lack efficient investment incentives.

"One might also hope that if an allocation algorithm approximately maximizes total welfare, then it generates approximately efficient investment incentives—but we show to the contrary that arbitrarily good approximations can have arbitrarily bad investment guarantees. To make this statement precise, we evaluate an algorithm's performance on any particular instance by the welfare it achieves divided by the maximum welfare. We refer to the worst-case ratio over all instances when values are exogenous as the allocative guarantee, and the worst-case ratio when one bidder's ex ante investment endogenously determines its value as the investment guarantee.1 (The investment guarantee measures welfare net of investment costs.)

"Because the investment guarantee is a worst case over instances and over investment technologies, it is never more than the allocative guarantee. We characterize the algorithms for which the allocative and investment guarantees are equal, and apply those results to evaluate and improve upon standard approximation algorithms."

Fairness in algorithms: Hans Sigrist Prize to Aaron Roth

 The University of Bern's Hans Sigrist Prize has been awarded to Penn computer scientist Aaron Roth, and will be celebrated today.

Here are today's symposium details and schedule:

The Hans Sigrist Symposium

Data Science: The Power of the Human Mind for the Sake of Humankind

Here's an interview:

Aaron Roth: Pioneer of fair algorithms  In December 2023, the most highly endowed prize of the University of Bern will go to the US computer scientist Aaron Roth. His research aims to incorporate social norms into algorithms and to better protect privacy.  by Ivo Schmucki 

"There are researchers who sit down and take on long-standing problems and just solve them, but I am not smart enough to do that," says Aaron Roth. "So, I have to be the other kind of researcher. I try to define a new problem that no one has worked on yet but that might be interesting."

"Aaron Roth's own modesty may stand in the way of understanding the depth of his contributions. In fact, when he authored his doctoral thesis on differential privacy about 15 years ago and then wrote on the fairness of algorithms a few years later, terms like “Artificial Intelligence” and “Machine Learning” were far from being as firmly anchored in our everyday lives as they are today. Aaron Roth was thus a pioneer, laying the foundation for a new branch of research.

"I am interested in real problems. Issues like data protection are becoming increasingly important as more and more data is generated and collected about all of us," says Aaron Roth about his research during the Hans Sigrist Foundation’s traditional interview with the prize winner. He focuses on algorithmic fairness, differential privacy, and their applications in machine learning and data analysis.

...

"It is important that more attention is paid to these topics," says Mathematics Professor Christiane Tretter, chair of this year's Hans Sigrist Prize Committee. Tretter says that many people perceive fairness and algorithms as two completely different poles, situated in different disciplines and incompatible with each other. "It is fascinating that Aaron Roth’s work shows that this is not a contradiction."

...

"The first step to improving the analysis of large data sets is to be aware of the problem: "We need to realize that data analysis can be problematic. Once we agree on this, we can consider how we can solve the problems," says Aaron Roth."

Refugee resettlement and the top trading cycles algorithm, by Farajzadeh, Killea, Teytelboym, and Trapp

 Here's a recent paper that (among other things) considers using the top trading cycles algorithm for matching refugees to sponsors (under a special program for Ukraine), to satisfy the location preferences of refugees.

Optimizing Sponsored Humanitarian Parole by Fatemeh Farajzadeh, Ryan B. Killea, Alexander Teytelboym, Andrew C. Trapp, working paper, 2023

Abstract: The United States has introduced a special humanitarian parole process for Ukrainian citizens in response to Russia’s 2022 invasion of Ukraine. To qualify for parole, Ukrainian applicants must have a sponsor in the United States. In collaboration with HIAS, a refugee resettlement agency involved in the parole process, we deployed RUTH (Refugees Uniting Through HIAS), a novel algorithmic matching system that is driven by the relocation preferences of refugees and the priorities of US sponsors. RUTH adapts Thakral [2016] Multiple-Waitlist Procedure (MWP) that combines the main First-In/First-Out (FIFO) queue with location specific FIFO queues in order to effectively manage the preferences of refugees and the supply of community sponsors. In addition to refugee preferences and sponsor priorities, RUTH incorporates various feasibility considerations such as community capacity, religious, and medical needs. The adapted mechanism is envy-free, efficient and strategy-proof for refugees. Our analysis reveals that refugee preferences over locations are diverse, even controlling for observables, by demonstrating the difficulty of solving a much simpler problem than modeling preferences directly from observables. We use our data for two counterfactual simulations. First, we consider the effects of increased waiting times for refugees on the quality of their matches. We find that with a periodic Top Trading Cycles algorithm, increasing period length from 24 days to 80 days, improves average rank of a refugee’s match from 3.20 to 2.44. On the other hand, using the available preference data RUTH achieved an average rank of 4.07 with a waiting time of 20 days. Second, we estimate the arrival rates of sponsors in each location that would be consistent with a long-run steady state. We find that more desirable locations (in terms of refugee preferences) require the highest arrival rates suggesting that preferences might be a useful indicator for investments in sponsorship capacity. Our study highlights the potential for preference-based algorithms such as RUTH to improve the efficiency and fairness of other rapidly-deployed humanitarian parole processes.

#######

Earlier:

Sunday, December 18, 2022

Resettling refugees using preferences of refugees and hosts