AF:Small:Markets, Allocations and Dynamics

点击翻译按钮获取中文摘要

The need for resource allocation is pervasive. Often, it involves participants with conflicting interests. Markets and auctions both serve to produce desirable outcomes despite such conflicting interests, and yet other mechanisms are used when money cannot be exchanged (e.g. in kidney exchanges). An important goal is to find stable outcomes, outcomes with which individual participants are content in the sense that they cannot improve the outcome; these outcomes are called equilibria.For existing settings, such as economic markets and widely used mechanisms (e.g. Internet routing protocols or the Generalized Second Price auction used by major search engines), one wants to understand how well the existing mechanisms work. Specifically (i) In what settings are there equilibrium outcomes? (ii) Can they (or near-equilibria) be found? (iii) Are the equilibrium outcomes plausible, i.e. does it seem reasonable that they will be reached due to the interactions induced by the mechanism? This research will focus on matching markets and the housing market in particular.In other settings, where there are no existing mechanisms or the costs of introducing new mechanisms are not prohibitive, one can seek to design mechanisms that produce desirable outcomes. This research will focus on the allocation of divisible goods (i.e. goods that can be split into many parts).The standard modeling of matching markets, such as the housing market, assumes buyers have sharp budget limits. Unfortunately, when this assumption holds there may be no equilibrium solution. Instead, this research will consider a natural soft budget limit based on residual wealth, a setting where equilibria are guaranteed. The main issue is whether equilibria in this setting are predictors of outcomes. Necessary conditions, which will be investigated, are that the equilibria can be computed efficiently, that approximate equilibria are close to the actual equilibria, and that these approximate equilibria could arise as a result of the actions of buyers and sellers.With regard to mechanism design, as is standard, this research will seek truthful mechanisms, mechanisms which give participants no incentive for strategizing. In other words, participants will achieve their best outcomes by making honest declarations (e.g. of their valuations for different possible allocations). In general, it is not possible to allocate all the resources using truthful mechanisms. Instead, this research aims to understand the quality of the solutions produced by under-allocating yet truthful mechanisms. In particular, this research intends to study the class of proportionally fair mechanisms, mechanisms which were first introduced in the context of internet routing.