Author name cluster

Evi Micha

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.

26 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Temporal Panel Selection in Ongoing Citizens' Assemblies

Yusuf Hakan Kalayci
Evi Micha

Permanent citizens’ assemblies are ongoing deliberative bodies composed of randomly selected citizens, organized into panels that rotate over time. Unlike one-off panels, which represent the population in a single snapshot, permanent assemblies enable shifting participation across multiple rounds. This structure offers a powerful framework for ensuring that different groups of individuals are represented over time across successive panels. In particular, it allows smaller groups of individuals that may not warrant representation in every individual panel to be represented across a sequence of them. We formalize this temporal sortition framework by requiring proportional representation both within each individual panel and across the sequence of panels. Building on the work of Ebadian and Micha (2025), we consider a setting in which the population lies in a metric space, and the goal is to achieve both proportional representation, ensuring that every group of citizens receives adequate representation, and individual fairness, ensuring that each individual has an equal probability of beingselected. Weextendthenotionofrepresentationtoatemporal settingbyrequiringthateveryinitialsegmentofthepanelsequence, viewed as a cumulative whole, proportionally reflects the structure of the population. We present algorithms that provide varying guarantees of proportional representation, both within individual panels and across any sequence of panels, while also maintaining individual fairness over time.

PDF

AAAI Conference 2025 Conference Paper

Axioms for AI Alignment from Human Feedback

Evi Micha

In the context of reinforcement learning from human feedback (RLHF), the reward function is generally derived from maximum likelihood estimation of a random utility model based on pairwise comparisons made by humans. The problem of learning a reward function is one of preference aggregation that, we argue, largely falls within the scope of social choice theory. From this perspective, we can evaluate different aggregation methods via established axioms, examining whether these methods meet or fail well-known standards. We demonstrate that both the Bradley-Terry-Luce Model and its broad generalizations fail to meet basic axioms. In response, we develop novel rules for learning reward functions with strong axiomatic guarantees. A key innovation from the standpoint of social choice is that our problem has a linear structure, which greatly restricts the space of feasible rules and leads to a new paradigm that we call linear social choice.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

Boosting Sortition via Proportional Representation

Soroush Ebadian
Evi Micha

Sortition is based on the idea of choosing randomly selected representatives for decision making. The main properties that make sortition particularly appealing are fairness — where every citizen has an equal chance of being selected— and proportional representation — where a randomly selected panel likely reflects the composition of the entire population. When the population lies on a representation metric, we formally define proportional representation by using a notion called the core. A panel is in the core if no group of individuals is underrepresented proportional to its size. While uniform selection is fair, it does not always return panels that are in the core. Thus, we ask if we can design a selection algorithm that satisfies fairness and ex post core simultaneously. We answer this question affirmatively and present an efficient selection algorithm that is fair and provides a constant-factor approximation to the optimal ex post core. Moreover, we show that uniformly random selection satisfies a constant-factor approximation to the optimal ex ante core. We complement our theoretical results by conducting experiments with real data.

PDF

ICML Conference 2025 Conference Paper

Computing Voting Rules with Improvement Feedback

Evi Micha
Vasilis Varsamis

Aggregating preferences under incomplete or constrained feedback is a fundamental problem in social choice and related domains. While prior work has established strong impossibility results for pairwise comparisons, this paper extends the inquiry to improvement feedback, where voters express incremental adjustments rather than complete preferences. We provide a complete characterization of the positional scoring rules that can be computed given improvement feedback. Interestingly, while plurality is learnable under improvement feedback—unlike with pairwise feedback—strong impossibility results persist for many other positional scoring rules. Furthermore, we show that improvement feedback, unlike pairwise feedback, does not suffice for the computation of any Condorcet-consistent rule. We complement our theoretical findings with experimental results, providing further insights into the practical implications of improvement feedback for preference aggregation.

Details

NeurIPS Conference 2025 Conference Paper

Pairwise Calibrated Rewards for Pluralistic Alignment

Daniel Halpern
Evi Micha
Ariel Procaccia
Itai Shapira

Current alignment pipelines presume a single, universal notion of desirable behavior. However, human preferences often diverge across users, contexts, and cultures. As a result, disagreement collapses into the majority signal and minority perspectives are discounted. To address this, we propose reflecting diverse human preferences through a distribution over multiple reward functions, each inducing a distinct aligned policy. The distribution is learned directly from pairwise preference without annotator identifiers or predefined groups. Instead, annotator disagreements are treated as informative soft labels. Our central criterion is \emph{pairwise calibration}: for every pair of candidate responses, the proportion of reward functions preferring one response matches the fraction of annotators with that preference. We prove that even a small outlier-free ensemble can accurately represent diverse preference distributions. Empirically, we introduce and validate a practical training heuristic to learn such ensembles, and demonstrate its effectiveness through improved calibration, implying a more faithful representation of pluralistic values.

PDF Details

ICLR Conference 2025 Conference Paper

Strategic Classification With Externalities

Safwan Hossain
Evi Micha
Yiling Chen 0001
Ariel D. Procaccia

We propose a new variant of the strategic classification problem: a principal reveals a classifier, and $n$ agents report their (possibly manipulated) features to be classified. Motivated by real-world applications, our model crucially allows the manipulation of one agent to affect another; that is, it explicitly captures inter-agent externalities. The principal-agent interactions are formally modeled as a Stackelberg game, with the resulting agent manipulation dynamics captured as a simultaneous game. We show that under certain assumptions, the pure Nash Equilibrium of this agent manipulation game is unique and can be efficiently computed. Leveraging this result, PAC learning guarantees are established for the learner: informally, we show that it is possible to learn classifiers that minimize loss on the distribution, even when a random number of agents are manipulating their way to a pure Nash Equilibrium. We also comment on the optimization of such classifiers through gradient-based approaches. This work sets the theoretical foundations for a more realistic analysis of classifiers that are robust against multiple strategic actors interacting in a common environment.

Details

NeurIPS Conference 2024 Conference Paper

Axioms for AI Alignment from Human Feedback

Luise Ge
Daniel Halpern
Evi Micha
Ariel D. Procaccia
Itai Shapira
Yevgeniy Vorobeychik
Junlin Wu

PDF Details DOI

ICML Conference 2024 Conference Paper

Can a Few Decide for Many? The Metric Distortion of Sortition

Ioannis Caragiannis
Evi Micha
Jannik Peters 0001

Recent works have studied the design of algorithms for selecting representative sortition panels. However, the most central question remains unaddressed: Do these panels reflect the entire population’s opinion? We present a positive answer by adopting the concept of metric distortion from computational social choice, which aims to quantify how much a panel’s decision aligns with the ideal decision of the population when preferences and agents lie on a metric space. We show that uniform selection needs only logarithmically many agents in terms of the number of alternatives to achieve almost optimal distortion. We also show that Fair Greedy Capture, a selection algorithm introduced recently by Ebadian and Micha (2024), matches uniform selection’s guarantees of almost optimal distortion and also achieves constant ex-post distortion, ensuring a “best of both worlds” performance.

Details

IJCAI Conference 2024 Conference Paper

Metric Distortion with Elicited Pairwise Comparisons

Soroush Ebadian
Daniel Halpern
Evi Micha

In many social choice applications, information about individuals' preferences can only be elicited using a limited number of pairwise comparisons. In these cases, the task is twofold: we must first choose the queries, and then second, we must aggregate the responses to choose an outcome. We study the problem of designing algorithms for this setting. To compare the effectiveness of different outcomes, we use the metric distortion framework. In addition, we consider various constraints on the query algorithms, namely, placing restrictions on how the choice of the next query may depend on previous answers. Our main contributions are nearly optimal algorithms for all settings considered.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Proportional Fairness in Non-Centroid Clustering

Ioannis Caragiannis
Evi Micha
Nisarg Shah

We revisit the recently developed framework of proportionally fair clustering, where the goal is to provide group fairness guarantees that become stronger for groups of data points that are large and cohesive. Prior work applies this framework to centroid-based clustering, where points are partitioned into clusters, and the cost to each data point is measured by its distance to a centroid assigned to its cluster. However, real-life applications often do not require such centroids. We extend the theory of proportionally fair clustering to non-centroid clustering by considering a variety of cost functions, both metric and non-metric, for a data point to be placed in a cluster with other data points. Our results indicate that Greedy Capture, a clustering algorithm developed for centroid clustering, continues to provide strong proportional fairness guarantees for non-centroid clustering, although the guarantees are significantly different and establishing them requires novel proof ideas. We also design algorithms for auditing proportional fairness of a given clustering solution. We conduct experiments on real data which suggest that traditional clustering algorithms are highly unfair, while our algorithms achieve strong fairness guarantees with a moderate loss in common clustering objectives.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

What Is Best for Students, Numerical Scores or Letter Grades?

Evi Micha
Shreyas Sekar
Nisarg Shah

We study letter grading schemes, which are routinely employed for evaluating student performance. Typically, a numerical score obtained via one or more evaluations is converted into a letter grade (e. g. , A+, B-, etc. ) by associating a disjoint interval of numerical scores to each letter grade. We propose the first model for studying the (de)motivational effects of such grading on the students and, consequently, on their performance in future evaluations. We use the model to compare uniform letter grading schemes, in which the range of scores is divided into equal-length parts that are mapped to the letter grades, to numerical scoring, in which the score is not converted to any letter grade (equivalently, every score is its own letter grade). Theoretically, we identify realistic conditions under which numerical scoring is better than any uniform letter grading scheme. Our experiments confirm that this holds under even weaker conditions, but also find cases where the converse occurs.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Best of Both Worlds Fairness under Entitlements

Haris Aziz
Aditya Ganguly
Evi Micha

We consider probabilistic allocation of indivisible items to agents with additive valuations and weighted entitlements. We explore how far ex-ante and ex-post fairness properties can be achieved simultaneously. Our first result is that in contrast to the case of same entitlements, well-established adaptations of ex-ante envy-freeness and ex-post envy-freeness up to one item (EF1) to the case of entitlements are not compatible. We then present a polynomial-time algorithm that achieves weighted ex-ante envy-freeness and ex-post weighted envy-freeness up to 1 transfer. The outcome is ex-ante weighted envy-free for all utilities consistent with the underlying ordinal preferences but it is not Pareto optimal. We then present an alternative polynomial-time algorithm that satisfies Pareto optimality (both ex-ante and ex-post), ex-ante weighted envy-freeness and ex-post weighted proportionality up to one item.

PDF

AAMAS Conference 2023 Conference Paper

Group Fairness in Peer Review

Haris Aziz
Evi Micha
Nisarg Shah

Conferences like AAMAS and NeurIPS have attracted submissions from a large number of communities. This has resulted in a poor reviewing experience for communities, whose submissions are assigned to less qualified reviewers outside of their communities. An often-advocated solution is to break up such large conferences into smaller conferences, but this can lead to the isolation of various communities. We tackle this challenge by introducing a notion of group fairness, called core, which requires every subset of researchers to be treated in such a manner such that they cannot benefit from organizing a smaller conference on their own. We study a simple peer review model, prove that it always admits a reviewing assignment in the core, and design an efficient algorithm to find one such assignment. On the negative side, we show that the core is incompatible with achieving a good worstcase approximation of social welfare, an often-sought desideratum. We complement these results by conducting experiments with real data.

PDF

NeurIPS Conference 2023 Conference Paper

Group Fairness in Peer Review

Haris Aziz
Evi Micha
Nisarg Shah

Large conferences such as NeurIPS and AAAI serve as crossroads of various AI fields, since they attract submissions from a vast number of communities. However, in some cases, this has resulted in a poor reviewing experience for some communities, whose submissions get assigned to less qualified reviewers outside of their communities. An often-advocated solution is to break up any such large conference into smaller conferences, but this can lead to isolation of communities and harm interdisciplinary research. We tackle this challenge by introducing a notion of group fairness, called the core, which requires that every possible community (subset of researchers) to be treated in a way that prevents them from unilaterally benefiting by withdrawing from a large conference. We study a simple peer review model, prove that it always admits a reviewing assignment in the core, and design an efficient algorithm to find one such assignment. We use real data from CVPR and ICLR conferences to compare our algorithm to existing reviewing assignment algorithms on a number of metrics.

PDF Details

AAAI Conference 2023 Conference Paper

Partitioning Friends Fairly

Lily Li
Evi Micha
Aleksandar Nikolov
Nisarg Shah

We consider the problem of partitioning n agents in an undirected social network into k almost equal in size (differing by at most one) groups, where the utility of an agent for a group is the number of her neighbors in the group. The core and envy-freeness are two compelling axiomatic fairness guarantees in such settings. The former demands that there be no coalition of agents such that each agent in the coalition has more utility for that coalition than for her own group, while the latter demands that no agent envy another agent for the group they are in. We provide (often tight) approximations to both fairness guarantees, and many of our positive results are obtained via efficient algorithms.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Proportionally Fair Online Allocation of Public Goods with Predictions

Siddhartha Banerjee
Vasilis Gkatzelis
Safwan Hossain
Billy Jin
Evi Micha
Nisarg Shah

We design online algorithms for fair allocation of public goods to a set of N agents over a sequence of T rounds and focus on improving their performance using predictions. In the basic model, a public good arrives in each round, and every agent reveals their value for it upon arrival. The algorithm must irrevocably decide the investment in this good without exceeding a total budget of B across all rounds. The algorithm can utilize (potentially noisy) predictions of each agent’s total value for all remaining goods. The algorithm's performance is measured using a proportional fairness objective, which informally demands that every group of agents be rewarded proportional to its size and the cohesiveness of its preferences. We show that no algorithm can achieve better than Θ(T/B) proportional fairness without predictions. With reasonably accurate predictions, the situation improves significantly, and Θ(log(T/B)) proportional fairness is achieved. We also extend our results to a general setting wherein a batch of L public goods arrive in each round and O(log(min(N, L)T/B)) proportional fairness is achieved. Our exact bounds are parameterized as a function of the prediction error, with performance degrading gracefully with increasing errors.

PDF Details DOI

AAAI Conference 2022 Conference Paper

A Little Charity Guarantees Fair Connected Graph Partitioning

Ioannis Caragiannis
Evi Micha
Nisarg Shah

Motivated by fair division applications, we study a fair connected graph partitioning problem, in which an undirected graph with m nodes must be divided between n agents such that each agent receives a connected subgraph and the partition is fair. We study approximate versions of two fairness criteria: α-proportionality requires that each agent receives a subgraph with at least 1/α · m/n nodes, and α-balancedness requires that the ratio between the sizes of the largest and smallest subgraphs be at most α. Unfortunately, there exist simple examples in which no partition is reasonably proportional or balanced. To circumvent this, we introduce the idea of charity. We show that by “donating” just n − 1 nodes, we can guarantee the existence of 2-proportional and almost 2balanced partitions (and find them in polynomial time), and that this result is almost tight. More generally, we chart the tradeoff between the size of charity and the approximation of proportionality or balancedness we can guarantee.

PDF Details

AAAI Conference 2022 Conference Paper

Individual Representation in Approval-Based Committee Voting

Markus Brill
Jonas Israel
Evi Micha
Jannik Peters

When selecting multiple candidates based on approval preferences of agents, the proportional representation of agents’ opinions is an important and well-studied desideratum. Existing criteria for evaluating the representativeness of outcomes focus on groups of agents and demand that sufficiently large and cohesive groups are “represented” in the sense that candidates approved by some group members are selected. Crucially, these criteria say nothing about the representation of individual agents, even if these agents are members of groups that deserve representation. In this paper, we formalize the concept of individual representation (IR) and explore to which extent, and under which circumstances, it can be achieved. We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible. We then focus on domain restrictions and establish an interesting contrast between “voter interval” and “candidate interval” preferences. This contrast can also be observed in our experimental results, where we analyze the attainability of IR for realistic preference profiles.

PDF Details

NeurIPS Conference 2022 Conference Paper

Is Sortition Both Representative and Fair?

Soroush Ebadian
Gregory Kehne
Evi Micha
Ariel D. Procaccia
Nisarg Shah

Sortition is a form of democracy built on random selection of representatives. Two of the key arguments in favor of sortition are that it provides representation (a random panel reflects the composition of the population) and fairness (everyone has a chance to participate). Uniformly random selection is perfectly fair, but is it representative? Towards answering this question, we introduce the notion of a representation metric on the space of individuals, and assume that the cost of an individual for a panel is determined by the $q$-th closest representative; the representation of a (random) panel is measured by the ratio between the (expected) sum of costs of the optimal panel for the individuals and that of the given panel. For $k/2 < q \le k-\Omega(k)$, where $k$ is the panel size, we show that uniform random selection is indeed representative by establishing a constant lower bound on this ratio. By contrast, for $q \leq k/2$, no random selection algorithm that is almost fair can give such a guarantee. We therefore consider relaxed fairness guarantees and develop a new random selection algorithm that sheds light on the tradeoff between representation and fairness.

PDF Details

NeurIPS Conference 2021 Conference Paper

Fair Algorithms for Multi-Agent Multi-Armed Bandits

Safwan Hossain
Evi Micha
Nisarg Shah

We propose a multi-agent variant of the classical multi-armed bandit problem, in which there are $N$ agents and $K$ arms, and pulling an arm generates a (possibly different) stochastic reward for each agent. Unlike the classical multi-armed bandit problem, the goal is not to learn the "best arm"; indeed, each agent may perceive a different arm to be the best for her personally. Instead, we seek to learn a fair distribution over the arms. Drawing on a long line of research in economics and computer science, we use the Nash social welfare as our notion of fairness. We design multi-agent variants of three classic multi-armed bandit algorithms and show that they achieve sublinear regret, which is now measured in terms of the lost Nash social welfare. We also extend a classical lower bound, establishing the optimality of one of our algorithms.

PDF Details

IJCAI Conference 2021 Conference Paper

Two-Sided Matching Meets Fair Division

Rupert Freeman
Evi Micha
Nisarg Shah

We introduce a new model for two-sided matching which allows us to borrow popular fairness notions from the fair division literature such as envy-freeness up to one good and maximin share guarantee. In our model, each agent is matched to multiple agents on the other side over whom she has additive preferences. We demand fairness for each side separately, giving rise to notions such as double envy-freeness up to one match (DEF1) and double maximin share guarantee (DMMS). We show that (a slight strengthening of) DEF1 cannot always be achieved, but in the special case where both sides have identical preferences, the round-robin algorithm with a carefully designed agent ordering achieves it. In contrast, DMMS cannot be achieved even when both sides have identical preferences.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Can We Predict the Election Outcome from Sampled Votes?

Evi Micha
Nisarg Shah

In the standard model of voting, it is assumed that a voting rule observes the ranked preferences of each individual over a set of alternatives and makes a collective decision. In practice, however, not every individual votes. Is it possible to make a good collective decision for a group given the preferences of only a few of its members? We propose a framework in which we are given the ranked preferences of k out of n individuals sampled from a distribution, and the goal is to predict what a given voting rule would output if applied on the underlying preferences of all n individuals. We focus on the family of positional scoring rules, derive a strong negative result when the underlying preferences can be arbitrary, and discover interesting phenomena when they are generated from a known distribution.

PDF Details

AIJ Journal 2020 Journal Article

The distortion of distributed voting

Aris Filos-Ratsikas
Evi Micha
Alexandros A. Voudouris

Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying the impact of utilizing only limited information in the voting process on the societal welfare for the outcome, by bounding the distortion of voting rules. Even though there has been significant progress towards this goal, almost all previous works have so far neglected the fact that in many scenarios (like presidential elections) voting is actually a distributed procedure. In this paper, we consider a setting in which the voters are partitioned into disjoint districts and vote locally therein to elect local winning alternatives using a voting rule; the final outcome is then chosen from the set of these alternatives. We prove tight bounds on the distortion of well-known voting rules for such distributed elections both from a worst-case perspective as well as from a best-case one. Our results indicate that the partition of voters into districts leads to considerably higher distortion, a phenomenon which we also experimentally showcase using real-world data.

Details DOI

AAAI Conference 2020 Conference Paper

The Surprising Power of Hiding Information in Facility Location

Safwan Hossain
Evi Micha
Nisarg Shah

Facility location is the problem of locating a public facility based on the preferences of multiple agents. In the classic framework, where each agent holds a single location on a line and can misreport it, strategyproof mechanisms for choosing the location of the facility are well-understood. We revisit this problem in a more general framework. We assume that each agent may hold several locations on the line with different degrees of importance to the agent. We study mechanisms which elicit the locations of the agents and different levels of information about their importance. Further, in addition to the classic manipulation of misreporting locations, we introduce and study a new manipulation, whereby agents may hide some of their locations. We argue for its novelty in facility location and applicability in practice. Our results provide a complete picture of the power of strategyproof mechanisms eliciting different levels of information and with respect to each type of manipulation. Surprisingly, we show that in some cases hiding locations can be a strictly more powerful manipulation than misreporting locations.

PDF Details

IJCAI Conference 2019 Conference Paper

A Contribution to the Critique of Liquid Democracy

Ioannis Caragiannis
Evi Micha

Liquid democracy, which combines features of direct and representative democracy has been proposed as a modern practice for collective decision making. Its advocates support that by allowing voters to delegate their vote to more informed voters can result in better decisions. In an attempt to evaluate the validity of such claims, we study liquid democracy as a means to discover an underlying ground truth. We revisit a recent model by Kahng et al. [2018] and conclude with three negative results, criticizing an important assumption of their modeling, as well as liquid democracy more generally. In particular, we first identify cases where natural local mechanisms are much worse than either direct voting or the other extreme of full delegation to a common dictator. We then show that delegating to less informed voters may considerably increase the chance of discovering the ground truth. Finally, we show that deciding delegations that maximize the probability to find the ground truth is a computationally hard problem.

PDF Details

IJCAI Conference 2017 Conference Paper

Learning a Ground Truth Ranking Using Noisy Approval Votes

Ioannis Caragiannis
Evi Micha

We consider a voting scenario where agents have opinions that are estimates of an underlying common ground truth ranking of the available alternatives, and each agent is asked to approve a set with her most preferred alternatives. We assume that estimates are implicitly formed using the well-known Mallows model for generating random rankings. We show that k-approval voting --- where all agents are asked to approve the same number k of alternatives and the outcome is obtained by sorting the alternatives in terms of their number of approvals --- has exponential sample complexity for all values of k. This negative result suggests that an exponential (in terms of the number of alternatives m) number of agents is always necessary in order to recover the ground truth ranking with high probability. In contrast, by just asking each agent to approve a random number of alternatives, the sample complexity improves dramatically: it now depends only polynomially on m. Our results may have implications on the effectiveness of crowdsourcing applications that ask workers to provide their input by approving sets of available alternatives.

PDF Details