No Arabic abstract
Many facts are learned through the intermediation of individuals with special access to information, such as law enforcement officers, officials with a security clearance, or experts with specific knowledge. This paper considers whether societies can learn about such facts when information is cheap to manipulate, produced sequentially, and these individuals are devoid of ethical motive. The answer depends on an information attrition condition pertaining to the amount of evidence available which distinguishes, for example, between reproducible scientific evidence and the evidence generated in a crime. Applications to institution enforcement, social cohesion, scientific progress, and historical revisionism are discussed.
We consider agents with non-linear preferences given by private values and private budgets. We quantify the extent to which posted pricing approximately optimizes welfare and revenue for a single agent. We give a reduction framework that extends the approximation of multi-agent pricing-based mechanisms from linear utility to nonlinear utility. This reduction framework is broadly applicable as Alaei et al. (2012) have shown that mechanisms for linear agents can generally be interpreted as pricing-based mechanisms. We give example applications of the framework to oblivious posted pricing (e.g., Chawla et al., 2010), sequential posted pricing (e.g., Yan, 2011), and virtual surplus maximization (Myerson, 1981).
We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful and envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional constraints are imposed on the mechanisms. Moreover, we provide bounds on the efficiency of mechanisms satisfying various properties, and give truthful mechanisms for multiple agents with restricted classes of valuations.
In 1998 a long-lost proposal for an election law by Gottlob Frege (1848--1925) was rediscovered in the Thuringer Universitats- und Landesbibliothek in Jena, Germany. The method that Frege proposed for the election of representatives of a constituency features a remarkable concern for the representation of minorities. Its core idea is that votes cast for unelected candidates are carried over to the next election, while elected candidates incur a cost of winning. We prove that this sensitivity to past elections guarantees a proportional representation of political opinions in the long run. We find that through a slight modification of Freges original method even stronger proportionality guarantees can be achieved. This modified version of Freges method also provides a novel solution to the apportionment problem, which is distinct from all of the best-known apportionment methods, while still possessing noteworthy proportionality properties.
The advent of machine learning tools has led to the rise of data markets. These data markets are characterized by multiple data purchasers interacting with a set of data sources. Data sources have more information about the quality of data than the data purchasers; additionally, data itself is a non-rivalrous good that can be shared with multiple parties at negligible marginal cost. In this paper, we study the multiple-principal, multiple-agent problem with non-rivalrous goods. Under the assumption that the principals payoff is quasilinear in the payments given to agents, we show that there is a fundamental degeneracy in the market of non-rivalrous goods. Specifically, for a general class of payment contracts, there will be an infinite set of generalized Nash equilibria. This multiplicity of equilibria also affects common refinements of equilibrium definitions intended to uniquely select an equilibrium: both variational equilibria and normalized equilibria will be non-unique in general. This implies that most existing equilibrium concepts cannot provide predictions on the outcomes of data markets emerging today. The results support the idea that modifications to payment contracts themselves are unlikely to yield a unique equilibrium, and either changes to the models of study or new equilibrium concepts will be required to determine unique equilibria in settings with multiple principals and a non-rivalrous good.
We consider an environment where players need to decide whether to buy a certain product (or adopt a technology) or not. The product is either good or bad but its true value is not known to the players. Instead, each player has her own private information on its quality. Each player can observe the previous actions of other players and estimate the quality of the product. A classic result in the literature shows that in similar settings information cascades occur where learning stops for the whole network and players repeat the actions of their predecessors. In contrast to the existing literature on informational cascades, in this work, players get more than one opportunity to act. In each turn, a player is chosen uniformly at random and can decide to buy the product and leave the market or to wait. We provide a characterization of structured perfect Bayesian equilibria (sPBE) with forward-looking strategies through a fixed-point equation of dimensionality that grows only quadratically with the number of players. In particular, a sufficient state for players strategies at each time instance is a pair of two integers, the first corresponding to the estimated quality of the good and the second indicating the number of players that cannot offer additional information about the good to the rest of the players. Based on this characterization we study informational cascades in two regimes. First, we show that for a discount factor strictly smaller than one, informational cascades happen with high probability as the number of players increases. Furthermore, only a small portion of the total information in the system is revealed before a cascade occurs. Secondly, and more surprisingly, we show that for a fixed number of players, as the discount factor approaches one, bad informational cascades are benign when the product is bad, and are completely eliminated when the discount factor equals one.