Reshef Meir

AAAI Conference 2026 Conference Paper

On Condorcet’s Jury Theorem with Abstention

• Reshef Meir
• Ganesh Ghalme

The well-known Condorcet Jury Theorem states that, under majority rule, the better of two alternatives is chosen with probability approaching one as the population grows. We study an asymmetric setting where voters face varying participation costs and share a possibly heuristic belief about their pivotality (ability to influence the outcome). In a costly voting setup where voters abstain if their participation cost is greater than their pivotality estimate, we identify a single property of the heuristic belief---weakly vanishing pivotality---that gives rise to multiple stable equilibria in which elections are nearly tied. In contrast, strongly vanishing pivotality (as in the standard Calculus of Voting model) yields a unique, trivial equilibrium where only zero-cost voters participate as the population grows. We then characterize when nontrivial equilibria satisfy a version of the Jury Theorem: below a sharp threshold, the majority-preferred candidate wins with probability approaching one; above it, both candidates either win with equal probability.

TCS Journal 2026 Journal Article

Strategy-proof budgeting via a VCG-like mechanism

• Jonathan Wagner
• Reshef Meir

AAMAS Conference 2025 Conference Paper

To Stand on the Shoulders of Giants: Should We Protect Initial Discoveries in Multi-Agent Exploration?

• Hodaya Lampert
• Reshef Meir
• Kinneret Teodorescu

We present a game theoretic analysis of a competitive search game which clarifies the expected advantages and disadvantages of granting first innovators exclusive rights to enjoy subsequent discoveries. We compare the theoretical predictions with actual behavior of players in the lab and find that the benefit of protection stems from increasing exploration efficiency, rather than encouraging initial exploration efforts. The latter, which contradicts theoretical predictions, can be explained by the cognitive bias of underweighting rare events.

AAMAS Conference 2025 Conference Paper

Tyranny of the Minority in Social Choice: a Call to Arms

• Reshef Meir

The vast majority of research in social choice theory, be it axiomatic characterizations, welfare bounds, or equilibrium analysis, makes the implicit assumption that the entire affected population votes. However this ideal description is very far from the situation in practice, and even more so in the age of online voting and various direct democracy initiatives—often, a handful of avid voters effectively make the decisions for the silent majority. Our starting point is that abstention and partial participation are not a curious exception but the norm. We therefore argue that models of abstention should be given at least as much attention (if not more) as models of strategic behavior, and theoretical properties of voting rules such as welfare and fairness guarantees must be evaluated in light of such models in order to be relevant. To that end, we call the multiagent systems research community to design more effective tools to better handle both causes and effects of low participation; and highlight promising directions.

AAAI Conference 2024 Conference Paper

Efficient Online Crowdsourcing with Complex Annotations

• Reshef Meir
• Viet-An Nguyen
• Xu Chen
• Jagdish Ramakrishnan
• Udi Weinsberg

Crowdsourcing platforms use various truth discovery algorithms to aggregate annotations from multiple labelers. In an online setting, however, the main challenge is to decide whether to ask for more annotations for each item to efficiently trade off cost (i.e., the number of annotations) for quality of the aggregated annotations. In this paper, we propose a novel approach for general complex annotation (such as bounding boxes and taxonomy paths), that works in an online crowdsourcing setting. We prove that the expected average similarity of a labeler is linear in their accuracy conditional on the reported label. This enables us to infer reported label accuracy in a broad range of scenarios. We conduct extensive evaluations on real-world crowdsourcing data from Meta and show the effectiveness of our proposed online algorithms in improving the cost-quality trade-off.

IJCAI Conference 2023 Conference Paper

Convergence in Multi-Issue Iterative Voting under Uncertainty

• Joshua Kavner
• Reshef Meir
• Francesca Rossi
• Lirong Xia

We study strategic behavior in iterative plurality voting for multiple issues under uncertainty. We introduce a model synthesizing simultaneous multi-issue voting with local dominance theory, in which agents repeatedly update their votes based on sets of vote profiles they deem possible, and determine its convergence properties. After demonstrating that local dominance improvement dynamics may fail to converge, we present two sufficient model refinements that guarantee convergence from any initial vote profile for binary issues: constraining agents to have O-legal preferences, where issues are ordered by importance, and endowing agents with less uncertainty about issues they are modifying than others. Our empirical studies demonstrate that while cycles are common for agents without uncertainty, introducing uncertainty makes convergence almost guaranteed in practice.

AAAI Conference 2023 Conference Paper

Frustratingly Easy Truth Discovery

• Reshef Meir
• Ofra Amir
• Omer Ben-Porat
• Tsviel Ben Shabat
• Gal Cohensius
• Lirong Xia

Truth discovery is a general name for a broad range of statistical methods aimed to extract the correct answers to questions, based on multiple answers coming from noisy sources. For example, workers in a crowdsourcing platform. In this paper, we consider an extremely simple heuristic for estimating workers' competence using average proximity to other workers. We prove that this estimates well the actual competence level and enables separating high and low quality workers in a wide spectrum of domains and statistical models. Under Gaussian noise, this simple estimate is the unique solution to the MLE with a constant regularization factor. Finally, weighing workers according to their average proximity in a crowdsourcing setting, results in substantial improvement over unweighted aggregation and other truth discovery algorithms in practice.

AAMAS Conference 2023 Conference Paper

Mitigating Skewed Bidding for Conference Paper Assignment

• Inbal Rozenzweig
• Reshef Meir
• Nicholas Mattei
• Ofra Amir

The explosion of conference paper submissions in AI and related fields has underscored the need to improve many aspects of the peer review process, especially the matching of papers and reviewers. Recent work argues that the key to improve this matching is to modify aspects of the bidding phase itself, to ensure that the set of bids over papers is balanced, and in particular to avoid orphan papers, i. e. , those papers that receive no bids. In an attempt to understand and mitigate this problem, we have developed a flexible bidding platform to test adaptations to the bidding process. Using this platform, we performed a field experiment during the bidding phase of a medium-size international workshop that compared two bidding methods. We further examined via controlled experiments on Amazon Mechanical Turk various factors that affect bidding, in particular the order in which papers are presented [11, 17]; and information on paper demand [33]. Our results suggest that several simple adaptations, that can be added to any existing platform, may significantly reduce the skew in bids, thereby improving the allocation for both reviewers and conference organizers.

UAI Conference 2022 Conference Paper

Empirical bayes approach to truth discovery problems

• Tsviel Ben Shabat
• Reshef Meir
• David Azriel

When aggregating information from conflicting sources, one’s goal is to find the truth. Most real-value truth discovery (TD) algorithms try to achieve this goal by estimating the competence of each source and then aggregating the conflicting information by weighing each source’s answer proportionally to her competence. However, each of those algorithms requires more than a single source for such estimation and usually does not consider different estimation methods other than a weighted mean. Therefore, in this work we formulate, prove, and empirically test the conditions for an Empirical Bayes Estimator (EBE) to dominate the weighted mean aggregation. Our main result demonstrates that EBE, under mild conditions, can be used as a second step of any TD algorithm in order to reduce the expected error.

EUMAS Conference 2022 Conference Paper

Proxy Manipulation for Better Outcomes

• Gili Bielous
• Reshef Meir

Abstract This paper offers a framework for the study of strategic behavior in proxy voting, where non-active voters delegate their votes to active voters. It further studies how proxy voting affects the strategic behavior of non-active voters and proxies (active voters) under complete and partial information. We focus on the median voting rule for single-peaked preferences. Our results show strategyproofness with respect to non-active voters. Furthermore, while strategyproofness does not extend to proxies, we show that under mild restrictions strategic behavior can lead to socially optimal outcomes. For partial information settings, our results show that while convergence is guaranteed, it may be sub-optimal.

JAAMAS Journal 2022 Journal Article

Strategyproof facility location mechanisms on discrete trees

• Alina Filimonov
• Reshef Meir

Abstract We address the problem of strategyproof (SP) facility location mechanisms on discrete trees. Our main result is a full characterization of onto and SP mechanisms. In particular, we prove that when a single agent significantly affects the outcome, the trajectory of the facility is almost contained in the trajectory of the agent, and both move in the same direction along the common edges. We show tight relations of our characterization to previous results on discrete lines and on continuous trees. We then derive further implications of the main result for infinite discrete lines.

EUMAS Conference 2022 Conference Paper

Sybil-Resilient Social Choice with Low Voter Turnout

• Reshef Meir
• Nimrod Talmon
• Gal Shahaf
• Ehud Shapiro

Abstract We address social choice in the presence of sybils (fake or duplicate votes) and low turnout, two behaviors that may each distort the will of the society. To do so we assume the status quo as an ever-present distinguished alternative. We propose a general Reality Enforcing mechanism, which can be combined with arbitrary voting rules and operates by adding virtual votes that support the status quo. We measure the tradeoff between safety and liveness (the ability of non-abstaining non-sybil voters to maintain or to change the status quo, respectively) in a variety of voting domains and show a tight inherent limit to the amount of sybils and abstentions that can be tolerated.

AAMAS Conference 2022 Conference Paper

Welfare vs. Representation in Participatory Budgeting

• Roy Fairstein
• Dan Vilenchik
• Reshef Meir
• Kobi Gal

Participatory budgeting (PB) is a democratic process for allocating funds to projects based on the votes of members of the community. Different rules have been used to aggregate participants’ votes. A recent paper by Lackner and Skowron [12] studied the tradeoff between notions of social welfare and representation in the multi-winner voting, which is a special case of participatory budgeting with identical project costs. But there is little understanding of this trade-off in the more general PB setting. This paper provides a theoretical and empirical study of the worst-case guarantees of several common rules to better understand the trade-off between social welfare and representation. We show that many of the guarantees from the multi-winner setting do not generalize to the PB setting, and that the introduction of costs leads to substantially worse guarantees, thereby exacerbating the welfare-representation trade-off. We further study how the requirement of proportionality over voting rules effects the guarantees on social welfare and representation. We study the latter point also empirically, both on real and synthetic datasets. We show that variants of the recently suggested voting rule Rule-X (which satisfies proportionality) do very well in practice both with respect to social welfare and representation.

AAAI Conference 2021 Conference Paper

A Market-Inspired Bidding Scheme for Peer Review Paper Assignment

• Reshef Meir
• Jérôme Lang
• Julien Lesca
• Nicholas Mattei
• Natan Kaminsky

We propose a market-inspired bidding scheme for the assignment of paper reviews in large academic conferences. We provide an analysis of the incentives of reviewers during the bidding phase, when reviewers have both private costs and some information about the demand for each paper; and their goal is to obtain the best possible k papers for a predetermined k. We show that by assigning ‘budgets’ to reviewers and a ‘price’ for every paper that is (roughly) proportional to its demand, the best response of a reviewer is to bid sincerely, i. e. , on her most favorite papers, and match the budget even when it is not enforced. This game-theoretic analysis is based on a simple, prototypical assignment algorithm. We show via extensive simulations on bidding data from real conferences, that our bidding scheme would substantially improve both the bid distribution and the resulting assignment.

JAIR Journal 2021 Journal Article

Representative Committees of Peers

• Reshef Meir
• Fedor Sandomirskiy
• Moshe Tennenholtz

A population of voters must elect representatives among themselves to decide on a sequence of possibly unforeseen binary issues. Voters care only about the final decision, not the elected representatives. The disutility of a voter is proportional to the fraction of issues, where his preferences disagree with the decision. While an issue-by-issue vote by all voters would maximize social welfare, we are interested in how well the preferences of the population can be approximated by a small committee. We show that a k -sortition (a random committee of k voters with the majority vote within the committee) leads to an outcome within the factor 1+ O (1/√ k ) of the optimal social cost for any number of voters n, any number of issues m, and any preference profile. For a small number of issues m, the social cost can be made even closer to optimal by delegation procedures that weigh committee members according to their number of followers. However, for large m, we demonstrate that the k -sortition is the worst-case optimal rule within a broad family of committee-based rules that take into account metric information about the preference profile of the whole population.

AAMAS Conference 2021 Conference Paper

Strategyproof Facility Location Mechanisms on Discrete Trees

• Alina Filimonov
• Reshef Meir

We address the problem of strategyproof (SP) facility location mechanisms on discrete trees. Our main result is a full characterization of onto and SP mechanisms. In particular, we prove that when a single agent significantly affects the outcome, the trajectory of the facility is almost contained in the trajectory of the agent, and both move in the same direction along the common edges. We show tight relations of our characterization to previous results on discrete lines and on continuous trees. We then derive further implications of the main result for infinite discrete lines.

ECAI Conference 2020 Conference Paper

Bidding in Spades

• Gal Cohensius
• Reshef Meir
• Nadav Oved
• Roni Stern

We present a Spades bidding algorithm that is superior to recreational human players and to publicly available bots. Like in Bridge, the game of Spades is composed of two independent phases, bidding and playing. This paper focuses on the bidding algorithm, since this phase holds a precise challenge: based on the input, choose the bid that maximizes the agent’s winning probability. Our Bidding-in-Spades (BIS) algorithm heuristically determines the bidding strategy by comparing the expected utility of each possible bid. A major challenge is how to estimate these expected utilities. To this end, we propose a set of domain-specific heuristics, and then correct them via machine learning using data from real-world players. The BIS algorithm we present can be attached to any playing algorithm. It beats rule-based bidding bots when all use the same playing component. When combined with a rule-based playing algorithm, it is superior to the average recreational human.

AAAI Conference 2020 Conference Paper

Distance-Based Equilibria in Normal-Form Games

• Erman Acar
• Reshef Meir

We propose a simple uncertainty modification for the agent model in normal-form games; at any given strategy profile, the agent can access only a set of “possible profiles” that are within a certain distance from the actual action profile. We investigate the various instantiations in which the agent chooses her strategy using well-known rationales e. g. , considering the worst case, or trying to minimize the regret, to cope with such uncertainty. Any such modification in the behavioral model naturally induces a corresponding notion of equilibrium; a distance-based equilibrium. We characterize the relationships between the various equilibria, and also their connections to well-known existing solution concepts such as Trembling-hand perfection. Furthermore, we deliver existence results, and show that for some class of games, such solution concepts can actually lead to better outcomes.

JAAMAS Journal 2020 Journal Article

Strategic voting in the lab: compromise and leader bias behavior

• Reshef Meir
• Kobi Gal
• Maor Tal

Abstract Plurality voting is perhaps the most commonly used way to aggregate the preferences of multiple voters. Yet, there is no consensus on how people vote strategically, even in very simple settings. The purpose of this paper is to provide a comprehensive study of people’s voting behavior in various online settings under the plurality rule. We implemented voting games that replicate two common real-world voting scenarios in controlled experiments. In the first, a single voter votes once after seeing a pre-election poll. In the second game, a group of voters play an iterative game, and change their vote as the game progresses (as in online voting). The winning candidate in each game (and hence the subject’s payment) is determined using the plurality rule. For each of these settings we generated hundreds of game instances, varying conditions such as the number of voters, subjects’ preferences over candidates and the poll information that was made available to the subjects prior to voting. We show that people can be classified into several groups, one of which is not engaged in any strategic behavior, while the largest group demonstrates both a tendency for strategic compromise, and a bias toward voting for the leader in the poll. We provide a detailed analysis of this group behavior for both settings, and how it depends on the poll information. Our study has insight for multi-agent system designers in uncovering patterns that provide reasonable predictions of voters’ behaviors, which may facilitate the design of agents that support people or act autonomously in voting systems.

AAMAS Conference 2019 Conference Paper

Contingent Payment Mechanisms for Resource Utilization

• Hongyao Ma
• Reshef Meir
• David C. Parkes
• James Zou

We introduce the problem of assigning resources to improve their utilization, for settings where agents have uncertainty about their own values for using a resource, and where it is in the interest of the society or the planner that resources be used and not wasted. Done in the right way, improved utilization maximizes social welfare— balancing the utility of a high value but unreliable agent with the group’s preference that resources be used. We introduce the family of contingent payment mechanisms (CP), which may charge an agent contingent on use (a penalty). A CP mechanism is parameterized by a maximum penalty, and has a simple dominant-strategy equilibrium. Under a set of axiomatic properties, we establish welfareoptimality for the special case CP(W ), with CP instantiated for a maximum penalty equal to societal value W for utilization. The special case with no upper bound on penalty, the contingent secondprice mechanism, maximizes utilization. We extend the mechanisms to assign multiple, heterogeneous resources, and present a simulation study of the welfare properties of these mechanisms.

AAAI Conference 2019 Conference Paper

Heuristic Voting as Ordinal Dominance Strategies

• Omer Lev
• Reshef Meir
• Svetlana Obraztsova
• Maria Polukarov

Decision making under uncertainty is a key component of many AI settings, and in particular of voting scenarios where strategic agents are trying to reach a joint decision. The common approach to handle uncertainty is by maximizing expected utility, which requires a cardinal utility function as well as detailed probabilistic information. However, often such probabilities are not easy to estimate or apply. To this end, we present a framework that allows for “shades of gray” of likelihood without probabilities. Specifically, we create a hierarchy of sets of world states based on a prospective poll, with inner sets contain more likely outcomes. This hierarchy of likelihoods allows us to define what we term ordinally-dominated strategies. We use this approach to justify various known voting heuristics as bounded-rational strategies.

AAMAS Conference 2019 Conference Paper

Modeling People's Voting Behavior with Poll Information

• Roy Fairstein
• Adam Lauz
• Reshef Meir
• Kobi Gal

Despite the prevalence of voting systems in the real world there is no consensus among researchers of how people vote strategically, even in simple voting settings. This paper addresses this gap by comparing different approaches that have been used to model strategic voting, including expected utility maximization, heuristic decisionmaking, and bounded rationality models. The models are applied to data collected from hundreds of people in controlled voting experiments, where people vote after observing non-binding poll information. We introduce a new voting model, the Attainability- Utility (AU) heuristic, which weighs the popularity of a candidate according to the poll, with the utility of the candidate to the voter. We argue that the AU model is cognitively plausible, and show that it is able to predict people’s voting behavior significantly better than other models from the literature. It was almost at par with (and sometimes better than) a machine learning algorithm that uses substantially more information. Our results provide new insights into the strategic considerations of voters, that undermine the prevalent assumptions of much theoretical work in social choice.

AAMAS Conference 2019 Conference Paper

Strategyproof Facility Location for Three Agents on a Circle

• Reshef Meir

We present two randomized facility location mechanisms on a circle that are strictly better than Random Dictator, and provide the first lower bound for randomized strategyproof facility location problems.

JAIR Journal 2018 Journal Article

Bounds on the Cost of Stabilizing a Cooperative Game

• Yoram Bachrach
• Edith Elkind
• Enrico Malizia
• Reshef Meir
• Dmitrii Pasechnik
• Jeffrey S. Rosenschein
• Jörg Rothe
• Michael Zuckerman

A key issue in cooperative game theory is coalitional stability, usually captured by the notion of the core---the set of outcomes that are resistant to group deviations. However, some coalitional games have empty cores, and any outcome in such a game is unstable. We investigate the possibility of stabilizing a coalitional game by using subsidies. We consider scenarios where an external party that is interested in having the players work together offers a supplemental payment to the grand coalition, or, more generally, a particular coalition structure. This payment is conditional on players not deviating from this coalition structure, and may be divided among the players in any way they wish. We define the cost of stability as the minimum external payment that stabilizes the game. We provide tight bounds on the cost of stability, both for games where the coalitional values are nonnegative (profit-sharing games) and for games where the coalitional values are nonpositive (cost-sharing games), under natural assumptions on the characteristic function, such as superadditivity, anonymity, or both. We also investigate the relationship between the cost of stability and several variants of the least core. Finally, we study the computational complexity of problems related to the cost of stability, with a focus on weighted voting games.

MFCS Conference 2018 Conference Paper

Directed Graph Minors and Serial-Parallel Width

• Argyrios Deligkas
• Reshef Meir

Graph minors are a primary tool in understanding the structure of undirected graphs, with many conceptual and algorithmic implications. We propose new variants of directed graph minors and directed graph embeddings, by modifying familiar definitions. For the class of 2-terminal directed acyclic graphs (TDAGs) our two definitions coincide, and the class is closed under both operations. The usefulness of our directed minor operations is demonstrated by characterizing all TDAGs with serial-parallel width at most k; a class of networks known to guarantee bounded negative externality in nonatomic routing games. Our characterization implies that a TDAG has serial-parallel width of 1 if and only if it is a directed series-parallel graph. We also study the computational complexity of finding a directed minor and computing the serial-parallel width.

AAMAS Conference 2018 Conference Paper

Playing the Wrong Game: Bounding Externalities in Diverse Populations of Agents

• Reshef Meir
• David Parkes

The robustness of multiagent systems can be affected by mistakes or behavioral biases (e. g. , risk-aversion, altruism, toll-sensitivity), with some agents playing the “wrong game. ” This can change the set of equilibria, and may in turn harm or improve the social welfare of agents in the system. We are interested in bounding what we call the biased price of anarchy (BPoA) in populations with diverse agent behaviors, which is the ratio between welfare in the “wrong” equilibrium and optimal welfare. We study nonatomic routing games, and derive an externality bound that depends on a key topological parameter of the underlying network. We then prove two general BPoA bounds for games with diverse populations: one that relies on the network structure and the average bias of all agents in the population, and one that is independent of the structure but depends on the maximal bias. Both types of bounds can be combined with known results to derive concrete BPoA bounds for a variety of specific behaviors (e. g. , varied levels of risk-aversion).

IJCAI Conference 2017 Conference Paper

Contract Design for Energy Demand Response

• Reshef Meir
• Hongyao Ma
• Valentin Robu

Power companies such as Southern California Edison (SCE) uses Demand Response (DR) contracts to incentivize consumers to reduce their power consumption during periods when demand forecast exceeds supply. Current mechanisms in use offer contracts to consumers independent of one another, do not take into consideration consumers' heterogeneity in consumption profile or reliability, and fail to achieve high participation. We introduce DR-VCG, a new DR mechanism that offers a flexible set of contracts (which may include the standard SCE contracts) and uses VCG pricing. We prove that DR-VCG elicits truthful bids, incentivizes honest preparation efforts, and enables efficient computation of allocation and prices. With simple fixed-penalty contracts, the optimization goal of the mechanism is an upper bound on probability that the reduction target is missed. Extensive simulations show that compared to the current mechanism deployed by SCE, the DR-VCG mechanism achieves higher participation, increased reliability, and significantly reduced total expenses.

AIJ Journal 2017 Journal Article

Iterative voting and acyclic games

• Reshef Meir
• Maria Polukarov
• Jeffrey S. Rosenschein
• Nicholas R. Jennings

AAMAS Conference 2017 Conference Paper

Proxy Voting for Better Outcomes

• Gal Cohensius
• Shie Mannor
• Reshef Meir
• Eli Meirom
• Ariel Orda

IS Journal 2016 Journal Article

AI's 10 to Watch

• Haris Aziz
• Elias Bareinboim
• Yejin Choi
• Daniel Hsu
• Shivaram Kalyanakrishnan
• Reshef Meir
• Suchi Saria
• Gerardo I. Simari

IEEE Intelligent Systems once again selected 10 young AI scientists as " AI's 10 to Watch. " This acknowledgment and celebration not only recognizes these young scientists and makes a positive impact in their academic career but also promotes the community and cutting-edge AI research among next-generation AI researchers, the industry, and the general public alike. The contributions are "Collective Decision Making in Multi-Agent Systems, " by Haris Aziz, "From Causal Inference and Data Fusion to an Automated Scientist, " by Elias Bareinboim, "Language, Vision, and Social AI, " by Yejin Choi, "Algorithms for Machine Learning, " by Daniel Hsu, "Learning Agents, " by Shivaram Kalyanakrishnan, "Strategy and Bounded Rationality, " by Reshef Meir, "; A Reasoning Engine for Tailoring Healthcare to the Individual, " by Suchi Saria, "Pushing the Limits of Knowledge Representation and Reasoning, " by Gerardo I. Simari, "Better Group Decision Making, " by Lirong Xia, and "Distributed Constraint Optimization, " by William Yeoh.

IJCAI Conference 2016 Conference Paper

Social Choice for Agents with General Utilities

• Hongyao Ma
• Reshef Meir
• David C. Parkes

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.

AAAI Conference 2015 Conference Paper

Congestion Games with Distance-Based Strict Uncertainty

• Reshef Meir
• David Parkes

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 worstcase 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.

AAAI Conference 2015 Conference Paper

Plurality Voting Under Uncertainty

• Reshef Meir

Understanding the nature of strategic voting is the holy grail of social choice theory, where game-theory, social science and recently computational approaches are all applied in order to model the incentives and behavior of voters. In a recent paper, Meir et al. (2014) made another step in this direction, by suggesting a behavioral game-theoretic model for voters under uncertainty. For a specific variation of best-response heuristics, they proved initial existence and convergence results in the Plurality voting system. This paper extends the model in multiple directions, considering voters with different uncertainty levels, simultaneous strategic decisions, and a more permissive notion of bestresponse. It is proved that a voting equilibrium exists even in the most general case. Further, any society voting in an iterative setting is guaranteed to converge to an equilibrium. An alternative behavior is analyzed, where voters try to minimize their worst-case regret. As it turns out, the two behaviors coincide in the simple setting of Meir et al. (2014), but not in the general case.

AIJ Journal 2014 Journal Article

On the value of using group discounts under price competition

• Reshef Meir
• Tyler Lu
• Moshe Tennenholtz
• Craig Boutilier

AAAI Conference 2013 Conference Paper

Bounding the Cost of Stability in Games over Interaction Networks

• Reshef Meir
• Yair Zick
• Edith Elkind
• Jeffrey Rosenschein

We study the stability of cooperative games played over an interaction network, in a model that was introduced by Myerson (1977). We show that the cost of stability of such games (i. e. , the subsidy required to stabilize the game) can be bounded in terms of natural parameters of their underlying interaction networks. Specifically, we prove that if the treewidth of the interaction network H is k, then the relative cost of stability of any game played over H is at most k + 1, and if the pathwidth of H is k, then the relative cost of stability is at most k. We show that these bounds are tight for all k ≥ 2 and all k ≥ 1, respectively.

AAAI Conference 2013 Conference Paper

Bundling Attacks in Judgment Aggregation

• Noga Alon
• Dvir Falik
• Reshef Meir
• Moshe Tennenholtz

We consider judgment aggregation over multiple independent issues, where the chairperson has her own opinion, and can try to bias the outcome by bundling several issues together. Since for each bundle judges must give a uniform answer on all issues, different partitions of the issues may result in an outcome that significantly differs from the “true”, issue-wise, decision. We prove that the bundling problem faced by the chairperson, i. e. trying to bias the outcome towards her own opinion, is computationally difficult in the worst case. Then we study the probability that an effective bundling attack exists as the disparity between the opinions of the judges and the chair varies. We show that if every judge initially agrees with the chair on every issue with probability of at least 1/2, then there is almost always a bundling attack (i. e. a partition) where the opinion of the chair on all issues is approved. Moreover, such a partition can be found efficiently. In contrast, when the probability is lower than 1/2 then the chair cannot force her opinion using bundling even on a single issue.

AAAI Conference 2013 Conference Paper

On the Value of Using Group Discounts under Price Competition

• Reshef Meir
• Tyler Lu
• Moshe Tennenholtz
• Craig Boutilier

The increasing use of group discounts has provided opportunities for buying groups with diverse preferences to coordinate their behavior in order to exploit the best offers from multiple vendors. We analyze this problem from the viewpoint of the vendors, asking under what conditions a vendor should adopt a volume-based price schedule rather than posting a fixed price, either as a monopolist or when competing with other vendors. When vendors have uncertainty about buyers’ valuations specified by a known distribution, we show that a vendor is always better off posting a fixed price, provided that buyers’ types are i. i. d. and that other vendors also use fixed prices. We also show that these assumptions cannot be relaxed: if buyers are not i. i. d. , or other vendors post discount schedules, then posting a schedule may yield higher profit for the vendor. We provide similar results under a distribution-free uncertainty model, where vendors minimize their maximum regret over all type realizations.

AIJ Journal 2012 Journal Article

Algorithms for strategyproof classification

• Reshef Meir
• Ariel D. Procaccia
• Jeffrey S. Rosenschein

AAAI Conference 2012 Conference Paper

Congestion Games with Agent Failures

• Reshef Meir
• Moshe Tennenholtz
• Yoram Bachrach
• Peter Key

We propose a natural model for agent failures in congestion games. In our model, each of the agents may fail to participate in the game, introducing uncertainty regarding the set of active agents. We examine how such uncertainty may change the Nash equilibria (NE) of the game. We prove that although the perturbed game induced by the failure model is not always a congestion game, it still admits at least one pure Nash equilibrium. Then, we turn to examine the effect of failures on the maximal social cost in any NE of the perturbed game. We show that in the limit case where failure probability is negligible new equilibria never emerge, and that the social cost may decrease but it never increases. For the case of nonnegligible failure probabilities, we provide a full characterization of the maximal impact of failures on the social cost under worst-case equilibrium outcomes.

AAMAS Conference 2012 Conference Paper

Stablity Scores: Measuring Coalitional Stability

• Michal Feldman
• Reshef Meir
• Moshe Tennenholtz

We introduce a measure for the level of stability against coalitional deviations, called \emph{stability scores}, which generalizes widely used notions of stability in non-cooperative games. We use the proposed measure to compare various Nash equilibria in congestion games, and to quantify the effect of game parameters on coalitional stability. For our main results, we apply stability scores to analyze and compare the Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG) ad auctions. We show that while a central result of the ad auction literatures is that the GSP and VCG auctions implement the same outcome in one of the equilibria of GSP, the GSP outcome is far more stable. Finally, a modified version of VCG is introduced, which is group strategy-proof, and thereby achieves the highest possible stability score.

IJCAI Conference 2011 Conference Paper

Research Proposal: Cooperation among Self Interested Agents

• Reshef Meir

This proposal briefly describes my recent work on prompting cooperation in two related domains, and outlines some future directions.

UAI Conference 2011 Conference Paper

Solving Cooperative Reliability Games

• Yoram Bachrach
• Reshef Meir
• Michal Feldman
• Moshe Tennenholtz

Cooperative games model the allocation of profit from joint actions, following considerations such as stability and fairness. We propose the reliability extension of such games, where agents may fail to participate in the game. In the reliability extension, each agent only "survives" with a certain probability, and a coalition's value is the probability that its surviving members would be a winning coalition in the base game. We study prominent solution concepts in such games, showing how to approximate the Shapley value and how to compute the core in games with few agent types. We also show that applying the reliability extension may stabilize the game, making the core non-empty even when the base game has an empty core.

IJCAI Conference 2011 Conference Paper

Subsidies, Stability, and Restricted Cooperation in Coalitional Games

• Reshef Meir
• Jeffrey S. Rosenschein
• Enrico Malizia

Cooperation among automated agents is becoming increasingly important in various artificial intelligence applications. Coalitional (i. e. , cooperative) game theory supplies conceptual and mathematical tools useful in the analysis of such interactions, and in particular in the achievement of stable outcomes among self-interested agents. Here, we study the minimal external subsidy required to stabilize the core of a coalitional game. Following the Cost of Stability (CoS) model introduced by Bachrach et al. [2009a], we give tight bounds on the required subsidy under various restrictions on the social structure of the game. We then compare the extended core induced by subsidies with the least core of the game, proving tight bounds on the ratio between the minimal subsidy and the minimal demand relaxation that each lead to stability.

AAMAS Conference 2011 Conference Paper

Tight Bounds for Strategyproof Classification

• Reshef Meir
• Shaull Almagor
• Assaf Michaely
• Jeffrey S. Rosenschein

Strategyproof (SP) classification considers situations in which a decision-maker must classify a set of input points with binary labels, minimizing expected error. Labels of input points are reported by self-interested agents, who may lie so as to obtain a classifier more closely matching their own labels. These lies would create a bias in the data, and thus motivate the design of truthful mechanisms that discourage false reporting. We here answer questions left open by previous research on strategyproof classification, in particular regarding the best approximation ratio (in terms of social welfare) that an SP mechanism can guarantee for n agents. Our primary result is a lower bound of 3 - 2/n on the approximation ratio of SP mechanisms under the shared inputs assumption; this shows that the previously known upper bound (for uniform weights) is tight. The proof relies on a result from Social Choice theory, showing that any SP mechanism must select a dictator at random, according to some fixed distribution. We then show how different randomizations can improve the best known mechanism when agents are weighted, matching the lower bound with a tight upper bound. These results contribute both to a better understanding of the limits of SP classification, as well as to the development of similar tools in other, related domains such as SP facility location.

AAAI Conference 2010 Conference Paper

Coalitional Structure Generation in Skill Games

• Yoram Bachrach
• Reshef Meir
• Kyomin Jung
• Pushmeet Kohli

We consider optimizing the coalition structure in Coalitional Skill Games (CSGs), a succinct representation of coalitional games (Bachrach and Rosenschein 2008). In CSGs, the value of a coalition depends on the tasks its members can achieve. The tasks require various skills to complete them, and agents may have different skill sets. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that CSGs can represent any characteristic function, and consider optimal coalition structure generation in this representation. We provide hardness results, showing that in general CSGs, as well as in very restricted versions of them, computing the optimal coalition structure is hard. On the positive side, we show that the problem can be reformulated as constraint satisfaction on a hyper graph, and present an algorithm that finds the optimal coalition structure in polynomial time for instances with bounded tree-width and number of tasks.

AAAI Conference 2010 Conference Paper

Convergence to Equilibria in Plurality Voting

• Reshef Meir
• Maria Polukarov
• Jeffrey Rosenschein
• Nicholas Jennings

Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to AI. In such situations, agents’ individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. Based on the fact that agents may have incentives to vote strategically and misreport their real preferences, a number of recent papers have explored different possibilities for avoiding or eliminating such manipulations. In contrast to most prior work, this paper focuses on convergence of strategic behavior to a decision from which no voter will want to deviate. We consider scenarios where voters cannot coordinate their actions, but are allowed to change their vote after observing the current outcome. We focus on the Plurality voting rule, and study the conditions under which this iterative game is guaranteed to converge to a Nash equilibrium (i. e. , to a decision that is stable against further unilateral manipulations). We show for the first time how convergence depends on the exact attributes of the game, such as the tie-breaking scheme, and on assumptions regarding agents’ weights and strategies.

AAMAS Conference 2010 Conference Paper

On the Limits of Dictatorial Classification

• Reshef Meir
• Ariel Procaccia
• Jeffrey Rosenschein

In the strategyproof classification setting, a set of labeledexamples is partitioned among multiple agents. Given thereported labels, an optimal classification mechanism returnsa classifier that minimizes the number of mislabeled examples. However, each agent is interested in the accuracy ofthe returned classifier on its own examples, and may misreport its labels in order to achieve a better classifier, thuscontaminating the dataset. The goal is to design strategyproof mechanisms that correctly label as many examplesas possible. Previous work has investigated the foregoing setting under limiting assumptions, or with respect to very restrictedclasses of classifiers. In this paper, we study the strategyproof classification setting with respect to prominent classesof classifiers—boolean conjunctions and linear separators - and without any assumptions on the input. On the negativeside, we show that strategyproof mechanisms cannot achievea constant approximation ratio, by showing that such mechanisms must be dictatorial on a subdomain, in the sensethat the outcome is selected according to the preferences ofa single agent. On the positive side, we present a randomizedmechanism—Iterative Random Dictator—and demonstrateboth that it is strategyproof and that its approximation ratiodoes not increase with the number of agents. Interestingly, the notion of dictatorship is prominently featured in all ourresults, helping to establish both upper and lower bounds.

IJCAI Conference 2009 Conference Paper

• Reshef Meir
• Ariel D. Procaccia
• Jeffrey S. Rosenschein

Strategyproof classification deals with a setting where a decision-maker must classify a set of input points with binary labels, while minimizing the expected error. The labels of the input points are reported by self-interested agents, who might lie in order to obtain a classifier that more closely matches their own labels, thus creating a bias in the data; this motivates the design of truthful mechanisms that discourage false reports. Previous work [Meir et al. , 2008] investigated both decisiontheoretic and learning-theoretic variations of the setting, but only considered classifiers that belong to a degenerate class. In this paper we assume that the agents are interested in a shared set of input points. We show that this plausible assumption leads to powerful results. In particular, we demonstrate that variations of a truthful random dictator mechanism can guarantee approximately optimal outcomes with respect to any class of classifiers.

MFCS Conference 2009 Conference Paper

The Cost of Stability in Network Flow Games

• Ezra Resnick
• Yoram Bachrach
• Reshef Meir
• Jeffrey S. Rosenschein

Abstract The core of a cooperative game contains all stable distributions of a coalition’s gains among its members. However, some games have an empty core, with every distribution being unstable. We allow an external party to offer a supplemental payment to the grand coalition, which may stabilize the game, if the payment is sufficiently high. We consider the cost of stability (CoS)—the minimal payment that stabilizes the game. We examine the CoS in threshold network flow games (TNFGs), where each agent controls an edge in a flow network, and a coalition wins if the maximal flow it can achieve exceeds a certain threshold. We show that in such games, it is coNP-complete to determine whether a given distribution (which includes an external payment) is stable. Nevertheless, we show how to bound and approximate the CoS in general TNFGs, and provide efficient algorithms for computing the CoS in several restricted cases.

AAMAS Conference 2008 Conference Paper

A Broader Picture of the Complexity of Strategic Behavior in Multi-Winner Elections

• Reshef Meir
• Ariel Procaccia
• Jeffrey Rosenschein

Recent work by Procaccia, Rosenschein and Zohar [14] established some results regarding the complexity of manipulation and control in elections with multiple winners, such as elections of an assembly or committee; that work provided an initial understanding of the topic. In this paper, we paint a more complete picture of the topic, investigating four prominent multi-winner voting rules. First, we characterize the complexity of manipulation and control in these voting rules under various kinds of formalizations of the manipulator’s goal. Second, we extend the results about complexity of control to various well-known types of control. This work enhances our comprehension of which multi-winner voting rules should be employed in various settings.

AAAI Conference 2008 Conference Paper

Strategyproof Classification under Constant Hypotheses: A Tale of Two Functions

• Reshef Meir

We consider the following setting: a decision maker must make a decision based on reported data points with binary labels. Subsets of data points are controlled by different selfish agents, which might misreport the labels in order to sway the decision in their favor. We design mechanisms (both deterministic and randomized) that reach an approximately optimal decision and are strategyproof, i. e. , agents are best off when they tell the truth. We then recast our results into a classical machine learning classification framework, where the decision maker must make a decision (choose between the constant positive hypothesis and the constant negative hypothesis) based only on a sampled subset of the agents’ points.