We study the complexity of (approximate) winner determination under the Monroe and Chamberlin--Courant multiwinner voting rules, which determine the set of representatives by optimizing the total (dis)satisfaction of the voters with their representatives. The total (dis)satisfaction is calculated either as the sum of individual (dis)satisfactions (the utilitarian case) or as the (dis)satisfaction of the worst off voter (the egalitarian case). We provide good approximation algorithms for the satisfaction-based utilitarian versions of the Monroe and Chamberlin--Courant rules, and inapproximability results for the dissatisfaction-based utilitarian versions of them and also for all egalitarian cases. Our algorithms are applicable and particularly appealing when voters submit truncated ballots. We provide experimental evaluation of the algorithms both on real-life preference-aggregation data and on synthetic data. These experiments show that our simple and fast algorithms can in many cases find near-perfect solutions.
In this paper we take the view that the Monroe and Chamberlin--Courant rules are special cases of the following resource allocation problem. The alternatives are shareable resources, each with a certain capacity defined as the maximal number of agents that may share this resource. Each agent has preferences over the resources and is interested in getting exactly one. The goal is to select a predetermined number @math of resources and to find an optimal allocation of these resources (see for details). This provides a unified framework for the two rules and reveals the connection of proportional representation problem to other resource allocation problems. In particular, it closely resembles multi-unit resource allocation with single-unit demand [Chapter 11] ley-sho:b:multiagent-systems (see also the work of @cite_38 for a survey of the most fundamental issues in the multiagent resource allocation theory) and resource allocation with sharable indivisible goods @cite_38 @cite_42 . Below, we point out other connections of the Monroe and Chamberlin--Courant rules to several other problems.
@cite_38 @cite_42
1521758236 1496970431
The allocation of resources within a system of autonomous agents, that not only havepreferences over alternative allocations of resources but also actively participate in com-puting an allocation, is an exciting area of research at the interface of Computer Scienceand Economics. This paper is a survey of some of the most salient issues in MultiagentResource Allocation. In particular, we review various languages to represent the pref-erences of agents over alternative allocations of resources as well as different measuresof social welfare to assess the overall quality of an allocation. We also discuss pertinentissues regarding allocation procedures and present important complexity results. Ourpresentation of theoretical issues is complemented by a discussion of software packagesfor the simulation of agent-based market places. We also introduce four major applica-tion areas for Multiagent Resource Allocation, namely industrial procurement, sharingof satellite resources, manufacturing control, and grid computing We study a particular multiagent resource allocation problem with indivisible, but sharable resources. In our model, the utility of an agent for using a bundle of resources is the difference between the valuation of that bundle and a congestion cost (or delay), a figure formed by adding up the individual congestion costs of each resource in the bundle. The valuation and the delay can be agent-dependent. When the agents that share a resource also share the resource's control, the current users of a resource will require some compensation when a new agent wants to use the resource. We study the existence of distributed protocols that lead to a social optimum. Depending on constraints on the valuation functions (mainly modularity), on the delay functions (e.g., convexity), and the structural complexity of the deals between agents, we prove either the existence of some sequences of deals or the convergence of all sequences of deals to a social optimum. When the agents do not have joint control over the resources (i.e., they can use any resource they want), we study the existence of pure Nash equilibria. We provide results for modular valuation functions and relate them to results from the literature on congestion games.