Essays On Mechanism Design Without Transfers

Open Access
Akyol, Ethem
Graduate Program:
Doctor of Philosophy
Document Type:
Date of Defense:
May 13, 2014
Committee Members:
  • Vijay Krishna, Dissertation Advisor
  • Kalyan Chatterjee, Committee Member
  • Marc Albert Henry, Committee Member
  • Aydin Alptekinoglu, Committee Member
  • Mechanism Design
  • School Choice
  • Colonel Blotto
  • Incomplete Information
This dissertation consists of three chapters. In Chapter 1, we compare two widely used allocation methods for school choice, the Deferred Acceptance (DA) mechanism and the Boston mechanism, in terms of welfare. We consider a symmetric incomplete information setting in which students have independently drawn valuations for schools and all schools have an identical ranking of the students. Our main result is that when each school has one available seat and the number of schools and students is large, every type of every student has a higher interim utility under the Boston mechanism than under the DA mechanism. Although this strong result is not true when the number of schools is small, even in this case, the Boston mechanism is ex-ante welfare superior to DA under weak conditions on the distribution of valuations. In Chapter 2, we consider the problem of allocating n≥2 indivisible distinct objects (possibly with multiple copies of each) to m≥2 agents without monetary transfers. We assume that agents have private preferences and consider mechanisms that depend only on agents' reported ordinal preferences. Full efficiency cannot be achieved in this environment, and so we look for a welfare maximizing, incentive compatible mechanism. We show that when agents' rankings over objects are independent of other agents' rankings and each possible ranking is equally likely, the so-called Ranking mechanism (first-order) stochastically dominates any other anonymous, neutral and incentive compatible ordinal mechanism. In particular, when agents' preferences over random allocations are responsive, every type of every agent has a higher interim welfare under the Ranking mechanism. In Chapter 3, we consider the problem of allocating multiple objects to agents via an auction by using "points" as in the "Course Bidding System" that is used by several business schools. Each agent has a fixed amount of divisible points which can only be used for bidding and have no monetary value. Agents simultaneously bid for the objects, and each object is given to the agent who bids highest for that object. This game is equivalent to the classical "Colonel Blotto" game. We consider this game under incomplete information when agents have private values for the objects. For a class of value distributions, we solve for a Bayes-Nash equilibrium of this game. Furthermore, for all the value distributions for which we can solve for equilibrium in closed form, we show that every type of agent has a higher interim payoff under this allocation method than any other incentive compatible allocation method that depends only on ordinal preferences.