BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Edith Elkind

Edith Elkind contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computer Science and Game TheoryComputational Complexityecon.THMultiagent SystemsMachine Learning

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2023arXiv

Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning

We use the ``map of elections'' approach of Szufa et al. (AAMAS-2020) to analyze several well-known vote distributions. For each of them, we give an explicit formula or an efficient algorithm for computing its frequency matrix, which captures the probability that a given candidate appears in a given position in a sampled vote. We use these matrices to draw the ``skeleton map'' of distributions, evaluate its robustness, and analyze its properties. Finally, we develop a general and unified framework for learning the distribution of real-world preferences using the frequency matrices of established vote distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Better Collective Decisions via Uncertainty Reduction

We consider an agent community wishing to decide on several binary issues by means of issue-by-issue majority voting. For each issue and each agent, one of the two options is better than the other. However, some of the agents may be confused about some of the issues, in which case they may vote for the option that is objectively worse for them. A benevolent external party wants to help the agents to make better decisions, i.e., select the majority-preferred option for as many issues as possible. This party may have one of the following tools at its disposal: (1) educating some of the agents, so as to enable them to vote correctly on all issues, (2) appointing a subset of highly competent agents to make decisions on behalf of the entire group, or (3) guiding the agents on how to delegate their votes to other agents, in a way that is consistent with the agents' opinions. For each of these tools, we study the complexity of the decision problem faced by this external party, obtaining both NP-hardness results and fixed-parameter tractability results.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Complexity of Deliberative Coalition Formation

Elkind et al. (AAAI, 2021) introduced a model for deliberative coalition formation, where a community wishes to identify a strongly supported proposal from a space of alternatives, in order to change the status quo. In their model, agents and proposals are points in a metric space, agents' preferences are determined by distances, and agents deliberate by dynamically forming coalitions around proposals that they prefer over the status quo. The deliberation process operates via k-compromise transitions, where agents from k (current) coalitions come together to form a larger coalition in order to support a (perhaps new) proposal, possibly leaving behind some of the dissenting agents from their old coalitions. A deliberation succeeds if it terminates by identifying a proposal with the largest possible support. For deliberation in d dimensions, Elkind et al. consider two variants of their model: in the Euclidean model, proposals and agent locations are points in R^d and the distance is measured according to ||...||_2; and in the hypercube model, proposals and agent locations are vertices of the d-dimensional hypercube and the metric is the Hamming distance. They show that in the continuous model 2-compromises are guaranteed to succeed, but in the discrete model for deliberation to succeed it may be necessary to use k-compromises with k >= d. We complement their analysis by (1) proving that in both models it is hard to find a proposal with a high degree of support, and even a 2-compromise transition may be hard to compute; (2) showing that a sequence of 2-compromise transitions may be exponentially long; (3) strengthening the lower bound on the size of the compromise for the d-hypercube model from d to 2^{Ω(d)}.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Contests to Incentivize a Target Group

We study how to incentivize agents in a target group to produce a higher output in the context of incomplete information, by means of rank-order allocation contests. We describe a symmetric Bayes--Nash equilibrium for contests that have two types of rank-based prizes: prizes that are accessible only to the agents in the target group; prizes that are accessible to everyone. We also specialize this equilibrium characterization to two important sub-cases: (i) contests that do not discriminate while awarding the prizes, i.e., only have prizes that are accessible to everyone; (ii) contests that have prize quotas for the groups, and each group can compete only for prizes in their share. For these models, we also study the properties of the contest that maximizes the expected total output by the agents in the target group.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Explaining Preferences by Multiple Patterns in Voters' Behavior

In some preference aggregation scenarios, voters' preferences are highly structured: e.g., the set of candidates may have one-dimensional structure (so that voters' preferences are single-peaked) or be described by a binary decision tree (so that voters' preferences are group-separable). However, sometimes a single axis or a decision tree is insufficient to capture the voters' preferences; rather, there is a small number $k$ of axes or decision trees such that each vote in the profile is consistent with one of these axes (resp., trees). In this work, we study the complexity of deciding whether voters' preferences can be explained in this manner. For $k=2$, we use the technique developed by Yang~[2020] in the context of single-peaked preferences to obtain a polynomial-time algorithm for several domains: value-restricted preferences, group-separable preferences, and a natural subdomain of group-separable preferences, namely, caterpillar group-separable preferences. For $k\ge 3$, the problem is known to be hard for single-peaked preferences; we show that this is also the case for value-restricted and group-separable preferences. Our positive results for $k=2$ make use of forbidden minor characterizations of the respective domains; in particular, we establish that the domain of caterpillar group-separable preferences admits a forbidden minor characterization.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results

A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demange (1982), and subsequently Trick (1989) described an efficient algorithm for deciding if a given profile is single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin-Courant rule for preferences single-peaked on trees. We show that the egalitarian version of this problem admits a polynomial-time algorithm. For the utilitarian version, we prove that winner determination remains NP-hard, even for the Borda scoring function; however, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We also consider several other optimization criteria for trees: for some we obtain polynomial-time algorithms, while for others we show NP-hardness results.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy

We study a general scenario of simultaneous contests that allocate prizes based on equal sharing: each contest awards its prize to all players who satisfy some contest-specific criterion, and the value of this prize to a winner decreases as the number of winners increases. The players produce outputs for a set of activities, and the winning criteria of the contests are based on these outputs. We consider two variations of the model: (i) players have costs for producing outputs; (ii) players do not have costs but have generalized budget constraints. We observe that these games are exact potential games and hence always have a pure-strategy Nash equilibrium. The price of anarchy is $2$ for the budget model, but can be unbounded for the cost model. Our main results are for the computational complexity of these games. We prove that for general versions of the model exactly or approximately computing a best response is NP-hard. For natural restricted versions where best response is easy to compute, we show that finding a pure-strategy Nash equilibrium is PLS-complete, and finding a mixed-strategy Nash equilibrium is (PPAD$\cap$PLS)-complete. On the other hand, an approximate pure-strategy Nash equilibrium can be found in pseudo-polynomial time. These games are a strict but natural subclass of explicit congestion games, but they still have the same equilibrium hardness results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Election Control by Manipulating Issue Significance

Integrity of elections is vital to democratic systems, but it is frequently threatened by malicious actors. The study of algorithmic complexity of the problem of manipulating election outcomes by changing its structural features is known as election control. One means of election control that has been proposed is to select a subset of issues that determine voter preferences over candidates. We study a variation of this model in which voters have judgments about relative importance of issues, and a malicious actor can manipulate these judgments. We show that computing effective manipulations in this model is NP-hard even with two candidates or binary issues. However, we demonstrate that the problem is tractable with a constant number of voters or issues. Additionally, while it remains intractable when voters can vote stochastically, we exhibit an important special case in which stochastic voting enables tractable manipulation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Keeping Your Friends Close: Land Allocation with Friends

We examine the problem of assigning plots of land to prospective buyers who prefer living next to their friends. They care not only about the plot they receive, but also about their neighbors. This externality results in a highly non-trivial problem structure, as both friendship and land value play a role in determining agent behavior. We examine mechanisms that guarantee truthful reporting of both land values and friendships. We propose variants of random serial dictatorship (RSD) that can offer both truthfulness and welfare guarantees. Interestingly, our social welfare guarantees are parameterized by the value of friendship: if these values are low, enforcing truthful behavior results in poor welfare guarantees and imposes significant constraints on agents' choices; if they are high, we achieve good approximation to the optimal social welfare.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stable Roommate Problem with Diversity Preferences

In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences [Bredereck et al., 2019]: each agent belongs to one of the two types (e.g., juniors and seniors, artists and engineers), and agents' preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem. Moreover, for the classic setting with rooms of size two, we present a linear-time algorithm that computes an outcome that is core and exchange stable as well as Pareto optimal. Many of our results for the stable roommate problem extend to the stable marriage problem.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Equilibria of Plurality Voting with Abstentions

In the traditional voting manipulation literature, it is assumed that a group of manipulators jointly misrepresent their preferences to get a certain candidate elected, while the remaining voters are truthful. In this paper, we depart from this assumption, and consider the setting where all voters are strategic. In this case, the election can be viewed as a game, and the election outcomes correspond to Nash equilibria of this game. We use this framework to analyze two variants of Plurality voting, namely, simultaneous voting, where all voters submit their ballots at the same time, and sequential voting, where the voters express their preferences one by one. For simultaneous voting, we characterize the preference profiles that admit a pure Nash equilibrium, but show that it is computationally hard to check if a given profile fits our criterion. For sequential voting, we provide a complete analysis of the setting with two candidates, and show that for three or more candidates the equilibria of sequential voting may behave in a counterintuitive manner.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Rationalizations of Condorcet-Consistent Rules via Distances of Hamming Type

The main idea of the {\em distance rationalizability} approach to view the voters' preferences as an imperfect approximation to some kind of consensus is deeply rooted in social choice literature. It allows one to define ("rationalize") voting rules via a consensus class of elections and a distance: a candidate is said to be an election winner if she is ranked first in one of the nearest (with respect to the given distance) consensus elections. It is known that many classic voting rules can be distance rationalized. In this paper, we provide new results on distance rationalizability of several Condorcet-consistent voting rules. In particular, we distance rationalize Young's rule and Maximin rule using distances similar to the Hamming distance. We show that the claim that Young's rule can be rationalized by the Condorcet consensus class and the Hamming distance is incorrect; in fact, these consensus class and distance yield a new rule which has not been studied before. We prove that, similarly to Young's rule, this new rule has a computationally hard winner determination problem.

0 citations0 reviewsNo code linkedOpen access