We investigate majority voting where agents possess private information about an unobservable ground truth that determines their preferences. In such settings, agents may hold different preferences and (collectively) engage in counterintuitive strategic behaviors. Previous work either assumes strategic behavior occurs without coordination or with unlimited coordination, yielding overly inclusive or exclusive predictions about voting outcomes. We incorporate coordination ability—the largest coalition size at which agents could strategically coordinate—into the analysis. Under the ex-ante Bayesian k-strong equilibrium framework, where no group of at most k agents can benefit from deviation, we provide closed-form characterizations of when informed majority decisions, the decision favored by the majority if the ground truth is common knowledge, are achievable. Specifically, we determine (1) when all k-strong equilibria reach the informed majority decision and (2) when at least one such equilibrium exists. These conditions depend on three factors: coordination ability, fraction of majority agents, and information structure. The boundary for the second question exhibits surprising complexity--non-continuous, non-linear, and segmental. Our results reveal the complicated landscape and provide refined predictions for strategic behavior across different coordination levels.

We study the voting problem with two alternatives where voters' preferences depend on a not-directly-observable state variable. While equilibria in the one-round voting mechanisms lead to a good decision, they are usually hard to compute and follow. We consider the two-round voting mechanism where the first round serves as a polling stage and the winning alternative only depends on the outcome of the second round. We show that the two-round voting mechanism is a powerful tool for making collective decisions. Firstly, every (approximated) equilibrium in the two-round voting mechanisms (asymptotically) leads to the decision preferred by the majority as if the state of the world were revealed to the voters. Moreover, there exist natural equilibria in the two-round game following intuitive behaviors such as informative voting, sincere voting, and surprisingly popular strategies. This sharply contrasts with the one-round voting mechanisms in the previous literature, where no simple equilibrium is known. Finally, we show that every equilibrium in the standard one-round majority vote mechanism gives an equilibrium in the two-round mechanisms that is not more complicated. Therefore, the two-round voting mechanism provides a natural equilibrium in every instance, including those where one-round voting fails, and it can reach an informed majority decision whenever one-round voting can. Our experiments on LLM voters also imply that two-round voting leads to the correct outcome more often than one-round voting under some circumstances.

Peer Reviewed

We study the group strategic behaviors in Bayesian games. Equilibria in previous work do not consider group strategic behaviors with bounded sizes and are too ''strong'' to exist in many scenarios. We propose the ex-ante Bayesian k-strong equilibrium and the Bayesian k-strong equilibrium, where no group of at most k agents can benefit from deviation. The two solution concepts differ in how agents calculate their utilities when contemplating whether a deviation is beneficial. Intuitively, agents are more conservative in the Bayesian k-strong equilibrium than in the ex-ante Bayesian k-strong equilibrium. With our solution concepts, we study collusion in the peer prediction mechanisms, as a representative of the Bayesian games with group strategic behaviors. We characterize the thresholds of the group size k so that truthful reporting in the peer prediction mechanism is an equilibrium for each solution concept, respectively. Our solution concepts can serve as criteria to evaluate the robustness of a peer prediction mechanism against collusion. Besides the peer prediction problem, we also discuss two other potential applications of our new solution concepts, voting and Blotto games, where introducing bounded group sizes provides more fine-grained insights into the behavior of strategic agents.

Recommendation algorithms play a pivotal role in shaping our media choices, which makes it crucial to comprehend their long-term impact on user behavior. These algorithms are often linked to two critical outcomes: homogenization, wherein users consume similar content despite disparate underlying preferences, and the filter bubble effect, wherein individuals with differing preferences only consume content aligned with their preferences (without much overlap with other users). Prior research assumes a trade-off between homogenization and filter bubble effects and then shows that personalized recommendations mitigate filter bubbles by fostering homogenization. However, because of this assumption of a tradeoff between these two effects, prior work cannot develop a more nuanced view of how recommendation systems may independently impact homogenization and filter bubble effects. We develop a more refined definition of homogenization and the filter bubble effect by decomposing them into two key metrics: how different the average consumption is between users (inter-user diversity) and how varied an individual's consumption is (intra-user diversity). We then use a novel agent-based simulation framework that enables a holistic view of the impact of recommendation systems on homogenization and filter bubble effects. Our simulations show that traditional recommendation algorithms (based on past behavior) mainly reduce filter bubbles by affecting inter-user diversity without significantly impacting intra-user diversity. Building on these findings, we introduce two new recommendation algorithms that take a more nuanced approach by accounting for both types of diversity.

Amidst growing uncertainty and frequent restructurings, the impacts of employee exits are becoming one of the central concerns for organizations. Using rich communication data from a large holding company, we examine the effects of employee departures on socialization networks among the remaining coworkers. Specifically, we investigate how network metrics change among people who historically interacted with departing employees. We find evidence of "breakdown" in communication among the remaining coworkers, who tend to become less connected with fewer interactions after their coworkers' departure. This effect appears to be moderated by both external factors, such as periods of high organizational stress, and internal factors, such as the characteristics of the departing employee. At the external level, periods of high stress correspond to greater communication breakdown; at the internal level, however, we find patterns suggesting individuals may end up better positioned in their networks after a network neighbor's departure. Overall, our study provides critical insights into managing workforce changes and preserving communication dynamics in the face of employee exits.

Because high-quality data is like oxygen for AI systems, effectively eliciting information from crowdsourcing workers has become a first-order problem for developing high-performance machine learning algorithms. Two prevalent paradigms, spot-checking and peer prediction, enable the design of mechanisms to evaluate and incentivize high-quality data from human labelers. So far, at least three metrics have been proposed to compare the performances of these techniques \citepzhang2022high,gao2016incentivizing,burrell2021measurement. However, different metrics lead to divergent and even contradictory results in various contexts. In this paper, we harmonize these divergent stories, showing that two of these metrics are actually the same within certain contexts and explain the divergence of the third. Moreover, we unify these different contexts by introducingSpot Check Equivalence, which offers an interpretable metric for the effectiveness of a peer prediction mechanism. Finally, we present two approaches to compute spot check equivalence in various contexts, where simulation results verify the effectiveness of our proposed metric.

Peer prediction aims to incentivize truthful reports from agents whose reports cannot be assessed with any objective ground truthful information. In the multi-task setting where each agent is asked multiple questions, a sequence of mechanisms have been proposed which are truthful — truth-telling is guaranteed to be an equilibrium, or even better, informed truthful — truth-telling is guaranteed to be one of the best-paid equilibria. However, these guarantees assume agents’ strategies are restricted to be task-independent: an agent’s report on a task is not affected by her information about other tasks.

We consider the crowdsourcing setting where, in response to the assigned tasks, agents strategically decide both how much effort to exert (from a continuum) and whether to manipulate their reports. The goal is to design payment mechanisms that (1) satisfy limited liability (all payments are non-negative), (2) reduce the principal’s cost of budget, (3) incentivize effort and (4) incentivize truthful responses. In our framework, the payment mechanism composes a performance measurement, which noisily evaluates agents’ effort based on their reports, and a payment function, which converts the scores output by the performance measurement to payments.

Multi-round competitions often double or triple the points awarded in the final round, calling it a bonus, to maximize spectators’ excitement. In a two-player competition with n rounds, we aim to derive the optimal bonus size to maximize the audience’s overall expected surprise (as defined in [7]). We model the audience’s prior belief over the two players’ ability levels as a beta distribution. Using a novel analysis that clarifies and simplifies the computation, we find that the optimal bonus depends greatly upon the prior belief and obtain solutions of various forms for both the case of a finite number of rounds and the asymptotic case. In an interesting special case, we show that the optimal bonus approximately and asymptotically equals to the “expected lead”, the number of points the weaker player will need to come back in expectation. Moreover, we observe that priors with a higher skewness lead to a higher optimal bonus size, and in the symmetric case, priors with a higher uncertainty also lead to a higher optimal bonus size. This matches our intuition since a highly asymmetric prior leads to a high “expected lead”, and a highly uncertain symmetric prior often leads to a lopsided game, which again benefits from a larger bonus.

We initiate the study of information elicitation mechanisms for a crowd containing both self-interested agents, who respond to incentives, and adversarial agents, who may collude to disrupt the system. Our mechanisms work in the peer prediction setting where ground truth need not be accessible to the mechanism or even exist.

Lock managers are among the most studied components in concurrency control and transactional systems. However, one question seems to have been generally overlooked: "When there are multiple lock requests on the same object, which one(s) should be granted first?"

While much of the research on transaction processing has focused on improving overall performance in terms of throughput and mean latency, surprisingly less attention has been given to performance predictability: how often individual transactions exhibit execution latency far from the mean. Performance predictability is increasingly important when transactions lie on the critical path of latency-sensitive applications, enterprise software, or interactive web services.

In this paper we study how the network of agents adopting a particular technology relates to the structure of the underlying network over which the technology adoption spreads. We develop a model and show that the network of agents adopting a particular technology may have characteristics that differ significantly from the social network of agents over which the technology spreads. For example, the network induced by a cascade may have a heavy-tailed degree distribution even if the original network does not.