Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Computation of Fully Proportional Representation
108
0
0.0
(
0
)
Added by
Nadja Betzler
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the sum of misrepresentations is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these minimax
rate research
Read More
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. (2015a;2017) 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 $kge 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 study the complexity of determining a winning committee under the Chamberlin--Courant voting rule when voters preferences are single-crossing on a line, or, more generally, on a median graph (this class of graphs includes, e.g., trees and grids). For the line, Skowron et al. (2015) describe an $O(n^2mk)$ algorithm (where $n$, $m$, $k$ are the number of voters, the number of candidates and the committee size, respectively); we show that a simple tweak improves the time complexity to $O(nmk)$. We then improve this bound for $k=Omega(log n)$ by reducing our problem to the $k$-link path problem for DAGs with concave Monge weights, obtaining a $nm2^{Oleft(sqrt{log kloglog n}right)}$ algorithm for the general case and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater, Puppe and Slinko (2015), and develop a $O(nmk)$ algorithm for this case as well. For grids, we formulate a conjecture about the structure of optimal solutions, and describe a polynomial-time algorithm that finds a winning committee if this conjecture is true; we also explain how to convert this algorithm into a bicriterial approximation algorithm whose correctness does not depend on the conjecture.
In this paper, we introduce a game that allows one to assess the potential loss of efficiency induced by a decentralized control or local management of a global epidemic. Each player typically represents a region or a country which is assumed to choose its control action to implement a tradeoff between socioeconomic aspects and the health aspect. We conduct the Nash equilibrium analysis of this game. Since the analysis is not trivial in general, sufficient conditions for existence and uniqueness are provided. Then we quantify through numerical results the loss induced by decentralization, measured in terms of price of anarchy (PoA) and price of connectedness (PoC). These results allow one to clearly identify scenarios where decentralization is acceptable or not regarding to the retained global efficiency measures.
We study strategic games on weighted directed graphs, where the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy augmented by a fixed non-negative bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. Prior work shows that the problem of determining the existence of a pure Nash equilibrium for these games is NP-complete already for graphs with all weights equal to one and no bonuses. However, for several classes of graphs (e.g. DAGs and cliques) pure Nash equilibria or even strong equilibria always exist and can be found by simply following a particular improvement or coalition-improvement path, respectively. In this paper we identify several natural classes of graphs for which a finite improvement or coalition-improvement path of polynomial length always exists, and, as a consequence, a Nash equilibrium or strong equilibrium in them can be found in polynomial time. We also argue that these results are optimal in the sense that in natural generalisations of these classes of graphs, a pure Nash equilibrium may not even exist.
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decision maker makes an immediate and irrevocable decision whether to accept each award upon its arrival. The requirement to make immediate decisions arises in many cases due to an implicit assumption regarding competition. Namely, if the decision maker does not take the offered award immediately, it will be taken by someone else. The novelty in this paper is in introducing a multi-agent model in which the competition is endogenous. In our model, multiple agents compete over the arriving awards, but the decisions need not be immediate; instead, agents may select previous awards as long as they are available (i.e., not taken by another agent). If an award is selected by multiple agents, ties are broken either randomly or according to a global ranking. This induces a multi-agent game in which the time of selection is not enforced by the rules of the games, rather it is an important component of the agents strategy. We study the structure and performance of equilibria in this game. For random tie breaking, we characterize the equilibria of the game, and show that the expected social welfare in equilibrium is nearly optimal, despite competition among the agents. For ranked tie breaking, we give a full characterization of equilibria in the 3-agent game, and show that as the number of agents grows, the winning probability of every agent under non-immediate selections approaches her winning probability under immediate selections.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
