
on Economic Design 
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 principalagent 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 budgetconstrained while the principal is not. The agent participates in the mechanism, but she can (strategically) approach the principal for decisionmaking. We derive the revenuemaximizing mechanism in a twodimensional 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:2202&r= 
By:  Lamprirni Zarpala; Dimitris Voliotis 
Abstract:  We introduce the \enquote{localglobal} approach for a divisible portfolio and perform an equilibrium analysis for two variants of coreselecting auctions. Our main novelty is extending the NearestVCG pricing rule in a dynamic tworound setup, mitigating bidders' freeriding incentives and further reducing the sellers' costs. The tworound setup admits an informationrevelation 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 multidimensional 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 opensource library for multidimensional 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 budgetconstrained 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 secondprice 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 fullinformation 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 OGDCB 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 increasinglypopular 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 $k1$ 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 realworld 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 singlepeaked preferences. Construction and characterization of social choice rules in the singlepeaked domain has been extensively studied in prior works. In fact, in the singlepeaked domain, it is known that unanimous and strategyproof deterministic rules have to be minmax 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 nontrivially add to this body of results by including fairness considerations in social choice. Our study directly addresses fairness for groups of agents. To study groupfairness, 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 groupwise 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 individualfairness notions and moreover provide nontrivial outcomes for strict ordinal preferences, unlike the existing groupfairness notions. We provide two separate characterizations of random social choice rules that satisfy groupfairness: (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 individualfairness. 
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 envyfree matching when each agent is assigned a single item. Given an envyfree matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envyfree matching. We repeat this operation as long as we can. We prove that the resulting envyfree matching is uniquely determined up to the choice of an initial envyfree matching, and can be found in polynomial time. We call the resulting matching a reformist envyfree matching, and then we study a shortest sequence to obtain the reformist envyfree matching from an initial envyfree 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 polynomialtime algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixedparameter (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 exante and expost 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 firstorder 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 TuckerFoltz; Richard Zeckhauser 
Abstract:  We study the classic divideandchoose method for equitably allocating divisible goods between two players who are rational, selfinterested 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 divideandchoose 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 buyandsell 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 winnertakeall 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 contestspecific 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 purestrategy 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 NPhard. For natural restricted versions where best response is easy to compute, we show that finding a purestrategy Nash equilibrium is PLScomplete, and finding a mixedstrategy Nash equilibrium is (PPAD$\cap$PLS)complete. On the other hand, an approximate purestrategy Nash equilibrium can be found in pseudopolynomial 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= 