Abstract : Market design, also known as mechanism design, is a practical application of game theory, whose purpose is to develop decision making rules under which each individual has an incentive to take a desirable action in an equilibrium. In recent years, the research of market design has attracted the attention of researchers in various research fields, including mathematics, economics, computer science, biology, politics, psychology, etc. We have nine prospective researches in this minisymposium as invited speakers, who give us state-of-the-art of the theory and applications of market design.
Organizer(s) : Ayumi Igarashi, Shunya Noda, Taiki Todo
[01516] Are Simple Mechanisms Optimal when Agents are Unsophisticated?
Format : Talk at Waseda University
Author(s) :
Jiangtao Li (Singapore Management University)
Piotr Dworczak (Northwestern University)
Abstract : We study the design of mechanisms involving agents that have limited strategic sophistication. We define a mechanism to be simple if—given the assumed level of strategic sophistication—agents can determine their optimal strategy. We examine whether it is optimal for the mechanism designer who faces strategically unsophisticated agents to offer a simple mechanism. We show that when the designer uses a mechanism that is not simple, while she loses the ability to predict play, she may nevertheless be better off no matter how agents resolve their strategic confusion.
[05446] Strategyproof Mechanisms for Group-Fair Facility Location Problems
Format : Talk at Waseda University
Author(s) :
Minming Li (City University of Hong Kong)
Houyu Zhou (City University of Hong Kong)
Hau Chan (University of Nebraska–Lincoln)
Abstract : We study the facility location problems where agents are located on a real line and divided into groups based on criteria such as ethnicity or age. Our aim is to design mechanisms to locate a facility to approximately minimize the costs of groups of agents to the facility fairly while eliciting the agents' locations truthfully. We first explore various well-motivated group fairness cost objectives for the problems and show that many natural objectives have an unbounded approximation ratio. We then consider minimizing the maximum total group cost and minimizing the average group cost objectives. For these objectives, we show that existing classical mechanisms (e.g., median) and new group-based mechanisms provide bounded approximation ratios, where the group-based mechanisms can achieve better ratios. We also provide lower bounds for both objectives. To measure fairness between groups and within each group, we study a new notion of intergroup and intragroup fairness (IIF) . We consider two IIF objectives and provide mechanisms with tight approximation ratios.
[01738] Optimal allocation with costly verification and distributional constraint
Format : Talk at Waseda University
Author(s) :
Yunan Li (City University of Hong Kong)
Abstract : A planner allocates multiple slots $\text{(e.g., a spot in college)}$ among a finite number of agents, each of whom wants one slot and privately knows the value to the planner of assigning one slot to him. The slots are allocated based on the agents’ reports. The planner can choose to inspect an agent’s report at a cost. The constrained efficient mechanism for a planner facing a distributional constraint adds a constant to the values of the agents in the targeted group $\text{(a “flat subsidy”)}$ and specifies a threshold. The slots are first allocated to the agents whose $\text{(adjusted)}$ values are above the threshold. Any remaining slots are randomly allocated among the agents whose $\text{(adjusted)}$ values are below the threshold. For a stringent distributional constraint, the randomization favors the targeted group $\text{(a “quota”)}$.
[01616] Optimal Dynamic Matching
Format : Talk at Waseda University
Author(s) :
Junpei Komiyama (New York University)
Akira Matsushita (The University of Tokyo)
Shunya Noda (The University of Tokyo)
Abstract : We propose a machine-learning method to construct an approximately optimal algorithm for a general class of dynamic matching problems. We apply our method to several problems and compare an algorithm generated by our method with simplistic ones, such as a greedy algorithm, to illustrate the importance of optimizing allocations in dynamic environments.
[01693] Mechanism Design Powered by Social Interactions
Format : Online Talk on Zoom
Author(s) :
Dengji Zhao (ShanghaiTech University)
Abstract : Mechanism design has traditionally assumed that the participants are fixed and independent. However, in reality, the participants are well-connected (e.g., via their social networks) and we can utilize their connections to power the design. One interesting trend is to incentivize the existing participants to use their connections to invite new participants. This helps to form larger games in auctions, coalitional games, matching etc., which is not achievable with the traditional solutions. The challenge is that the participants are competitors and they would not invite each other by default. Solving this is well-coupled with the existing challenges. For example, in auctions, solving it may require revenue monotonicity and false-name-proofness, which were proved impossible to achieve under certain sensible conditions. In matching, this cannot get along with standard optimality and stability. Hence, we believe there is an important theoretical value to discover and the study will stimulate many interesting applications, especially under decentralized systems with blockchain.
[01426] Tract housing, the core, and pendulum auctions
Format : Online Talk on Zoom
Author(s) :
Andrew Mackenzie (∗Department of Microeconomics and Public Economics, Maastricht University)
Yu Zhou (Graduate School of Economics, Kyoto University )
Abstract : We consider a model of tract housing where buyers and sellers have (i) wealth constraints, and (ii) unit demand over identical indivisible objects represented by a valuation. First, we characterize the strong core. Second, we characterize the bilateral weak core, or the weak core allocations with no side-payments. Finally, when buyer wealth constraints and valuations are private information and when transfers are discrete, we introduce two families of pendulum auctions, both of which consist of obviously strategy-proof implementations of the bilateral weak core. The buyer-optimal pendulum auctions are preferred by the buyers but are inefficient when side-payments are possible, while the efficient pendulum auctions are efficient.
[01327] Mechanism Design with Uncertainty
Format : Talk at Waseda University
Author(s) :
Taiki Todo (Kyushu University)
Abstract : My research is summarized as mechanism design with uncertainty. Traditional mechanism design focuses on static environments where all the (possibly probabilistic) information about the agents are observable by the mechanism designer. In practice, however, it is possible that the set of participating agents and/or some of their actions are not observable a priori. We therefore focused on various kinds of uncertainty in mechanism design and developed/analyzed several market mechanisms that incentivize agents to behave in a sincere way.
[01620] Multi-Unit Bilateral Trade
Format : Online Talk on Zoom
Author(s) :
Bart de Keijzer (King's College London)
Abstract : We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular.
Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1 − e) approximation mechanism, matching the best known bounds for the single-item setting.
Joint work with Matthias Gerstgrasser, Paul Goldberg, Philip Lazos, and Alexander Skopalik. Based on a paper published in the Proceedings of AAAI 2019.
Abstract : Traditional approaches for fair allocation of indivisible resources focus either on randomized allocations that are fair in expectation or deterministic allocations that are approximately fair. I will discuss an algorithmic framework that reconciles randomization and approximation. Specifically, I will present an algorithm for finding a randomized allocation of indivisible goods that is ex-ante fair, i.e., envy-free in expectation, and ex-post approximately fair, i.e., envy-free up to one good.
https://arxiv.org/abs/2005.14122
https://arxiv.org/abs/2004.02554
[01408] Strong Revenue (Non-)Monotonicity of Single-parameter Auctions
Format : Talk at Waseda University
Author(s) :
Ziyun Chen (Tsinghua University)
Zhiyi Huang (The University of Hong Kong)
Dorsa Majdi (Sharif University of Technology)
Zipeng Yan (The University of Hong Kong)
Abstract : Consider Myerson’s optimal auction with respect to an inaccurate prior, e.g., estimated from data, which is an underestimation of the true value distribution. Can the auctioneer expect getting at least the optimal revenue w.r.t. the inaccurate prior since the true value distribution is larger? This so-called strong revenue monotonicity is known to be true for single-parameter auctions when the feasible allocations form a matroid. We find that strong revenue monotonicity fails to generalize beyond the matroid setting, and further show that auctions in the matroid setting are the only downward-closed auctions that satisfy strong revenue monotonicity. On the flip side, we recover an approximate version of strong revenue monotonicity that holds for all single-parameter auctions, even without downward-closedness. As applications, we get sample complexity upper bounds for single-parameter auctions under matroid constraints, downward-closed constraints, and general constraints. They improve the state-of-the-art upper bounds and are tight up to logarithmic factors.
[01530] Representation Theorems for Path-Independent Choice Rules
Format : Talk at Waseda University
Author(s) :
Koji Yokote (The University of Tokyo)
Isa E. Hafalir (University of Technology Sydney)
Fuhito Kojima (The University of Tokyo)
M. Bumin Yenmez (Boston College)
Abstract : Path independence is arguably the most important property of choice rules in market design. For example, it guarantees the existence of a desirable matching in two-sided markets. We show that a choice rule is path independent if and only if it is rationalized by a valuation function satisfying ordinal concavity. We also provide a representation result for choice functions that satisfy path independence and the law of aggregate demand using valuation functions satisfying ordinal concavity.
[01261] Fair division algorithms for house chores
Format : Talk at Waseda University
Author(s) :
Ayumi Igarashi (The University of Tokyo)
Abstract : Couples often encounter the challenge of sharing house chores. This raises the fundamental question of how to divide chores. In this paper, we present a new application for a fair division of household chores. Our platform, called Kajibuntan, allows couples to specify the set of chores to be shared, their preferences over them, and the current allocation. Our tool visualizes the current allocation and makes proposals according to their preferences based on the theory of fair division. The goal of our tool is to provide a systematic and transparent system to divide household chores and help creating harmony in the home.
