Tag Archive: market design

First time to attend SAET. Happy experience! Conference website: http://www.saet.uiowa.edu/2017/

2017 Conference Program.

Some nice remarks 🙂

  1. Got a lot of useful feedback on my presentation on unraveling under distributional constraints. I realized that I have so many things to work on.
  2. Met many new people, and made new friends with whom we share similar interests. Coffee breaks and lunch/dinner times were really great opportunities to exchange ideas.
  3. Attended Shengwu’s Aliprantis Prize Lecture with Paul after lunch. It’s my third time to hear his talk, but every time I was very impressed 🙂
  4. Got Paul’s signature for his new book “Discovering Prices – Auction Design with Complex Constraint”. His words are always so encouraging. Yes, I must keep working hard 🙂
  5. Asked a question on whether we should diversify research interests on the Plenary session memorizing Ken Arrow, and got useful insights from the panelists. During our social dinner the next day, our SAET president Prof. Robert Townsend restated this question and encouraged us to do interdisciplinary research. I really appreciate that they were still thinking over it, and they were trying to guide us young economists so carefully.
  6. The ending is pleasantly surprising: in the early morning on June 30, Prof. Robert Townsend was sitting near me on the same plane! 🙂






Nice stay at Hong Kong!

My presentation slide here: Presentation. This is a project that I started 4 years ago, suspended for a long time, now finally got time to continue working on it!

Screen Shot 2017-06-06 at 3.52.04 AM

The conference website: http://www.econ.cuhk.edu.hk/2017AMES/


Workshop website: http://marketplaceinnovation.net/

It was such a nice stay at Stanford! Thanks for all the feedback 🙂

Yuqing Hu - 1



8:00 A.M. Breakfast
8.45 A.M. Invited Talk 1 —Estelle Cantillon, Université libre de Bruxelles

The efficiency – stability tradeoff in school choice: Lessons for market design

Abstract: A well-known result for the school choice problem is that ex-post efficiency and stability may not be compatible. In the field, that trade-off is sometimes small, sometimes big.  This talk will summarize existing and new results on the drivers of this trade-off and derive the implications for the design of priorities and tie-breaking rules.

9.30 A.M. Session 1
A Simple Model for the Top Trading Cycles School Choice Mechanism Using Fluid Approximation

Speakers: Jacob Leshno and Irene Lo

Abstract: Many cities determine the assignment of students to schools through a school choice mechanism which calculates an assignment based on student preferences and school priorities. The prominent Top Trading Cycles (TTC) algorithm can be applied to give a strategy-proof and Pareto efficient assignment, but the combinatorial description of TTC makes it non-transparent to parents and difficult to analyze for designers. Using a fluid approximation model, we give a tractable characterization of the TTC mechanism for school choice: the TTC assignment can be simply described by n^{2} admission thresholds, where n is the number of schools, and these thresholds can be calculated by a differential equation.

The model also allows us to analyze general sequential trade procedures, and show that changes in trading priority can have non-trivial indirect effects on the allocation. We also apply this model to solve for optimal investment in school quality, and help explain empirical findings about the relation between the TTC assignment and the Deferred Acceptance assignment. To validate the fluid model we show that it gives a good approximation for strongly converging economies. Our analysis draws on an interesting connection between continuous trading procedures and continuous time Markov chains.

Pairwise Matching in Large Economies

Speakers: Michael Greinecker and Christopher Kah

Abstract: We formulate a general model of two-sided pairwise matching for continuum economies and prove the existence of stable matchings. The data of our model are not individual agents but the population distribution of their characteristics, which can be multidimensional and need not lie in a compact set. Our model allows for transfers as well as their absence, general widespread externalities, and match specific contracts and activities. Continuum versions of the assignment game or the marriage model can be obtained as special cases, as well as intermediate models with limited side payments. Our distributional model can be interpreted as both a limit of finite matching models and as a reduced form of a genuine continuum model in which individual agents are explicitly modeled.

Lone Wolves in Infinite, Discrete Matching Markets

Speaker: Ravi Jagadeesan

Abstract: In finite two-sided matching markets, the lone wolf theorem guarantees that the same agents remain unmatched in all stable outcomes. I show by example that this assertion is not true in infinite, discrete markets. However, despite the fact that the lone wolf theorem is often used to derive strategy-proofness, deferred acceptance remains (group) strategy-proof in many infinite markets.

10.30 A.M. Break
10.50 A.M. Session 2
Dynamic Reserves in Matching Markets: Theory and Applications

Speakers: Bertan Turhan and Orhan Aygun

Abstract: Indian engineering school admissions, which draw more than 500,000 applications per year, suffer from an important market failure: Through their affirmative action program, a certain number of seats are reserved for different castes and tribes. How- ever, when some of these seats are unfilled, they are not offered to other groups, and the system is vastly wasteful. Moreover, since students care not only about the school they are assigned to but also whether they are assigned through reserves or not, they may manipulate the system both by not revealing their privilege type and by changing their preferences over programs. In this paper, we propose a new matching model with the ability to release vacant seats to the use of other students by respecting certain affirmative action objectives. We design a new choice function for schools that respects affirmative action objectives, and increases efficiency. We propose a mechanism that is stable, strategy proof, and respects test-score improvements with respect to these choice functions. Moreover, we show that some distributional objectives that can be achieved by capacity-transfers cannot be achieved by slot-specific priorities.

Strategyproof Pareto-Stable Mechanisms for Two-Sided Matching with Indifferences

Speakers: Nevzat Onur Domanic, Chi-Kit Lam and C. Gregory Plaxton

Abstract: We study variants of the stable marriage and college admissions models in which the agents are allowed to express weak preferences over the set of agents on the other side of the market and the option of remaining unmatched. For the problems that we address, previous authors have presented polynomial-time algorithms for computing a “Pareto-stable” matching. In the case of college admissions, these algorithms require the preferences of the colleges over groups of students to satisfy a technical condition related to responsiveness. We design new polynomial-time Pareto-stable algorithms for stable marriage and college admissions that correspond to strategyproof mechanisms. For stable marriage, it is known that no Pareto-stable mechanism is strategyproof for all of the agents; our algorithm provides a mechanism that is strategyproof for the agents on one side of the market. For college admissions, it is known that no Pareto-stable mechanism can be strategyproof for the colleges; our algorithm provides a mechanism that is strategyproof for the students.

First Choice-Maximizing School Choice Mechanisms

Speakers: Umut DurTimo Mennle and Sven Seuken

Abstract: We investigate first choice-maximality (FCM) (i.e., a maximal share of students is matched to their reported first choices), a common desideratum in many school districts. No FCM mechanism can be stable; however, we find first choice-stability (FCS) (i.e., no student forms a blocking pair with her first choice) to be the strongest rank-based relaxation of stability that is compatible with FCM. Focusing on the class of FCM and FCS mechanisms (which includes the widely used Boston mechanism and its variants), we show that the Pareto efficient members of this class form a minimally manipulable subset. Moreover, we identify the Nash equilibrium outcomes of any mechanism in this class when all students are strategic and when some student are sincere. Our analysis generalizes that of Ergin and Sönmez (2006) and Pathak and Sönmez (2008) from the Boston mechanism to the general class of FCM and FCS mechanisms. Our results suggest a novel approach to the design of school choice mechanisms where strategic students self-select into receiving their reported school in a first step, so that in a second step, the matching of sincere students can be made independently of the usual incentive constraints.

Endowments, Exclusion, and Exchange

Speakers: Ivan Balbuzanov and Maciej Kotowski

Abstract: We study a discrete exchange and assignment economy with a rich endowment structure. Identifying deficiencies with classic solutions, such as the core, we propose a new cooperative solution concept for resource allocation problems, the exclusion core. The exclusion core is neither weaker nor stronger than the (strong) core and it rests upon a foundational idea in the legal understanding of property, the right to exclude others. We extend the exclusion core to relational economies where ownership rights and endowments are qualified by social hierarchies or priorities. A generalization of the top trading cycles algorithm can identify exclusion core allocations.

Efficient and Essentially Stable Assignments

Speakers: Andrew Kloosterman and Peter Troyan

Abstract: An important desideratum in priority-based allocation is stability: no agent should claim an object because she has higher priority than the agent to whom it is assigned. However, stable matchings are in general Pareto inefficient, forcing upon designers a difficult trade-off. This paper alleviates this tension between efficiency and stability by defining an assignment to be essentially stable if any claim an agent has to an object she prefers is vacuous, in the sense that it initiates a chain of reassignments that ultimately results in the initial claimant losing the object to a third student with even higher priority; on the other hand, if a non-vacuous claim exists, the assignment is strongly unstable. A main practical advantage to our definition is its simplicity: under an essentially stable assignment, explaining to agents why their claims are vacuous becomes straightforward, even to non-experts who may not fully understand the inner workings of a given mechanism. We show that mechanisms based on Shapley and Scarf’s TTC algorithm, while efficient, are strongly unstable, while Kesten’s EADA mechanism is both Pareto efficient and essentially stable.

12.30 P.M. Lunch
1:00 P.M. Outlook Talk 1 – Al Roth, Stanford

Frontiers of Kidney Exchange

Abstract: Kidney exchange is different from many market design efforts I’ve been involved in, because it affects the everyday conduct of transplant centers, so we’re constantly adapting to their big strategy sets…(in contrast to e.g. annual labor markets or school choice which don’t affect the daily conduct of residency programs and schools …)The early design challenges in kidney exchange mostly involved dealing with congestion (and the solutions involved long chains, standard acquisition charges, and attempts to better elicit surgeons’ preferences over kidneys).The current challenges to kidney exchange involve creating more thickness in the markets, and I’ll touch on several new initiatives:

·  1. Frequent flier programs to encourage transplant centers to enroll more of their easy to match pairs;

·  2. Global kidney exchange;

·  3. Information deserts: populations of Americans who don’t get transplants;

·  4. Deceased donor initiated chains;

a. Increasing deceased donation: military share, priority in Israel

2:00 P.M. Session 3
On likely solutions of the stable matching problem with unequal numbers of men and women

Speaker: Boris Pittel

Abstract: Consider a set of men and a set of women contemplating selection of a marriage partner. It is assumed that each man and each woman has his/her preferences for a marriage partner, with no ties allowed. A maximal matching is called stable if there is no unmarried pair who prefer each other to their respective partners in the matching. A classic theorem, due to Gale and Shapley, asserts that, given any system of preferences, there exists at least one stable matching. Most of algorithmic/probabilistic research had been focused on the case of two sides having the same size. Recently Ashlagi, Kanoria and Leshno discovered that even a relatively slight difference between two sizes leads to a dramatic change in the likely properties of the stable matchings. As a follow-up, we extend our previous work on the expected number of stable matchings for the balanced case and derive an asymptotic formula for the expected number of stable matchings for the full range of tthe unequal sizes. For the size difference 1, the expected number is instantly smaller than its counterpart for the balanced case by a squared logarithmic factor, but remains quite sizable. As soon as the size difference is of the order of smaller size, the expected, whence the likely, number of stable matchings becomes bounded as both sizes grow indefinitely.

Circulation under Responsive Preferences

Speakers: Peter Biro, Flip Klijn and Szilvia Papai

Abstract: We study markets in which each agent is endowed with multiple units of an indivisible and agent-specific good. Monetary compensations are not possible. An outcome of a market is given by a circulation which consists of a balanced exchange of goods. Agents only have (responsive) preferences over the bundles they receive.We prove that for general capacity configurations there is no circulation rule that satisfies individual rationality, Pareto-efficiency, and strategy-proofness. We characterize the capacity configurations for which the three properties are compatible, and show that in this case the Circulation Top Trading Cycle (cTTC) rule is the unique rule that satisfies all three properties. We explore the incentive and efficiency properties of the cTTC rule for general capacity configurations and provide a characterization of the rule for lexicographic preferences.Next, we introduce and study two families of individually rational serial rules in which agents sequentially choose single goods or bundles. We show that in the first (second) case the rules are Pareto-efficient for lexicographic (responsive) preferences. Finally, we consider the family of Segmented Trading Cycle (STC) rules where agents are required to exchange their goods in market segments. We show that STC rules are strategy-proof.

Strategy-Proof Tie-Breaking

Speakers: Lars Ehlers and Alexander Westkamp

Abstract: A set of indivisible objects is allocated among agents with strict preferences. Each object has a weak priority ranking of the agents. A collection of priority rankings, a priority structure, is solvable if there is a strategy-proof mechanism that is constrained efficient, i.e. that always produces an agent-optimal stable matching. We characterize all solvable priority structures satisfying the following two restrictions:

(A) Either there are no ties, or there is at least one four-way tie.

(B) For any two agents i and j, if there is an object that assigns higher priority to i than j, there is also an object that assigns higher priority to j than i.

We show that there are at most three types of solvable priority structures: The strict type, the house allocation with existing tenants (HET) type, where, for each object, there is at most one agent who has strictly higher priority than another agent, and the task allocation with unqualied agents (TAU) type, where, for each object, there is at most one agent who has strictly lower priority than another agent. Out of these three, only HET priority structures are shown to admit a strongly group strategy-proof and constrained ecient mechanism.

Strategy-proof Pareto Improvement

Speakers: Samson Alva and Vikram Manjunath

Abstract: We consider a general model of resource allocation with unit-demand agents, each of whom have an outside option of privately known value. The model encompasses (priority-based) object allocation, matching with contracts, provision of a public good when agents may choose not to participate, and more. If a mechanism designer’s choice of a strategy-proof allocation rule must weakly Pareto-dominate an individually rational and participation-maximal benchmark rule, we show there is a unique solution to his problem, if one exists. As a consequence, for many market design applications, many known rules are on the efficient frontier of strategy-proof rules.

We relate strategy-proof Pareto improvements of a rule with expansions in the set of participating agents. This implies a revenue equivalence result for dominant strategy incentive compatible and individually rational rules in settings with quasilinear preferences and transfers.

Effect of selfish choices in deferred acceptance with short lists

Speakers: Hedyeh Beyhaghi, Daniela Saban and Eva Tardos

Abstract: We study the outcome of deferred acceptance when prospective medical residents can only apply to a limited set of hospitals. This limitation requires residents to make a strategic choice about the quality of hospitals they apply to. Through a mix of theoretical and experimental results, we study the effect of this strategic choice on the preferences submitted by participants, as well as on the overall welfare. We find that residents’ choices in our model mimic the behavior observed in real systems where individuals apply to a mix of positions consisting mostly of places where they are reasonably likely to get accepted, as well as a few “reach” applications to hospitals of very high quality, and a few “safe” applications to hospitals of lower than their expected level. Surprisingly, the number of such “safe” applications is not monotone in the number of allowed applications. We also find that selfish behavior can hurt social welfare, but the deterioration of overall welfare is very minimal.

3.40 P.M. Break
4:00 P.M. Session 4
Assortment Planning in School Choice

Speaker: Peng Shi

Abstract: In many public school systems across the US, school choice has become the preferred alternative to the traditional method of assigning each student to a neighborhood school. In a typical school choice system, each student submits a preference ranking for a set of schools called the student’s \emph{menu}. The school board then assigns students to schools using the Gale-Shapley deferred acceptance (DA) algorithm, which takes into account \emph{priorities} that differentiate certain types of students, as well as \emph{quotas} for students at each school. The menus, priorities and quotas are policy levers with which the school board may induce socially desirable outcomes. This paper presents a systematic approach for optimizing these policy levers.

Our methodology is based on a novel connection between stable matching and assortment planning, which allows us to approximate school choice as a convex optimization problem. The key to solving this convex optimization is to find an assortment of schools for each student type that maximizes the sum of utilities for this type and externalities for others. We refer to this as the “socially-optimal assortment planning” problem, and show that it is a generalization of the revenue-maximizing assortment planning problem studied in the revenue management literature. We give efficient algorithms for the socially-optimal assortment planning problem for the multinomial logit (MNL), nested logit, and Markov chain based utility distributions.

We demonstrate the effectiveness of our methodology by applying it to actual data from Boston Public Schools. We construct optimized menus and priority distributions that outperform the status quo, improving the expected utilities of students and the predictability of the assignment outcome while maintaining the same amount of busing.

The Iterative Deferred Acceptance Mechanism

Speakers: Inacio Bo and Rustamdjan Hakimov

Abstract: We introduce a new mechanism for matching students to schools or universities, denoted Iterative Deferred Acceptance Mechanism (IDAM), inspired by procedures currently being used to match millions of students to public universities in Brazil and China. Unlike most options available in the literature, IDAM is not a direct mechanism. Instead of requesting from each student a full preference over all colleges, the student is instead repeatedly asked to choose one college among those which would accept her given the current set of students choosing that college. Although the induced sequential game has no dominant strategy, when students simply choose the most preferred college in each period (denoted the straightforward strategy), the matching that is produced is the Student Optimal Stable Matching. Moreover, under imperfect information, students following the straightforward strategy is an Ordinal Perfect Bayesian Equilibrium. Based on data from 2016, we also provide evidence that, due to shortcomings which are absent in the modified version that we propose, the currently used mechanism in Brazil fails to assist the students with reliable information about the universities that they are able to attend, and are subject to manipulation via cutoffs, a new type of strategic behavior that is introduced by this family of iterative mechanisms and observed in the field.

Dynamic Matching in School Choice: Efficient Seat Reallocation After Late Cancellations

Speakers: Itai Feigenbaum, Yash Kanoria, Irene Lo and Jay Sethuraman

Abstract: In many centralized school admission systems, a significant fraction of allocated seats are later vacated, often due to students obtaining better outside options. We consider the problem of reassigning these seats in a fair and efficient manner while also minimizing the movement of students between schools. Centralized admissions are typically conducted using the deferred acceptance (DA) algorithm, with a lottery used to break ties caused by indifferences in school priorities. The key idea we introduce is to reassign vacated seats using a suitable permutation of the first round lottery numbers. In particular, we show that a mechanism based on a simple reversal of the first round lottery order performs the best among all truthful mechanisms satisfying some natural efficiency and fairness properties. Empirical investigations based on data from NYC high school admissions support our theoretical findings.

5:00 P.M. Invited Talk 2 – Aaron Roth, UPENNApproximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)

Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)

Abstract: In this talk, we will walk through a case study of how techniques developed to design “stable” algorithms can be brought to bear to design asymptotically dominant strategy truthful mechanisms in large markets, without the need to make any assumptions about the structure of individual preferences. Specifically, we will consider the many-to-one matching problem, and see a mechanism for computing school optimal stable matchings, that makes truthful reporting an approximately dominant strategy for the student side of the market. The approximation parameter becomes perfect at a polynomial rate as the number of students grows large, and the analysis holds even for worst-case preferences for both students and schools.

Joint work with: Sampath Kannan, Jamie Morgenstern, and Zhiwei Steven Wu.

5.45 P.M. Break
6:00 P.M. Poster Lightning Talks
6.30 P.M. Reception and Poster Session
8:00 P.M. END
8:00 A.M. Breakfast
8.45 A.M. Invited Talk 3 — Michael Ostrovsky, Stanford

Matching under preferences: beyond the two-sided case

Abstract: I will present an overview of several recent papers showing that most of the key results of matching theory generalize naturally to a much richer setting: trading networks. These networks do not need to be two-sided, and agents do not have to be grouped into classes (“firms”, “workers”, and so on). What is essential for the generalization is that the bilateral contracts representing relationships in the network have a direction (e.g., one agent is the seller and the other is the buyer), and that agents’ preferences satisfy a suitably adapted substitutability notion. For this setting, for the cases of discrete and continuous sets of possible contracts, I will discuss the existence of stable outcomes, the lattice structure of the sets of stable outcomes, the relationship between various solution concepts (stability, core, competitive equilibrium, etc.), and other results familiar from the literature on two-sided markets.

9.30 A.M. Session 5
Trading Networks with Bilateral Contracts

Speakers: Alexander Teytelboym, Tamas Fleiner, Zsuzsanna Jankó and Akihisa Tamura

Abstract: We consider general networks of bilateral contracts that include supply chains. We define a new stability concept, called trail stability, and show that any network of bilateral contracts has a trail-stable outcome whenever agents’ choice functions satisfy full substitutability. Trail stability is a natural extension of chain stability, but is a stronger solution concept in general contract networks. Trail-stable outcomes are not immune to deviations of arbitrary sets of firms. In fact, we show that outcomes satisfying an even more demanding stability property – full trail stability – always exist. For fully trail-stable outcomes, we prove results on the lattice structure, the rural hospitals theorem, strategy-proofness and comparative statics of firm entry and exit. We pin down a condition under which trail-stable and fully trail-stable outcomes coincide. We then completely describe the relationships between various other concepts. When contracts specify trades and prices, we also show that competitive equilibrium exists in networked markets even in the absence of fully transferrable utility. The competitive equilibrium outcome is (fully) trail-stable.

Too Good to Fire: Non-Assortative Matching to Play a Dynamic Game

Speakers: Benjamin Sperisen and Thomas Wiseman

Abstract: We study stable outcomes in a one-to-one matching market with firms and workers. The model endogenizes how transferable utility is within a match: when a firm-worker pair is matched, they play an infinite-horizon discounted dynamic game with one-sided, observable effort. Partners’ types are complementary in determining the maximal feasible payoffs. In our setting, the classic result that with complementary types stable matchings are positively assortative does not hold. Increasing the quality of a match harms dynamic incentives, because a firm cannot credibly threaten to fire a worker who is productive even with low effort. Thus, firms may prefer lower-type workers who will exert more effort. Our analysis suggests a new interpretation of efficiency wages: committing to pay a high wage can improve effort incentives indirectly by making the firm more willing to walk away.

Matching Auctions

Speakers: Alessandro Pavan and Daniel Fershtman

Abstract: We study mediated many-to-many matching in markets in which valuations evolve over time as the result of shocks, learning through experimentation, or a preference for variety. The matching dynamics that maximize either the platform’s profits, or welfare can be sustained through auctions implementing the matches with the highest bilateral score up to capacity. In equilibrium, bidding is straight-forward and myopic. The analysis also sheds light on the merits of regulating such markets. When match values are positive, proÖt maximization involves fewer and shorter interactions than welfare maximization. This conclusion need not extend to markets where certain agents dislike certain interactions.

10.30 A.M. Break
10.50 A.M. Session 6
Communication Requirements and Informative Signaling in Matching Markets

Speakers: Itai Ashlagi, Mark Braverman, Yash Kanoria and Peng Shi

Abstract: We study the amount of communication needed to find a stable matching in a two-sided matching market with private preferences when agents have some knowledge of the preference distribution. We show that in a two-sided market with workers and firms, when the preferences of workers are arbitrary and private and the preferences of firms follow a multinomial-logit (MNL) choice model with commonly known and heterogeneous parameters, there exists an algorithm that finds a stable matching with high probability and requires at most $O^*(\sqrt{n})$ bits of communication per agent. (We show that this is the best possible under this setting.) The algorithm, which we call communication efficient deferred acceptance (CEDA), is a modification of the deferred acceptance algorithm with workers applying. In this algorithm, firms help workers better target applications by signaling workers that they idiosyncratically like and broadcasting to the market a qualification requirement to discourage those with no realistic chances from applying. In the special case in which preferences of both workers and firms follow a tiered structure, we show that the signaling can be done in a parallel and decentralized way. In terms of incentives, the protocols we propose inherit many properties of DA under full preference elicitation. In large markets with a small core, they are incentive compatible for everyone. These results yield insights on how matching markets can be better organized to reduce congestion.

A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas

Speaker: Yu Yokoi

Abstract: Classified stable matching, proposed by Huang, describes a matching model between academic institutes and applicants, in which each institute has upper and lower quotas on classes, i.e., subsets of applicants. Huang showed that it is NP-hard to decide whether there exists a stable matching or not in general. On the other hand, he showed that the problem is solvable if classes form a laminar family. For this case, Fleiner and Kamiyama gave a concise interpretation in terms of matroids and showed the lattice structure of stable matchings.In this paper, we introduce stable matchings on generalized matroids, extending the model of Fleiner and Kamiyama. We design a polynomial-time algorithm which finds a stable matching or reports the nonexistence. We also show that, the set of stable matchings, if nonempty, forms a lattice with several significant properties. Furthermore, we extend this structural result to the polyhedral framework, which we call stable allocations on generalized polymatroids.

The weighted stable matching problem

Speakers: Linda Farczadi and Natalia Guricanova

Abstract: We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general. Our contribution is two fold: a polyhedral characterization and an approximation algorithm. Previously Chen et al. have shown that the stable matching polytope is integral if and only if the subgraph obtained after running phase one of Irving’s algorithm is bipartite. We improve upon this result by showing that there are instances where this subgraph might not be bipartite but one can further eliminate some edges and arrive at a bipartite subgraph. Our elimination procedure ensures that the set of stable matchings remains the same, and thus the stable matching polytope of the final subgraph contains the incidence vectors of all stable matchings of our original graph. This allows us to characterize a larger class of instances for which the weighted stable matching problem is polynomial-time solvable. We also show that our edge elimination procedure is best possible, meaning that if the subgraph we arrive at is not bipartite, then there is no bipartite subgraph that has the same set of stable matchings as the original graph. We complement these results with a 2-approximation algorithm for the minimum weight stable matching problem for instances where each agent has at most two possible partners in any stable matching. This is the first approximation result for any class of instances with general weights.

New and simple algorithms for stable flow problems

Speakers: Ágnes Cseh and Jannik Matuschke

Abstract: Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network, in which the vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk.Fleiner established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmenting-path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocation as a black-box subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges in an elegant way. Finally, we study the stable multicommodity flow model by Király and Pap. We present several graph-based reductions that show that it is without loss of generality to assume that no commodity-specific preference lists at the vertices and no commodity-specific capacities on the edges exist. We further show that it is NP-complete to decide whether an integral solution exists.

Stable Matching with Uncertain Pairwise Preferences

Speakers: Haris Aziz, Peter Biro, Tamas Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei and Baharak Rastegari

Abstract: In this paper we study a two-sided matching problem under preferences, where the agents have independent pairwise comparisons on their possible partners and these preferences may be uncertain. In this case preferences may be intransitive and agents may even have certain cycles in their preferences; e.g. an agent $a$ may prefer $b$ to $c$, $c$ to $d$, and $d$ to $b$, all with probability one. If an instance has such a cycle, then there may not exist any matching that is stable with positive probability. We focus on the computational problems of checking the existence of possibly and certainly stable matchings, i.e., matchings whose probability of being stable is positive or one, respectively. We show that finding possibly stable matchings is NP-hard, even if only one side can have cyclic preferences.

On the other hand we show that the problem of finding a certainly stable matching is polynomial-time solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NP-hard when both sides can have cyclic preferences. The latter complexity result also implies the hardness of finding a kernel in a special class of directed graphs.

12.30 P.M. Lunch
1:00 P.M. Lunch w/Outlook Talk 2 — David Manlove, University of Glasgow

Selected Algorithmic Open Problems in Matching Under Preferences

Abstract: The research community working on matching problems involving preferences has grown in recent years, but even so, plenty of interesting open problems still exist, many with large-scale practical applications.  In this talk I will outline some of these open problems that are of an algorithmic flavour, thus giving an outlook on some of the research challenges in matching under preferences that the computer science community might seek to tackle over the next decade.

2:00 P.M. Session 7

Speakers: Avinatan Hassidim, Assaf Romm and Ran Shorrer

Abstract: We present direct field evidence of preference misrepresentation under deferred acceptance. A large fraction of highly educated participants, who had been informed about the strategy-proof nature of the mechanism in numerous ways, failed to play truthfully: they ranked a non-funded position above a funded position in the same program. This is despite being informed that rank-ordered lists are never made public, that funding is a positive signal of ability, and that funding comes with no strings attached. Preference misrepresentation is associated with weaker applicants. A laboratory experiment documents a strong negative causal relationship between applicants’ expected desirability and preference misrepresentation.

Stable matching mechanisms are not obviously strategy-proof

Speakers: Itai Ashlagi and Yannai A Gonczarowski

Abstract: Many two-sided matching markets, from labor markets to school choice programs, use a clearinghouse based on the applicant-proposing deferred acceptance algorithm, which is well known to be strategy-proof for the applicants. Nonetheless, a growing amount of empirical evidence reveals that applicants misrepresent their preferences when this mechanism is used. This paper shows that no mechanism that implements a stable matching is obviously strategy-proof for any side of the market, a stronger incentive property than strategy-proofness introduced by Li (2015). A stable mechanism that is obviously strategy-proof for applicants is introduced for the case in which agents on the other side have acyclical preferences. Our findings suggest that strategic reasoning in two-sided markets requires more cognitive effort by participants than in one-sided markets.

Strategic Stable Marriage

Speakers: James Bailey and Craig Tovey

Abstract: We study stable marriage where individuals strategically submit private preference information to a publicly known stable marriage algorithm. We prove that no stable marriage algorithm ensures actual stability at a Nash equilibrium when individuals are strategic. Thus the set of Nash equilibria provides no predictive value nor guidance for mechanism design. We propose the following new minimal dishonesty equilibrium refinement, supported by experimental economics results: an individual will not strategically submit preference list $L$ if there exists a more honest $L’$ that yields as preferred an outcome. Then for all marriage algorithms satisfying monotonicity and IIA, every minimally dishonest equilibrium yields a sincerely stable marriage. This result supports the use of algorithms less biased than the (Gale-Shapley) man-optimal, which we prove yields the woman-optimal marriage in every minimally dishonest equilibrium. However, bias cannot be totally eliminated, in the sense that no monotonic IIA stable marriage algorithm is certain to yield the egalitarian-optimal marriage in a minimally dishonest equilibrium — thus answering an open question of Gusfield and Irving’s in the negative. Finally, we show that these results extend to student placement problems, where women are polyandrous and honest. but not to admissions problems, where women are both polyandrous and strategic.

Making it Safe to Use Centralized Markets: Epsilon – Dominant Individual Rationality and Applications to Market Design

Speakers: Ben Roth and Ran Shorrer

Abstract: A critical, yet under-appreciated feature of market design is that centralized markets operate within a broader context; often market designers cannot force participants to join a centralized market. Well-designed centralized markets must induce participants to join voluntarily, in spite of pre-existing decentralized institutions they may already be using. We take the view that centralizing a market is akin to designing a mechanism to which people may voluntarily sign away their decision rights. We study the ways in which market designers can provide robust incentives that guarantee agents will participate in a centralized market. Our first result is negative and derives from adverse selection concerns. Near any game with at least one pure strategy equilibrium, we prove there is another game in which no mechanism can eliminate the equilibrium of the original game.

In light of this result we offer a new desideratum for mechanism and market design, which we term epsilon-dominant individual rationality. After noting its robustness, we establish two positive results about centralizing large markets. The first offers a novel justification for stable matching mechanisms and an insight to guide their design to achieve epsilon-dominant individual rationality. Our second result demonstrates that in large games, any mechanism with the property that every player wants to use it conditional on sufficiently many others using it as well can be modified to satisfy epsilon-dominant individual rationality while preserving its behavior conditional on sufficient participation. The modification relies on a class of mechanisms we refer to as random threshold mechanisms and resembles insights from the differential privacy literature.

Integrating Schools for Centralized Admissions

Speakers: Mehmet Ekmekci and M. Bumin Yenmez

Abstract: As school districts integrate charter schools for centralized admissions in Denver, New Orleans, Newark and Washington D.C., some schools have stayed out. Likewise, there is a recent proposal in Boston to unify public school admissions in a centralized clearinghouse. We provide a new framework to study the incentives of a school to join a clearinghouse and we show that each school prefers to remain out of the system when others join it. Therefore, our analysis provides an explanation of why some charter schools have evaded (or may evade) the clearinghouse. To overcome this issue, we propose two schemes that can be used by policymakers to incentivize schools to join the system, which achieves the desired integration of schools.

3.40 P.M. Break
4:00 P.M. Session 8
Competitive Equilibrium and a Dynamic Auction for Allocation with Priorities

Speakers: Isa Hafalir and Tayfun Sonmez

Abstract: We consider an assignment problem where a set of items need to be allocated to a set of agents. Agents have different priorities for claiming different items, and personalized (discrete) pricesterms of the contracts can be used in the allocation process. We allow each item having some copies are for sale and some copies for free. In this model, we  first define a competitive equilibrium with personalized prices and show that there exists a strategy-proof mechanism that results in the best competitive equilibrium. We then propose a Nash incentive-compatible dynamic auction that results in the same competitive equilibrium allocation.

Competitive Equilibria with Indivisible Goods and Generic Budgets

Speakers: Moshe BabaioffNoam Nisan and Inbal Talgam-Cohen

Abstract: We study competitive equilibria in the basic Fisher market model, but with indivisible goods. Such equilibria fail to exist in the simplest possible market of two players with equal budgets and a single good, yet this is a knife’s edge instance as equilibria exist once budgets are not precisely equal. Is non-existence of equilibria also a knife-edge phenomenon in complex markets with multiple goods? Our computerized search has indicated that equilibria often exist when budgets are “generic”. We prove several existence results both for the case of general preferences and for the special case of additive preferences, and relate competitive equilibria to notions of fair allocation of indivisible items.

Object Allocation via Immediate-Acceptance: Characterizations and an Affirmative Action Application

Speakers: Battal Dogan and Bettina Klaus

Abstract: Which mechanism to use to allocate school seats to students still remains a question of hot debate. Meanwhile, immediate acceptance mechanisms remain popular in many school districts. We formalize desirable properties of mechanisms when respecting the relative rank of a school among the students’ preferences is crucial. We show that those properties, together with well-known desirable resource allocation properties, characterize immediate acceptance mechanisms. Moreover, we show that replacing one of the properties, consistency, with a weaker property, non-bossiness, leads to a characterization of a much larger class of mechanisms, which we call choice-based immediate acceptance mechanisms. It turns out that certain objectives that are not achievable with immediate acceptance mechanisms, such as affirmative action, can be achieved with a choice-based immediate acceptance mechanism.

Fair Division of goods, bads, and satiable items

Speakers: Anna BogomolnaiaHerve MoulinFedor Sandomirskiy and Elena Yanovskaya

Abstract: How to divide items that can be desirable (goods), or not (bads), and can also allow satiation? When all items are goods and preferences are represented by utility functions homothetic and concave, the Competitive Equilibrium with Equal Incomes (CEEI) is famously compelling because it maximizes the Nash product of utilities, is single-valued and easy to compute. The CEEI to divide only bads captures similarly all critical points of the Nash product in the efficient frontier. But it is far from resolute or easy to compute: the number of allocationsdistinct welfare-wise can be exponential in the number of agents and items.General problems behave as if we divide only goods, or as if we divide only bads. In the former case, everyone who can is strictly better off than zero (the ex ante utility), the CEEI is unique and maximizes the Nash product of utilities. In the latter everyone is strictly worse off than zero, and the CEEI collects all critical points of the Nash product of disutilities. Thus the task of dividing a mixed manna is either good news for everyone, or bad news for everyone.We refine our results in the practically important case of linear preferences, where the axiomatic comparison between the division of goods and that of bads is especially sharp. When we divide goods and the manna improves, everyone weakly benefit under the CEEI rule; but no reasonable rule to divide bads can be similarly Resource Monotonic. Also, the much larger set of Non Envious and Efficient divisions of bads can be disconnected so that it will admit no continuous selection.

5.20 P.M. Break
5.30 P.M. Invited Talk 4 — Marek Pycia, UCLA

Invariance and Matching Market Outcomes

Abstract: The empirical studies of school choice provide evidence that standard measures of admission outcomes are the same for many Pareto efficient mechanisms that determine the market allocation based on ordinal rankings of individual outcomes. The paper shows that two factors drive this intriguing puzzle: market size and the invariance properties of the measures for which the regularity has been documented. In addition, the talk will explore the consequences of these findings: the usefulness of non-invariant outcome measures and of mechanisms that elicit preference intensities.

6.15 P.M. Closing Remarks
6.30 P.M. END

It’s really great to go back to Peking University 🙂

Here is the link of the news  (updated on June 30): http://www.econ.pku.edu.cn/displaynews.php?id=101395

Conference Agenda

June 25 – 26, 2016

Room 307, School of Economics, Peking University

Organizers: Xuezheng Qin and Qingmin Liu

Sponsor: School of Economics, Peking University

June 25 (Saturday)

08:00 – 08:30 Registration

08:30 – 08:45 Welcome Speech

Qixiang Sun, Professor and Dean, School of Economics at PKU

08:45 – 09:45 Xi Weng (Peking University):

“A Theory of Organizational Dynamics: Internal Politics and Efficiency”

(joint with Hongbin Cai and Hong Feng)

09:45 – 10:45 Dilip Abreu (Princeton University):

“Bargaining with One‐sided Asymmetric Information under Ideal

Reputational Conditions” (joint work with David Pearce and Ennio


10:45 – 11:05 Photo Session

Venue: Outside the main entrance of SEPKU Building (Ground Floor)

11:05 – 11:25 Coffee Break outside Room 307, SEPKU Building

11:25 – 12:25 Ning Sun (Shanghai University of Economics and Finance)

“A Theory of Marriage with Mutually Consented Divorces”

12:25 – 14:00 Lunch in Room B103 (Underground level 1 of SEPKU Building)

14:00 – 15:00 Xianwen Shi (University of Toronto):

“The Dimensions of Consensus” (joint with Alex Gershkov and Benny


15:00 – 16:00 Wing Suen (Hong Kong University):

Competition for Attention in the News Media Market(joint with

Heng Chen)

16:00 – 16:20 Coffee Break outside Room 307, SEPKU Building

16:20 – 17:20 Felix Kübler (University of Zurich):

The identification of beliefs from asset demand(joint with Herakles


18:30 – 20:30 Reception Dinner (by invitation only)

Venue: ZHILIHUIGUAN Restaurant

June 26 (Sunday)

09:00 – 10:00 Zenan Wu (Peking University):

“Managerial Turnover and Entrenchment” (joint with Xi Weng)

10:00 – 11:00 Sylvain Chassang (Princeton University):


11:00 – 11:20 Coffee Break outside Room 307, SEPKU Building

11:20 – 12:20 Tilman Börgers (University of Michigan):

“Revealed Relative Utilitarianism” (joint with Yan-Min Choo)

12:20 – 14:00 Lunch in Room B103 (Underground level 1 of SEPKU Building)

14:00 – 15:00 Qingmin Liu (Columbia University):

“Auctions with Limited Commitment” (joint with Konrad Mierendorff

and Xianwen Shi)

15:00 – 16:00 Jimmy Chan (Fudan University):

“Fiscal Receipt Lottery”

16:00 – 16:20 Coffee Break outside Room 307, SEPKU Building

16:20 – 17:20 Cheng Sun (Peking University):

Reputation and Social Media

Conference Photo - PKU Summer Conference on Microeconomic Theory


I wrote this article to introduce the contributions of Alvin Roth, Atila Abdulkadiroglu, Parag Pathak and Tayfun Sönmez to public school choice in the U.S.


Here is the link: http://paper.nandu.com/nis/201501/08/314808.html




胡雨青 经济学硕士  目前在世界银行任职

王健 经济学博士  美联储达拉斯联邦储备银行  高级经济学家兼政策顾问






后来是什么样的机制克服了这种录取过程中的缺陷呢?10年前,几位博弈论经济学家包括阿尔文.罗斯 (Alvin Roth), 阿迪拉. 阿布杜卡迪罗古路 (Atila Abdulkadiroglu),帕拉戈.帕沙克 (Parag Pathak)和塔伊丰.森梅兹 (Tayfun Sönmez) 对择校机制进行了研究,并提出了改进的方法。他们的方法基于一种由大卫.盖尔 (David Gale)和劳埃德.沙普利(Lloyd Shapley)在1962年首创的延迟接受算法 (Gale-Shapley Deferred Acceptance Algorithm)。学生于是再也不需要担心自己不被第一志愿录取而丧失其他学校的录取机会,同时学校也不必担心错失优秀学生的情况。这种贡献在一定程度上帮助了罗斯和沙普利获得了2012年的诺贝尔经济学奖。


虽然同样的机制长期以来在美国公立学校的录取过程中被广泛采用,由于罗斯等人最早是对波士顿地区进行研究,因此他们把这种机制命名为“波士顿机制”(Boston Mechanism)。波士顿机制的配对规则是这样的:

第​一​轮:学校只考虑第一志愿的学生,根据成绩等优先条件(priority) 给申请学生排序,然后按照排名从前往后依次录取,直到学校名额被录满;如果学校的录取名额大于第一志愿学生的总人数,





波士顿机制存在一个严重的不足:如果一个学生在第一​轮没被第一志愿的学校录取,而且他申请的其他志愿的的学校在第一轮中就已经录满,那么这个学生即使成绩远超过第二和第三志愿的要求,也无法被这些学校录取了。这种风险导致很多学生不敢把他们最喜欢的学校列在申请第一位,而更保守地把他们有更大录取概率的学校列在第一位。这种志愿和真实偏好不一致的现象,在博弈论中被称为“非抗操控性”(non strategy-proof)。






这种录取过程一直持续到所有学生都被录取,或者所有学校的名额都被录满,所有“预录取”的学生在最后一轮中被正式录取​,此时的录取才是最终结果​。正是因为这种正式录取被延迟到最后一轮的特点,这种算法被经济学家命名为“盖尔-沙普利-延迟接受算法” (Gale-Shapley Deferred Acceptance Algorithm)。




中国高考近十年来很多省份在填报志愿的制度上也在进行改革,逐步由“顺序志愿”改到“平行志愿”。 从2003年由湖南省率先实施,到目前为止已经有包括江苏、上海、新疆等28个省市自治区实行了“平行志愿” 。在机制上,顺序志愿本质上是波士顿机制,平行志愿本质上是延迟接受算法,学生的成绩决定了他们录取过程中的“优先权”。平行志愿很大程度上减少了“高分低就”或“低分高就”的不公平现象。比如,今年是北京实行平行志愿的第一个年份,一批第一志愿满足率高达97%,较往年大幅提升 。





Abdulkadiroglu, A., & Sonmez, T. (2003). School Choice: A Mechanism Design Approach. American Economic Review, 93(3), 729–747. Retrieved from http://www.jstor.org/stable/10.2307/3132114

Abdulkadiroglu, A., Pathak, P. A., & Roth, A. E. (2005). The New York city high school match. American Economic Review, 95(2), 364–367. Retrieved from http://www.jstor.org/stable/10.2307/4132848

新浪教育. (2014)“北京首次平行志愿,高考呈现四大特点”. Retrieved from http://edu.sina.com.cn/gaokao/2014-09-10/1721433217.shtml

Tullis. T. (2014) How Game Theory Helped Improve New York City’s High School Application Process. Retrieved fromhttp://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html?_r=0



My presentation at Students’ poster session: Poster for Summer School


2014 Economics School poster


Econ 206 Term Paper, finally done!!! Thank Prof. Kibris and Prof. Becker!

Abstract: Pre-exam recruitment (PER) self-arranged by colleges in China is the alternative admission method outside the centralized National College Entrance Examination (NCEE) System, and it has become increasingly prevalent among colleges over the recent years. We attribute this rapid spread of PER to the reform of the admission policy which renders the admission mechanism vulnerable to college manipulation. The former “sequential mechanism” is equivalent to Boston mechanism, and it is not strategy-proof for students or colleges. Under that old mechanism, students strategize in a sophisticated level that leaves no incentive for colleges to manipulate, since the overall space for Pareto improvement is limited. The reform brings about the “parallel mechanism”, which generates the matchings that are equivalent to both the student-optimal and college-optimal deferred acceptance algorithm under the acyclic priority structure. Since students can only submit a fixed length of preference list in the application, this new mechanism is strategy-proof for them. However, it is manipulable for individual colleges because PER allows them to reallocate their type specific quotas. Colleges can reduce the quality gap between different types of students, so as to improve the overall qualities of students admitted. However, unlike the manipulation under the inefficient “sequential mechanism”, the “parallel mechanism” which is college optimal has no space for Pareto improvement for all the colleges as a whole. Under this mechanism, individual college benefits themselves at the expense of hurting other colleges, but some students of cyclic preferences strictly benefits from PER as they are able to attend their more favorable colleges. In equilibrium, all the colleges participate in PER and allocate their quotas in accordance with the distributions of students across types. However, this equilibrium is unattainable as the proportion of capacities set aside for PER can never be 100% under the existing education policy. Colleges thus keep enlarging this proportion as a response of other colleges’ PER, and this may partly explain why we observe the increasing prevalence of PER.