Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSelecting Matchings via Multiwinner Voting: How Structure Defeats a Large Candidate Space
105
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a set of agents with approval preferences over each other, we study the task of finding $k$ matchings fairly representing everyones preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of all possible matchings and agents preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmen) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the general multiwinner setting. Assuming that approvals are symmetric, we show that proportional approval voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and its sequential variant (seq-PAV), which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our positive computational results extend to other types of compactly representable elections with an exponential candidate space.
rate research
Read More
Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than $k$ candidates. In this paper, we study such groups -- known as $n/k$-justifying groups -- both theoretically and empirically. First, we show that under the impartial culture model, $n/k$-justifying groups of size less than $k/2$ are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small $n/k$-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small $n/k$-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.
We study single-candidate voting embedded in a metric space, where both voters and candidates are points in the space, and the distances between voters and candidates specify the voters preferences over candidates. In the voting, each voter is asked to submit her favorite candidate. Given the collection of favorite candidates, a mechanism for eliminating the least popular candidate finds a committee containing all candidates but the one to be eliminated. Each committee is associated with a social value that is the sum of the costs (utilities) it imposes (provides) to the voters. We design mechanisms for finding a committee to optimize the social value. We measure the quality of a mechanism by its distortion, defined as the worst-case ratio between the social value of the committee found by the mechanism and the optimal one. We establish new upper and lower bounds on the distortion of mechanisms in this single-candidate voting, for both general metrics and well-motivated special cases.
The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) score of at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee, and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for $Theta_{2}^{P}$. We also demonstrate efficient algorithms for the second problem when the input consists of single-peaked rankings. Our contribution fills an essential gap in the literature for these important multi-winner rules.
We define the notion of Bayes correlated Wardrop equilibrium for general nonatomic games with anonymous players and incomplete information. Bayes correlated Wardrop equilibria describe the set of equilibrium outcomes when a mediator, such as a traffic information system, provides information to the players. We relate this notion to Bayes Wardrop equilibrium. Then, we provide conditions -- existence of a convex potential and complete information -- under which mediation does not improve equilibrium outcomes. We then study full implementation and, finally, information design in anonymous games with a finite set of players, when the number of players tends to infinity.
Many economic-theoretic models incorporate finiteness assumptions that, while introduced for simplicity, play a real role in the analysis. Such assumptions introduce a conceptual problem, as results that rely on finiteness are often implicitly nonrobust; for example, they may depend upon edge effects or artificial boundary conditions. Here, we present a unified method that enables us to remove finiteness assumptions, such as those on market sizes, time horizons, and datasets. We then apply our approach to a variety of matching, exchange economy, and revealed preference settings. The key to our approach is Logical Compactness, a core result from Propositional Logic. Building on Logical Compactness, in a matching setting, we reprove large-market existence results implied by Fleiners analysis, and (newly) prove both the strategy-proofness of the man-optimal stable mechanism in infinite markets and an infinite-market version of Nguyen and Vohras existence result for near-feasible stable matchings with couples. In a trading-network setting, we prove that the Hatfield et al. result on existence of Walrasian equilibria extends to infinite markets. In a dynamic matching setting, we prove that Pereyras existence result for dynamic two-sided matching markets extends to a doubly infinite time horizon. Finally, beyond existence and characterization of solutions, in a revealed-preference setting we reprove Renys infinite-data version of Afriats theorem and (newly) prove an infinite-data version of McFadden and Richters characterization of rationalizable stochastic datasets.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
