Job Market Paper
Large Matchings in Large Markets with Flexible Supply
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.
Full Surplus Extraction and within-period Ex Post Implementation in Dynamic Environments
Forthcoming in Theoretical Economics.
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.
Mechanism Design in Hidden Action and Hidden Information: Richness and Pure-VCG
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.
Strategic Experimentation with Random Serial Dictatorship
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.
Size Versus Truncation Robustness in the Assignment Problem
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
Kicking the Rascals Out: On the Strategic Incentives under the Single Non-Transferable Vote
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.
The Amplification of Discrimination via Crowdsourcing in Online Platforms
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.