Matching in Budapest in July: call for papers

First announcement and call for papers (with apologies if you receive this

more than once):

                           MATCH-UP 2012:

   the Second International Workshop on Matching Under Preferences

                          19-20 July 2012

                         Budapest, Hungary

        http://econ.core.hu/english/res/MATCH-UP_2012.html

  co-located with SING8: The 8th Spain-Italy-Netherlands Meeting

              on Game Theory (http://sing8.iehas.hu)

    

   

Celebrating the 50th anniversary of the seminal paper by Gale and Shapley,

and following the success of the first MATCH-UP workshop in Reykjavík in

2008 (http://www.optimalmatching.com/workshop), we are organising another

interdisciplinary workshop on stable matchings and related topics.

Background

----------

Matching problems with preferences occur in widespread applications such

as the assignment of school-leavers to universities, junior doctors to

hospitals, students to campus housing, children to schools, kidney

transplant patients to donors and so on. The common thread is that

individuals have preference lists over the possible outcomes and the task

is to find a matching of the participants that is in some sense optimal

with respect to these preferences.

The remit of this workshop is to explore matching problems with

preferences from the perspective of algorithms and complexity, discrete

mathematics, combinatorial optimization, game theory, mechanism design

and economics, and thus a key objective is to bring together the research

communities of the related areas.

Invited speakers

----------------

* Nicole Immorlica, Northwestern University

* Rob Irving, University of Glasgow

* Fuhito Kojima, Stanford University (on leave at Columbia University)

* Tayfun Sönmez, Boston College

List of topics

--------------

The matching problems under consideration include, but are not limited to:

* two-sided matchings involving agents on both sides (e.g. college

  admissions, resident allocation, job markets, school choice, etc.)

* two-sided matchings involving agents and items (e.g. house allocation,

  course allocation, project allocation, assigning papers to reviewers,

  school choice, etc.)

* one-sided matchings (roommates problem, kidney exchanges, etc.)

* matching with payments (assignment game, auctions, etc.)

Submissions

-----------

We call for two types of contributed papers.

Format A: original contribution

* at most 12 pages

* accepted papers will be published in proceedings (however, this should

  not prevent the simultaneous or subsequent submission of contributed

  papers to other workshops, conferences or journals)

Format B: not necessarily original work

* no page limit

* only the abstract will be published in proceedings

Authors should indicate which format type their paper should be considered

under.

Important dates

---------------

* Deadline for submission of contributed papers: 19 March 2012

* Notification of acceptance: 20 April 2012

* Early registration deadline: 18 May 2012

* Workshop: 19-20 July 2012

Organising committee

--------------------

* Péter Biró (Institute of Economics, Hungarian Academy of Sciences)

* Tamás Fleiner (Budapest University of Technology and Economics)

* David Manlove (University of Glasgow)

* Tamás Solymosi (Corvinus University, Budapest)

Programme committee

-------------------

* Péter Biró (Chair, Institute of Economics, Hungarian Academy of Sciences)

* Estelle Cantillon (Université Libre de Bruxelles)

* Katarína Cechlárová (Univerzita Pavla Jozefa Safárika)

* Paul Dütting (EPFL, Lausanne)

* Aytek Erdil (University of Cambridge)

* Tamás Fleiner (Budapest University of Technology and Economics)

* Guillaume Haeringer (Universitat Autonoma de Barcelona)

* Elena Inarra (University of the Basque Country)

* Zoltán Király (Eötvös Loránd University, Budapest)

* Flip Klijn (Universitat Autonoma de Barcelona)

* David Manlove (University of Glasgow)

* Eric McDermid (21st Century Technologies)

* Shuichi Miyazaki(Kyoto University)

* Marina Nunez (Universitat de Barcelona)

* Ildikó Schlotter (Budapest University of Technology and Economics)

* Tamás Solymosi (Corvinus University, Budapest)

Further information

-------------------

See http://econ.core.hu/english/res/MATCH-UP_2012.html

The roommate problem on TV

James Boudreau writes to alert us to some matching theory on television:

"The NBC show ``Community'' chronicles the misadventures of a diverse and wacky group of students at a community college.  On the last night's episode (season 3, episode three, ``Competitive Ecology'') the group was confronted with the problem of dividing into pairs for the purpose of being lab partners.  When their initial pairings don't work out, one member of the group realizes that they are in a classic roommates problem and suggests that they re-match by writing down lists of ordinal preferences and submitting them to one member of the group who is unanimously selected  as the matchmaker.  Unfortunately, the algorithm that the matchmaker uses (which focuses on balancing popularity across the pairs) proves to be unstable--eventually the group is forced to share one set of equipment since they can not agree on pairings.

"The episode is currently available for free on Hulu.  The most relevant scene begins at about 8:20.  Later on, around 14:33, one member of the group even accuses others of strategically manipulating their preferences to suggest that he is unpopular. "

Judd Kessler on the roommate problem in 2002

In response to my recent posts on roommate matching for college students, Judd Kessler points me to a newspaper column he wrote in 2002, on roommates, peer effects, and the Harvard housing system: More Than A Bunkmate.

Matchmaking at Harvard, the roommate problem

The Crimson reports, In Choosing Roommates, Deans Become Matchmakers.

"The day is June 10, and Resident Dean of Freshmen Sue Brown embarks upon what will be a five-week quest: sorting 398 first-years into rooms in Grays, Matthews, and Weld Halls.


"Much of this task remains the same as it has been in years past. She sorts freshmen largely by hand, thoroughly reading incoming freshmen’s responses to roommate questionnaires. During the process, her floor is covered with a mass of paper that is eventually divided into nine distinct piles—one of the early steps in the lengthy matchmaking process.

"But in the midst of that process, technology rears its head. In Adobe Acrobat, Brown categorizes freshmen, using colors to sort the incoming students by geography and stamping the freshmen’s rooming surveys with various logos made in Photoshop. A cartoon of a chess piece marks a chess player. A compass is reserved for the “curious and adventurous” freshman, Brown says.

"Emblazoned with colors and cartoons, the surveys are printed out and scattered on a floor in Brown’s residence in Weld Hall. From there, she divides the students into three categories based on students’ self-reported levels of sociability.

"Social tendencies are one of the most important factors in determining roommate compatibility “because it’s going to be something that comes between roommates before they even meet each other,” she says.

"But other factors matter as well, Brown adds. From the sleeping habits freshmen keep and the sports they play, to the neatness they maintain and the number of roommates they want, the resident deans take into account a slew of determinants of each first-year’s personality.

"Some factors, like musical tastes, are often stronger predictors of compatibility than others, according to Brown.
...
"Resident deans often try to place local freshmen with those from outside the area, especially international students for whom going home during vacations is more difficult, according to Dean of Freshmen Thomas A. Dingman ’67.
...
"Every year, a small margin of freshmen—”about half a dozen”—are switched out of their original suites after approaching the FDO, Dingman says. Many more choose to block with and live with others in future years.

...
"After organizing the rooms, the deans turn to assembling the entryways.
“You want it to be a dIverse group, a microcosm of the freshman class,” Brown says.
But at the same time, the entryway can’t be so diverse that a student feels isolated. For example, the FDO tries to avoid placing only one international student in any entryway, Brown says. She also avoids putting two students from the same varsity sport or the same high school in a single entryway."

Roommate matching and the social internet

Roommate matching continues to evolve, with Facebook playing a key role: Students Turn to Online Roommate Matching Services to Avoid Getting Paired With a Stranger (HT: Mike Ruberry)

The Chronicle gives a good description: Colleges Use Facebook to Let Freshmen Find Their Own Roommates
"This summer, incoming freshmen at five universities can use a Facebook application to find their roommates. Students can use the application, RoomBug, to fill out forms about their preferences for living and qualities they'd like to see in a roommate. Students can then request a match, which the other incoming freshman must confirm.
RoomBug is hardly the first service to let students match themselves: Tulane University announced a partnership with online service RoommateClick two years ago.
But RoomBug, which the company U-Match LLC just rolled out at Emory University, the University of Florida, Temple University, Wichita State University, and William Paterson University of New Jersey, tries to go where the students are.
"Everyone is on Facebook," says Robert Castellucci, the service's co-founder and sales director.
Over a quarter of the University of Florida's incoming freshmen have added the Facebook application, he says, but numbers on how many matches the service helped make are not yet available."

Maureen Dowd regrets the trend, writing in her NY Times column
"The serendipity of ending up with roommates that you like, despite your differences, or can’t stand, despite your similarities, or grow to like, despite your reservations, is an experience that toughens you up and broadens you out for the rest of life.

"So I was dubious when I read in The Wall Street Journal last week that students are relying more on online roommate matching services to avoid getting paired with strangers or peers with different political views, study habits and messiness quotients."

Roommate matching

"Male or female? Smoker or nonsmoker?
Those two questions have long been the basis for the University of Arizona’s roommate-pairing formula. But a year ago the university decided to give incoming students seeking deeper compatibility another option: shopping for their roommates on the Web."


That's the first paragraph of an interesting story at Inside Higher Ed about using the web to improve roommate matching: Match at First Site .


"Arizona is one of a small but growing number of colleges that have contracted with RoommateClick, a service that lets students take the lead on a task that has historically fallen to campus housing officials by browsing and communicating with future classmates who have also signed up for the service. Students who have hit it off online can then request to bunk with each other."


For a different market, see my earlier post Housemate match .