Workshop website: http://marketplaceinnovation.net/
It was such a nice stay at Stanford! Thanks for all the feedback 🙂
Workshop website: http://marketplaceinnovation.net/
It was such a nice stay at Stanford! Thanks for all the feedback 🙂
“Understanding cognition and decision making by children”
May 4 – 5, 2017
PROGRAM
Thursday, May 4, 20178:45 – 9:15 Continental Breakfast
9:15 – 9:30 Introductory remarks
9:30 – 10:15 “The role of agency in regret and relief in 3 to 10yearold children”. Giorgio Coricelli (USC)
10:15 – 11:00 “Young Children’s Exploration of Alternative Possibilities”. Henrike Moll (USC)
11:00 – 11:30 Coffee break
11:30 – 12:15 “Navigating Uncertainty: Neural Correlates of Decisions from Experience in Adolescence”. Wouter van de Bos (Max Planck – Berlin)
12:15 – 1:45 Lunch
1:45 – 2:30 “The Costs and Benefits of Growing Up”. Michael Norton (Harvard U.)
2:30 – 3:15 “Using economic experiments to detect drivers of behavior at early ages: Evidence from a large field experiment in Chicago”. Ragan Petrie (Texas A&M)
3:15 – 3:45 Coffee break
3:45 – 4:30 “Does the little mermaid compete? An experiment on competitiveness with children”. Marco Piovesan (U. Copenhagen)
6:30 Dinner (by invitation)
Friday May 5, 2017 Radisson Los Angeles at USC
9:00 – 9:30 Continental Breakfast
9:30 – 10:15 “Altruism and strategic giving in children and adolescents”. Isabelle Brocas (USC)
10:15 – 11:00 “Theory of Mind among Disadvantaged Children”. Aldo Rustichini (U. Minnesota)
11:00 – 11:30 Coffee break
11:30 – 12:15 “The development of reciprocal sharing in relation to intertemporal choice”. Felix Warneken (Harvard U.)
12:15 – 1:45 Lunch
1:45 – 2:30 “Group and Normative Influences on Children’s Exchange Behavior”. Yarrow Dunham (Yale U.)
2:30 – 3:15 “The role of social preferences and emotions in children’s decision making a view from developmental psychology”. Michaela Gummerum (Plymouth U.)
3:15 – 3:45 Coffee Break
3:45 – 4:30 “Sociocognitive mechanisms of prosocial behavior”. Nadia Chernyak (Boston U.)
Yuqing Hu, Juvenn Woo
GARP, the generalized axiom of revealed preference, is a dichotomous notion. A dataset can either satisfy the theory of a rational consumer or violate it[1]. There are several challenges in testing GARP consistency in an experiment. One challenge comes from the nature of budget sets, as there are more individuallevel variations in expenditure than variations in prices. This causes the overlap of two budget sets, upon which the test based could bias towards the satisfaction of GARP, with the extreme case that no violation would occur if the budget sets are nested. Another challenge stems from lack of identities of consumers such that individuals have to be treated as the same for revealed preference tests (Chambers & Echenique, 2016).
A few indices have been invented to measure the degree of GARP violations. One is Afriat’s efficiency index (AEI) (Afriat, 1967), which uses the degree of “deflation” of expenditure that is needed to make GARP consistent. Other variations of AEI are Varian’s efficiency index (VEI) (Varian, 1983), and the money pump index (MPI) (Echenique, Lee, & Shum, 2011).
There is a modest amount of literature in experimental economics that test GARP consistency, which is summarized below.
Battalio et al.(1973) pioneered applying GARP consistency in experimental study. They ran field experiments among psychotic patients to let them exchange tokens for different consumption goods. They induced a variety of different budget sets by changing the value of tokens, and they found that if small measurement errors were allowed, then almost all patients’ behavior was consistent with GARP.
Sippel (1997) ran lab experiments in which 42 students were asked to repeatedly choose a bundle of priced entertaining items under different standard budget constraints. Individuals were paid in consumption goods, and were required to actually consume the goods at the experiment. The experiment showed 63% of subjects made choices violating GARP, though the median number of violations over all subjects was only 1 of 45 choices. The number did not change even if the study perturbed demand close to actual demand. Even though the (remarkably) low number of violations for individual indicates the subjects were highly motivated when making choices, a majority of subjects could not be classified as rational in the sense of utility maximization.
Harbaugh, Krause and Berry (2001) examined the development of choice behavior for kids. The study conducted simple choice experiments over cohorts of second graders, sixth graders, and undergraduates. They measured and compared number of GARP violations. It found out that for the particular test, about 25% of 7yearolds, and 60% of 11yearolds were making choices consistent with GARP respectively, and there is no increase in consistency from 11 to 21year old. They also found that violations of GARP are not significantly correlated with the results of a test that measures mathematical ability in children.
Andreoni and Miller (2002) ran dictatorgame experiments to test whether the observed altruistic behavior is utilitymaximizing. They found that 98% of subjects make choices that are consistent with utility maximization. Andreoni and Miller went further than most revealedpreference exercises in estimating a parametric function of a utility function accounting for subject’s choices (about half the subjects can be classified as using a linear, CES (constant elasticity of substitution), or Leontief utility).
Hammond and Traub (2012) designed a threestage experiment, where participant advances to next stage of test only if he or she made GARP consistent choices at current one. It had been conducted over 41 (noneconomics) undergraduates. The study found that, at the 10% significance level, only 22% of subjects (compared to 6.7% of simulated random choicemaker) passed secondstage tests, and 19.5% passed all three stage tests. The result reinforced Sippel’s study suggesting that human is generally not perfectly rational. It should be noted though conditional on passing secondstage rationality, 62.5% of subjects passed thirdstage tests.
Choi, Kariv, Müller and Silverman (2014) conducted with CentERpanel survey a comprehensive study on rationality. Measuring GARP consistency by Afriat Critical Cost Efficiency Index (CCEI) and correlation with socioeconomic factors, it found that: on average, younger subjects are more consistent than older, men more than women, higheducation more than loweducation, and highincome subjects more consistent than lowincome.
Brocas, Carillo, Combs and Kodaverdian (2016) studied choice behaviors in cohorts of young and older adults, varying choice tasks from simple domain to complex domain. They showed that while both young and older adults are about equally well consistent in simple domain, older ones were observed being significantly more inconsistent in complex tasks. Beyond that, by performing working memory and fluid intelligence (IQ) test, further correlation examinations reveal that older adults’ inconsistency in complex domain can be attributed to decline in working memory and fluid intelligence.
[1] One can, however, evaluate the degree of violations.
Reference:
Afriat, S. N. (1967). The Construction of Utility Functions from Expenditure Data. International Economic Review, 8(1), 67–77.
Andreoni, J., & Miller, J. (2002). Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism. Econometrica, 70(2), 737–753.
Battalio, R. C., Kagel, J. H., Winkler, R. C., Edwin B. Fisher, J., Basmann, R. L., & Krasner, L. (1973). A Test of Consumer Demand Theory Using Observations of Individual Consumer Purchases. Western Economic Journal, XI(4), 411–428.
Brocas, I., Carillo, J. D., Combs, T. D., & Kodaverdian, N. (2016). Consistency in Simple vs. Complex Choices over the Life Cycle.
Chambers, C. P., & Echenique, F. (2016). Revealed Preference Theory. Cambridge University Press.
Choi, S., Kariv, S., Müller, W., & Silverman, D. (2014). Who Is (More) Rational? The American Economic Review, 104(6), 1518–1550.
Echenique, F., Lee, S., & Shum, M. (2011). The Money Pump as a Measure of Revealed Preference Violations. Journal of Political Economy, 119(6), 1201–1223.
Grether, D. M., & Plott, C. R. (1979). Economic Theory of Choice and the Preference Reversal Phenomenon. The American Economic Review, 69(4), 623–638.
Hammond, P., & Traub, S. (2012). A ThreeStage Experimental Test of Revealed Preference.
Harbaugh, W. T., Krause, K., & Berry, T. R. (2001). GARP for Kids: On the Development of Rational Choice Behavior. American Economic Review, 91(5), 1539–1545. http://doi.org/10.1257/aer.91.5.1539
Sippel, R. (1997). An Experiment on the Pure Theory of Consumer’s Behaviour. The Economic Journal, 107(444), 1431–1444. http://doi.org/Doi 10.1111/14680297.00231
Varian, H. R. (1983). NonParametric Tests of Consumer Behaviour. The Review of Economic Studies, 50(1), 99–110. http://doi.org/10.1007/sl08690079037x
https://www.microsoft.com/enus/research/event/matchup2017/
DAY 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 wellknown result for the school choice problem is that expost efficiency and stability may not be compatible. In the field, that tradeoff is sometimes small, sometimes big. This talk will summarize existing and new results on the drivers of this tradeoff and derive the implications for the design of priorities and tiebreaking 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 strategyproof and Pareto efficient assignment, but the combinatorial description of TTC makes it nontransparent 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 nontrivial 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 twosided 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 twosided 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 strategyproofness, deferred acceptance remains (group) strategyproof 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 testscore improvements with respect to these choice functions. Moreover, we show that some distributional objectives that can be achieved by capacitytransfers cannot be achieved by slotspecific priorities. 

Strategyproof ParetoStable Mechanisms for TwoSided Matching with Indifferences
Speakers: Nevzat Onur Domanic, ChiKit 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 polynomialtime algorithms for computing a “Paretostable” 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 polynomialtime Paretostable algorithms for stable marriage and college admissions that correspond to strategyproof mechanisms. For stable marriage, it is known that no Paretostable 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 Paretostable mechanism can be strategyproof for the colleges; our algorithm provides a mechanism that is strategyproof for the students. 

First ChoiceMaximizing School Choice Mechanisms
Speakers: Umut Dur, Timo Mennle and Sven Seuken Abstract: We investigate first choicemaximality (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 choicestability (FCS) (i.e., no student forms a blocking pair with her first choice) to be the strongest rankbased 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 selfselect 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 prioritybased 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 tradeoff. 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 nonvacuous 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 nonexperts 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 followup, 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 agentspecific 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, Paretoefficiency, and strategyproofness. 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 Paretoefficient 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 strategyproof. 

StrategyProof TieBreaking
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 strategyproof mechanism that is constrained efficient, i.e. that always produces an agentoptimal 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 fourway 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 strategyproof and constrained ecient mechanism. 

Strategyproof Pareto Improvement
Speakers: Samson Alva and Vikram Manjunath Abstract: We consider a general model of resource allocation with unitdemand agents, each of whom have an outside option of privately known value. The model encompasses (prioritybased) 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 strategyproof allocation rule must weakly Paretodominate an individually rational and participationmaximal 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 strategyproof rules. We relate strategyproof 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 GaleShapley 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 “sociallyoptimal assortment planning” problem, and show that it is a generalization of the revenuemaximizing assortment planning problem studied in the revenue management literature. We give efficient algorithms for the sociallyoptimal 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 StudentTruthful ManytoOne Matchings (via Differential Privacy)
Approximately Stable, School Optimal, and StudentTruthful ManytoOne 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 manytoone 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 worstcase 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 
DAY 2  
8:00 A.M.  Breakfast 
8.45 A.M.  Invited Talk 3 — Michael Ostrovsky, Stanford
Matching under preferences: beyond the twosided 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 twosided, 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 twosided 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 trailstable 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. Trailstable 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 trailstable outcomes, we prove results on the lattice structure, the rural hospitals theorem, strategyproofness and comparative statics of firm entry and exit. We pin down a condition under which trailstable and fully trailstable 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) trailstable. 

Too Good to Fire: NonAssortative Matching to Play a Dynamic Game
Speakers: Benjamin Sperisen and Thomas Wiseman Abstract: We study stable outcomes in a onetoone matching market with firms and workers. The model endogenizes how transferable utility is within a match: when a firmworker pair is matched, they play an infinitehorizon discounted dynamic game with onesided, 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 lowertype 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 manytomany 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 straightforward 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 twosided matching market with private preferences when agents have some knowledge of the preference distribution. We show that in a twosided market with workers and firms, when the preferences of workers are arbitrary and private and the preferences of firms follow a multinomiallogit (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 NPhard 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 polynomialtime 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 nonbipartite 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 NPhard 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 polynomialtime 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 2approximation 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 wellknown 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 augmentingpath algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocation as a blackbox 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 graphbased reductions that show that it is without loss of generality to assume that no commodityspecific preference lists at the vertices and no commodityspecific capacities on the edges exist. We further show that it is NPcomplete 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 twosided 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 NPhard, 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 polynomialtime solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NPhard 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 largescale 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 
“STRATEGIC” BEHAVIOR IN A STRATEGYPROOF ENVIRONMENT
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 strategyproof nature of the mechanism in numerous ways, failed to play truthfully: they ranked a nonfunded position above a funded position in the same program. This is despite being informed that rankordered 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 strategyproof
Speakers: Itai Ashlagi and Yannai A Gonczarowski Abstract: Many twosided matching markets, from labor markets to school choice programs, use a clearinghouse based on the applicantproposing deferred acceptance algorithm, which is well known to be strategyproof 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 strategyproof for any side of the market, a stronger incentive property than strategyproofness introduced by Li (2015). A stable mechanism that is obviously strategyproof for applicants is introduced for the case in which agents on the other side have acyclical preferences. Our findings suggest that strategic reasoning in twosided markets requires more cognitive effort by participants than in onesided 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 (GaleShapley) manoptimal, which we prove yields the womanoptimal 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 egalitarianoptimal 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 underappreciated feature of market design is that centralized markets operate within a broader context; often market designers cannot force participants to join a centralized market. Welldesigned centralized markets must induce participants to join voluntarily, in spite of preexisting 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 epsilondominant 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 epsilondominant 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 epsilondominant 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 strategyproof mechanism that results in the best competitive equilibrium. We then propose a Nash incentivecompatible dynamic auction that results in the same competitive equilibrium allocation. 

Competitive Equilibria with Indivisible Goods and Generic Budgets
Speakers: Moshe Babaioff, Noam Nisan and Inbal TalgamCohen 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 nonexistence of equilibria also a knifeedge 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 ImmediateAcceptance: 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 wellknown desirable resource allocation properties, characterize immediate acceptance mechanisms. Moreover, we show that replacing one of the properties, consistency, with a weaker property, nonbossiness, leads to a characterization of a much larger class of mechanisms, which we call choicebased 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 choicebased immediate acceptance mechanism. 

Fair Division of goods, bads, and satiable items
Speakers: Anna Bogomolnaia, Herve Moulin, Fedor 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 singlevalued 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 welfarewise 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 noninvariant outcome measures and of mechanisms that elicit preference intensities. 
6.15 P.M.  Closing Remarks 
6.30 P.M.  END 
Lemma: Let be any individually rational matching with respect to strict preferences and let be all men who prefer to . If is nonempty, there is a pair that blocks such that is in and is in .
Proof.
Case 1: , i.e. the set of men who prefer to are matched to different sets of women under the matching rules and .
Pick any . Note that in this case because it’s a onetoone matching.
Denote , and , so , and . This implies that and .
Note that , otherwise will block , contradicting to that .
Therefore, blocks such that and $m\in MM’$.
Case 2:, i.e. the set of men who prefer to are matched to the same set of women under the matching rules and .
Let be the last woman in to receive a proposal from an acceptable member of in the deferred acceptance. Denote this man by . So there are two possibilities: 1) has not been proposed before, and ; 2) is already engaged with some other man , and she rejects and accepts .
1) is not possible: If it were true, then since , there must be some such that . That means when we run the deferredacceptance algorithm to implement , has already proposed to and got rejected, contradicting that has not been proposed.
2) i. , otherwise will propose to another woman, contradicting that is the last woman in to receive a proposal. Therefore . And since , that means . This implies .
ii. Since is the last woman to receive the proposal, it must be that before rejects , she must have rejected , i.e. her mate under . That means .
Combine i. and ii., we conclude that blocks .
Q.E.D.
Alternative proof:
Case 1: The same as above.
Case 2: .
Define the new market . is the same as restricted to , and is the same as restricted to , , .
Note that , , we must have and , otherwise would be blocked. We can write this as:
and
.
So that means under , is now ranked just below , and is now ranked just below .
In other words, the only men in who are unacceptable to are those such that , so is acceptable to under for all .
Note that restricted to is still stable for , because any pair that blocks under would also block it under .
Let be the optimal matching for , then by Paretooptimality Theorem, it must be that
(*) .
Otherwise, if , then it would be contradicting .
Furthermore, by the construction of .
Define on by on , and $latex\mu’=\mu_M$ on .
Combine it with (*), we have . is not stable for , so let be a blocking pair.
i). If in , and would be mutually acceptable under , by construction of , and so would block . Also note that
then
and
.
So does not block .
ii). If , and , then
and
.
blocks , but it does not block .
iii). If , , then
and
.
So does not block .
iv). If , , then
and
.
So does blocks . It’s the desired blocking pair.
Q.E.D.
References:
Gale, D., & Sotomayor, M. (1985). Some Remarks on the Stable Matching. Discrete Applied Mathematics, 11, 223–232.
Roth, A. E., & Sotomayor, M. (1990). TwoSided Matching: A Study in GameTheoretic Modeling and Analysis. Cambridge University Press.
Bounded: for all .
Uniformly bounded: for all ,
Pointwise bounded: where is a finite valued function, and ,
is compact, is pointwise bounded and equitcontinuous is uniformly bounded, and contains a uniformly convergent subsequence.
Continuous: s.t. .
Uniformly continuous: s.t. .
Equicontinuous: s.t. .
Equicontinuous uniformly continuous.
Compact set, uniformly convergence equicontinuous.
Convergent: A sequence in a metric space s.t. s.t. .
Uniformly convergent (definition 1): a sequence of functions converges uniformly on to a function if s.t. for all .
Uniformly convergent (definition 2): s.t. .
Pointwise convergent: .
If is uniformly convergent, then .
is compact, is continuous and pointwise convergent, uniformly.
uniformly, where .
is differentiable, converge uniformly on converges uniformly, and $f'(x)=\lim_{n\to\infty}f_n'(x) (a\le x\le b)$.
is differentiable, is uniformly bounded is equicontinuous.
by Calvin Leather, Yuqing Hu
In response to this article: http://www.jneurosci.org/content/36/39/10016
Recent literature in reinforcement learning has demonstrated that the context in which a decision is made influences subject reports and neural correlates of perceived reward. For example, consider visiting a restaurant where have previously had many excellent meals. Expecting another excellent meal, when you receive a merely satisfactory meal, your subjective experience is negative. Had you received this objectively decent meal elsewhere, without the positive expectations, your experience would have been better. This intuition is captured in adaptive models of value, where a stimuli’s reward (i.e. Qvalue) is expressed as being relative to the expected reward in a situation, and it has been found that this accurately models activation in value regions (Palminteri et al 2015). Such a model also can be beneficial as it allows reinforcement learning models to learn to avoid punishment, as avoiding a contextuallyexpected negative payoff results in a positive reward. This had previously been challenging to express within the same framework as reinforcement learning models (Kim et al, 2006).
Alongside these benefits, there has been concern that adaptive models might be confused by certain choice settings. In particular, agents with an adaptive model of value would have an identical hedonic experience (i.e. Qvalues in the model) when receiving a reward of +10 units, in a setting where they might receive either +10 or 0 units, and a reward of 0 units, in a setting where they might receive either 10 or 0 units (we will refer to this later as the ‘confusing situation’). With this issue in mind, Burke et. al. (2016) develop an extension to the adaptive model, where contextual information only has a partial influence on reward. So, whereas the previous, fullyadaptive model has a subjective reward (Qvalue) of +5 units for receiving an objective reward of 0 in the context where the possibilities were 0 and 10, and an absolute model ignoring context would experience a reward of 0, the Burke model would experience a reward of +2.5. It takes the context into account, but only partially, and accordingly they call their model ‘partiallyadaptive’. Burke et. al. compare this partiallyadaptive model with a fullyadaptive model, and an absolute model (which ignores context). When subjects were given the same contexts and choices as the confusing situation outlined above, Burke et. al. found that the partiallyadaptive model reflects neural data in the vmPFC and striatum better than the fullyadaptive or absolute models.
The partiallyadaptive model is interesting, as it has the same advantages as the fullyadaptive model (reflecting subjective experience and neural data well, allowing for avoidance learning), while potentially avoiding the confusion outlined above. Here, we seek to investigate the implications and benefits of Burke et. al.’s partiallyadaptive model more thoroughly. In particular, we will consider the confusion situation’s ecological validity and potential resolution, whether it is reasonable that partiallyadaptive representations might extend beyond decision (to learning and memory), and the implications of the theory for future work. Before we do this we would like to briefly present an alternative interpretation of their findings.
The finding that the fMRI signal is best classified by a partiallyadaptive model does not necessarily entail the brain utilizing a partiallyadaptive encoding as the value over which decisions occur. All neurons within a voxel can influence the fMRI signal, so it is possible that the signal may reflect a combination of multiple activity patterns present within a voxel. This mixing phenomenon has been used to explain the success of decoding early visual cortex, where the overall fMRI signal in a voxel reflects the specific distribution of orientationspecific columns within a voxel (Swisher, 2010). Similarly, the partiallyadaptive model’s fit might be explained by the average contribution of some cells with a fulladaptive encoding, and other cells with absolute encodings of value (within biological constraints). This concern is supported by the cooccurrence of adaptive and nonadaptive cells in macaque OFC (Kobayashi, 2010). Therefore, more work is needed to understand the local circuitry and encoding heterogeneity of regions supporting valuebased decision making.
Returning to the theory presented by the authors, we would like to consider whether a fullyadaptive encoding of value is truly suboptimal. The type of confusing situation presented above was shown to be problematic for real decision makers in Pompilio and Kacelnik (2010), where starlings became indifferent between two options with different objective values, due to the contexts those options appeared in during training. However, this type of choice context might not be ecologically valid. If two stimuli are exclusively evaluated within different contexts, as in Pompilio and Kacelnik, it is not relevant whether they are confusable, as the decision maker would never need to compare them.
Separate from the confusion problem’s ecological validity is the inquiry into its solution. Burke et. al. suggest partiallyadaptive encoding avoids confusion, and therefore should be preferred to a fullyadaptive encoding. However, this might only be true for the particular payoffs used in the experiment. Consider a decision maker who makes choices in two contexts. One, the loss context, has two outcomes, L_{0} (worth 0), and L_{neg} (worth less than 0), while the other, the gain context, has two outcomes, G_{0} (worth 0), and G_{pos} (worth more than 0). If L_{0}L_{neg }= G_{pos}– G_{0}, as in Burke et. al., a fullyadaptive agent would be indifferent between G_{0} and L_{neg }(and between G_{pos} and L_{0}). A partiallyadaptive agent, however, would not be indifferent, as the value of G_{0} would be higher than L_{neg. } Now consider what happens if we raise the value the value of G_{pos}. By doing this, we can raise the average value of the gain context by any amount. Now consider what this does the experienced value (Qvalue) of G_{0}. As we increase the average reward of the context, G_{0} becomes a poorer option in terms of its Qvalue. Note that since the only reward we are changing is G_{pos}, the Qvalues for the loss context do not change. Therefore, we can decrease the Qvalue for G_{0 }until it is equal to that of L_{neg}. This is exactly the confusion that we had hoped the partiallyadaptive model would avoid. Furthermore, this argument will work for any partiallyadaptive model: we are unable to defeat this concern by parameterizing the influence of context in the update equations, and manipulating this parameter.
As mentioned earlier, it is possible that some cells might encode partiallyadaptive value, while others might have a fully or nonadaptive encoding. We should be open to the possibility that even if partiallyadaptive value occurs in decision, nonadaptive encodings might be used for storage of value information, and are transformed at the time of decision into the observed partiallyadaptive signals. Why might this be reasonable? An agent who maintains partiallyadaptive representations in memory faces several computational issues. One is efficiency: storage requirements for a partiallyadaptive representation requires S*C quantities or distributions to be stored (one for each of the S stimuli in each of the C contexts). On the other hand, consider an agent who stores nonadaptive stimulus values and the average value of each context, and then adjusts stimulus values using the context values at the time of decision. They could utilize the same information, but only store S+C quantities. Another problem with storage of value information in an adaptive format is the transfer of learning across contexts. If I encounter a stimulus in context A, my experiences should alter my evaluation of that stimulus in context B: getting sick after eating a food should reduce my preference for that food in every context. An agent who stores value adaptively would need to update one quantity for the encountered stimulus in each context, namely C quantities. An agent who stores value nonadaptively only updates a single quantity. So, even if decision utilizes partiallyadaptive encoding, nonadaptive representation is most efficient for storage. Furthermore, nonadaptive information is present in the state of the world (e.g. concentration of sucrose in a juice does not adapt to expectations), so this information is available to agents during learning. Accordingly, it must be asked why agents would discard information that might ease learning. While these differences do not necessarily affect the authors’ claims about value during decision, they should be considered when investigating the merits of different models of value.
In sum, while partial adaption is an exciting theory that may provide novel motivations for empirical work, more effort is needed to understand when and where it is optimal. If we can overcome these concerns, the new theory opens up potential investigation into the nature of contextual influence: if we allow a range of contextual influence (via a parameter) in the partiallyadaptive model, do certain individuals have more contextual influence, and does this heterogeneity correlate with learning performance? Do different environments (e.g. noise in signals conveying the context) alter the parameter? Do different cells or regions respond with different amounts of contextual influence? As such, the theory opens up new experimental hypotheses that might allow us to better understand how the brain incorporates context in the learning and decisionmaking processes.
References
Burke, C. J., Baddeley, X. M., Tobler, X. P. N., & Schultz, X. W. (2016). Partial Adaptation of Obtained and Observed Value Signals Preserves Information about Gains and Losses. Journal of Neuroscience, 36(39), 10016–10025. doi:10.1523/JNEUROSCI.048716.2016
Kim, H., Shimojo, S., & Doherty, J. P. O. (2006). Is Avoiding an Aversive Outcome Rewarding ? Neural Substrates of Avoidance Learning in the Human Brain. PLoS Biology, 4(8), 1453–1461. doi:10.1371/journal.pbio.0040233
Kobayashi, S., Carvalho, O. P. De, & Schultz, W. (2010). Adaptation of Reward Sensitivity in Orbitofrontal Neurons. Journal of Neuroscience, 30(2), 534–544. doi:10.1523/JNEUROSCI.400909.2010
Palminteri, S., Khamassi, M., Joffily, M., & Coricelli, G. (2015). Contextual modulation of value signals in reward and punishment learning. Nature Communications, 6, 1–14. doi:10.1038/ncomms9096
Pompilio, L., & Kacelnik, A. (2010). Contextdependent utility overrides absolute memory as a determinant of choice. PNAS, 107(1), 508–512. doi:10.1073/pnas.0907250107
Swisher, J. D., Gatenby, J. C., Gore, J. C., Wolfe, B. A., Moon, H., Kim, S., & Tong, F. (2010). Multiscale pattern analysis of orientationselective activity in the primary visual cortex. Journal of Neuroscience, 30(1), 325–330. doi:10.1523/JNEUROSCI.481109.2010.Multiscale
With the advent of the internet economy, there has been a remarkable convergence in lines of inquiry between the fields of economic theory and computer science. The emergence of new markets mediated by information technology has spurred new research on how strategic agents interact with complex institutions, and also on how best to design institutions in the face of limited information and limited computational resources. The disciplines of game theory and complexity theory provide complementary approaches to understanding these issues. This conference brings together leading researchers from these fields to share and discuss exciting new developments. The broader goal is to facilitate a dialogue on how best to advance the common objective of understanding strategic behavior and institutional design in complex environments.
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
Stacchetti)
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
Moldovanu)
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
Polemarchakis)
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):
TBA
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 YanMin 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”
The original paper: download
Summary for each part:
I: The mathematical solution to constructing a rational economic order is to achieve the same marginal rates of substitution between any two goods. This is not realistic, because it relies on the assumption of complete command of knowledge in a central single mind, while in the real society the knowledge is dispersed among separate individuals. This causes misconception about the nature of economic problem, which is essentially how to efficiently allocate resources by utilizing individual knowledge, rather than utilizing it in its integrated form.
II: Utilizing knowledge, which involves communicating it to the planner and among different individuals, is important in designing an efficient economic system, which can be in the form of central planning, completion and monopoly. Which kind of the economic systems is more efficient depends on whether the existing knowledge can be fuller used.
III: Different kinds of knowledge define different positions of the economic systems. The prominent position of central planning in public imagination is due to the exaggeration of the importance of scientific knowledge. Selecting a group of experts to command such knowledge is actually only a fraction of the wider problem. The knowledge of the particular circumstances, which is not always available, is equivalently socially useful, although it is sometimes regarded as disreputable if one gains advantage by using this knowledge.
IV: Economic problems arise as a result of change of circumstances, making the knowledge of the particular place and time important in making economic decisions. This sort of knowledge, however, cannot be statistically calculated therefore cannot be conveyed to the central authority who make plans based on statistical information.
V: Decentralization is necessary in solving economic problems, because adaptions to changes in economic systems require the knowledge of the particular circumstances to be promptly used. A price system helps coordinate separate actions for individuals whose visions in their own fields sufficiently overlap through intermediaries, thus brings about the outcome that might have been achieved by central planning with complete information.
VI: The price system acts as a mechanism that communicates only the most essential information for individuals to take the right action, and it extends the span of resources utilization beyond the control of any single mind. Like language, this is one of the formations upon which the foundation of civilization is built.
VII: The dispute about the indispensability of price system is not purely a political dissent, but also intellectual and methodological differences. Schumpeter’s argument that valuation of factors of production is implied in the valuation of consumers’ goods is untrue, because it also depends on the supply of the factors. His argument disregards the essential fact of imperfection of knowledge in the real world. Thus the solution to the economic problem has to be processed by interactions of people who possess their partial knowledge.
In sum, the key takeaway ideas are:
In the real world, knowledge is spread throughout the society. The knowledge of particular circumstances of place and time is not always public available, but it is useful in making economic decisions. This is an essential feature of the real world’s economic problem, which makes central planning inefficient and infeasible. That’s because central planning requires a single mind processing all the knowledge. Decentralization overcomes this problem via a price system in which individuals with their own partial knowledge coordinate with each other and utilize resources that are beyond the control of any one person.