We study strategic behavior of project proposers in the context of approval-based participatory budgeting (PB). In our model we assume that the votes are fixed and known and the proposers want to set as high project prices as possible, provided that their projects get selected and the prices are not below the minimum costs of their delivery. We study the existence of pure Nash equilibria (NE) in such games, focusing on the AV/Cost, Phragmen, and Method of Equal Shares rules. We also provide an experimental study of cost selection on real-life PB election data.

Pure proportional voting rules can sometimes lead to highly suboptimal outcomes. We introduce the Method of Equal Shares with Bounded Overspending (BOS Equal Shares), a robust variant of the Method of Equal Shares that balances proportionality and efficiency. BOS Equal Shares addresses inefficiencies implied by strict proportionality axioms, yet still provides fairness guarantees, similar to the original Equal Shares. Our extensive empirical analysis shows excellent performance of BOS Equal Shares across several metrics. In the course of the analysis, we also study a fractional variant of the Method of Equal Shares.

Our main contribution is the introduction of the map of elections framework. A map of elections consists of three main elements: (1) a dataset of elections (i.e., collections of ordinal votes over given sets of candidates), (2) a way of measuring similarities between these elections, and (3) a representation of the elections in the 2D Euclidean space as points, so that the more similar two elections are, the closer are their points. In our maps, we mostly focus on datasets of synthetic elections, but we also show an example of a map over real-life ones. To measure similarities, we would have preferred to use, e.g., the isomorphic swap distance, but this is infeasible due to its high computational complexity. Hence, we propose polynomial-time computable positionwise distance and use it instead. Regarding the representations in 2D Euclidean space , we mostly use the Kamada-Kawai algorithm, but we also show two alternatives. We develop the necessary theoretical results to form our maps and argue experimentally that they are accurate and credible. Further, we show how coloring the elections in a map according to various criteria helps in analyzing results of a number of experiments. In particular, we show colorings according to the scores of winning candidates or committees, running times of ILP-based winner determination algorithms, and approximation ratios achieved by particular algorithms.

We introduce and study isomorphic distances between ordinal elections (with the same numbers of candidates and voters). The main feature of these distances is that they are invariant to renaming the candidates and voters, and two elections are at distance zero if and only if they are isomorphic. Specifically, we consider isomorphic extensions of distances between preference orders: Given such a distance d , we extend it to distance d - ID between elections by unifying candidate names and finding a matching between the votes, so that the sum of the d -distances between the matched votes is as small as possible. We show that testing isomorphism of two elections can be done in polynomial time so, in principle, such distances can be tractable. Yet, we show that two very natural isomorphic distances are NP-complete and hard to approximate. We attempt to rectify the situation by showing FPT algorithms for several natural parameterizations.

We consider a voting model, where a number of candidates need to be selected subject to certain feasibility constraints. The model generalizes committee elections (where there is a single constraint on the number of candidates that need to be selected), various elections with diversity constraints, the model of public decisions (where decisions need to be taken on a number of independent issues), and the model of collective scheduling. A critical property of voting is that it should be fair---not only to individuals but also to groups of voters with similar opinions on the subject of the vote; in other words, the outcome of an election should proportionally reflect the voters' preferences.

We provide a library of participatory budgeting data (Pabulib) and open source tools (Pabutools and Pabustats) for analysing this data. We analyse how the results of participatory budgeting elections would change if a different selection rule was applied. We provide evidence that the outcomes of the Method of Equal Shares would be considerably fairer than those of the Utilitarian Greedy rule that is currently in use. We also show that the division of the projects into districts and/or categories can in many cases be avoided when using proportional rules. We find that this would increase the overall utility of the voters.

We consider a setting where a group of individuals needs to make a number of independent decisions. The decisions should proportionally represent the views of the voters. We formulate new criteria of proportionality and analyse two rules, Proportional Approval Voting and the Method of Equal Shares, that are inspired by the corresponding approval-based committee election rules. We prove that the two rules provide very strong proportionality guarantees when applied to the setting of public decisions.

We study two concepts of proportionality in the model of approval-based committee elections. In degressive proportionality small minorities of voters are favored in comparison with the standard linear proportionality. Regressive proportionality, on the other hand, requires that larger subdivisions of voters are privileged. We introduce a new family of rules that broadly generalize Phragmén's Sequential Rule spanning the spectrum between degressive and regressive proportionality. We analyze and compare the two principles of proportionality assuming the voters and the candidates can be represented as points in an Euclidean issue space.

Assume k candidates need to be selected. The candidates appear over time. Each time one appears, it must be immediately selected or rejected---a decision that is made by a group of individuals through voting. Assume the voters use approval ballots, i.e., for each candidate they only specify whether they consider it acceptable or not. This setting can be seen as a voting variant of choosing k secretaries. Our contribution is twofold. (1) We assess to what extent the committees that are computed online can proportionally represent the voters. (2) If a prior probability over candidate approvals is available, we show how to compute committees with maximal expected score.

We study approval-based committee elections for the case where the voters' preferences come from a 2D-Euclidean model. We consider two main issues: First, we ask for the complexity of computing election results. Second, we evaluate election outcomes experimentally, following the visualization technique of Elkind et al., (AAAI-2017). Regarding the first issue, we find that many NP-hard rules remain intractable for 2D-Euclidean elections. For the second one, we observe that the behavior and nature of many rules strongly depends on the exact protocol for choosing the approved candidates.

We consider approval-based committee elections, in which a size-k subset of available candidates must be selected given approval sets for each voter, indicating the candidates approved by the voter. A number of axioms capturing ideas of fairness and proportionality have been proposed for this framework. We argue that even the strongest of them, such as priceability and the core, only rule out certain undesirable committees, but fail to ensure that the selected committee is fair in all cases. We propose two new solution concepts, stable priceability and balanced stable priceability, and show that they select arguably fair committees. Our solution concepts come with a non-trivial-to-construct but easy-to-understand market-based explanation for why the chosen committee is fair. We show that stable priceability is closely related to the notion of Lindahl equilibrium from economics.

We study voting rules for participatory budgeting, where a group of voters collectively decides which projects should be funded using a common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate two axioms that guarantee proportional representation to groups of voters with common interests. To the best of our knowledge, all known rules for participatory budgeting do not satisfy either of the two axioms; in addition we show that the most prominent proportional rule for committee elections, Proportional Approval Voting, cannot be adapted to arbitrary costs nor to additive valuations so that it would satisfy our axioms of proportionality. We construct a simple and attractive voting rule that satisfies one of our axioms (for arbitrary costs and arbitrary additive valuations), and that can be evaluated in polynomial time. We prove that our other stronger axiom is also satisfiable, though by a computationally more expensive and less natural voting rule.

An instance of an approval-based multiwinner election consists of a set of alternatives, a population of voters---each voter approves a subset of alternatives, and the desired committee size k; the goal is to select a committee (a subset) of k alternatives according to the preferences of the voters. We investigate a number of election rules and ask whether the committees that they return represent the voters proportionally. In contrast to the classic literature, we employ quantitative techniques that allow to measure the extent to which the considered rules are proportional. This allows us to arrange the rules in a clear hierarchy. For example, we find that Proportional Approval Voting (PAV) has better proportionality guarantees than its sequential counterpart, and that Phragmen's Sequential Rule is worse than Sequential PAV. Yet, the loss of proportionality for the two sequential rules is moderate and in some contexts can be outweighed by their other appealing properties. Finally, we measure the tradeoff between proportionality and utilitarian efficiency for a broad subclass of committee election rules.

Election rules are formal processes that aggregate voters' preferences, typically to select a single winning candidate. Most of the election rules studied in the literature require the voters to rank the candidates from the most to the least preferred one. This method of eliciting preferences is impractical when the number of candidates to be ranked is large. We ask how well certain election rules (focusing on positional scoring rules and the Minimax rule) can be approximated from partial preferences collected through one of the following procedures: (i) randomized—we ask each voter to rank a random subset of ℓ candidates, and (ii) deterministic—we ask each voter to provide a ranking of her ℓ most preferred candidates (the ℓ-truncated ballot). We establish theoretical bounds on the approximation ratios and complement our theoretical analysis with computer simulations. We find that it is usually better to use the randomized approach.

A group of agents needs to divide a divisible common resource (such as a monetary budget) among several uses or projects. We assume that agents have approval preferences over projects, and their utility is the fraction of the budget spent on approved projects. If we maximize utilitarian social welfare, the entire budget will be spent on a single popular project, even if a substantial fraction of the agents disapprove it. This violates the individual fair share axiom (IFS) which requires that for each agent, at least 1/n of the budget is spent on approved projects. We study the price of imposing such fairness axioms on utilitarian social welfare. We show that no division rule satisfying IFS can guarantee to achieve more than an O(1/√m) fraction of maximum utilitarian welfare, in the worst case. However, imposing stronger group fairness conditions (such as the core) does not come with an increased price, since both the conditional utilitarian rule and the Nash rule match this bound and guarantee an Ώ(1/√m) fraction. The same guarantee is attained by the rule under which the spending on a project is proportional to its approval score. We also study a family of rules interpolating between the utilitarian and the Nash rule, quantifying a trade-off between welfare and group fairness. An experimental analysis by sampling using several probabilistic models shows that the conditional utilitarian rule achieves very high welfare on average.

We study a model where a group of representatives is elected to make a series of decisions on behalf of voters. The quality of such a representative committee is judged based on the extent to which the decisions it makes are consistent with the voters' preferences. We assume the set of issues on which the committee will make the decisions is unknown---a committee is elected based on the preferences of the voters over the candidates, which only reflect how similar are the preferences of the voters and candidates regarding the issues. In this model we theoretically and experimentally assess qualities of various multiwinner election rules.

We study two influential voting rules proposed in the 1890s by Phragmen and Thiele, which elect a committee of k candidates which proportionally represents the voters. Voters provide their preferences by approving an arbitrary number of candidates. Previous work has proposed proportionality axioms satisfied by Thiele's rule (now known as Proportional Approval Voting, PAV) but not by Phragmen's rule. By proposing two new proportionality axioms (laminar proportionality and priceability) satisfied by Phragmen but not Thiele, we show that the two rules achieve two distinct forms of proportional representation. Phragmen's rule ensures that all voters have a similar amount of influence on the committee, and Thiele's rule ensures a fair utility distribution. Thiele's rule is a welfarist voting rule (one that maximizes a function of voter utilities). We show that no welfarist rule can satisfy our new axioms, and we prove that no such rule can satisfy the core. Conversely, some welfarist fairness properties cannot be guaranteed by Phragmen-type rules. This formalizes the difference between the two types of proportionality. We then introduce an attractive committee rule which satisfies a property intermediate between the core and extended justified representation (EJR). It satisfies laminar proportionality, priceability, and is computable in polynomial time. We show that our new rule provides a logarithmic approximation to the core. On the other hand, PAV provides a factor-2 approximation to the core, and this factor is optimal for rules that are fair in the sense of the Pigou--Dalton principle. The full version of the paper is available at http://arxiv.org/pdf/1911.11747.pdf.

We introduce the ELECTION ISOMORPHISM problem and a family of its approximate variants, which we refer to as dISOMORPHISM DISTANCE (d-ID) problems (where d is a metric between preference orders). We show that ELECTION ISOMORPHISM is polynomial-time solvable, and that the d-ISOMORPHISM DISTANCE problems generalize various classic rank-aggregation methods (e.g., those of Kemeny and Litvak). We establish the complexity of our problems (including their inapproximability) and provide initial experiments regarding the ability to solve them in practice.

We study the following multiagent variant of the knapsack problem. We are given a set of items, a set of voters, and a value of the budget; each item is endowed with a cost and each voter assigns to each item a certain value. The goal is to select a subset of items with the total cost not exceeding the budget, in a way that is consistent with the voters’ preferences. Since the preferences of the voters over the items can vary significantly, we need a way of aggregating these preferences, in order to select the socially best valid knapsack. We study three approaches to aggregating voters’ preferences, which are motivated by the literature on multiwinner elections and fair allocation. This way we introduce the concepts of individually best, diverse, and fair knapsack. We study the computational complexity (including parameterized complexity, and complexity under restricted domains) of the aforementioned multiagent variants of knapsack.

To choose a suitable multi-winner voting rule is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an "optimal" subset.In this paper, we offer a new perspective on measuring the quality of such subsets and---consequently---of multi-winner rules. We provide a quantitative analysis using methods from the theory of approximation algorithms and estimate how well multi-winner rules approximate two extreme objectives: diversity as captured by the Approval Chamberlin--Courant rule and individual excellence as captured by Multi-winner Approval Voting. With both theoretical and experimental methods we classify multi-winner rules in terms of their quantitative alignment with these two opposing objectives.

We consider elections where both voters and candidates can be associated with points in a metric space and voters prefer candidates that are closer to those that are farther away. It is often assumed that the optimal candidate is the one that minimizes the total distance to the voters. Yet, the voting rules often do not have access to the metric space M and only see preference rankings induced by M. Consequently, they often are incapable of selecting the optimal candidate. The distortion of a voting rule measures the worst-case loss of the quality being the result of having access only to preference rankings. We extend the idea of distortion to approval-based preferences. First, we compute the distortion of Approval Voting. Second, we introduce the concept of acceptability-based distortion---the main idea behind is that the optimal candidate is the one that is acceptable to most voters. We determine acceptability-distortion for a number of rules, including Plurality, Borda, k-Approval, Veto, Copeland, Ranked Pairs, the Schulze's method, and STV.

We consider the problem of selecting a fixed-size committee based on approval ballots. It is desirable to have a committee in which all voters are fairly represented. Aziz et al. (2015a; 2017) proposed an axiom called extended justified representation (EJR), which aims to capture this intuition; subsequently, Sanchez-Fernandez et al. (2017) proposed a weaker variant of this axiom called proportional justified representation (PJR). It was shown that it is coNP-complete to check whether a given committee provides EJR, and it was conjectured that it is hard to find a committee that provides EJR. In contrast, there are polynomial-time computable voting rules that output committees providing PJR, but the complexity of checking whether a given committee provides PJR was an open problem. In this paper, we answer open questions from prior work by showing that EJR and PJR have the same worst-case complexity: we provide two polynomial-time algorithms that output committees providing EJR, yet we show that it is coNP-complete to decide whether a given committee provides PJR. We complement the latter result by fixed-parameter tractability results.

We develop a model of multiwinner elections that combines performance-based measures of the quality of the committee (such as, e.g., Borda scores of the committee members) with diversity constraints. Specifically, we assume that the candidates have certain attributes (such as being a male or a female, being junior or senior, etc.) and the goal is to elect a committee that, on the one hand, has as high a score regarding a given performance measure, but that, on the other hand, meets certain requirements (e.g., of the form "at least 30% of the committee members are junior candidates and at least 40% are females"). We analyze the computational complexity of computing winning committees in this model, obtaining polynomial-time algorithms (exact and approximate) and NP-hardness results. We focus on several natural classes of voting rules and diversity constraints.

We study a generic framework that provides a unified view on two important classes of problems: (i) extensions of the k-median problem where clients are interested in having multiple facilities in their vicinity (e.g., due to the fact that, with some small probability, the closest facility might be malfunctioning and so might not be available for using), and (ii) finding winners according to some appealing multiwinner election rules, i.e., election system aimed for choosing representatives bodies, such as parliaments, based on preferences of a population of voters over individual candidates. Each problem in our framework is associated with a vector of weights: we show that the approximability of the problem depends on structural properties of these vectors. We specifically focus on the harmonic sequence of weights for which the objective function interpreted in a multiwinner election setup reflects to the well-known Proportional Approval Voting (PAV) rule. Our main result is that, due to the specific (harmonic) structure of weights, the problem allows constant factor approximation. This is surprising since the problem can be interpreted as a variant of the k-median problem where we do not assume that the connection costs satisfy the triangle inequality. The algorithm we propose is based on dependent rounding [Srinivasan, FOCS'01] applied to the solution of a natural LP-relaxation of the problem. The rounding process is well known to produce distributions over integral solutions satisfying Negative Correlation (NC), which is usually sufficient for the analysis of approximation guarantees offered by rounding procedures. In our analysis, however, we need to use the fact that the carefully implemented rounding process satisfies a stronger property, called Negative Association (NA), which allows us to apply standard concentration bounds for conditional random variables.

We investigate the possibility of strategic voting in approval-based multiwinner rules. In particular, we define three axiomatic properties that guarantee resilience to certain forms of strategic voting: independence of irrelevant alternatives (IIA), monotonicity, and SD-strategyproofness. In this paper, we systematically analyze multiwinner rules based on these axioms and provide a fine-grained picture of their resilience to strategic voting. Both our axiomatic and experimental analysis show that approval-based multiwinner rules are generally very susceptible to strategic voting---with one exception: multiwinner approval voting.

We thoroughly study a generalized version of the famous Stable Marriage problem, now based on multi-modal preference lists. The central twist herein is to allow each agent to rank its potentially matching counterparts based on more than one "evaluation mode" (e.g., more than one criterion); thus, each agent is equipped with multiple preference lists, each ranking the counterparts in a possibly different way. We introduce and study three natural concepts of stability, investigate their mutual relations and focus on computational complexity aspects with respect to computing stable matchings in these new scenarios. Mostly encountering computational hardness (NP-hardness), we can also spot few islands of tractability and make a surprising connection to the Graph Isomorphism problem.

This paper is an axiomatic study of consistent approval-based multi-winner rules, i.e., voting rules that select a fixed-size group of candidates based on approval ballots. We introduce the class of counting rules, provide an axiomatic characterization of this class and, in particular, show that counting rules are consistent. Building upon this result, we axiomatically characterize three important consistent multi-winner rules: Proportional Approval Voting, Multi-Winner Approval Voting and the Approval Chamberlin--Courant rule. Our results demonstrate the variety of multi-winner rules and illustrate three different, orthogonal principles that multi-winner voting rules may represent: individual excellence, diversity, and proportionality.

We establish a link between multiwinner elections and apportionment problems by showing how approval-based multiwinner election rules can be interpreted as methods of apportionment. We consider several multi-winner rules and observe that some, but not all, of them induce apportionment methods that are well established in the literature and in the actual practice of proportional representation. For instance, we show that Proportional Approval Voting induces the D'Hondt method and that Monroe's rule induces the largest remainder method. We also consider properties of apportionment methods and exhibit multiwinner rules that induce apportionment methods satisfying these properties.

We visualize aggregate outputs of popular multiwinner voting rules — SNTV, STV, Bloc, k-Borda, Monroe, Chamberlin–Courant, and PAV — for elections generated according to the two-dimensional Euclidean model. We consider three applications of multiwinner voting, namely, parliamentary elections, portfolio/movie selection, and shortlisting, and use our results to understand which of our rules seem to be best suited for each application. In particular, we show that STV (one of the few nontrivial rules used in real high-stake elections) exhibits excellent performance, whereas the Bloc rule (also often used in practice) performs poorly.

The goal of multi-winner elections is to choose a fixed-size committee based on voters’ preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the election winners. Recently, Aziz et al. proposed two axioms that aim to capture this idea: justified representation (JR) and its strengthening extended justified representation (EJR). In this paper, we extend the work of Aziz et al. in several directions. First, we answer an open question of Aziz et al., by showing that Reweighted Approval Voting satisfies JR for k = 3; 4; 5, but fails it for k >= 6. Second, we observe that EJR is incompatible with the Perfect Representation criterion, which is important for many applications of multi-winner voting, and propose a relaxation of EJR, which we call Proportional Justified Representation (PJR). PJR is more demanding than JR, but, unlike EJR, it is compatible with perfect representation, and a committee that provides PJR can be computed in polynomial time if the committee size divides the number of voters. Moreover, just like EJR, PJR can be used to characterize the classic PAV rule in the class of weighted PAV rules. On the other hand, we show that EJR provides stronger guarantees with respect to average voter satisfaction than PJR does.

We consider voting under metric preferences: both voters and candidates are associated with points in a metric space, and each voter prefers candidates that are closer to her to ones that are further away. In this setting, it is often desirable to select a candidate that minimizes the sum of distances to the voters. However, common voting rules operate on voters' preference rankings and therefore may be unable to identify the best candidate. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of a candidate selected by the rule and that of an optimal candidate. Anshelevich, Bhardwaj and Postl show that some popular rules such as Borda and Plurality do badly in this regard: their distortion scales linearly with the number of candidates. On the positive side, Anshelevich et al. identify a few voting rules whose distortion is bounded by a constant; however, these rules are rarely used in practice. In this paper, we analyze the distortion of two widely used (classes of) voting rules, namely, scoring rules and Single Transferable Vote (STV). We show that all scoring rules have super-constant distortion, answering a question that was left open by Anshelevich et al.; however, we identify a scoring rule whose distortion is asymptotically better than that of Plurality and Borda. For STV, we obtain an upper bound of O(log m), where m is the number of candidates, as well as a super-constant lower bound; thus, STV is a reasonable, though not a perfect rule from this perspective.

We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second one, local stability, is introduced in this paper, and focuses on voter representation. The goal of this paper is to explore these two notions, their implications on restricted domains, and the computational complexity of rules that are consistent with them.

The classical multiwinner rules are designed for particular purposes. For example, variants of k-Borda are used to find k best competitors in judging contests while the Chamberlin-Courant rule is used to select a diverse set of k products. These rules represent two extremes of the multiwinner world. At times, however, one might need to find an appropriate trade-off between these two extremes. We explore continuous transitions from k-Borda to Chamberlin-Courant and study intermediate rules.

We extend the principle of proportional representation to rankings: given approval preferences, we aim to generate aggregate rankings so that cohesive groups of voters are represented proportionally in each initial segment of the ranking. Such rankings are desirable in situations where initial segments of different lengths may be relevant, e.g., in recommender systems, for hiring decisions, or for the presentation of competing proposals on a liquid democracy platform. We define what it means for rankings to be proportional, provide bounds for well-known aggregation rules, and experimentally evaluate the performance of these rules.

We consider the problem of winner determination under Chamberlin--Courant's multiwinner voting rule with approval utilities. This problem is equivalent to the well-known NP-complete MaxCover problem and, so, the best polynomial-time approximation algorithm for it has approximation ratio 1 - 1/e. We show exponential-time/FPT approximation algorithms that, on one hand, achieve arbitrarily good approximation ratios and, on the other hand, have running times much better than known exact algorithms. We focus on the cases where the voters have to approve of at most/at least a given number of candidates.

We characterize the class of committee scoring rules that satisfy the fixed-majority criterion. In some sense, the committee scoring rules in this class are multiwinner analogues of the single-winner Plurality rule, which is uniquely characterized as the only single-winner scoring rule that satisfies the simple majority criterion. We find that, for most of the rules in our new class, the complexity of winner determination is high (i.e., the problem of computing the winners is NP-hard), but we also show some examples of polynomial-time winner determination procedures, exact and approximate.

We consider the following problem in which a given number of items has to be chosen from a predefined set. Each item is described by a vector of attributes and for each attribute there is a desired distribution that the selected set should fit. We look for a set that fits as much as possible the desired distributions on all attributes. Examples of applications include choosing members of a representative committee, where candidates are described by attributes such as sex, age and profession, and where we look for a committee that for each attribute offers a certain representation, i.e., a single committee that contains a certain number of young and old people, certain number of men and women, certain number of people with different professions, etc. With a single attribute the problem boils down to the apportionment problem for party-list proportional representation systems (in such case the value of the single attribute is the political affiliation of a candidate). We study some properties of the associated subset selection rules, and address their computation.

Summary P2P architecture is a viable option for enterprise backup. In contrast to dedicated backup servers, nowadays, a standard solution, making backups directly on organization's workstations should be cheaper as existing hardware is used, more efficient as there is no single bottleneck server, and more reliable as the machines can be geographically dispersed. We present an architecture of a P2P backup system that uses pairwise replication contracts between a data owner and a replicator. In contrast to a standard P2P storage system using directly a distributed hash table (DHT), the contracts allow our system to optimize replicas' placement depending on a specific optimization strategy and so to take advantage of the heterogeneity of the machines and the network. Such optimization is particularly appealing in the context of backup: replicas can be geographically dispersed, the load sent over the network can be minimized, or the optimization goal can be to minimize the backup/restore time. However, managing the contracts, keeping them consistent and adjusting them in response to dynamically changing environment is challenging. We built a scientific prototype and ran experiments on 150 workstations in our university's computer laboratories and, separately, on 50 PlanetLab nodes. We found out that the main factor affecting the performance of the system is the availability of the machines. Yet, our main conclusion is that it is possible to build an efficient and reliable backup system on highly unavailable machines, as our computers had just 13% average availability. Copyright © 2015 John Wiley & Sons, Ltd.

We consider the problem of winner determination under Chamberlin--Courant's multiwinner voting rule with approval utilities. This problem is equivalent to the well-known NP-complete MaxCover problem (i.e., a version of the SetCover problem where we aim to cover as many elements as possible) and, so, the best polynomial-time approximation algorithm for it has approximation ratio 1 - 1/e. We show exponential-time/FPT approximation algorithms that, on one hand, achieve arbitrarily good approximation ratios and, on the other hand, have running times much better than known exact algorithms. We focus on the cases where the voters have to approve of at most/at least a given number of candidates.

We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i.e., in our example we are to pick K movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.

In geographically-distributed systems, communication latencies are non-negligible. The perceived processing time of a request is thus composed of the time needed to route the request to the server and the true processing time. Once a request reaches a target server, the processing time depends on the total load of that server, this dependency is described by a load function. We consider a broad class of load functions, we just require that they are convex and two times differentiable. In particular our model can be applied to heterogeneous systems in which every server has a different load function. We present optimization centralized and a decentralized algorithms for load balancing. We prove bounds on the algorithms' convergence. To the best of our knowledge these bounds were not known even for the special cases studied previously (queuing theory and batches of requests). Both algorithms are any-time and self-stabilizing algorithms.

We investigate elections that are simultaneously single-peaked and single-crossing (SPSC). We show that the domain of 1-dimensional Euclidean elections (where voters and candidates are points on the real line, and each voter prefers the candidates that are close to her to the ones that are further away) is a proper subdomain of the SPSC domain, by constructing an election that is single-peaked and single-crossing, but not 1-Euclidean. We then establish a connection between narcissistic elections (where each candidate is ranked first by at least one voter), single-peaked elections and single-crossing elections, by showing that an election is SPSC if and only if it can be obtained from a narcissistic single-crossing election by deleting voters. We show two applications of our characterization.

We consider a multi-organizational system in which each organization contributes processors to the global pool but also jobs to be processed on the common resources. The fairness of the scheduling algorithm is essential for the stability and even for the existence of such systems (as organizations may refuse to join an unfair system).

Beyond handling user reads and writes, storage systems execute multiple background tasks of various types, such as reconstruction of missing parity data and defragmentation. The resources of the system must be divided between user loads and internal tasks using a specific policy.