Fields:
Market Design, Microeconomic Theory

Expected Graduation Date:
June, 2019

References:
Fuhito Kojima (Primary):
fkojima@stanford.edu

Itai Ashlagi:
iashlagi@stanford.edu

Gabriel Carroll:
gdc@stanford.edu

Takuo Sugaya:
tsugaya@stanford.edu

Job Market Paper

The size of a matching is defined as the expected number of agents who are matched to some objects. It is an important design objective in many applications, including refugee resettlement, daycare assignment, and mass vaccination campaigns. This paper studies the matching size achieved by strategy-proof mechanisms in a general model of matching with constraints. Our model generalizes a number of constraint structures considered in the extant literature. We show that naive extensions of classical mechanisms may generate an arbitrarily small matching when we have such generalized constraints. Assuming a large market (in that the variety of objects is fixed but the capacities are large), we develop a technique to reshape a given resource constraint to a more structured one, called a polymatroidal constraint, with which a classical mechanism performs well. We propose a mechanism that (i) satisfies strategy-proofness, (ii) always achieves at least 1-1/e = 63.2% of the maximum size (which is the best approximation ratio a strategy-proof mechanism can achieve), (iii) respects agents' preferences, and (iv) is computationally efficient, for general instances.

Journal Publication

Forthcoming in Theoretical Economics.

Online Appendix

We study full surplus extraction and implementation in dynamic environments. We exploit intertemporal correlations of agents' types to construct within-period ex post incentive compatible mechanisms. First, we formulate one-shot environments, in which a single agent has a hidden type and the planner observes a public signal about the agent's type after a type-contingent allocation is chosen. We propose necessary and sufficient conditions for full surplus extraction (strong detectability) and for implementability of the targeted allocation rule (weak detectability) in this one-shot problem. We decompose the general dynamic problem into one-shot problems and obtain sufficient conditions for surplus extraction and implementation.

Working Paper

Joint with Hitoshi Matsushima.

We investigate general mechanism design problems in which agents can take hidden actions that influence state distribution. Their action choices exert externality effects on their valuations through this influence. We characterize all mechanisms that resolve the hidden action problem (i.e., that induce a targeted action profile). A variety of action choices shrinks the set of mechanisms that induce the targeted action profile, leading to the equivalence properties in the ex-post term with respect to payoffs, payments, and revenues. When the agents can take unilateral deviations to change the state distribution in various directions (i.e., when the action profile satisfies the richness condition), pure-VCG mechanisms---the simplest form of canonical VCG mechanism, which is implemented via open-bid descending procedures that determine the losers' compensation---are the only mechanisms that induce an efficient action profile. Contrariwise, the popular pivot mechanism, implemented by ascending auctions that determine the winner's payment, generally fails to induce any efficient action profile.

We consider one-sided matching problems in which agents can endogenously acquire information about objects in order to evaluate their values more precisely. In such situations, whether agents acquire information crucially depends on their beliefs about their choice set (i.e., the set of objects each agent can obtain through some type reports). In this paper, we fix the assignment rule to be the random serial dictatorship, and study the efficiency of each disclosure policy of choice sets. With a stylized environment where only one object has an ex ante unobservable private-value component, we demonstrate that the full-disclosure policy, which perfectly discloses each agent's choice set, is typically inefficient, because it fails to take advantage of the positive externality of information acquisition. Then, we illustrate that by obscuring the information about the best available fixed-valued objects, we can induce more efficient information acquisition. We also show that, in the worst case, the loss of the full-disclosure policy relative to the optimal one is large.

I study the size of matching (i.e., expected number of agents matched to some objects) achieved by the random serial dictatorship mechanism (RSD). I establish a rigorous proof for the fact that RSD achieves the guaranteed size ratio of 1-1/e (= 63.2%), which implies that for every instance, the size of matching generated by RSD is not smaller than 63.2% of the maximum feasible size. I also show that no mechanism that satisfies weak truncation robustness and weak regularity can achieve a guaranteed size ratio better than 1-1/e.

I have one more working paper, but I have not released it to public because it is under double-blind peer review by a computer-science conference. I am allowed to disclose it to a limited audience.

Work in Progress

Joint with Hiroto Katsumata. [Slides]

We study the strategic voting in M-seat multi-member districts under the single non-transferable vote (SNTV). We find that under a wide range of parameters, SNTV fails to discriminate a loser from winners in that the loser's probability of winning does not converge to zero even when the number of voters goes to infinity, in contrast to single-member districts (SMD). This is because (i) voters do not always vote for their most favorite candidates if they are clear winners, and (ii) the most effective way of making the least favorite candidate out of office is to vote for the first runner-up. Such strategic voting increases the first runner-up's vote share, leading to an equilibrium where the vote share of top (M+1)-candidates are the same in the limit. We also find several evidences that support our theoretical predictions in Japanese election data.

Joint with Guido Martirena.

It has been well documented that minority workers (e.g., people of color, women, people with disabilities) get a significantly worse reputation than majority workers in a variety of crowdsourcing platforms. In this paper, we develop a tractable dynamic model of a crowdsourcing platform, in which consumers review workers' task performance. We show that if the platform discloses the full set of past reviews and a small fraction of consumers discriminate against minority workers (make biased reviews), then minority workers are discouraged from exerting effort since they cannot develop a sufficiently strong reputation to find doing so profitable. Our result suggests that poor rating and platform design may amplify discrimination and endogenously decrease the observed productivity of minority workers.