Summer School on Matching Problems, Markets, and Mechanisms: going on now in Budapest

Summer School on Matching Problems, Markets, and Mechanisms:

(And don't miss the link to ruin pubs at the bottom...)

the first summer school of the COST project on Computational Social Choice

Monday, 24 June 2013

8:00-8:45 Registration

8:45-9:00 Opening

9:00-10:30 First tutorial of David Manlove

Hospitals / Residents problem and its variants

10:30-11:00 Coffee break

11:00-12:30 First tutorial of Tamás Fleiner

Two-sided problems with choice functions, matroids and lattices

12:30-14:00 Lunch break

14:00-15:30 First tutorial of Atila Abdulkadiroglu

School choice - Theory

15:30-16:00 Coffee break

16:00-17:30 Invited talk 1

Marina Nunez: Introduction to assignment games

18:30-21:30 Poster session with welcome reception

In the main building of Corvinus University of Budapest. Address: Budapest, Fővám tér 8., main hall. 33 posters will be presented.

Tuesday, 25 June 2013

9:00-10:30 Second tutorial of Tamás Fleiner

Generalised stable roommates problems

10:30-11:00 Coffee break

11:00-12:30 Second tutorial of Atila Abdulkadiroglu

Market design and recent issues in school choice

12:30-14:00 Lunch break

14:00-15:30 Second tutorial of David Manlove

The House Allocation problem (with applications to reviewer assignment)

15:30-16:00 Coffee break

16:00-17:30 Invited talk 2

Tamás Solymosi: The nucleolus and other core allocations in assignment games

Wednesday, 26 June 2013

9:00-10:30 Third tutorial of Atila Abdulkadiroglu

From design to evaluation to redesign

10:30-11:00 Coffee break

11:00-12:30 Third tutorial of David Manlove

Kidney exchange

12:30-14:00 Lunch break

14:00-15:30 Third tutorial of Tamás Fleiner

Stable allocations and flows

16:00-18:00 Facultative social program

Hiking to the Citadella (top of Gellért hill), or going to Gellért bath. Meeting after at 18:00 at the fountain in front of hotel Gellért.

18:30- Conference dinner

Buffet dinner at Trófea Grill Restaurant Újbuda.

Thursday, 27 June 2013

9:00-10:30 Invited talk 3

Ildikó Schlotter: Parameterized complexity of some stable matching problems

10:30-11:00 Coffee break

11:00-12:30 Invited talk 4

Katarína Cechlárová: Computational complexity of competitive equilibria in exchange markets

12:30-14:00 Lunch break

14:00-15:30 Invited talk 5

Francis Bloch: Dynamic matching problems

15:30-16:00 Coffee break

16:00-17:30 Invited talk 6

Joana Pais: Experimental studies in matching markets

Friday, 28 June 2013

9:00-10:30 Invited talk 7

Szilvia Pápai: Matching with priorities

10:30-11:00 Coffee break

11:00-12:30 Invited talk 8

Estelle Cantillon: Preference formation in matching mechanisms

12:30-14:00 Lunch break

14:00-15:30 Invited talk 9

Lars Ehlers: Strategy-proofness in markets with indivisibilities

15:30-16:00 Coffee break

16:00-17:30 Invited talk 10

Dorothea Kuebler: University admissions in Germany: empirical and experimental evidence

Facultative social program

Visiting ruin pubs, meeting from 18:00 in Szimpla Kert

Courts and assisted suicide in Britain

Here is a judicial philosophy that seems hard to sympathize with: Lord Chief Justice won't allow 'personal sympathy' to sway decision on assisted suicide

"The Lord Chief Justice, Lord Judge, said he and his fellow judges were “acutely aware of the desperate situation” faced by people such as Tony Nicklinson, the “locked-in” syndrome sufferer who starved himself to death last year after losing a right-to-die case.

"But he said “only basic principles of law” could decide whether or not there could ever be any relaxation of the ban on assisted suicide.

"He also challenged lawyers brandishing opinion poll findings pointing to strong public support for a change in the law, questioning how it was relevant, adding: “The public may change its mind next week.”

"He said the case could not be decided “on the basis of opinion polls”.

"Lord Judge was speaking as he, joined by the Master of the Rolls Lord Dyson and Lord Justice Elias, began to hear submissions as part of a wide ranging Court of Appeal challenge to the UK’s laws on euthanasia."

More unraveling in the private equity labor market

The NY Times is on the story: A Rush to Recruit Young Analysts, Only Months on the Job

"For Wall Street’s top young analysts, landing at a prestigious investment bank out of college was the easy part. Now comes the fierce competition to line up a high-paying job at a prominent buyout fund, just months into their first professional jobs.
...
"Traditionally, these jobs do not begin immediately but a year and a half later, after analysts finish their two-year contracts.
...
"One second-year analyst at a large bank said she had hardly been exposed to working in the finance world when the rush to find a job on the “buy side” began.

“There’s a progression that people go through,” she said. “You’re two months in, you start getting calls from recruiters, and you feel left out if you’re not participating. It’s a very enticing concept to lock up a job and your ticket out of banking a year and a half out.”
...
"Because they are trying to place analysts with such little work experience, recruiters will look for anything to identify the cream of the crop. College grade-point averages, high school test scores and community service are all fair game, Ms. Morgan said.
...
"Efforts have been made to push back a process that has been inching ahead, earlier and earlier. Last year, a handful of top-flight private equity funds including Blackstone, Carlyle and Warburg Pincus tried to delay recruiting until analysts were halfway through their second year, according to multiple private equity executives.

"The larger private equity funds waited, partly in response to big banks that were cracking down on recruiting. Goldman Sachs fired analysts who conceded they had lined up new positions in their first year, and Morgan Stanley banned first-year bankers from looking for new jobs, according to executives at both banks.

“There has been backlash,” said a former Goldman Sachs analyst who went through the recruiting process three years ago and is now an associate at a midmarket private equity fund. “You don’t really want your full investment banking analyst class checking out with a year and a half left on their contracts because they know they have another job lined up.”

"The banks were not concerned about losing talent but frustrated with the conflicts of interest that emerge after analysts pledge themselves to another employer.

...

“Once you have an offer, maybe you don’t want to work late nights three, four or five nights a week,” she said. “Maybe you don’t want to hop on every single live deal.”

"Morgan Stanley has since bowed to employee complaints, lifting its ban on first-year bankers’ job hunts this spring, according to two people briefed on the decision. Morgan Stanley declined to comment.

...

"The large buyout funds began ratcheting up recruitment drives last month, once again pursuing analysts in their first year.

"The funds that agreed to wait felt they had lost top employees to hedge funds and middle-market shops that aggressively recruited first-year analysts, said a private equity executive who oversees his firm’s hiring efforts.

“It’s back to a knife fight in an alley,” the executive said. “And it’s not fair because these kids get barely any on-the-job training before a recruiter reaches out to them. We should just be recruiting these kids out of middle school. Forget high school, college and Goldman Sachs.”

HT:: Eric Budish

"דוקטור לשם כבוד" 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.

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)

Witchcraft as a repugnant transaction in Indonesia?

Al Jazeera reports on efforts to ban witchcraft in Indonesia: Indonesia considers ban on witchcraft

"People accused of practising black magic in Indonesia could be jailed for five years if a revised criminal code is accepted by parliament.

"However, there is a lot of resistance to the proposed new law, as witchcraft is big business in the country."
*********

In the United States and elsewhere, there are all sorts of laws and regulations about who may (and who may not) practice medicine, and I expected the story to be about efforts to ban witchdoctors on the grounds of practicing medicine without a license.  But the story suggests that at least some of the motivation for the ban comes from a feeling that witchcraft is effective...

Kidney exchange about to begin in France?

The story (in French) is here: Dons croisés d'organe : c'est maintenant (ou presque) ! 

Here's Google translate:

"In France, the law authorizing donations cross between living persons of July 2011 and its implementing decree was published in the Official Journal in September 2012. With the development of matching software, the first cross-kidney donation could take place before the end of 2013. Experts expect twenty additional transplants per year in the country.
Organ donation called "crossover" allows a living person who has expressed its intention to grant the benefit of a receiver identified on hold, to be offered to participate in a cross organ donation in cases of medical incompatibility receiver initially selected. General ethical principles for donations and uses of elements and products of the human body must be met: consent to the collection, revocable at any time, free, anonymous; estimate of the risk / benefit of interventions and implementation of the system of health surveillance . That the pairing mechanism is put in place, there must be at least 50 "couples" of volunteers. The selection process is currently underway. Each donor should have a complete medical checkup. The "couples" then pass a special committee to verify the absence of coercion and financial dealings. The donor is heard by a court. Then the couples are reviewed by the National Center for allocating grafts, which decides on their eligibility or not the database pairs.
It must be the work of computerized winners of Nobel Prize in Economics in 2012 matching the Americans Alvin Roth and Lloyd Shapley. Their game theory has revolutionized the organization of cross donation for kidney transplantation in the United States by allowing the matching of thousands of donors and recipients of organs. It is estimated that about 2000 patients so far received a kidney through this system, without which they would not have been grafted.
On the occasion of the third day of the Biomedicine Agency, held in Paris on Thursday 30 and Friday, May 31, Marie-Alice Macher, the transplant center strategy, announced the start of the first cross donations, originally scheduled for last spring, was now imminent. "The matching software is ready, the agreements were signed with most departments of institutions, which must leave the operating room available in case of successful matching. The only thing we lack is a sufficient number of pairs of donors in the database, "she said. The logistics system is also heavy as to ensure the reciprocity of gifts, the two samples and two transplants must be performed simultaneously, requiring the mobilization of four operating theaters."

Compensating kidney donors with charitable contributions--Choi, Gulati and Posner

Organ shortages remain despite the increase in live donation that has accompanied kidney exchange. But it is illegal to pay donors, so there's an ongoing discussion of other ways to induce a greater supply.  Here's a proposal by Choi, Gulati and Posner...

Altruism Exchanges and the Kidney Shortage

Stephen J. Choi 

New York University School of Law

G. Mitu Gulati 

Duke University - School of Law

Eric A. Posner 

University of Chicago - Law School
January 16, 2013

University of Chicago Institute for Law & Economics Olin Research Paper No. 630
NYU Law and Economics Research Paper No. 13-03 
Abstract:      
Not enough kidneys are donated each year to satisfy the demand from patients who need them. Strong moral and legal norms interfere with market-based solutions. To improve the supply of kidneys without violating these norms, we propose legal reforms that would strengthen the incentive to donate based on altruistic motives. We propose that donors be permitted to donate kidneys in exchange for commitments by recipients or their benefactors to engage in charitable activity or to donate funds to charities chosen by donors. And we propose that charities be permitted to create Altruism Exchanges, which would permit large numbers of altruists to make charitable exchanges with each other, including but not limited to kidney donations. Altruism Exchanges would solve two significant problems with the current system of voluntary kidney donations: the risk of default and the lack of liquidity.



 HT: Alexander Berger

My graduation speech to Stanford economics grads, June 16, 2013

On Sunday I got to dress as Harry Potter and give the Stanford economics graduation speech (on matching and graduation) at Stanford's commencement exercises.

Non-directed kidney donation is up in the UK

Altruistic organ donations rise in UK almost three-fold

"The number of living people giving one of their organs to a stranger almost tripled last year in the UK, according to new figures.

The Human Tissue Authority (HTA) approved 104 so-called altruistic organ donations in 2012-13 compared with 38 the previous year."
*******************

Here are the UK statistics, and here is the page for the UK's kidney exchange program: Paired donation matching scheme

Deceased organ donation and solicitation in Israel: video of my talk at the conference in memory of Jean Francois Mertens in Jerusalem

Here's a video of the talk I gave at the Center for Rationality conference in memory of Jean Francois Mertens on June 7 2013.

An unusual blogging distinction, if it were true

Science writer Colin Schultz writing about Why Scientists Shouldn’t Be Afraid of Blogging and Social Media, presents a slide show that makes the following claim:

So this is Market Design. It’s written by Alvin Roth. Alvin stands as being, as far as I know, the only person with a Nobel prize who runs a blog. Alvin, along with Lloyd Shapley, won the Nobel Memorial Prize in Economic Sciences last year, and this was Alvin’s blog post that day.
******************

I would count the Becker-Posner blog in this category too, but I can't tell whether Mr. Schultz overlooked it, or doesn't count it as what he thinks of as a blog...

Are there any others that you know of?

EC 13: ACM conference on Electronic Commerce, in Philadelphia, June 16-20 2013

EC 13, the 14th ACM conference on Electronic Commerce, will be held in Philadelphia, at Penn.

There will be workshops the 16th and 17th, and the conference proper will be the 18-20th. Some of the sessions that may be of particular interest to readers of this blog are Monday June 17 tutorials on market design by Utku Unver from 9-12:30 and by Tayfun Sonmez from 2-5:30, a session on kidney exchange on Wednesday June 19 (chaired by Aaron Roth) from 10:20-11:20, my talk on kidney exchange on Thursday June 20 from 9-10:00, and a session on Matching (chaired by Itai Ashlagi) from 11:40-12:40. There are also a bunch of sessions on mechanism design, with and without money.


 Here's the program (and here are the abstracts):

Tuesday, June 18, 2013
8:45 - 9:00 AM	Keynote Talk I Chair: Eva Tardos
9:00 - 10:00 AM	Cascading Behavior in Social and Economic Networks Jon Kleinberg
10:20 - 11:20 AM	Session 2a: Mechanism Design I Chair: Costis Daskalakis  Prior-Independent Auctions for Risk-Averse Agents Hu Fu, Jason Hartline and Darrell Hoy Prior-free Auctions for Budgeted Agents Nikhil R Devanur, Bach Ha and Jason Hartline On the Ratio of Revenue to Welfare in Single-Parameter Mechanism Design Robert Kleinberg and Yang Yuan
	Session 2b: Prediction Markets Chair: David Pennock  Cost Function Market Makers for Measurable Spaces,  Yiling Chen, Michael Ruberry and Jennifer Wortman Vaughan What You Jointly Know Determines How You Act --- Strategic Interactions in Prediction Markets Xi Alice Gao, Jie Zhang and Yiling Chen An Axiomatic Characterization of Adaptive-Liquidity Market Makers,  Xiaolong Li and Jennifer Wortman Vaughan
11:20 - 11:40 AM	Break
11:40 - 12:40 AM	Session 3a: Multidimensional Mechanism Design Chair: Michal Feldman Multi-parameter Mechanisms with Implicit Payment Computation,  Moshe Babaioff, Robert Kleinberg and Aleksandrs Slivkins Optimal Auctions via the Multiplicative Weight Method Anand Bhalgat, Sreenivas Gollapudi and Kamesh Munagala The Menu-Size Complexity of Auctions Sergiu Hart and Noam Nisan Session 3b: Ad Auctions I Chair: Sébastien Lahaie Real-time Optimization of Personalized Assortments Negin Golrezaei, Hamid Nazerzadeh and Paat Rusmevichientong A Dynamic Axiomatic Approach to First-Price Auctions,  Darrell Hoy, Kamal Jain and Chris Wilkens Competition Among Asymmetric Sellers With Fixed Supply Uriel Feige, Ron Lavi and Moshe Tennenholtz
12:40 - 2:00 PM	Lunch
2:10 - 3:30 PM	Session 4: Online Auctions Chair: Ron Lavi  Ranking and Tradeoffs in Sponsored Search Auctions Ben Roberts, Dinan Gunawardena, Ian Kash and Peter Key Whole-page Optimization and Submodular Welfare Maximization with Online Bidders Nikhil R Devanur, Nitish Korula, Zhiyi Huang, Vahab Mirrokni and Qiqi Yan Peaches, Lemons, and Cookies: Designing Auction Markets with Dispersed Information Ittai Abraham, Susan Athey, Moshe Babaioff and Michael Grubb Auctions for Online Display Advertising Exchanges: Approximations and Design Santiago R. Balseiro, Omar Besbes and Gabriel Y. Weintraub
3:30 - 3:50 PM	Break
3:50 - 4:50 PM	Session 5a: Mechanism Design II Chair: Jason Hartline  Cost-Recovering Bayesian Algorithmic Mechanism Design  Hu Fu, Brendan Lucier, Balasubramanian Sivan and Vasilis Syrgkanis Near-Optimal Multi-Unit Auctions with Ordered Bidders Sayan Bhattacharya, Elias Koutsoupias, Janardhan ,Kulkarni Stefano Leonardi, Tim Roughgarden and Xiaoming Xu Truthfulness and Stochastic Dominance with Monetary Transfers Martin Hoefer, Thomas Kesselhei and Berthold Voecking
	Session 5b: Price of Anarchy and Incentives Chair: Nikhil R. Devanur  Risk Sensitivity of Price of Anarchy under Uncertainty Georgios Piliouras, Evdokia Nikolova and Jeff S. Shamma Improved Bounds on the Price of Stability in Network Cost Sharing Games Euiwoong Lee and Katrina Ligett Sincere and Sophisticated Players in the Envy-free Allocation Problem Rodrigo Velez
4:55 - 6:15 PM	Session 6: Estimation and Forecasting Chair: Michael Wellman  Primary-Market Auctions for Event Tickets: Eliminating the Rents of "Bob the Broker" Eric Budish and Aditya Bhave Measuring the Performance of Large-Scale Combinatorial Auctions: A Structural Estimation Approach Sang Won Kim, Marcelo Olivares and Gabriel Weintraub When Do Noisy Votes Reveal the Truth?  Ioannis Caragiannis Ariel Procaccia and Nisarg Shah A Combinatorial Prediction Market for the U.S. Elections Miroslav Dudik, Sébastien Lahaie, David Pennock and David Rothschild
6:15 - 7:00 PM	Business Meeting
7:00 - 8:30 PM	Poster Session
Wednesday, June 19, 2013
9:00 - 10:00 AM	Session 7: Mechanism Design III Chair: Moshe Babaioff Mechanism Design via Optimal Transport Costis Daskalakis, Alan Deckelbaum and Christos Tzamos Optimal and Near-Optimal Mechanism Design with Interdependent Values Tim Roughgarden and Inbal Talgam-Cohen Truthful Mechanisms for Agents that Value Privacy Yiling Chen, Stephen Chong, Ian Kash, Tal Moran and Salil Vadhan
10:00 - 10:20 AM	Break
10:20 - 11:20 AM	Session 8a: Mechanism Design IV Chair: Robert Kleinberg  Differential Pricing with Inequity Aversion in Social Networks Noga Alon, Yishay Mansour and Moshe Tennenholtz Approximation in Mechanism Design with Interdependent Values Yunan Li Accounting for Price Dependencies in Simultaneous Sealed-Bid Auctions Brandon Mayer, Eric Sodomka, Amy Greenwald and Michael Wellman Session 8b: Kidney Exchange Chair: Aaron Roth Failure-Aware Kidney Exchange John Dickerson, Ariel Procaccia and Tuomas Sandholm Harnessing the Power of Two Crossmatches Avrim Blum, Anupam Gupta, Ariel Procaccia and Ankit Sharma Kidney Exchange in Dynamic Sparse Heterogenous PoolsItai Ashlagi, Patrick Jaillet and Vahideh Manshadi
11:20 - 11:40 AM	Break
11:40 - 12:40 PM	Session 9a: Mechansim Design without Money I Chair: Ariel Procaccia Strategyproof Facility Location for Concave Cost Functions Dimitris Fotakis and Christos Tzamos Strategyproof Facility Location and the Least Squares Objective Yoav Wilf and Michal Feldman Loss Calibrated Methods for Bipartite Rationing Herve Moulin and Jay Sethuraman Session 9b: Public Goods and Networks Chair: Arpita Ghosh A Network Approach to Public Goods Matt Elliott and Ben Golub Empirical Agent Based Models of Cooperation in Public Goods GamesMichael Wunder, Siddharth Suri and Duncan Watts Pricing Public Goods for Private Sale  Michal Feldman, David Kempe, Brendan Lucier and Renato Paes Leme
12:40 - 2:00 PM	Lunch
2:00 - 3:20 PM	Session 10a: Social Networks Chair: Jeff MacKie Mason  Complex Contagion and the Weakness of Long Ties in Social Networks: Revisited Roozbeh Ebrahimi, Golnaz Ghasemiesfeh and Jie Gao Selection and Influence in Cultural Dynamics David Kempe, Jon Kleinberg, Sigal Oren and Aleksandrs Slivkins Incentives, Gamification, and Game Theory: An Economic Approach to Badge Design David Easley and Arpita Ghosh A Markov Chain Approximation to Choice ModelingJose Blanchet, Guillermo Gallego and Vineet Goyal Session 10b: Complexity and Learning Chair: Yishay Mansour  Best-Response Dynamics Out of Sync Roee Engelberg, Alex Fabrikant, Michael Schapira and David Wajc The Empirical Implications of Rank in Bimatrix Games Siddharth Barman, Umang Bhaskar, Federico Echenique and Adam Wierman Learning Equilibria of Games via Payoff QueriesRahul Savani, John Fearnley, Martin Gairing and Paul Goldberg Super-Efficient Rational ProofsPablo Azar and Silvio Micali
3:20 - 3:50 PM	Break
3:50 - 4:50 PM	Session 11: Networks Chair: Jon Kleinberg  Selection Effects in Online Sharing: Consequences for Peer Adoption Sean J Taylor, Eytan Bakshy and Sinan Aral Bertrand Networks Moshe Babaioff, Brendan Lucier and Noam Nisan Potential Games are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games Ragavendran Gopalakrishnan, Jason Marden and Adam Wierman
6:00 - 10:00 PM	Conference Dinner
Thursday, June 20, 2013
	Keynote Talk II Chair: Preston McAfee
9:00 -10:00 AM	Kidney Exchange: Where We’ve Been and Where We Can Go From Here Alvin E. Roth
10:00 -10:20 AM	Break
10:20 - 11:20 AM	Session 13: Mechanism Design without Money II Chair: Mallesh Pai Unbalanced Random Matching Markets Itai Ashlagi, Yashodhan Kanoria and Jacob Leshno Existence of Stable Matchings in Large Markets with Complementarities Eduardo Azevedo and John Hatfield Mechanism Design for Fair Division Richard Cole, Vasilis Gkatzelis and Gagan Goel
11:20 - 11:40 AM	Break
11:40 - 12:40 AM	Session 14a: Ad Auctions II Chair: Noam Nisan Budget Smoothing for Internet Ad Auctions: A Game Theoretic Approach Denis Charles, Deeparnab Chakrabarty, Max Chickering, Nikhil R Devanur and Lei Wang Revenue Optimization in the Generalized Second-Price Auction David Thompson and Kevin Leyton-Brown Auctions with Unique Equilibria Shuchi Chawla and Jason Hartline Session 14b: Matching Chair: Itai Ashlagi Designing for Diversity in Matching Scott D Kominers and Tayfun Sonmez Two-Sided Matching with Partial Information Baharak Rastegari, Anne Condon, Nicole Immorlica and Kevin Leyton-Brown House Allocation with Indifferences: A Generalization and a Unified View Daniela Saban and Jay Sethuraman
12:40 - 2:00 PM	Lunch
2:10 - 3:30 PM	Session 15a: Crowd Sourcing in networks Chair: Jenn Wortman Vaughan Sybil-proof Mechanisms in Query Incentive Networks Wei Chen, Wang Yajun, Dongxiao Yu and Li Zhang On Discrete Preferences and CoordinationFlavio Chierichetti, Jon Kleinberg and Sigal Oren Incentivizing Participation in Online Forums for Education Arpita Ghosh and Jon Kleinberg Privacy and Coordination: Computing on Databases with Endogenous Participation Arpita Ghosh and Katrina Ligett Session 15b: Online experience Chair: Siddharth Suri Pick Your Poison: Pricing and Inventories at Unlicensed Online Pharmacies Nektarios Leontiadis, Tyler Moore and Nicolas Christin Down-to-the-Minute Effects of Super Bowl Advertising on Online Search Behavior Randall A Lewis and David Reiley Optimizing Password Composition Policies Jeremiah M Blocki, Saranga Komanduri, Ariel Procaccia and Or Sheffet Latency Arbitrage, Market Fragmentation, and Efficiency: A Two-Market Model Elaine Wah and Michael Wellman
3:30 - 3:50 PM	Break
3:50 - 4:50 PM	Session 16: Information and Networks Chair: Nicole Immorlica Robust Incentives for Information Acquisition,  Gabriel Carroll Social Learning and Aggregate Network Uncertainty Ilan Lobel and Evan Sadler Implementing the "Wisdom of the Crowd" Ilan Kremer, Yishay Mansour and Motty Perry
4:50 PM	End

Is the set of stable matchings generically small? Ashlagi, Kanoria and Leshno on large random marriage markets

Suppose you have a matching market with two kinds of players, say each player of one kind owns a single left shoe and the other kind each owns a single right shoe, and they can earn $1 by assembling a pair of shoes.  Then if there are more left shoe owners than right shoe owners, the core of the game will give $1 to every right shoe owner and $0 to every left shoe owner. (Here's an old  experiment on such a game.)

The situation is very much less clear if the game isn't played for money, and if the players are not all identical. But in a surprising result, Itai Ashlagi, Yash Kanoria and Jacob Leshno have shown that in a two sided marriage model (in which each man has preferences over all the women and each women over all the men, so agents aren't at all identical), then even a slight imbalance in the sizes of the two sides of the market makes the set of stable matchings very small: Unbalanced random matching markets, by Itai Ashlagi, Yashodhan Kanoria, and Jacob D. Leshno.

"Abstract: We analyze large random matching markets with unequal numbers of men and women. We fi nd that being on the short side of the market confers a large advantage. For each agent, assign

a rank of 1 to the agent's most preferred partner, a rank of 2 to the next most preferred partner

and so forth. If there are n men and n + 1 women then, we show that with high probability, in

any stable matching, the men's average rank of their wives is no more than 3 logn, whereas the

women's average rank of their husbands is at least n/(3 logn). If there are n men and (1 +lamda )n

women for lamda> 0 then, with high probability, in any stable matching the men's average rank of

wives is O(1), whereas the women's average rank of husbands is Omega(n). Simulations show that

our results hold even for small markets."

We already knew that large matching markets have small sets of stable matchings when preference lists are short. This result suggests that small sets of stable matchings may arise for quite different reasons.

Who Gets What: video of a lecture I gave at Stanford GSB

One hour of market design (45 minutes of lecture, 15 of very good questions and my attempts to answer them...)

"Published on May 13, 2013

Stanford University Professor and 2012 Nobel Laureate Al Roth speaks on his prize-winning research and ground-breaking successes with exchange markets and his life-saving favorite, kidney exchanges.

Dr. Roth was the keynote speaker for the GSB Spring Reunions on May 3, 2013. He was introduced by Dean Garth Saloner.

Roth is the Craig and Susan McCaw Professor of Economics at Stanford University.

Related Links
http://alumni.gsb.stanford.edu/events...

Selected Works from Dr. Roth

http://www.stanford.edu/~alroth/

• Category

  Education

• License

  Standard YouTube License"

Matching in Paris: conference this week

Workshop on “Advances in Mechanism Design”, June 11–12, 2013
Paris School of Economics, “Grande Salle”, 48 Boulevard Jourdan, 75014 Paris, France

Here's the program:
Tuesday, June 11
09:00 - 10:00: Fuhito Kojima (Stanford):
“Efficient Matching under Distributional Constraints: Theory and Applications”
10:00 - 11:00: Dorothea Kubler (WZB Berlin):
“Implementing Quotas in University Admissions: Experimental Evidence”
Coffee Break
11:30 - 12:30: Yinghua He (TSE):
“Competitive Equilibrium from Equal Incomes for Two-Sided Matching”
Lunch
14:00 - 15:00: Alfred Galichon (Sciences Po):
“The Roomate Problem Is More Stable Than You Think”
15:00 - 16:00: Estelle Cantillon (ULB):
“Endogenous Preferences and the Role of the Mechanism in School Choice”
Coffee Break
16:30 - 17:30: Eduardo Azevedo (U Penn):
“A Supply and Demand Framework for Two-Sided Matching Markets”

Wednesday, June 12
09:00 - 10:00: Jinwoo Kim (Seoul National U):
“Stable Matching in Large Economies”
10:00 - 11:00: Francis Bloch (Polytechnique):
“Dynamic Allocation of Objects to Queuing Agents”
Coffee Break
11:30 - 12:30: Sonia Jaffe (Harvard):
“Taxation in Matching Markets”
Lunch
14:00 - 15:00: Tadashi Hashimoto (Stanford):
“The Generalized Random Priority Mechanism with Budgets”
15:00 - 16:00: Clayton Featherstone (U Penn):
“A Rank-based Refinement of Ordinal Efficiency and a New (but familiar) Class of Ordinal
Assignment Mechanisms”
Coffee Break
16:30 - 17:30: Muriel Niederle (Stanford):
“Propose with a Rose? Signaling in Internet Dating Markets”

Matching news from Peter Biro: a conference volume, a summer school at the end of the month and a workshop in October

Peter Biro writes:

The proceedings of the Japanese-Hungarian Symposium is now available online:

http://www.cs.bme.hu/~jh2013/nagy.pdf

with papers on stable matchings and flows from pages: 55, 65, 133, 225, 243, 301, 347

Our summer school starts in 2 weeks time with 83 participants (+speakers)

registered: http://econ.core.hu/english/res/MatchingSchool.html

The COST Action will have a workshop on 16-18 October in Barcelona, organised locally by Flip. The topics will be matchings and information merging (WGs 3 and 4 of the action: http://www.illc.uva.nl/COST-IC1205/).

You would be very welcome there as well if you have time.

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

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.