Search

Motivated by online advertising auctions, we study auction design in repeated auctions played by simple Artificial Intelligence algorithms (Q-learning). We find that first-price auctions with no additional feedback lead to tacit-collusive outcomes (bids lower than values), while second-price auctions do not. We show that the difference is driven by the incentive in first-price auctions to outbid opponents by just one bid increment. This facilitates re-coordination on low bids after a phase of experimentation. We also show that providing information about lowest bid to win, as introduced by Google at the time of switch to first-price auctions, increases competitiveness of auctions., Comment: 30 pages, 11 figures

We study how long-lived, rational agents learn in a social network. In every period, after observing the past actions of his neighbors, each agent receives a private signal, and chooses an action whose payoff depends only on the state. Since equilibrium actions depend on higher order beliefs, it is difficult to characterize behavior. Nevertheless, we show that regardless of the size and shape of the network, the utility function, and the patience of the agents, the speed of learning in any equilibrium is bounded from above by a constant that only depends on the private signal distribution., Comment: 28 pages

I construct a novel random double auction as a robust bilateral trading mechanism for a profit-maximizing intermediary who facilitates trade between a buyer and a seller. It works as follows. The intermediary publicly commits to charging a fixed commission fee and randomly drawing a spread from a uniform distribution. Then the buyer submits a bid price and the seller submits an ask price simultaneously. If the difference between the bid price and the ask price is greater than the realized spread, then the asset is transacted at the midpoint price, and each pays the intermediary half of the fixed commission fee. Otherwise, no trade takes place, and no one pays or receives anything. I show that the random double auction maximizes the worst-case expected profit across all dominant-strategy incentive compatible and ex-post individually rational mechanisms for the symmetric case. I also construct a robust trading mechanism with similar properties for the asymmetric case.

We consider the problem of aggregating individual preferences over alternatives into a social ranking. A key feature of the problems that we consider, and the one that allows us to obtain positive results, in contrast to negative results such as Arrow's Impossibility Theorem, is that the alternatives to be ranked are outcomes of a competitive process. Examples include rankings of colleges or academic journals. The foundation of our ranking method is that alternatives that an agent desires, those that they have been rejected by, should be ranked higher than the one they receive. We provide a mechanism to produce a social ranking given any preference profile and outcome assignment, and characterize this ranking as the unique one that satisfies certain desirable axioms.

Cryptographic Self-Selection is a subroutine used to select a leader for modern proof-of-stake consensus protocols, such as Algorand. In cryptographic self-selection, each round $r$ has a seed $Q_r$. In round $r$, each account owner is asked to digitally sign $Q_r$, hash their digital signature to produce a credential, and then broadcast this credential to the entire network. A publicly-known function scores each credential in a manner so that the distribution of the lowest scoring credential is identical to the distribution of stake owned by each account. The user who broadcasts the lowest-scoring credential is the leader for round $r$, and their credential becomes the seed $Q_{r+1}$. Such protocols leave open the possibility of a selfish-mining style attack: a user who owns multiple accounts that each produce low-scoring credentials in round $r$ can selectively choose which ones to broadcast in order to influence the seed for round $r+1$. Indeed, the user can pre-compute their credentials for round $r+1$ for each potential seed, and broadcast only the credential (among those with a low enough score to be the leader) that produces the most favorable seed. We consider an adversary who wishes to maximize the expected fraction of rounds in which an account they own is the leader. We show such an adversary always benefits from deviating from the intended protocol, regardless of the fraction of the stake controlled. We characterize the optimal strategy; first by proving the existence of optimal positive recurrent strategies whenever the adversary owns last than $38\%$ of the stake. Then, we provide a Markov Decision Process formulation to compute the optimal strategy., 31 pages, ACM EC 2022

We study sequential bargaining between a proposer and a veto player. Both have single-peaked preferences, but the proposer is uncertain about the veto player's ideal point. The proposer cannot commit to future proposals. When players are patient, there can be equilibria with Coasian dynamics: the veto player's private information can largely nullify proposer's bargaining power. Our main result, however, is that under some conditions there are also equilibria in which the proposer obtains the high payoff that he would with commitment power. The driving force is that the veto player's single-peaked preferences give the proposer an option to "leapfrog", i.e., to secure agreement from only low-surplus types early on to credibly extract surplus from high types later. Methodologically, we exploit the connection between sequential bargaining and static mechanism design.

The internet advertising market is a multibillion dollar industry in which advertisers buy thousands of ad placements every day by repeatedly participating in auctions. An important and ubiquitous feature of these auctions is the presence of campaign budgets, which specify the maximum amount the advertisers are willing to pay over a specified time period. In this paper, we present a new model to study the equilibrium bidding strategies in standard auctions, a large class of auctions that includes first and second price auctions, for advertisers who satisfy budget constraints on average. Our model dispenses with the common yet unrealistic assumption that advertisers’ values are independent and instead assumes a contextual model in which advertisers determine their values using a common feature vector. We show the existence of a natural value pacing–based Bayes–Nash equilibrium under very mild assumptions. Furthermore, we prove a revenue equivalence showing that all standard auctions yield the same revenue even in the presence of budget constraints. Leveraging this equivalence, we prove price of anarchy bounds for liquid welfare and structural properties of pacing-based equilibria that hold for all standard auctions. In recent years, the internet advertising market has adopted first price auctions as the preferred paradigm for selling advertising slots. Our work, thus, takes an important step toward understanding the implications of the shift to first price auctions in internet advertising markets by studying how the choice of the selling mechanism impacts revenues, welfare, and advertisers’ bidding strategies. This paper was accepted by Itai Ashlagi, revenue management and market analytics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2023.4719 .

The expectation is an example of a descriptive statistic that is monotone with respect to stochastic dominance, and additive for sums of independent random variables. We provide a complete characterization of such statistics, and explore a number of applications to models of individual and group decision-making. These include a representation of stationary, monotone time preferences, extending the work of Fishburn and Rubinstein (1982) to time lotteries, as well as a characterization of risk-averse preferences over monetary gambles that are invariant to mean-zero background risks.

We study the effects of data sharing between firms on prices, profits, and consumer welfare. Although indiscriminate sharing of consumer data decreases firm profits due to the subsequent increase in competition, selective sharing can be beneficial. We show that there are data-sharing mechanisms that are strictly Pareto-improving, simultaneously increasing firm profits and consumer welfare. Within the class of Pareto-improving mechanisms, we identify one that maximizes firm profits and one that maximizes consumer welfare.

In selection processes such as hiring, promotion, and college admissions, implicit bias toward socially-salient attributes such as race, gender, or sexual orientation of candidates is known to produce persistent inequality and reduce aggregate utility for the decision maker. Interventions such as the Rooney Rule and its generalizations, which require the decision maker to select at least a specified number of individuals from each affected group, have been proposed to mitigate the adverse effects of implicit bias in selection. Recent works have established that such lower-bound constraints can be very effective in improving aggregate utility in the case when each individual belongs to at most one affected group. However, in several settings, individuals may belong to multiple affected groups and, consequently, face more extreme implicit bias due to this intersectionality. We consider independently drawn utilities and show that, in the intersectional case, the aforementioned non-intersectional constraints can only recover part of the total utility achievable in the absence of implicit bias. On the other hand, we show that if one includes appropriate lower-bound constraints on the intersections, almost all the utility achievable in the absence of implicit bias can be recovered. Thus, intersectional constraints can offer a significant advantage over a reductionist dimension-by-dimension non-intersectional approach to reducing inequality., This is the full version of a paper accepted for presentation in ACM FAccT 2022

We study a game theoretic model of standardized testing for college admissions. Students are of two types; High and Low. There is a college that would like to admit the High type students. Students take a potentially costly standardized exam which provides a noisy signal of their type. The students come from two populations, which are identical in talent (i.e. the type distribution is the same), but differ in their access to resources: the higher resourced population can at their option take the exam multiple times, whereas the lower resourced population can only take the exam once. We study two models of score reporting, which capture existing policies used by colleges. The first policy (sometimes known as "super-scoring") allows students to report the max of the scores they achieve. The other policy requires that all scores be reported. We find in our model that requiring that all scores be reported results in superior outcomes in equilibrium, both from the perspective of the college (the admissions rule is more accurate), and from the perspective of equity across populations: a student's probability of admission is independent of their population, conditional on their type. In particular, the false positive rates and false negative rates are identical in this setting, across the highly and poorly resourced student populations. This is the case despite the fact that the more highly resourced students can -- at their option -- either report a more accurate signal of their type, or pool with the lower resourced population under this policy.

In recent years, prominent blockchain systems such as Bitcoin and Ethereum have experienced explosive growth in transaction volume, leading to frequent surges in demand for limited block space and causing transaction fees to fluctuate by orders of magnitude. The status quo auctions sell space using a first-price auction [27]; however, users find it difficult to estimate how much they need to bid in order to get their transactions accepted onto the chain. If they bid too low, their transactions can have long confirmation times. If they bid too high, they pay larger fees than necessary. In light of these issues, new transaction fee mechanisms have been proposed, most notably EIP-1559 [4], aiming to provide better usability. EIP-1559 is a history-dependent mechanism that relies on block utilization to adjust a base fee. We propose an alternative design - a dynamic posted-price mechanism - which uses not only block utilization but also observable bids from past blocks to compute a posted-price for subsequent blocks. We show its potential to reduce price volatility by providing examples for which the prices of EIP-1559 are unstable while the prices of the proposed mechanism are stable. More generally, whenever the demand for the blockchain stabilizes, we ask if our mechanism is able to converge to a stable state. Our main result provides sufficient conditions in a probabilistic setting for which the proposed mechanism is approximately welfare optimal and the prices are stable. Our main technical contribution towards establishing stability is an iterative algorithm that, given oracle access to a Lipschitz continuous and strictly concave function f, converges to a fixed point of f.

Motivated by kidney exchange, we study the following mechanism-design problem: On a directed graph (of transplant compatibilities among patient-donor pairs), the mechanism must select a simple path (a chain of transplantations) starting at a distinguished vertex (an altruistic donor) such that the total length of this path is as large as possible (a maximum number of patients receive a kidney). However, the mechanism does not have direct access to the graph. Instead, the vertices are partitioned over multiple players (hospitals), and each player reports a subset of her vertices to the mechanism. In particular, a player may strategically omit vertices to increase how many of her vertices lie on the path returned by the mechanism. Our objective is to find mechanisms that limit incentives for such manipulation while producing long paths. Unfortunately, in worst-case instances, competing with the overall longest path is impossible while incentivizing (approximate) truthfulness, i.e., requiring that hiding nodes cannot increase a player's utility by more than a factor of $1 + o(1)$. We therefore adopt a semi-random model where a small ($o(n)$) number of random edges are added to worst-case instances. While it remains impossible for truthful mechanisms to compete with the overall longest path, we give a truthful mechanism that competes with a weaker but non-trivial benchmark: the length of any path whose subpaths within each player have a minimum average length. In fact, our mechanism satisfies even a stronger notion of truthfulness, which we call matching-time incentive compatibility. This notion of truthfulness requires that each player not only reports her nodes truthfully but also does not stop the returned path at any of her nodes in order to divert it to a continuation inside her own subgraph., Full version of EC'21 paper

We study the Proportional Response dynamic in exchange economies, where each player starts with some amount of money and a good. Every day, the players bring one unit of their good and submit bids on goods they like, each good gets allocated in proportion to the bid amounts, and each seller collects the bids received. Then every player updates the bids proportionally to the contribution of each good in their utility. This dynamic models a process of learning how to bid and has been studied in a series of papers on Fisher and production markets, but not in exchange economies. Our main results are as follows: - For linear utilities, the dynamic converges to market equilibrium utilities and allocations, while the bids and prices may cycle. We give a combinatorial characterization of limit cycles for prices and bids. - We introduce a lazy version of the dynamic, where players may save money for later, and show this converges in everything: utilities, allocations, and prices. - For CES utilities in the substitute range $[0,1)$, the dynamic converges for all parameters. This answers an open question about exchange economies with linear utilities, where tatonnement does not converge to market equilibria, and no natural process leading to equilibria was known. We also note that proportional response is a process where the players exchange goods throughout time (in out-of-equilibrium states), while tatonnement only explains how exchange happens in the limit., 25 pages, 6 figures

A monopolist seller of multiple goods screens a buyer whose type is initially unknown to both but drawn from a commonly known distribution. The buyer privately learns about his type via a signal. We derive the seller's optimal mechanism in two different information environments. We begin by deriving the buyer-optimal outcome. Here, an information designer first selects a signal, and then the seller chooses an optimal mechanism in response; the designer's objective is to maximize consumer surplus. Then, we derive the optimal informationally robust mechanism. In this case, the seller first chooses the mechanism, and then nature picks the signal that minimizes the seller's profits. We derive the relation between both problems and show that the optimal mechanism in both cases takes the form of pure bundling.

We study a repeated persuasion setting between a sender and a receiver, where at each time $t$, the sender observes a payoff-relevant state drawn independently and identically from an unknown prior distribution, and shares state information with the receiver, who then myopically chooses an action. As in the standard setting, the sender seeks to persuade the receiver into choosing actions that are aligned with the sender's preference by selectively sharing information about the state. However, in contrast to the standard models, the sender does not know the prior, and has to persuade while gradually learning the prior on the fly. We study the sender's learning problem of making persuasive action recommendations to achieve low regret against the optimal persuasion mechanism with the knowledge of the prior distribution. Our main positive result is an algorithm that, with high probability, is persuasive across all rounds and achieves $O(\sqrt{T\log T})$ regret, where $T$ is the horizon length. The core philosophy behind the design of our algorithm is to leverage robustness against the sender's ignorance of the prior. Intuitively, at each time our algorithm maintains a set of candidate priors, and chooses a persuasion scheme that is simultaneously persuasive for all of them. To demonstrate the effectiveness of our algorithm, we further prove that no algorithm can achieve regret better than $\Omega(\sqrt{T})$, even if the persuasiveness requirements were significantly relaxed. Therefore, our algorithm achieves optimal regret for the sender's learning problem up to terms logarithmic in $T$., Comment: 25 pages, 2 figures

Rationing of healthcare resources has emerged as an important issue, which has been discussed by medical experts, policy-makers, and the general public. We consider a rationing problem where medical units are to be allocated to patients. Each unit is reserved for one of several categories and each category has a priority ranking of the patients. We present an allocation rule that respects the priorities, complies with the eligibility requirements, allocates the largest feasible number of units, and does not incentivize agents to hide that they qualify through a category. The rule characterizes all possible allocations that satisfy the first three properties and is polynomial-time computable., The new version focusses on different rules and has new characterisation results

Pandemic response is a complex affair. Most governments employ a set of quasi-standard measures to fight COVID-19 including wearing masks, social distancing, virus testing and contact tracing. We argue that some non-trivial factors behind the varying effectiveness of these measures are selfish decision-making and the differing national implementations of the response mechanism. In this paper, through simple games, we show the effect of individual incentives on the decisions made with respect to wearing masks and social distancing, and how these may result in a sub-optimal outcome. We also demonstrate the responsibility of national authorities in designing these games properly regarding the chosen policies and their influence on the preferred outcome. We promote a mechanism design approach: it is in the best interest of every government to carefully balance social good and response costs when implementing their respective pandemic response mechanism.

We show that, with indivisible goods, the existence of competitive equilibrium fundamentally depends on agents' substitution effects, not their income effects. Our Equilibrium Existence Duality allows us to transport results on the existence of competitive equilibrium from settings with transferable utility to settings with income effects. One consequence is that net substitutability---which is a strictly weaker condition than gross substitutability---is sufficient for the existence of competitive equilibrium. We also extend the ``demand types'' classification of valuations to settings with income effects and give necessary and sufficient conditions for a pattern of substitution effects to guarantee the existence of competitive equilibrium., Comment: 46 pages, 1 figure

We initiate the study of the natural multiplayer generalization of the classic continuous Colonel Blotto game. The two-player Blotto game, introduced by Borel as a model of resource competition across $n$ simultaneous fronts, has been studied extensively for a century and seen numerous applications throughout the social sciences. Our work defines the multiplayer Colonel Blotto game and derives Nash equilibria for various settings of $k$ (number of players) and $n$. We also introduce a "Boolean" version of Blotto that becomes interesting in the multiplayer setting. The main technical difficulty of our work, as in the two-player theoretical literature, is the challenge of coupling various marginal distributions into a joint distribution satisfying a strict sum constraint. In contrast to previous works in the continuous setting, we derive our couplings algorithmically in the form of efficient sampling algorithms., Comment: 24 pages; minor additions to introduction

We consider the sale of a single item to multiple buyers by a revenue-maximizing seller. Recent work of Akbarpour and Li formalizes \emph{credibility} as an auction desideratum, and prove that the only optimal, credible, strategyproof auction is the ascending price auction with reserves (Akbarpour and Li, 2019). In contrast, when buyers' valuations are MHR, we show that the mild additional assumption of a cryptographically secure commitment scheme suffices for a simple \emph{two-round} auction which is optimal, strategyproof, and credible (even when the number of bidders is only known by the auctioneer). We extend our analysis to the case when buyer valuations are $\alpha$-strongly regular for any $\alpha > 0$, up to arbitrary $\varepsilon$ in credibility. Interestingly, we also prove that this construction cannot be extended to regular distributions, nor can the $\varepsilon$ be removed with multiple bidders.

We consider a robust version of the revenue maximization problem, where a single seller wishes to sell $n$ items to a single unit-demand buyer. In this robust version, the seller knows the buyer's marginal value distribution for each item separately, but not the joint distribution, and prices the items to maximize revenue in the worst case over all compatible correlation structures. We devise a computationally efficient (polynomial in the support size of the marginals) algorithm that computes the worst-case joint distribution for any choice of item prices. And yet, in sharp contrast to the additive buyer case (Carroll, 2017), we show that it is NP-hard to approximate the optimal choice of prices to within any factor better than $n^{1/2-\epsilon}$. For the special case of marginal distributions that satisfy the monotone hazard rate property, we show how to guarantee a constant fraction of the optimal worst-case revenue using item pricing; this pricing equates revenue across all possible correlations and can be computed efficiently.

27 pages; Following the ideas laid out in Myerson (1996), Hofbauer (2000) defined a Nash equilibrium of a finite game as sustainable if it can be made the unique Nash equilibrium of a game obtained by deleting/adding a subset of the strategies that are inferior replies to it. This paper proves two results about sustainable equilibria. The first concerns the Hofbauer-Myerson conjecture about the relationship between the sustainability of an equilibrium and its index: for a generic class of games, an equilibrium is sustainable iff its index is $+1$. Von Schemde and von Stengel (2008) proved this conjecture for bimatrix games; we show that the conjecture is true for all finite games. More precisely, we prove that an isolated equilibrium has index +1 if and only if it can be made unique in a larger game obtained by adding finitely many strategies that are inferior replies to that equilibrium. Our second result gives an axiomatic extension of sustainability to all games and shows that only the Nash components with positive index can be sustainable.

Using two lab experiments, we investigate the real-life performance of envy-free and proportional cake-cutting procedures with respect to fairness and preference manipulation. Although the observed subjects' strategic behavior eliminates the fairness guarantees of envy-free procedures, we nonetheless find evidence that suggests that envy-free procedures are fairer than their proportional counterparts. Our results support the practical use of the celebrated Selfridge-Conway procedure, and more generally, of envy-free cake-cutting mechanisms.We also find that subjects learn their opponents' preferences after repeated interaction and use this knowledge to improve their allocated share of the cake. Learning increases strategic behavior, but also reduces envy.

We introduce a model of probabilistic verification in a mechanism design setting. The principal selects a statistical test to verify the agent's claim. The agent's true type determines the probability with which he can pass each test. We characterize whether each type has an associated test that best screens out all other types, no matter the social choice rule. If this condition holds, then the testing technology can be represented in a tractable reduced form. We use this reduced form to solve for profit-maximizing mechanisms with verification. As verification improves, the solution continuously interpolates from the no-verification solution to full surplus extraction.

We describe our experience with designing and running a matching market for the Israeli "Mechinot" gap-year programs. The main conceptual challenge in the design of this market was the rich set of diversity considerations, which necessitated the development of an appropriate preference-specification language along with corresponding choice-function semantics, which we also theoretically analyze. Our contribution extends the existing toolbox for two-sided matching with soft constraints. This market was run for the first time in January 2018 and matched 1,607 candidates (out of a total of 3,120 candidates) to 35 different programs, has been run twice more since, and has been adopted by the Joint Council of the "Mechinot" gap-year programs for the foreseeable future.

This paper is an axiomatic study of consistent approval-based multi-winner rules, i.e., voting rules that select a fixed-size group of candidates based on approval ballots. We introduce the class of counting rules and provide an axiomatic characterization of this class based on the consistency axiom. Building upon this result, we axiomatically characterize three important consistent multi-winner rules: Proportional Approval Voting, Multi-Winner Approval Voting and the Approval Chamberlin--Courant rule. Our results demonstrate the variety of multi-winner rules and illustrate three different, orthogonal principles that multi-winner voting rules may represent: individual excellence, diversity, and proportionality., Comment: Presented at the 19th ACM Conference on Economics and Computation (EC 2018)

Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. Despite the simplicity of this problem, a classical result by Myerson and Satterthwaite (1983) affirms the impossibility of designing a mechanism which is simultaneously efficient, incentive compatible, individually rational, and budget balanced. This impossibility result fostered an intense investigation of meaningful trade-offs between these desired properties. Much work has focused on approximately efficient fixed-price mechanisms, i.e., Blumrosen and Dobzinski (2014; 2016), Colini-Baldeschi et al. (2016), which have been shown to fully characterize strong budget balanced and ex-post individually rational direct revelation mechanisms. All these results, however, either assume some knowledge on the priors of the seller/buyer valuations, or a black box access to some samples of the distributions, as in D{\"u}tting et al. (2021). In this paper, we cast for the first time the bilateral trade problem in a regret minimization framework over rounds of seller/buyer interactions, with no prior knowledge on the private seller/buyer valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different models of feedback and private valuations, using as benchmark the best fixed price in hindsight. More precisely, we prove the following bounds on the regret: $\bullet$ $\widetilde{\Theta}(\sqrt{T})$ for full-feedback (i.e., direct revelation mechanisms); $\bullet$ $\widetilde{\Theta}(T^{2/3})$ for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities; $\bullet$ $\Theta(T)$ for realistic feedback and seller/buyer valuations with bounded densities; $\bullet$ $\Theta(T)$ for realistic feedback and independent seller/buyer valuations; $\bullet$ $\Theta(T)$ for the adversarial setting.