
on Economic Design 
By:  Yuan Deng; Jieming Mao; Balasubramanian Sivan; Kangning Wang 
Abstract:  We study bilateral trade between two strategic agents. The celebrated result of Myerson and Satterthwaite states that in general, no incentivecompatible, individually rational and weakly budget balanced mechanism can be efficient. I.e., no mechanism with these properties can guarantee a trade whenever buyer value exceeds seller cost. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the firstbest gainsfromtrade, namely a constant fraction of the gainsfromtrade attainable whenever buyer's value weakly exceeds seller's cost. In this work, we positively resolve this longstanding open question on constantfactor approximation, mentioned in several previous works, using a simple mechanism. 
Date:  2021–11 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2111.03611&r= 
By:  Hao Chung; Elaine Shi 
Abstract:  In blockchains such as Bitcoin and Ethereum, users compete in a transaction fee auction to get their transactions confirmed in the next block. A line of recent works set forth the desiderata for a "dream" transaction fee mechanism (TFM), and explored whether such a mechanism existed. A dream TFM should satisfy 1) user incentive compatibility (UIC), i.e., truthful bidding should be a user's dominant strategy; 2) miner incentive compatibility (MIC), i.e., the miner's dominant strategy is to faithfully implement the prescribed mechanism; and 3) mineruser side contract proofness (SCP), i.e., no coalition of the miner and one or more user(s) can increase their joint utility by deviating from the honest behavior. The weakest form of SCP is called 1SCP, where we only aim to provide resilience against the collusion of the miner and a single user. Sadly, despite the various attempts, to the best of knowledge, no existing mechanism can satisfy all three properties in all situations. Since the TFM departs from classical mechanism design in modeling and assumptions, to date, our understanding of the design space is relatively little. In this paper, we further unravel the mathematical structure of transaction fee mechanism design by proving the following results:  Can we have a dream TFM?  Rethinking the incentive compatibility notions.  Do the new design elements make a difference? 
Date:  2021–11 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2111.03151&r= 
By:  Kenzo Imamura (University of Tokyo Market Design Center); Hideo Konishi (Boston College) 
Abstract:  We consider a onetoone assortative matching problem in which matched pairs compete for a prize. With such externalities, the standard solution concept, pairwise stable matching, may not exist. In this paper, we consider farsighted agents and analyze the largest consistent set (LCS) of Chwe (1994). Despite the assortative structure of the problem, LCS tend to be large with the standard effectiveness functions: LCS can be the set of all matchings, including an empty matching with no matched pair. By modifying the effectiveness function motivated by Knuth (1976), LCS becomes a singleton of the positive assortative matching. Our results suggest that the choice of effectiveness function can significantly impact the solution in a matching problem with externalities. 
Keywords:  group contest, pairwise stable matching, assortative matching, farsightedness, largest consistent set, effectiveness function 
JEL:  C7 D71 D72 
Date:  2021–11–04 
URL:  http://d.repec.org/n?u=RePEc:boc:bocoec:1040&r= 
By:  Kenzo Imamura (University of Tokyo Market Design Center); Hideo Konishi (Boston College); ChenYu Pan (National Chengchi University, Taiwan) 
Abstract:  This paper presents onetoone matching and assignment problems with externalities across pairs such as pairs figure skating competition and joint ventures in oligopolistic markets. In these models, players care not only about their partners but also which and how many rival pairs are formed. Thus, it is important for a deviating pair to know which matching will realize after it deviates from a matching (an effectiveness function) in order to define pairwise stable matching. Using a natural effectiveness function for such environments, we show that the assortative matching is pairwise stable. We discuss two generalizations of our model including intrinsic preferences on partners and pairspecific match qualities to see how our stability concept performs in these generalized models. 
Keywords:  onetoone matching, matching with externalities, pairwise stable matching, coalition formation, group contest, joint ventures, myopia, farsightedness. 
JEL:  C7 D71 D72 
Date:  2021–11–04 
URL:  http://d.repec.org/n?u=RePEc:boc:bocoec:1039&r= 
By:  Haris Aziz; Alexander Lam 
Abstract:  The GibbardSatterthwaite theorem states that no unanimous and nondictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability that was proposed by Troyan and Morrill (2020). We identify several classes of voting rules that satisfy this notion. We also show that several voting rules including kapproval fail to satisfy this property. We characterize conditions under which voting rules are obviously manipulable. One of our insights is that certain rules are obviously manipulable when the number of alternatives is relatively large compared to the number of voters. In contrast to the GibbardSatterthwaite theorem, many of the rules we examined are not obviously manipulable. This reflects the relatively easier satisfiability of the notion and the zero information assumption of not obvious manipulability, as opposed to the perfect information assumption of strategyproofness. We also present algorithmic results for computing obvious manipulations and report on experiments. 
Date:  2021–11 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2111.01983&r= 
By:  Itzhak Rasooly 
Abstract:  In this paper, we design and implement an experiment aimed at testing the levelk model of auctions. We begin by asking which (simple) environments can best disentangle the levelk model from its leading rival, BayesNash equilibrium. We find two environments that are particularly suited to this purpose: an allpay auction with uniformly distributed values, and a firstprice auction with the possibility of cancelled bids. We then implement both of these environments in a virtual laboratory in order to see which theory can best explain observed bidding behaviour. We find that, when plausibly calibrated, the levelk model substantially underpredicts the observed bids and is clearly outperformed by equilibrium. Moreover, attempting to fit the levelk model to the observed data results in implausibly high estimated levels, which in turn bear no relation to the levels inferred from a game known to trigger levelk reasoning. Finally, subjects almost never appeal to iterated reasoning when asked to explain how they bid. Overall, these findings suggest that, despite its notable success in predicting behaviour in other strategic settings, the levelk model (and its close cousin cognitive hierarchy) cannot explain behaviour in auctions. 
Date:  2021–11 
URL:  http://d.repec.org/n?u=RePEc:arx:papers:2111.05686&r= 