Person:

Meir, Reshef

In this extended abstract, we consider simple coordination problems, such as allocating the right to use a shared sports facility in a way that maximizes its usage, or picking the time of a meeting in a way that maximizes attendance. More generally, an alternative is selected by a mechanism in period zero based on reports from agents. This induces a decision problem facing agents in the next period (e.g., to use a resource, or to attend a meeting.) Outcomes are designated as either good or bad, and the design goal is to maximize the probability of good outcomes. For example, a good outcome may be the resource being used, or having enough people attend a meeting.

We consider a recent innovative theory by Chastain et al. on the role of sex in evolution [10]. In short, the theory suggests that the evolutionary process of gene recombination implements the celebrated multiplicative weights updates algorithm (MWUA). They prove that the population dynamics induced by sexual reproduction can be precisely modeled by genes that use MWUA as their learning strategy in a particular coordination game. The result holds in the environments of weak selection, under the assumption that the population frequencies remain a product distribution.

We revisit the theory, eliminating both the requirement of weak selection and any assumption on the distribution of the population. Removing the assumption of product distributions is crucial, since as we show, this assumption is inconsistent with the population dynamics. We show that the marginal allele distributions induced by the population dynamics precisely match the marginals induced by a multiplicative weights update algorithm in this general setting, thereby affirming and substantially generalizing these earlier results.

We further revise the implications for convergence and utility or fitness guarantees in coordination games. In contrast to the claim of Chastain et al.[10], we conclude that the sexual evolutionary dynamics does not entail any property of the population distribution, beyond those already implied by convergence.

The existence of truthful social choice mechanisms strongly depends on whether monetary transfers are allowed. Without payments there are no truthful, non-dictatorial mechanisms under mild requirements, whereas the VCG mechanism guarantees truthfulness along with welfare maximization when there are payments and utility is quasi-linear in money. In this paper we study mechanisms in which we can use payments but where agents have non quasi-linear utility functions. Our main result extends the Gibbard-Satterthwaite impossibility result by showing that, for two agents, the only truthful mechanism for at least three alternatives under general decreasing utilities remains dictatorial. We then show how to extend the VCG mechanism to work under a more general utility space than quasi-linear (the "parallel domain) and show that the parallel domain is maximal—no mechanism with the VCG properties exists in any larger domain.

In many situations a player may act so as to maximize a perceived utility that is not exactly her utility function, but rather some other, biased, utility. Examples of such biased utility functions are common in behavioral economics, and include risk attitudes, altruism, present-bias and so on. When analyzing a game, one may ask how inefficiency, measured by the Price of Anarchy (PoA) is affected by the perceived utilities.

The smoothness method naturally extends to games with such perceived utilities or costs, regardless of the game or the behavioral bias. We show that such biased smoothness is broadly applicable in the context of nonatomic congestion games. First, we show that on series-parallel networks we can use smoothness to yield PoA bounds even for diverse populations with different biases. Second, we identify various classes of cost functions and biases that are smooth, thereby substantially improving some recent results from the literature.

Doodle is a simple and popular online system for scheduling events. It is an implementation of the approval voting mechanism, where candidates are the time slots and each responder approves a subset of the slots. We analyze all the Doodle polls created in the US from JulySeptember 2011 (over 340,000 polls), consisting of both hidden polls (where you cannot see other people’s votes) and open polls (where you can see all the previous responses). By analyzing the differences in behavior in hidden and open polls, we gain unique insights into strategies that people apply in natural voting settings. Responders in open polls are more likely to approve slots that are very popular or very unpopular, but not intermediate slots. We show that this behavior is inconsistent with models that have been proposed in the voting literature, and propose a new model based on combining personal and social utilities to explain the data.

Finding a common time slot for a group event is a daily conundrum and illustrates key features of group decision-making. It is a complex interplay of individual incentives and group dynamics. A participant would like the final time to be convenient for her, but she is also expected to be cooperative towards other people's preferences. We combine large-scale data analysis with theoretical models from the voting literature to investigate strategic behaviors in event scheduling. We analyze all Doodle polls created in the US from July-September 2011 (over 340,000 polls), consisting of both hidden polls (a user cannot see other responses) and open polls (a user can see all previous responses). By analyzing the differences in behavior in hidden and open polls, we gain unique insights into strategies that people apply in a natural decision-making setting. Responders in open polls are more likely to approve slots that are very popular or very unpopular, but not intermediate slots. We show that this behavior is inconsistent with models that have been proposed in the voting literature, and propose a new model based on combining personal and social utilities to explain the data.

We consider a recent innovative theory by Chastain et al. on the role of sex in evolution [PNAS'14]. In short, the theory suggests that the evolutionary process of gene recombination implements the celebrated multiplicative weights updates algorithm (MWUA). They prove that the population dynamics induced by sexual reproduction can be precisely modeled by genes that use MWUA as their learning strategy in a particular coordination game. The result holds in the environments of weak selection, under the assumption that the population frequencies remain a product distribution. We revisit the theory, eliminating both the requirement of weak selection and any assumption on the distribution of the population. Removing the assumption of product distributions is crucial, since as we show, this assumption is inconsistent with the population dynamics. We show that the marginal allele distributions induced by the population dynamics precisely match the marginals induced by a multiplicative weights update algorithm in this general setting, thereby affirming and substantially generalizing these earlier results. We further revise the implications for convergence and utility or fitness guarantees in coordination games. In contrast to the claim of Chastain et al.[PNAS'14], we conclude that the sexual evolutionary dynamics does not entail any property of the population distribution, beyond those already implied by convergence.

We put forward a new model of congestion games where agents have uncertainty over the routes used by other agents. We take a non-probabilistic approach, assuming that each agent knows that the number of agents using an edge is within a certain range. Given this uncertainty, we model agents who either minimize their worst-case cost (WCC) or their worst-case regret (WCR), and study implications on equilibrium existence, convergence through adaptive play, and efficiency. Under the WCC behavior the game reduces to a modified congestion game, and welfare improves when agents have moderate uncertainty. Under WCR behavior the game is not, in general, a congestion game, but we show convergence and efficiency bounds for a simple class of games.