Search

We consider a matching with contracts problem where there is an initial matching a priori. Both sides of the market can veto the new matching whenever they would rather keep their initial contract. We propose a stability notion, called ``conditional stability." Our first mechanism---``Non-Vetoed Deferred Acceptance" ($NDA$)---is non-vetoed, conditionally stable, and strategy-proof. These three properties are incompatible with (two-sided) constrained efficiency; hence $NDA$ is not constrained efficient. However, no mechanism that is non-vetoed, conditionally stable, and strategy-proof improves on $NDA$. Lastly, we propose a non-vetoed, conditionally stable, and constrained efficient mechanism that dominates $NDA$.

In dispute resolution, arbitrator assignments are decentralized and they incorporate parties’ preferences, in total contrast to referee assignments in sports. We suggest that there can be gains (i) in dispute resolution from centralizing the allocation by bundling the newly arriving cases, and (ii) in sports from incorporating teams’ preferences. To that end, we introduce a class of Arbiter Assignment Problems where a set of matches (e.g., disputes or games), each made up of two agents, are to be assigned arbiters (e.g., arbitrators or referees). In this new set of problems, the question of how agents in a match should compromise becomes critical. To evaluate the value of an arbiter for a match, we introduce the (Rawlsian) notion of depth, defined as the arbiter’s worst position in the two agents’ rankings. Depth optimal assignments minimize depth over matches, and they are Pareto optimal. We first introduce and analyze depth optimal (and fair) mechanisms. We then propose and study strategy-proof mechanisms.

In unit-demand and multi-copy object allocation problems, we say that a mechanism size-wise dominates another mechanism if the latter never allocates more objects than the former does, while the converse is true for some problem. Our main result shows that no individually rational and strategy-proof mechanism size-wise dominates a non-wasteful, truncation-invariant, and extension-responding mechanism. As a corollary of this, the wellknown deferred-acceptance, serial dictatorship, and Boston mechanisms are not size-wise dominated by an individually rational and strategy-proof mechanism. We also show that whenever the number of agents does not exceed the total number of object copies, no group strategy-proof and ecient mechanism, such as top trading cycles mechanism, is size-wise dominated by an individually rational, weakly population-monotonic, and strategy-proof mechanism.

We evaluate the goal of maximizing the number of individually rational assignments. We show that it implies incentive, fairness, and implementation impossibilities. Despite that, we present two classes of mechanisms that maximize assignments. The first are Pareto efficient, and undominated - in terms of number of assignments - in equilibrium. The second are fair for unassigned students and assign weakly more students than stable mechanisms in equilibrium. We provide comparisons with well-known mechanisms through computer simulations. Those show that the difference in number of matched agents between the proposed mechanisms and others in the literature is large and significant.

Motivated by various trade restrictions in real-life object allocation problems, we introduce an object allocation with a particular class of trade restrictions model. The set of matchings that can occur through a market-like process under such restrictions is defined, and each such matching is called feasible. We then introduce a class of mechanisms, which we refer to as “Restricted Trading Cycles” (RTC). Any RTC mechanism is feasible, constrained efficient, and respects endowments. An axiomatic characterization of RT C is obtained, with feasibility, constrained efficiency, and a new property that we call hierarchically mutual best. In terms of strategic issues, feasibility, constrained efficiency, and respecting endowments together turns out to be incompatible with strategy-proofness. This in particular implies that no RTC mechanism is strategy-proof. Lastly, we consider a probabilistically restricted trading cycles (PRTC) mechanism, which is obtained by introducing a certain randomness to the RTC class. While PRTC continues to be manipulable, compared to RTC, it is more robust to truncations and reshufflings.

We analyze the school choice model and introduce costly appeals against violations of students' priorities. If these costs are sufficiently high, then some of such appeals may not provide benefits to the parents even when their priorities are violated. Instead of working with cardinal notions, our construction elicits the relevant ordinal implications of these costs, the information about the least rank decrease a student would be appealing against a priority violation (his/her stickiness degree), from the students before the assignment is determined. Then the notion of stability, the main desiderata in school choice known to be at odds with efficiency, is weakened by disregarding priority violations not worth the cost and the notion of sticky stability is obtained. The first mechanism we introduce is ``efficiency improving deferred acceptance mechanism'' (EIDA) and we show that it is sticky stable and superior to the deferred acceptance mechanism (DA) in terms of efficiency and involves truthful revelations of the stickiness degrees. The EIDA not maximally improving efficiency in the class of sticky stable solutions, leads us to design ``efficiency corrected deferred acceptance mechanism'' (ECDA) which turns out to be both sticky stable and efficient within the class of sticky stable mechanisms. While both mechanisms lack full incentive properties in the complete information case, in certain incomplete information settings, the former becomes immune to manipulations, whereas, the latter is still manipulable but with a diminished scope.

One of the main problems in the hospital-doctor matching is the maldistribution of doctor assignments across hospitals. Namely, many hospitals in rural areas are matched with far fewer doctors than what they need. The so called "Rural Hospital Theorem" (Roth (1984)) reveals that it is unavoidable under stable assignments. On the other hand, the counterpart of the problem in the school choice context|low enrollments at schools| has important consequences for schools as well. In the current study, we approach the problem from a different point of view and investigate whether hospitals can increase their filled positions by misreporting their preferences under well-known Boston, Top Trading Cycles, and stable rules. It turns out that while it is impossible under Boston and stable mechanisms, Top Trading Cycles rule is manipulable in that sense.

This study presents a modified version of the repeated discounted prisoners' dilemma with long and short-run players. In our setting a short-run player does not observe the history that has occurred before he was born, and survives into next phases of the game with a probability given by the current action profile in the stage game. Thus, even though it is improbable, a short-run player may live and interact with the long-run player for infinitely long amounts of time. In this model we prove that under a mild incentive condition on the stage game payoffs, the cooperative outcome path is not subgame perfect no matter how patient the players are. Moreover with an additional technical assumption aimed to provide a tractable analysis, we also show that payoffs arbitrarily close to that of the cooperative outcome path, cannot be obtained in equilibrium even with patient players.

This study presents a modified version of the repeated discounted prisoners'dilemma with long and short-run players. In our setting a short-runplayer does not observe the history that has occurred before he was born,and survives into next phases of the game with a probability given by thecurrent action profile in the stage game. Thus, even though it is improbable,a short-run player may live and interact with the long-run player forinf,nitely long amounts of time. In this model we prove that under a mildincentive condition on the stage game payos, the cooperative outcome pathis not subgame perfect no matter how patient the players are. Moreover withan additional technical assumption aimed to provide a tractable analysis, wealso show that payos arbitrarily close to that of the cooperative outcomepath, cannot be obtained in equilibrium even with patient players. Bu calsma uzun ve ksa donemli oyuncularla oynanan tekrarl iskontoedilmis tutuklu acmaz oyununun degisiklik yaplms halidir. Bu calsmamzda,ksa donem oyuncu dogmadan onceki gecmisi gozlemlemiyor ve oyunun birsonraki tekrar icin hayatta kalabilme ihtimali o periyottaki aksiyon pro-li tarafndan belirleniyor. Bu suretle, mumkun gorunmesede ksa donemoyuncu sonsuz zaman diliminde hayatta kalabilir ve uzun donem oyuncuylaoyunu oynayabilir. Bu modelde, periyot getirileri uzerine bir varsayim altnda,oyuncularn sabr seviyelerinden bagmsz olarak isbirlikci sonuc gidishatnnalt oyun tam Nash dengesi olmadgn ispatladk. Ayrca, analizimizi kolaylastrmay saglayan teknik bir varsaym ile, sabrl oyuncularla bile isbirlikcisonuc gidishatnn sagladg getirilere rastgele yakn olan getirileri dengedeelde edemedigimizi gosterdik. 42

This study presents a modified version of the repeated discounted prisoners' dilemma with long-run and short-run players. Even though it is highly improbable, a short-run player may live and interact with the long-run player for infinitely long amounts of time. We prove that under a mild incentive condition on the stage game payoffs, the cooperative outcome path is not subgame perfect no matter how patient the players are.

2018 senesinde Türk hükümeti çesitli sebeplerle lise yerlestirme sistemini degistirmistir.Bir dizayncı olarak hükümet, ögrencilerin büyük bir çogunlugu için tammerkezi bir sistemde sıralamalara göre yerlestirilecek okulların yerine lokasyonlaragöre ögrencilerin yerlestirilecegi mahalle liseleri kurmayı hedeflemistir. Bu sistemde,hükümet her bir ögrenciye lokasyonlarına göre okullar atar. Ardından ögrencilerkendilerine atanan okullar üzerine olusturdukları tercih listesini sunarlar. Hükümether bir ögrenciyi mümkün olan en yakın okula yerlestirmeyi arzular. Ancak ögrencilerintercih listesi hükümetin isteginden bagımsızdır. Böylece hükümetin istegive ögrencilerin tercihleri arasında bir uyumsuzluk olusacaktır. Bu çalısma, buuyumsuzlugu ortadan kaldıracaktır. Bu tezde önerilen Iki-Etaplı-Genellestirilmis-Takaddüm-Mekanizması ilk etabında bütün dizayncı-optimal sonuçların kümesinibulur. Ardından ikinci etabında ögrencilerin tercih listelerine göre en-iyi dizayncıoptimal(kısıtlı etkin) eslesmeyi verecektir. Bu tezin son kısmında ise, önerilenmekanizmanın stratejik analizi yapılacak ve sonuçları sunulacaktır. Turkish government changed the high-school placement system for several concernsin 2018. The government as a designer designates and orders schools to each studentin terms of location. Then students reveal their preference list over these designatedschools. The government desires students to be assigned to as possible as the closestschools. However, students' preference list is independent from the designationorder. In this context, there is an incompatibility between the students' preferencesand the concern of the designer. The thesis will solve this sort of incompatibility.Two-Stage-Generalized-Priority-Mechanism proposed in the thesis finds the set ofall possible designer-optimal matchings. At the second-stage, TSGPM yields thebest designer-optimal matching in terms of the students' preference list. At the lastpart of the thesis, strategic properties of the mechanism will be discussed. 39

Bu makalede, sözleşmelerle eşleşme sisteminde ana mekanizma olan Kümülatif Teklif Süreci'ni (COP) inceliyoruz. Sözleşmelerle eşleşme, temel analiz birimi olarak sözleşmeleri kullanan bir tahsisat problemidir. COP'un ikame (S) koşulu ile iki taraflı ikame (BS) ve tek taraflı ikame (US) koşulları altındaki özelliklerini inceliyoruz. Bu koşullar, istenen eşleşmeleri elde etmek için hastanelerin seçim işlevlerine dayatılır. Araştırmamızda, IRC'nin yokluğunda US'nin ve böylece otomatik olarak BS'nin COP tarafından üretilen uygun bir tahsisatın varlığını garanti etmediğini, ancak S'nin bunu garanti ettiğini gördük. Bu nedenle, çalışmamız, COP mekanizmasının BS veya US altında tanımlanabilmesi için, IRC'nin hastanelerin seçim işlevlerinin vazgeçilmez bir özelliği olması gerektiğini göstermektedir. This thesis examines the properties of an algorithm, namely the Cumulative Offer Process (COP), which has been the principal algorithm in the matching with contracts setting. Matching with contracts is an allocation problem which employs contracts as its basic unit of analysis. We examine properties of COP under the substitutes (S) condition as well as the bilateral substitutes (BS) and the unilateral substitutes (US) conditions. These conditions are imposed on the choice functions of hospitals to obtain desirable matchings. In our research, we found that in the absence of IRC, the US, and hence automatically the BS, does not guarantee the existence of a feasible allocation that is produced by COP, yet S guarantees it. Therefore, our study shows that IRC is an essential property of choice functions of hospitals in order for the COP algorithm to be well-defined under BS or US. 30

Tercihe riayetli sabitlik adında, okullar için tolerans değerleri içeren ve hem okulların önceliklerine hem de öğrencilerin tercihlerine önem veren, yeni bir sabitlik nosyonu sunduk. Her okul seçimi problemi için bir tercihe riayetli sabit eşleşmenin var olduğunu ve Gale-Shapley sabit eşleşmesine Pareto-üstün olduğunu bulduk. Sınırlı-verimli bir tercihe riayetli sabit eşleşmeye ulaşmak için geliştirme çemberlerine dayanan, iki adımlı bir mekanizma geliştirdik. Mekanizmamız geniş bir sınıf mekanizmaların doğal bir genellemesi ve öğrenci-optimal Sabit Mekanizma ve Boston Mekanizması'nı özel vakalar olarak kapsamakta. Ayrıca, mekanizmanın stratejik özelliklerini tam ve eksik bilgi durumları altında inceledik ve tercihleri dürüst bildirmenin, öğrenciler için ordinal Bayes Nash Dengesi olduğunu bulduk. We introduce a new stability notion called preference respecting stability that incorporates tolerance values for schools and attaches importance to both the preferences of students and the priorities of schools, and study its properties. We find that a preference respecting stable allocation exists in any school choice problem, and it Pareto-dominates the Gale-Shapley stable allocation. We construct a two part mechanism that depends on improvement cycles to reach a constrained efficient preference respecting stable allocation. Our mechanism is a natural generalization of a broad class of mechanisms and admits the student-optimal Stable Mechanism and the Boston Mechanism as special cases. We also study its strategic properties under complete and incomplete information settings and find that truthful reporting of preferences is an ordinal Bayesian Nash equilibrium for the students. 58

Biz bu çalışmada pozitif ayrımcılık politikalarının Boston mekanizması altında azınlık öğrenci grubu açısından nasıl çalıştıklarını inceledik. Çoğunluk öğrenci grubuna kota koyan pozitif ayrımcılık politikası Boston mekanizması altında her zaman olumlu sonuç vermezken, oncelik bazlı ve azınlık öğrencilere yer ayıran politikalar Boston mekanizmasında olumlu sonuclar vermektedirler. Bununla birlikte daha güçlü refah sonucları istendiğinde ve kişilerin stratejik davrandıkları durumlarda bu üç politika da Boston mekanizması altında azınlık öğrencilerin faydasına çalışmayabilmektedir. We consider three popular affirmative action policies in school choice: quota-based, priority-based, and reserve-based affirmative actions. The Boston mechanism (BM) is responsive to the latter two policies in that a stronger priority-based or reserve-based affirmative action makes some minority student better off. However, a stronger quota-based affimative action may yield a Pareto inferior outcome for the minority under the BM. These positive results disappear once we look for a stronger welfare consequence on the minority or focus on BM equilibrium outcomes. 44