|
on Economic Design |
|
Issue of 2022‒08‒22
eleven papers chosen by Guillaume Haeringer, Baruch College and Alex Teytelboym, University of Oxford |
| By: | Debasis Mishra (Indian Statistical Institute, Delhi); Kolagani Paramahamsa (Indian Statistical Institute, Delhi) |
| Abstract: | We analyze a model of selling a single object to a principal-agent pair who want to acquire the object for a firm. The principal and the agent have different assessments of the object's value to the firm. The agent is budget-constrained while the principal is not. The agent participates in the mechanism, but she can (strategically) approach the principal for decision-making. We derive the revenue-maximizing mechanism in a two-dimensional type space (values of the agent and the principal). We show that below a threshold budget, a mechanism involving two posted prices and three outcomes (one of which involves randomization) is the optimal mechanism for the seller. Otherwise, a single posted price mechanism is optimal. |
| Keywords: | budget constraint, posted price, multidimensional mechanisms, behavioral mechanism design |
| JEL: | D82 |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:alo:isipdp:22-02&r= |
| By: | Lamprirni Zarpala; Dimitris Voliotis |
| Abstract: | We introduce the \enquote{local-global} approach for a divisible portfolio and perform an equilibrium analysis for two variants of core-selecting auctions. Our main novelty is extending the Nearest-VCG pricing rule in a dynamic two-round setup, mitigating bidders' free-riding incentives and further reducing the sellers' costs. The two-round setup admits an information-revelation mechanism that may offset the \enquote{winner's curse}, and it is in accord with the existing iterative procedure of combinatorial auctions. With portfolio trading becoming an increasingly important part of investment strategies, our mechanism contributes to increasing interest in portfolio auction protocols. |
| Date: | 2022–06 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2206.11516&r= |
| By: | Alexey Kushnir; James Michelson |
| Abstract: | We explore the properties of optimal multi-dimensional auctions in a model where a single object of multiple qualities is sold to several buyers. Using simulations, we test some hypotheses conjectured by Belloni et al. [3] and Kushnir and Shourideh [7]. As part of this work, we provide the first open-source library for multi-dimensional auction simulations written in Python. |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2207.01664&r= |
| By: | Zhaohua Chen; Chang Wang; Qian Wang; Yuqi Pan; Zhuming Shi; Chuyue Tang; Zheng Cai; Yukun Ren; Zhihua Zhu; Xiaotie Deng |
| Abstract: | Throttling is one of the most popular budget control methods in today's online advertising markets. When a budget-constrained advertiser employs throttling, she can choose whether or not to participate in an auction after the advertising platform recommends a bid. This paper focuses on the dynamic budget throttling process in repeated second-price auctions from a theoretical view. An essential feature of the underlying problem is that the advertiser does not know the distribution of the highest competing bid upon entering the market. To model the difficulty of eliminating such uncertainty, we consider two different information structures. The advertiser could obtain the highest competing bid in each round with full-information feedback. Meanwhile, with partial information feedback, the advertiser could only have access to the highest competing bid in the auctions she participates in. We propose the OGD-CB algorithm, which involves simultaneous distribution learning and revenue optimization. In both settings, we demonstrate that this algorithm guarantees an $O(\sqrt{T\log T})$ regret with probability $1 - O(1/T)$ relative to the fluid adaptive throttling benchmark. By proving a lower bound of $\Omega(\sqrt{T})$ on the minimal regret for even the hindsight optimum, we establish the near optimality of our algorithm. Finally, we compare the fluid optimum of throttling to that of pacing, another widely adopted budget control method. The numerical relationship of these benchmarks sheds new light on the understanding of different online algorithms for revenue maximization under budget constraints. |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2207.04690&r= |
| By: | Kiran Tomlinson; Johan Ugander; Jon Kleinberg |
| Abstract: | Instant runoff voting (IRV) is an increasingly-popular alternative to traditional plurality voting in which voters submit rankings over the candidates rather than individual votes. In practice, municipalities often restrict the ballot length, the number of candidates a voter is allowed to rank on their ballot. We theoretically and empirically analyze how ballot length can influence the outcome of an election, given fixed voter preferences. We show that there exist preference profiles over $k$ candidates such that up to $k-1$ different candidates win at different ballot lengths. We derive exact lower bounds on the number of voters required for such profiles and provide constructions matching these bounds. Additionally, we fully characterize which sequences of winners are possible over ballot lengths and provide explicit profile constructions achieving any feasible winner sequence. Finally, we analyze a collection of 168 real-world elections, where we truncate rankings to simulate shorter ballots. We find that shorter ballots could have changed the outcome in one quarter of these elections and that longer ballots can favor particular candidates. Our results highlight ballot length as a consequential degree of freedom in the design of IRV elections. |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2207.08958&r= |
| By: | Gogulapati Sreedurga; Soumyarup Sadhukhan; Souvik Roy; Yadati Narahari |
| Abstract: | We study fairness in social choice settings under single-peaked preferences. Construction and characterization of social choice rules in the single-peaked domain has been extensively studied in prior works. In fact, in the single-peaked domain, it is known that unanimous and strategy-proof deterministic rules have to be min-max rules and those that also satisfy anonymity have to be median rules. Further, random social choice rules satisfying these properties have been shown to be convex combinations of respective deterministic rules. We non-trivially add to this body of results by including fairness considerations in social choice. Our study directly addresses fairness for groups of agents. To study group-fairness, we consider an existing partition of the agents into logical groups, based on natural attributes such as gender, race, and location. To capture fairness within each group, we introduce the notion of group-wise anonymity. To capture fairness across the groups, we propose a weak notion as well as a strong notion of fairness. The proposed fairness notions turn out to be natural generalizations of existing individual-fairness notions and moreover provide non-trivial outcomes for strict ordinal preferences, unlike the existing group-fairness notions. We provide two separate characterizations of random social choice rules that satisfy group-fairness: (i) direct characterization (ii) extreme point characterization (as convex combinations of fair deterministic social choice rules). We also explore the special case where there are no groups and provide sharper characterizations of rules that achieve individual-fairness. |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2207.07984&r= |
| By: | Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki |
| Abstract: | We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed. |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2207.02641&r= |
| By: | Tom Demeulemeester; Juan S. Pereyra |
| Abstract: | We study the assignment of indivisible objects to individuals when transfers are not allowed. Previous literature has mainly focused on efficiency (from an ex-ante and ex-post perspective), and individually fair assignments. Consequently, egalitarian concerns have been overlooked. We are inspired by the assignment of apartments in housing cooperatives where families regard the egalitarianism of the assignments as a first-order requirement. In particular, they want to avoid assignments where some families get their most preferred apartment, while others get options ranked very low in their preferences. Based on Rawls' idea of fairness, we introduce the notion of Rawlsian assignments. We prove that there always exists a unique Rawlsian assignment, which is ordinally efficient, and satisfies equal treatment of equals. We illustrate our analysis with preference data from housing cooperatives. Our results show that the Rawlsian assignment substantially improves, from an egalitarian perspective, both the probabilistic serial mechanism, and the mechanism currently in use. |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2207.02930&r= |
| By: | Jamie Tucker-Foltz; Richard Zeckhauser |
| Abstract: | We study the classic divide-and-choose method for equitably allocating divisible goods between two players who are rational, self-interested Bayesian agents. The players have additive private values for the goods. The prior distributions on those values are independent and common knowledge. We characterize the structure of optimal divisions in the divide-and-choose game and show how to efficiently compute equilibria. We identify several striking differences between optimal strategies in the cases of known versus unknown preferences. Most notably, the divider has a compelling "diversification" incentive in creating the chooser's two options. This incentive, hereto unnoticed, leads to multiple goods being divided at equilibrium, quite contrary to the divider's optimal strategy when preferences are known. In many contexts, such as buy-and-sell provisions between partners, or in judging fairness, it is important to assess the relative expected utilities of the divider and chooser. Those utilities, we show, depend on the players' uncertainties about each other's values, the number of goods being divided, and whether the divider can offer multiple alternative divisions. We prove that, when values are independently and identically distributed across players and goods, the chooser is strictly better off for a small number of goods, while the divider is strictly better off for a large number of goods. |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2207.03076&r= |
| By: | Kazuya Kikuchi; Yukio Koriyama |
| Abstract: | We consider collective decision making when the society consists of groups endowed with voting weights. Each group chooses an internal rule that specifies the allocation of its weight to the alternatives as a function of its members' preferences. Under fairly general conditions, we show that the winner-take-all rule is a dominant strategy, while the equilibrium is Pareto dominated, highlighting the dilemma structure between optimality for each group and for the whole society. We also develop a technique for asymptotic analysis and show Pareto dominance of the proportional rule. Our numerical computation for the US Electoral College verifies its sensibility. |
| Date: | 2022–06 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2206.09574&r= |
| By: | Edith Elkind; Abheek Ghosh; Paul W. Goldberg |
| Abstract: | We study a general scenario of simultaneous contests that allocate prizes based on equal sharing: each contest awards its prize to all players who satisfy some contest-specific criterion, and the value of this prize to a winner decreases as the number of winners increases. The players produce outputs for a set of activities, and the winning criteria of the contests are based on these outputs. We consider two variations of the model: (i) players have costs for producing outputs; (ii) players do not have costs but have generalized budget constraints. We observe that these games are exact potential games and hence always have a pure-strategy Nash equilibrium. The price of anarchy is $2$ for the budget model, but can be unbounded for the cost model. Our main results are for the computational complexity of these games. We prove that for general versions of the model exactly or approximately computing a best response is NP-hard. For natural restricted versions where best response is easy to compute, we show that finding a pure-strategy Nash equilibrium is PLS-complete, and finding a mixed-strategy Nash equilibrium is (PPAD$\cap$PLS)-complete. On the other hand, an approximate pure-strategy Nash equilibrium can be found in pseudo-polynomial time. These games are a strict but natural subclass of explicit congestion games, but they still have the same equilibrium hardness results. |
| Date: | 2022–07 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:2207.08151&r= |