|
on Economic Design |
|
Issue of 2021‒11‒15
six papers chosen by Guillaume Haeringer, Baruch College and Alex Teytelboym, University of Oxford |
| 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 incentive-compatible, 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 first-best gains-from-trade, namely a constant fraction of the gains-from-trade attainable whenever buyer's value weakly exceeds seller's cost. In this work, we positively resolve this long-standing open question on constant-factor 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) miner-user 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 1-SCP, 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 one-to-one 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); Chen-Yu Pan (National Chengchi University, Taiwan) |
| Abstract: | This paper presents one-to-one 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 pair-specific match qualities to see how our stability concept performs in these generalized models. |
| Keywords: | one-to-one 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 Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial 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 k-approval 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 Gibbard-Satterthwaite 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 level-k model of auctions. We begin by asking which (simple) environments can best disentangle the level-k model from its leading rival, Bayes-Nash equilibrium. We find two environments that are particularly suited to this purpose: an all-pay auction with uniformly distributed values, and a first-price 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 level-k model substantially under-predicts the observed bids and is clearly out-performed by equilibrium. Moreover, attempting to fit the level-k 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 level-k 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 level-k 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= |