Arrow Research search

Author name cluster

Omer Lev

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

43 papers
2 author rows

Possible papers

43

AAAI Conference 2026 Conference Paper

Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints

  • Yaron Salman
  • Tamir Tassa
  • Omer Lev
  • Roie Zivan

Cake-cutting algorithms, which aim to fairly allocate a continuous resource based on individual agent preferences, have seen significant progress over the past two decades. Much of the research has concentrated on fairness, with comparatively less attention given to other important aspects. In 2010, Chen et al. introduced an algorithm that, in addition to ensuring fairness, was strategyproof---meaning agents had no incentive to misreport their valuations. However, even in the absence of strategic incentives to misreport, agents may still hesitate to reveal their true preferences due to privacy concerns (e.g., when allocating advertising time between firms, revealing preferences could inadvertently expose planned marketing strategies or product launch timelines). In this work, we extend the strategyproof algorithm of Chen et al. by introducing a privacy-preserving dimension. To the best of our knowledge, we present the first private cake-cutting protocol, and, in addition, this protocol is also envy-free and strategyproof. Our approach replaces the algorithm’s centralized computation with a novel adaptation of cryptographic techniques, enabling privacy without compromising fairness or strategyproofness. Thus, our protocol encourages agents to report their true preferences not only because they are not incentivized to lie, but also because they are protected from having their preferences exposed.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Insights Regarding the Success of Damping in Improving Belief Propagation

  • Uriel Zaed
  • Omer Lev
  • Roie Zivan

A common approach for solving distributed constraint optimization problems (DCOPs) is to represent them with a graphical model and to solve them with a message passing algorithm. Belief propagation is a popular and well studied such incomplete inference algorithm. Min-sum (often referred to as Max-sum) is the belief propagation version that is used for solving minimization DCOPs. Belief propagation is performed on a factor graph representation of the problem, in which the graph nodes take an active role in the algorithm, i. e. , they perform calculations and exchange messages with their neighbors. Unfortunately, the standard version of Min-sum fails to converge in many cases, and produces low quality solutions. Previous studies proposed methods to encourage its convergence and improve solution quality. Recently, empirical evidence indicated that the performance of Min-sum can be immensely improved by enhancing it with damping of beliefs (constraint costs) that are exchanged by the graph nodes. However, while this was empirically validated, a theoretical understanding of this phenomenon has not yet been established. In this research, we present a number of theoretical and empirical results that achieve important mile-stones in understanding damping’s success in improving Min-sum. These include adapting theoretical tools that were suggested for analyzing Min-sum to work with Damped Min-sum (DMS) and analyzing the effect of damping on graphs with special structures. We show that when belief propagation instantly converges, damping is redundant, and thus, the main contribution of damping is in reducing the exponential growth of the inconsistent beliefs that are propagated in the first steps of the algorithm’s run.

PDF

AIJ Journal 2025 Journal Article

Separate but equal: Equality in belief propagation for single-cycle graphs

  • Erel Cohen
  • Ben Rachmut
  • Omer Lev
  • Roie Zivan

Belief propagation is a widely used, incomplete optimization algorithm whose main theoretical properties hold only under the assumption that beliefs are not equal. Nevertheless, there is substantial evidence to suggest that equality between beliefs does occur. A published method to overcome belief equality, which is based on the use of unary function-nodes, is commonly assumed to resolve the problem. In this study, we focus on min-sum, the version of belief propagation that is used to solve constraint optimization problems. We prove that for the case of a single-cycle graph, belief equality can only be avoided when the algorithm converges to the optimal solution. Under any other circumstances, the unary function method will not prevent equality, indicating that some of the existing results presented in the literature are in need of reassessment. We differentiate between belief equality, which refers to equal beliefs in a single message, and assignment equality, which prevents the coherent assignment of values to the variables, and we provide conditions for both.

Details DOI

AAMAS Conference 2025 Conference Paper

Who Reviews The Reviewers? A Multi-Level Jury Problem

  • Ben Abramowitz
  • Omer Lev
  • Nicholas Mattei

We consider the problem of determining a binary ground truth using advice from a group of independent reviewers (experts) who express their guess about a ground truth correctly with some independent probability (competence) 𝑝𝑖. In this setting, when all reviewers are competent with 𝑝 ≥ 0. 5, the Condorcet Jury Theorem tells us that adding more reviewers increases the overall accuracy, and if all 𝑝𝑖’s are known, then there exists an optimal weighting of the reviewers. However, in practical settings, reviewers may be noisy or incompetent, i. e. , 𝑝𝑖 ≤ 0. 5, and the number of experts may be small, so the asymptotic Condorcet Jury Theorem is not practically relevant. In such cases we explore appointing one or more chairs (judges) who determine the weight of each reviewer for aggregation, creating multiple levels. However, these chairs may be unable to correctly identify the competence of the reviewers they oversee, and therefore unable to compute the optimal weighting. We give conditions on when a set of chairs is able to weight the reviewers optimally, and depending on the competence distribution of the agents, give results about when it is better to have more chairs or more reviewers. Through simulations we show that in some cases it is better to have more chairs, but in many cases it is better to have more reviewers.

PDF

AIJ Journal 2024 Journal Article

Primarily about primaries

  • Allan Borodin
  • Omer Lev
  • Nisarg Shah
  • Tyrone Strangway

Much of the social choice literature examines direct voting systems, in which voters submit their ranked preferences over candidates and a voting rule picks a winner. Real-world elections and decision-making processes are often more complex and involve multiple stages. For instance, one popular voting system filters candidates through primaries: first, voters affiliated with each political party vote over candidates of their own party and the voting rule picks a set of candidates, one from each party, who then compete in a general election. We present a model to analyze such multi-stage elections, and conduct what is, to the best of our knowledge, the first quantitative comparison of the direct and primary voting systems in terms of the quality of the elected candidate, using the metric of distortion, which attempts to quantify how far from the optimal winner is the actual winner of an election. Our main theoretical result is that voting rules (which are independent of party affiliations, of course) are guaranteed to perform in the primary system within a constant factor of the direct, single stage setting. Surprisingly, the converse does not hold: we show settings in which there exist voting rules that perform significantly better under the primary system than under the direct system. Using simulations, we see that plurality benefits significantly from using a primary system over a direct one, while Condorcet-consistent rules do not.

Details DOI

AAAI Conference 2024 Conference Paper

Towards a More Burkean Approach to Computational Social Choice

  • Omer Lev

In the last few years, a lot of the activity of the computational social choice community has focused on novel mechanisms for reaching decisions by large groups of people. While this research makes meaningful scientific contributions, many of these mechanisms are not quite useful in realistic decision-making settings. Moreover, their radicalism ignores the centuries-old experience we have with large-scale human decision-making, and what it teaches us about what works. We believe it is important the community engage with mechanisms which are widely-used in the real world, as they may hold a key to a deeper understanding of how people reach decisions and the way that helps them do that productively. Moreover, letting the community bring its analysis and understanding to these will allow for algorithmic suggestions that have some chance of being implemented (and, thus, can contribute to the public debate on these topics). In particular, we highlight the relatively less-investigated role of parties and grouping of voters and candidates, and the role of executive capacity in analyzing decision-making structures.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Ask and You Shall be Served: Representing & Solving Multi-agent Optimization Problems with Service Requesters and Providers

  • Maya Lavie
  • Tehila Caspi
  • Omer Lev
  • Roie Zivan

In scenarios with numerous emergencies that arise and require the assistance of various rescue units (e. g. , medical, fire, & police forces), the rescue units would ideally be allocated quickly and distributedly while aiming to minimize casualties. This is one of many examples of distributed settings with service providers (the rescue units) and service requesters (the emergencies) which we term service oriented settings. Allocating the service providers in a distributed manner while aiming for a global optimum is hard to model, let alone achieve, using the existing Distributed Constraint Optimization Problem (DCOP) framework. Hence, the need for a novel approach and corresponding algorithms. We present the Service Oriented Multi-Agent Optimization Problem (SOMAOP), a new framework to overcome DCOP’s shortcomings in service oriented settings. We evaluate the framework using algorithms based on auctions and matching (e. g. , Gale Shapely). We empirically show that algorithms based on repeated auctions converge to a high quality solution very fast, while repeated matching problems converge slower, but produce higher quality solutions. We demonstrate the advantages of our approach over standard incomplete DCOP algorithms and a greedy centralized algorithm.

PDF

AIJ Journal 2023 Journal Article

PeerNomination: A novel peer selection algorithm to handle strategic and noisy assessments

  • Omer Lev
  • Nicholas Mattei
  • Paolo Turrini
  • Stanislav Zhydkov

In peer selection a group of agents must choose a subset of themselves, as winners for, e. g. , peer-reviewed grants or prizes. We take a Condorcet view of this aggregation problem, assuming that there is an objective ground-truth ordering over the agents. We study agents that have a noisy perception of this ground truth and give assessments that, even when truthful, can be inaccurate. Our goal is to select the best set of agents according to the underlying ground truth by looking at the potentially unreliable assessments of the peers. Besides being potentially unreliable, we also allow agents to be self-interested, attempting to influence the outcome of the decision in their favour. Hence, we are focused on tackling the problem of impartial (or strategyproof) peer selection – how do we prevent agents from manipulating their reviews while still selecting the most deserving individuals, all in the presence of noisy evaluations? We propose a novel impartial peer selection algorithm, PeerNomination, that aims to fulfil the above desiderata. We provide a comprehensive theoretical analysis of the recall of PeerNomination and prove various properties, including impartiality and monotonicity. We also provide empirical results based on computer simulations to show its effectiveness compared to the state-of-the-art impartial peer selection algorithms. We then investigate the robustness of PeerNomination to various levels of noise in the reviews. In order to maintain good performance under such conditions, we extend PeerNomination by using weights for reviewers which, informally, capture some notion of reliability of the reviewer. We show, theoretically, that the new algorithm preserves strategyproofness and, empirically, that the weights help identify the noisy reviewers and hence to increase selection performance. 1

Details DOI

AAAI Conference 2023 Conference Paper

Separate but Equal: Equality in Belief Propagation for Single Cycle Graphs

  • Erel Cohen
  • Omer Lev
  • Roie Zivan

Belief propagation is a widely used incomplete optimization algorithm, whose main theoretical properties hold only under the assumptions that beliefs are not equal. Nevertheless, there is much evidence that equality between beliefs does occur. A method to overcome belief equality by using unary function-nodes is assumed to resolve the problem. We focus on Min-sum, the belief propagation version for solving constraint optimization problems. We prove that on a single cycle graph, belief equality can be avoided only when the algorithm converges to the optimal solution. In any other case, the unary function methods will not prevent equality, rendering some existing results in need of reassessment. We differentiate between belief equality, which includes equal beliefs in a single message, and assignment equality, that prevents a coherent selection of assignments to variables. We show the necessary and satisfying conditions for both.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Little House (Seat) on the Prairie: Compactness, Gerrymandering, and Population Distribution

  • Allan Borodin
  • Omer Lev
  • Nisarg Shah
  • Tyrone Strangway

Gerrymandering is the process of creating electoral districts for partisan advantage, allowing a party to win more seats than what is reasonable for their vote. While research on gerrymandering has recently grown, many issues are still not fully understood such as what influences the degree to which a party can gerrymander and what techniques can be used to counter it. One commonly suggested (and, in some US states, mandated) requirement is that districts be “geographically compact”. However, there are many competing compactness definitions and the impact of compactness on the gerrymandering abilities of the parties is not well understood. Also not well understood is how the growing urban-rural divide between supporters of different parties impacts redistricting. We develop a modular, scalable, and efficient algorithm that can design districts for various criteria. We confirm its effectiveness on several US states by pitting it against maps “hand-drawn” by political experts. Using real data from US political elections we use our algorithm to study the interaction between population distribution, partisanship, and geographic compactness. We find that compactness can lead to more fair plans (compared to implemented plans) and limit gerrymandering potential, but there is a consistent asymmetry where the party with rural supporters has an advantage. We also show there are plans which are fair from a partisan perspective, but they are far from optimally compact.

PDF

AIJ Journal 2022 Journal Article

Predicting voting outcomes in the presence of communities, echo chambers and multiple parties

  • Jacques Bara
  • Omer Lev
  • Paolo Turrini

When individuals interact in a social network their opinions can change, at times quite significantly, as a result of social influence. In elections, for example, while they might initially support one candidate, what their friends say may lead them to support another. But how do opinions settle in a social network, as a result of social influence? A recently proposed graph-theoretic metric, the influence gap, has shown to be a reliable predictor of the effect of social influence in two-party elections, albeit only tested on regular and scale-free graphs. Here, we investigate whether the influence gap is able to predict the outcome of multi-party elections on networks exhibiting community structure, i. e. , made of highly interconnected components, and therefore more resembling of real-world interaction. To encode communities we build on the classical model of caveman graphs, which we extend to a richer graph family that displays different levels of homophily, i. e. , how many connections and opinions are intertwined. Our contribution is three-fold. First, we study the predictive power of the influence gap in the presence of communities. We show that when there is no clear initial majority the influence gap is not a good predictor of the election outcome. When we instead allow for varying majorities, although the influence gap improves as a predictor, counting the initial partisan majority does consistently better, across all levels of homophily. Second, we study the combined effect of the more predictive metrics, as function of the homophily levels. Using regression models, we demonstrate that the influence gap combined with the initial votes count does increase the overall predictive power for some levels of homophily. Third, we study elections with more than two parties. Specifically, we extend the definition of the influence gap to any number of parties, considering various generalisations, and show that the initial votes count has an even higher predictive power when compared to influence gap than it did in the two-party case.

Details DOI

AAMAS Conference 2021 Conference Paper

Learning Cooperative Solution Concepts from Voting Behavior: A Case Study on the Israeli Knesset

  • Omer Lev
  • Wei Lu
  • Alan Tsang
  • Yair Zick

Most frameworks for computing solution concepts in hedonic games are theoretical in nature, and require complete knowledge of all agent preferences, an impractical assumption in real-world settings. This paper presents the first application of strategic hedonic game models on real-world data. We show that PAC stable solutions can reflect Members of Knesset’ political positions and reveal politicians who are known to deviate from party lines. Moreover, these models compare favorably to machine learning models.

PDF

AAMAS Conference 2021 Conference Paper

Predicting Voting Outcomes in Presence of Communities

  • Jacques Bara
  • Omer Lev
  • Paolo Turrini

Individuals in a social network may form their views as a result of the influence exerted by their connections. In elections, for example, while they might initially support one candidate, social influence may lead them to support another. Here, we investigate whether a recently proposed metric, influence gap, designed to measure the effect of social influence in voting on social networks, is able to predict the outcome of a vote on networks exhibiting community structure, i. e. , made of highly interconnected components, and therefore more resembling of real-world interaction. To encode communities, we extend the classical model of caveman graphs to a richer graph family that displays levels of homophily, i. e. , where connections and opinions are highly intertwined. We show that, across these graphs, there are important cases when the influence gap correlation is a weak predictor due to communities, and a simpler metric, counting the initial partisan majority, provides a more accurate prediction overall. Using regression models, we further demonstrate that the influence gap combined with the more successful metrics does increase their predictive power for some levels of homophily.

PDF

AAMAS Conference 2021 Conference Paper

The Price is (Probably) Right: Learning Market Equilibria from Samples

  • Omer Lev
  • Neel Patel
  • Vignesh Viswanathan
  • Yair Zick

Equilibrium computation in markets usually considers settings where player valuation functions are known. We consider the setting where player valuations are unknown; using a PAC learningtheoretic framework, we analyze some classes of common valuation functions, and provide algorithms which output direct PAC equilibrium allocations, not estimates based on attempting to learn valuation functions. Since there exist trivial PAC market outcomes with an unbounded worst-case efficiency loss, we lower-bound the efficiency of our algorithms. While the efficiency loss under general distributions is rather high, we show that in some cases (e. g. , unit-demand valuations), it is possible to find a PAC market equilibrium with significantly better utility.

PDF

AAAI Conference 2020 Conference Paper

Beyond Trees: Analysis and Convergence of Belief Propagation in Graphs with Multiple Cycles

  • Roie Zivan
  • Omer Lev
  • Rotem Galiki

Belief propagation, an algorithm for solving problems represented by graphical models, has long been known to converge to the optimal solution when the graph is a tree. When the graph representing the problem includes a single cycle, the algorithm either converges to the optimal solution or performs periodic oscillations. While the conditions that trigger these two behaviors have been established, the question regarding the convergence and divergence of the algorithm on graphs that include more than one cycle is still open. Focusing on Max-sum, the version of belief propagation for solving distributed constraint optimization problems (DCOPs), we extend the theory on the behavior of belief propagation in general – and Max-sum specifically – when solving problems represented by graphs with multiple cycles. This includes: 1) Generalizing the results obtained for graphs with a single cycle to graphs with multiple cycles, by using backtrack cost trees (BCT). 2) Proving that when the algorithm is applied to adjacent symmetric cycles, the use of a large enough damping factor guarantees convergence to the optimal solution.

PDF Details

IJCAI Conference 2020 Conference Paper

Selecting Voting Locations for Fun and Profit

  • Zack Fitzsimmons
  • Omer Lev

While manipulative attacks on elections have been well-studied, only recently has attention turned to attacks that account for geographic information, which are extremely common in the real world. The most well known in the media is gerrymandering, in which district border-lines are changed to increase a party's chance to win, but a different geographical manipulation involves influencing the election by selecting the location of polling places, as many people are not willing to go to any distance to vote. In this paper we initiate the study of this manipulation. We find that while it is easy to manipulate the selection of polling places on the line, it becomes difficult already on the plane or in the case of more than two candidates. Moreover, we show that for more than two candidates the problem is inapproximable. However, we find a few restricted cases on the plane where some algorithms perform well. Finally, we discuss how existing results for standard control actions hold in the geographic setting, consider additional control actions in the geographic setting, and suggest directions for future study.

PDF Details DOI

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.

PDF Details

AAAI Conference 2019 Conference Paper

Primarily about Primaries

  • Allan Borodin
  • Omer Lev
  • Nisarg Shah
  • Tyrone Strangway

Much of the social choice literature examines direct voting systems, in which voters submit their ranked preferences over candidates and a voting rule picks a winner. Real-world elections and decision-making processes are often more complex and involve multiple stages. For instance, one popular voting system filters candidates through primaries: first, voters affiliated with each political party vote over candidates of their own party and the voting rule picks a candidate from each party, which then compete in a general election. We present a model to analyze such multi-stage elections, and conduct the first quantitative comparison (to the best of our knowledge) of the direct and primary voting systems with two political parties in terms of the quality of the elected candidate. Our main result is that every voting rule is guaranteed to perform almost as well (i. e. , within a constant factor) under the primary system as under the direct system. Surprisingly, the converse does not hold: we show settings in which there exist voting rules that perform significantly better under the primary system than under the direct system.

PDF Details

AIJ Journal 2019 Journal Article

Strategyproof peer selection using randomization, partitioning, and apportionment

  • Haris Aziz
  • Omer Lev
  • Nicholas Mattei
  • Jeffrey S. Rosenschein
  • Toby Walsh

Peer reviews, evaluations, and selections are a fundamental aspect of modern science. Funding bodies the world over employ experts to review and select the best proposals from those submitted for funding. The problem of peer selection, however, is much more general: a professional society may want to give a subset of its members awards based on the opinions of all members; an instructor for a Massive Open Online Course (MOOC) or an online course may want to crowdsource grading; or a marketing company may select ideas from group brainstorming sessions based on peer evaluation. We make three fundamental contributions to the study of peer selection, a specific type of group decision-making problem, studied in computer science, economics, and political science. First, we propose a novel mechanism that is strategyproof, i. e. , agents cannot benefit by reporting insincere valuations. Second, we demonstrate the effectiveness of our mechanism by a comprehensive simulation-based comparison with a suite of mechanisms found in the literature. Finally, our mechanism employs a randomized rounding technique that is of independent interest, as it solves the apportionment problem that arises in various settings where discrete resources such as parliamentary representation slots need to be divided proportionally.

Details DOI

AAAI Conference 2019 Conference Paper

“Reverse Gerrymandering”: Manipulation in Multi-Group Decision Making

  • Omer Lev
  • Yoad Lewenberg

District-based manipulation, or gerrymandering, is usually taken to refer to agents who are in fixed location, and an external division is imposed upon them. However, in many real-world setting, there is an external, fixed division – an organizational chart of a company, or markets for a particular product. In these cases, agents may wish to move around (“reverse gerrymandering”), as each of them tries to maximize their influence across the company’s subunits, or resources are “working” to be allocated to areas where they will be most needed. In this paper we explore an iterative dynamic in this setting, finding that allowing this decentralized system results, in some particular cases, in a stable equilibrium, though in general, the setting may end up in a cycle. We further examine how this decentralized process affects the social welfare of the system.

PDF Details

IJCAI Conference 2018 Conference Paper

Big City vs. the Great Outdoors: Voter Distribution and How It Affects Gerrymandering

  • Allan Borodin
  • Omer Lev
  • Nisarg Shah
  • Tyrone Strangway

Gerrymandering is the process by which parties manipulate boundaries of electoral districts in order to maximize the number of districts they can win. Demographic trends show an increasingly strong correlation between residence and party affiliation; some party’s supporters congregate in cities, while others stay in more rural areas. We investigate both theoretically and empirically the effect of this trend on a party's ability to gerrymander in a two-party model ("urban party" and "rural party"). Along the way, we propose a definition of the gerrymandering power of a party, and an algorithmic approach for near-optimal gerrymandering in large instances. Our results suggest that beyond a fairly small concentration of urban party's voters, the gerrymandering power of a party depends almost entirely on the level of concentration, and not on the party's share of the population. As partisan separation grows, the gerrymandering power of both parties converge so that each party can gerrymander to get only slightly more than what its voting share warrants, bringing about, ultimately, a more representative outcome. Moreover, there seems to be an asymmetry between the gerrymandering power of the parties, with the rural party being more capable of gerrymandering.

PDF Details

AAMAS Conference 2018 Conference Paper

Seasonal Goods and Spoiled Milk: Pricing for a Limited Shelf-Life

  • Atiyeh Ashari Ghomi
  • Allan Borodin
  • Omer Lev

We consider a “price-committment model” where a single seller announces prices for some extended period of time. More specifically, we examine the case of items with a limited shelf-life where storing an item (before consumption) may carry a cost to a buyer (or distributor). For example, eggs, milk, or Groupon coupons have a fixed expiry date, and seasonal goods can suffer a decrease in value. We show how this setting contrasts with recent results by Berbeglia et al [4] for items with infinite shelf-life. We prove tight bounds on the seller’s profits showing how they relate to the items’ shelf-life. We show, counterintuitively, that in our limited shelf-life setting, increasing storage costs can sometimes lead to less profit for the seller which cannot happen when items have unlimited shelf-life. We also provide an algorithm that calculates optimal prices. Finally, we examine empirically the relationship between profits and buyer utility as the storage cost and shelf-life duration change, and observe properties, some of which are unique to the limited shelf-life setting.

PDF

IJCAI Conference 2018 Conference Paper

Socially Motivated Partial Cooperation in Multi-agent Local Search

  • Tal Ze'evi
  • Roie Zivan
  • Omer Lev

Partial Cooperation is a paradigm and a corresponding model, proposed to represent multi-agent systems in which agents are willing to cooperate to achieve a global goal, as long as some minimal threshold on their personal utility is satisfied. Distributed local search algorithms were proposed in order to solve asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative. We contribute by: 1) extending the partial cooperative model to allow it to represent dynamic cooperation intentions, affected by changes in agents’ wealth, in accordance with social studies literature. 2) proposing a novel local search algorithm in which agents receive indications of others’ preferences on their actions and thus, can perform actions that are socially beneficial. Our empirical study reveals the advantage of the proposed algorithm in multiple benchmarks. Specifically, on realistic meeting scheduling problems it overcomes limitations of standard local search algorithms.

PDF Details

AAMAS Conference 2018 Conference Paper

Socially Motivated Partial Cooperation in Multi-agent Local Search

  • Tal Ze'evi
  • Roie Zivan
  • Omer Lev

Partial Cooperation is a paradigm and a corresponding model for representing multi-agent systems in which agents are willing to cooperate in order to achieve a global goal, as long as some minimal threshold on their personal utility is satisfied. Distributed local search algorithms were proposed in order to solve asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative. We contribute by: 1) extending the partial cooperative model to allow it to represent dynamic cooperation intentions, affected by changes in agents’ wealth, in accordance with social studies literature. 2) proposing a novel local search algorithm in which agents receive indications of others’ preferences on their actions and thus, can perform actions that are socially beneficial. Our empirical study reveals the advantage of the proposed algorithm in multiple benchmarks. Specifically, on realistic meeting scheduling problems it overcomes limitations of standard local search algorithms.

PDF

IS Journal 2017 Journal Article

Agent Failures in All-Pay Auctions

  • Yoad Lewenberg
  • Omer Lev
  • Yoram Bachrach
  • Jeffrey S. Rosenschein

All-pay auctions, a common mechanism for various human and agent interactions, suffers (like many other mechanisms) from the possibility of players' failure to participate in the auction. The authors model such failures and fully characterize equilibrium for this class of games, presenting a symmetric equilibrium and showing that under some conditions the equilibrium is unique. They also reveal various properties of the equilibrium, such as the lack of influence of the most-likely-to-participate player on the behavior of the other players. The authors perform this analysis with two scenarios: the sum-profit model, in which the auctioneer obtains the sum of all submitted bids, and the max-profit model of crowdsourcing contests, in which the auctioneer can only use the best submissions and thus obtains only the winning bid. Finally, the authors examine various methods of influencing the probability of participation such as the effects of misreporting one's own probability of participating and how influencing another player's participation chances changes a player's strategy.

Details DOI

IJCAI Conference 2017 Conference Paper

Convergence and Quality of Iterative Voting Under Non-Scoring Rules

  • Aaron Koolyk
  • Tyrone Strangway
  • Omer Lev
  • Jeffrey S. Rosenschein

Iterative voting is a social choice mechanism that assumes all voters are strategic, and allows voters to change their stated preferences as the vote progresses until an equilibrium is reached (at which point no player wishes to change their vote). Previous research established that this process converges to an equilibrium for the plurality and veto voting methods and for no other scoring rule. We consider iterative voting for non-scoring rules, examining the major ones, and show that none of them converge when assuming (as most research has so far) that voters pursue a best response strategy. We investigate other potential voter strategies, with a more heuristic flavor (since for most of these voting rules, calculating the best response is NP-hard); we show that they also do not converge. We then conduct an empirical analysis of the iterative voting winners for these non-scoring rules, and compare the winner quality of various strategies.

PDF Details

AAMAS Conference 2017 Conference Paper

Distant Truth: Bias Under Vote Distortion Costs

  • Svetlana Obraztsova
  • Omer Lev
  • Evangelos Markakis
  • Zinovi Rabinovich
  • Jeffrey S. Rosenschein

In recent years, there has been increasing interest within the computational social choice community regarding models where voters are biased towards specific behaviors or have secondary preferences. An important representative example of this approach is the model of truth bias, where voters prefer to be honest about their preferences, unless they are pivotal. This model has been demonstrated to be an effective tool in controlling the set of pure Nash equilibria in a voting game, which otherwise lacks predictive power. However, in the models that have been used thus far, the bias is binary, i. e. , the final utility of a voter depends on whether he cast a truthful vote or not, independently of the type of lie. In this paper, we introduce a more robust framework, and eliminate this limitation, by investigating truth-biased voters with variable bias strength. Namely, we assume that even when voters face incentives to lie towards a better outcome, the ballot distortion from their truthful preference incurs a cost, measured by a distance function. We study various such distance-based cost functions and explore their effect on the set of Nash equilibria of the underlying game. Intuitively, one might expect that such distance metrics may induce similar behavior. To our surprise, we show that the presented metrics exhibit quite different equilibrium behavior. CCS Concepts •Theory of computation → Solution concepts in game theory; Convergence and learning in games;

PDF

AAMAS Conference 2017 Conference Paper

Divide and Conquer: Using Geographic Manipulation to Win District-Based Elections

  • Yoad Lewenberg
  • Omer Lev
  • Jeffrey S. Rosenschein

District-based elections, in which voters vote for a district representative and those representatives ultimately choose the winner, are vulnerable to gerrymandering, i. e. , manipulation of the outcome by changing the location and borders of districts. Many countries aim to limit blatant gerrymandering, and thus we introduce a geographically-based manipulation problem, where voters must vote at the ballot box closest to them. We show that this problem is NP-complete in the worst case. However, we present a greedy algorithm for the problem; testing it both on simulation data as well as on realworld data from the 2015 Israeli and British elections, we show that many parties are potentially able to make themselves victorious using district manipulation. Moreover, we show that the relevant variables here go beyond share of the vote; the form of geographic dispersion also plays a crucial role. CCS Concepts •Theory of computation → Solution concepts in game theory; •Applied computing → Sociology;

PDF

TARK Conference 2017 Conference Paper

Group Recommendations: Axioms, Impossibilities, and Random Walks

  • Omer Lev
  • Moshe Tennenholtz

We introduce an axiomatic approach to group recommendations, in line of previous work on the axiomatic treatment of trust-based recommendation systems, ranking systems, and other foundational work on the axiomatic approach to internet mechanisms in social choice settings. In group recommendations we wish to recommend to a group of agents, consisting of both opinionated and undecided members, a joint choice that would be acceptable to them. Such a system has many applications, such as choosing a movie or a restaurant to go to with a group of friends, recommending games for online game players, & other communal activities. Our method utilizes a given social graph to extract information on the undecided, relying on the agents influencing them. We first show that a set of fairly natural desired requirements (a. k. a axioms) leads to an impossibility, rendering mutual satisfaction of them unreachable. However, we also show a modified set of axioms that fully axiomatize a group variant of the random-walk recommendation system, expanding a previous result from the individual recommendation case.

Details DOI

AAMAS Conference 2016 Conference Paper

Budgetary Effects on Pricing Equilibrium in Online Markets

  • Allan Borodin
  • Omer Lev
  • Tyrone Strangway

Following the work of Babaioff et al [4], we consider the pricing game with strategic vendors and a single buyer, modeling a scenario in which multiple competing vendors have very good knowledge of a buyer, as is common in online markets. We add to this model the realistic assumption that the buyer has a fixed budget and does not have unlimited funds. When the buyer’s valuation function is additive, we are able to completely characterize the different possible pure Nash Equilibria (PNE) and in particular obtain a necessary and sufficient condition for uniqueness. Furthermore, we characterize the market clearing (or Walresian) equilibria for all submodular valuations. Surprisingly, for certain monotone submodular function valuations, we show that the pure NE can exhibit some counterintuitive phenomena; namely, there is a valuation such that the pricing will be market clearing and within budget if the buyer does not reveal the budget but will result in a smaller set of allocated items (and higher prices for items) if the buyer does reveal the budget. It is also the case that the conditions that guarantee market clearing in Babaioff et al [4] for submodular functions are not necessarily market clearing when there is a budget. Furthermore, with respect to social welfare, while without budgets all equilibria are optimal (i. e. POA = POS = 1), we show that with budgets the worst equilibrium may only achieve 1 n−2 of the best equilibrium.

PDF

AAMAS Conference 2016 Conference Paper

Convergence and Quality of Iterative Voting Under Non-Scoring Rules (Extended Abstract)

  • Aaron Koolyk
  • Omer Lev
  • Jeffrey S. Rosenschein

Iterative voting is a social choice mechanism whereby voters are allowed to continually make strategic changes to their stated preferences until no further change is desired. We study the iterative voting framework for several common voting rules and show that, for these rules, an equilibrium may never be reached. We also consider several variations of iterative voting and show that with these variations equilibrium likewise may not be reached. Finally, we present an empirical analysis of the quality of candidates elected through iterative voting.

PDF

JAIR Journal 2016 Journal Article

Convergence of Iterative Scoring Rules

  • Omer Lev
  • Jeffrey S. Rosenschein

In multiagent systems, social choice functions can help aggregate the distinct preferences that agents have over alternatives, enabling them to settle on a single choice. Despite the basic manipulability of all reasonable voting systems, it would still be desirable to find ways to reach plausible outcomes, which are stable states, i.e., a situation where no agent would wish to change its vote. One possibility is an iterative process in which, after everyone initially votes, participants may change their votes, one voter at a time. This technique, explored in previous work, converges to a Nash equilibrium when Plurality voting is used, along with a tie-breaking rule that chooses a winner according to a linear order of preferences over candidates. In this paper, we both consider limitations of the iterative voting method, as well as expanding upon it. We demonstrate the significance of tie-breaking rules, showing that no iterative scoring rule converges for all tie-breaking. However, using a restricted tie-breaking rule (such as the linear order rule used in previous work) does not by itself ensure convergence. We prove that in addition to plurality, the veto voting rule converges as well using a linear order tie-breaking rule. However, we show that these two voting rules are the only scoring rules that converge, regardless of tie-breaking mechanism.

PDF Details DOI

IJCAI Conference 2016 Conference Paper

Misrepresentation in District Voting

  • Yoram Bachrach
  • Omer Lev
  • Yoad Lewenberg
  • Yair Zick

Voting systems in which voters are partitioned to districts encourage accountability by providing voters an easily identifiable district representative, but can result in a selection of representatives not representative of the electorate's preferences. In some cases, a party may have a majority of the popular vote, but lose the elections due to districting effects. We define the Misrepresentation Ratio which quantifies the deviation from proportional representation in a district-based election, and provide bounds for this ratio under various voting rules. We also examine probabilistic models for election outcomes, and provide an algorithm for approximating the expected Misrepresentation Ratio under a given probabilistic election model. Finally, we provide simulation results for several such probabilistic election models, showing the effects of the number of voters and candidates on the misrepresentation ratio.

PDF Details

AAAI Conference 2016 Conference Paper

Strategyproof Peer Selection: Mechanisms, Analyses, and Experiments

  • Haris Aziz
  • Omer Lev
  • Nicholas Mattei
  • Jeffrey Rosenschein
  • Toby Walsh

We study an important crowdsourcing setting where agents evaluate one another and, based on these evaluations, a subset of agents are selected. This setting is ubiquitous when peer review is used for distributing awards in a team, allocating funding to scientists, and selecting publications for conferences. The fundamental challenge when applying crowdsourcing in these settings is that agents may misreport their reviews of others to increase their chances of being selected. We propose a new strategyproof (impartial) mechanism called Dollar Partition that satisfies desirable axiomatic properties. We then show, using a detailed experiment with parameter values derived from target real world domains, that our mechanism performs better on average, and in the worst case, than other strategyproof mechanisms in the literature.

PDF Details

TARK Conference 2015 Conference Paper

An Axiomatic Approach to Routing

  • Omer Lev
  • Moshe Tennenholtz
  • Aviv Zohar

Information delivery in a network of agents is a key issue for large, complex systems that need to do so in a predictable, efficient manner. The delivery of information in such multi-agent systems is typically implemented through routing protocols that determine how information flows through the network. Different routing protocols exist each with its own benefits, but it is generally unclear which properties can be successfully combined within a given algorithm. We approach this problem from the axiomatic point of view, i. e. , we try to establish what are the properties we would seek to see in such a system, and examine the different properties which uniquely define common routing algorithms used today. We examine several desirable properties, such as robustness, which ensures adding nodes and edges does not change the routing in a radical, unpredictable ways; and properties that depend on the operating environment, such as an "economic model", where nodes choose their paths based on the cost they are charged to pass information to the next node. We proceed to fully characterize minimal spanning tree, shortest path, and weakest link routing algorithms, showing a tight set of axioms for each.

Details DOI

AAAI Conference 2015 Conference Paper

Analysis of Equilibria in Iterative Voting Schemes

  • Zinovi Rabinovich
  • Svetlana Obraztsova
  • Omer Lev
  • Evangelos Markakis
  • Jeffrey Rosenschein

Following recent studies of iterative voting and its effects on plurality vote outcomes, we provide characterisations and complexity results for three models of iterative voting under the plurality rule. Our focus is on providing a better understanding regarding the set of equilibria attainable by iterative voting processes. We start with the basic model of plurality voting. We first establish some useful properties of equilibria, reachable by iterative voting, which enable us to show that deciding whether a given profile is an iteratively reachable equilibrium is NP-complete. We then proceed to combine iterative voting with the concept of truth bias, a model where voters prefer to be truthful when they cannot affect the outcome. We fully characterise the set of attainable truth-biased equilibria, and show that it is possible to determine all such equilibria in polynomial time. Finally, we also examine the model of lazy voters, in which a voter may choose to abstain from the election. We establish convergence of the iterative process, albeit not necessarily to a Nash equilibrium. As in the case with truth bias, we also provide a polynomial time algorithm to find all the attainable equilibria.

PDF Details

IJCAI Conference 2015 Conference Paper

How Robust Is the Wisdom of the Crowds?

  • Noga Alon
  • Michal Feldman
  • Omer Lev
  • Moshe Tennenholtz

We introduce the study of adversarial effects on wisdom of the crowd phenomena. In particular, we examine the ability of an adversary to influence a social network so that the majority of nodes are convinced by a falsehood, using its power to influence a certain fraction, µ 0. 5. When we examine expander graphs as well as random graphs we prove such bounds even for stronger adversaries, who are able to pick and choose not only who the experts are, but also which ones of them would communicate the wrong values, as long as their proportion is 1 − p. Furthermore, we study different propagation models and their effects on the feasibility of obtaining the true value for different adversary types.

PDF Details

IJCAI Conference 2015 Conference Paper

Impartial Peer Review

  • David Kurokawa
  • Omer Lev
  • Jamie Morgenstern
  • Ariel D. Procaccia

Motivated by a radically new peer review system that the National Science Foundation recently experimented with, we study peer review systems in which proposals are reviewed by PIs who have submitted proposals themselves. An (m, k)-selection mechanism asks each PI to review m proposals, and uses these reviews to select (at most) k proposals. We are interested in impartial mechanisms, which guarantee that the ratings given by a PI to others’ proposals do not affect the likelihood of the PI’s own proposal being selected. We design an impartial mechanism that selects a k-subset of proposals that is nearly as highly rated as the one selected by the non-impartial (abstract version of) the NSF pilot mechanism, even when the latter mechanism has the “unfair” advantage of eliciting honest reviews.

PDF Details

AAAI Conference 2015 Conference Paper

The Pricing War Continues: On Competitive Multi-Item Pricing

  • Omer Lev
  • Joel Oren
  • Craig Boutilier
  • Jeffrey Rosenschein

We study a game with strategic vendors (the agents) who own multiple items and a single buyer with a submodular valuation function. The goal of the vendors is to maximize their revenue via pricing of the items, given that the buyer will buy the set of items that maximizes his net payoff. We show this game may not always have a pure Nash equilibrium, in contrast to previous results for the special case where each vendor owns a single item. We do so by relating our game to an intermediate, discrete game in which the vendors only choose the available items, and their prices are set exogenously afterwards. We further make use of the intermediate game to provide tight bounds on the price of anarchy for the subset games that have pure Nash equilibria; we find that the optimal PoA reached in the previous special cases does not hold, but only a logarithmic one. Finally, we show that for a special case of submodular functions, efficient pure Nash equilibria always exist.

PDF Details

IJCAI Conference 2013 Conference Paper

Agent Failures in All-Pay Auctions

  • Yoad Lewenberg
  • Omer Lev
  • Yoram Bachrach
  • Jeffrey S. Rosenschein

All-pay auctions, a common mechanism for various human and agent interactions, suffers, like many other mechanisms, from the possibility of players’ failure to participate in the auction. We model such failures and show how they affect the equilibrium state, revealing various properties, such as the lack of influence of the most-likely-to-participate player on the behavior of the other players. We perform this analysis with two scenarios: the sum-profit model, where the auctioneer obtains the sum of all submitted bids, and the max-profit model of crowdsourcing contests, where the auctioneer can only use the best submissions and thus obtains only the winning bid. Furthermore, we examine various methods of influencing the probability of participation such as the effects of misreporting one’s own probability of participating, and how influencing another player’s participation chances (e. g. , sabotage) changes the player’s strategy.

PDF Details DOI

AAMAS Conference 2012 Conference Paper

Convergence of Iterative Voting

  • Omer Lev
  • Jeffrey Rosenschein

In multiagent systems, social choice functions can help aggregate the distinct preferences that agents have over alternatives, enabling them to settle on a single choice. Despite the basic manipulability of all reasonable voting systems, it would still be desirable to find ways to reach a \emph{stable} result, i. e. , a situation where no agent would wish to change its vote. One possibility is an iterative process in which, after everyone initially votes, participants may change their votes, one voter at a time. This technique, explored in previous work, converges to a Nash equilibrium when Plurality voting is used, along with a tie-breaking rule that chooses a winner according to a linear order of preferences over candidates. In this paper, we both consider limitations of the iterative voting method, as well as expanding upon it. We demonstrate the significance of tie-breaking rules, showing that when using a general tie-breaking rule, no scoring rule (nor Maximin) need iteratively converge. However, using a restricted tie-breaking rule (such as the linear order rule used in previous work) does not by itself \emph{ensure} convergence. We demonstrate that many scoring rules (such as Borda) need not converge, regardless of the tie-breaking rule. On a more encouraging note, we prove that Iterative Veto does converge - but that voting rules "between" Plurality and Veto, $k$-approval rules, do not.

PDF

AAMAS Conference 2011 Conference Paper

An Algorithm for the Coalitional Manipulation Problem under Maximin

  • Michael Zuckerman
  • Omer Lev
  • Jeffrey S. Rosenschein

We introduce a new algorithm for the Unweighted Coalitional Manipulation problem under the Maximin voting rule. We prove that the algorithm gives an approximation ratio of 12/3 to the corresponding optimization problem. This is an improvement over the previously known algorithm that gave a 2-approximation. We also prove that its approximation ratio is no better than 11/2, i. e. , there are instances on which a 11/2 -approximation is the best the algorithm can achieve. Finally, we prove that no algorithm can approximate the problem better than to the factor of 11/2, unless P = NP.

PDF

LPAR Conference 2008 Conference Paper

On the Relative Succinctness of Nondeterministic Büchi and co-Büchi Word Automata

  • Benjamin Aminof
  • Orna Kupferman
  • Omer Lev

Abstract The practical importance of automata on infinite objects has motivated a re-examination of the complexity of automata-theoretic constructions. One such construction is the translation, when possible, of nondeterministic Büchi word automata (NBW) to nondeterministic co-Büchi word automata (NCW). Among other applications, it is used in the translation (when possible) of LTL to the alternation-free μ -calculus. The best known upper bound for the translation of NBW to NCW is exponential (given an NBW with n states, the best translation yields an equivalent NCW with 2 O ( n log n ) states). On the other hand, the best known lower bound is trivial (no NBW with n states whose equivalent NCW requires even n + 1 states is known). In fact, only recently was it shown that there is an NBW whose equivalent NCW requires a different structure. In this paper we improve the lower bound by showing that for every integer k ≥ 1 there is a language L k over a two-letter alphabet, such that L k can be recognized by an NBW with 2 k + 1 states, whereas the minimal NCW that recognizes L k has 3 k states. Even though this gap is not asymptotically very significant, it nonetheless demonstrates for the first time that NBWs are more succinct than NCWs. In addition, our proof points to a conceptual advantage of the Büchi condition: an NBW can abstract precise counting by counting to infinity with two states. To complete the picture, we consider also the reverse NCW to NBW translation, and show that the known upper bound, which duplicates the state space, is tight.

Details