Search

We consider a group of agents who can each take an irreversible costly action whose payoff depends on an unknown state. Agents learn about the state from private signals, as well as from past actions of their social network neighbors, which creates an incentive to postpone taking the action. We show that outcomes depend on network structure: on networks with a linear structure patient agents do not converge to the first-best action, while on regular directed tree networks they do.

We study a multi-agent contract design problem with moral hazard. In our model, each agent exerts costly effort towards an individual task at which it may either succeed or fail, and the principal, who wishes to encourage effort, has an exclusive-use budget that it can use to reward the agents. We first show that any optimal contract must distribute the entire budget among the successful agents. Moreover, every such contract is optimal for some objective function. Our main contribution is then to introduce a novel class of contracts, which we call Luce contracts, and show that there is always a Luce contract that is optimal. A (generic) Luce contract assigns weights to the agents and distributes the entire budget among the successful agents in proportion to their weights. Lastly, we characterize effort profiles that can be implemented by Luce contracts, and note that Luce contracts offer a desirable alternative for implementation over commonly studied contracts, like piece-rate and bonus-pool contracts, on account of their reward variance-minimizing property., Comment: 35 pages

We consider a principal agent project selection problem with asymmetric information. There are $N$ projects and the principal must select exactly one of them. Each project provides some profit to the principal and some payoff to the agent and these profits and payoffs are the agent's private information. We consider the principal's problem of finding an optimal mechanism for two different objectives: maximizing expected profit and maximizing the probability of choosing the most profitable project. Importantly, we assume partial verifiability so that the agent cannot report a project to be more profitable to the principal than it actually is. Under this no-overselling constraint, we characterize the set of implementable mechanisms. Using this characterization, we find that in the case of two projects, the optimal mechanism under both objectives takes the form of a simple cutoff mechanism. The simple structure of the optimal mechanism also allows us to find evidence in support of the well-known ally-principle which says that principal delegates more authority to an agent who shares their preferences., Comment: 20 pages, 2 figures

We consider the facility location problem in two dimensions. In particular, we consider a setting where agents have Euclidean preferences, defined by their ideal points, for a facility to be located in $\mathbb{R}^2$. We show that for the $p-norm$ ($p \geq 1$) objective, the coordinate-wise median mechanism (CM) has the lowest worst-case approximation ratio in the class of deterministic, anonymous, and strategyproof mechanisms. For the minisum objective and an odd number of agents $n$, we show that CM has a worst-case approximation ratio (AR) of $\sqrt{2}\frac{\sqrt{n^2+1}}{n+1}$. For the $p-norm$ social cost objective ($p\geq 2$), we find that the AR for CM is bounded above by $2^{\frac{3}{2}-\frac{2}{p}}$. We conjecture that the AR of CM actually equals the lower bound $2^{1-\frac{1}{p}}$ (as is the case for $p=2$ and $p=\infty$) for any $p\geq 2$., Comment: 25 pages, SAGT 2022

Let $\Sigma$ be a countable alphabet. For $r\geq 1$, an infinite sequence $s$ with characters from $\Sigma$ is called $r$-quasi-regular, if for each $\sigma\in\Sigma$ the ratio of the longest to shortest interval between consecutive occurrences of $\sigma$ in $s$ is bounded by $r$. In this paper, we answer a question asked by Kempe, Schulman, and Tamuz, and prove that for any probability distribution $\mathbf{p}$ on a finite alphabet $\Sigma$, there exists a $2$-quasi-regular infinite sequence with characters from $\Sigma$ and density of characters equal to $\mathbf{p}$. We also prove that as $\left\lVert\mathbf{p}\right\rVert_\infty$ tends to zero, the infimum of $r$ for which $r$-quasi-regular sequences with density $\mathbf{p}$ exist, tends to one. This result has a corollary in the Pinwheel Problem: as the smallest integer in the vector tends to infinity, the density threshold for Pinwheel schedulability tends to one., Comment: 47 pages

We say that two unitary or orthogonal representations of a finitely generated group $G$ are additive conjugates if they are intertwined by an additive map, which need not be continuous. We associate to each representation of $G$ a topological action that is a complete additive conjugacy invariant: the action of $G$ by group automorphisms on the Bohr compactification of the underlying Hilbert space. Using this construction we show that the property of having almost invariant vectors is an additive conjugacy invariant. As an application we show that $G$ is amenable if and only if there is a nonzero homomorphism from $L^2(G)$ into $\mathbb{R}/\mathbb{Z}$ that is invariant to the $G$-action., Comment: 16 pages

May's Theorem (1952), a celebrated result in social choice, provides the foundation for majority rule. May's crucial assumption of symmetry, often thought of as a procedural equity requirement, is violated by many choice procedures that grant voters identical roles. We show that a weakening of May's symmetry assumption allows for a far richer set of rules that still treat voters equally. We show that such rules can have minimal winning coalitions comprising a vanishing fraction of the population, but not less than the square root of the population size. Methodologically, we introduce techniques from group theory and illustrate their usefulness for the analysis of social choice questions., Comment: 43 pages, 5 figures

In the classic herding model, agents receive private signals about an underlying binary state of nature, and act sequentially to choose one of two possible actions, after observing the actions of their predecessors. We investigate what types of behaviors lead to asymptotic learning, where agents will eventually converge to the right action in probability. It is known that for rational agents and bounded signals, there will not be asymptotic learning. Does it help if the agents can be cooperative rather than act selfishly? This is simple to achieve if the agents are allowed to use randomized protocols. In this paper, we provide the first deterministic protocol under which asymptotic learning occurs. In addition, our protocol has the advantage of being much simpler than previous protocols.

In the classical herding literature, agents receive a private signal regarding a binary state of nature, and sequentially choose an action, after observing the actions of their predecessors. When the informativeness of private signals is unbounded, it is known that agents converge to the correct action and correct belief. We study how quickly convergence occurs, and show that it happens more slowly than it does when agents observe signals. However, we also show that the speed of learning from actions can be arbitrarily close to the speed of learning from signals. In particular, the expected time until the agents stop taking the wrong action can be either finite or infinite, depending on the private signal distribution. In the canonical case of Gaussian private signals we calculate the speed of convergence precisely, and show explicitly that, in this case, learning from actions is significantly slower than learning from signals., Comment: Forthcoming in the Journal of Economic Theory