NDLI: Of the People: Voting Is More Effective with Representative Candidates

Please wait, while we are loading the content...

Fair Algorithms for Machine Learning

Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison

The Double Clinching Auction for Wagering

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm

A "Quantal Regret" Method for Structural Econometrics in Repeated Games

The Scope of Sequential Screening with Ex Post Participation Constraints

Accounting for Strategic Response in an Agent-Based Model of Financial Regulation

Stable Secretaries

Making Right Decisions Based on Wrong Opinions

A Simple and Approximately Optimal Mechanism for a Buyer with Complements: Abstract

Optimal Signaling Mechanisms in Unobservable Queues with Strategic Customers

Combinatorial Cost Sharing

Makespan Minimization via Posted Prices

Convex Program Duality, Fisher Markets, and Nash Social Welfare

Online Auctions and Multi-scale Online Learning

The Tragedy of your Upstairs Neighbors: Is the Negative Externality of Airbnb Internalized?

Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness

Planning with Multiple Biases

Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms

Nash Social Welfare Approximation for Strategic Agents

Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks

Stability, Strategy-Proofness, and Cumulative Offer Mechanisms

Simple Approximate Equilibria in Games with Many Players

Deferred-Acceptance Auctions for Multiple Levels of Service

Forecast Aggregation

Facilitating the Search for Partners on Matching Platforms: Restricting Agent Actions

The Theory is Predictive, but is it Complete?: An Application to Human Perception of Randomness

Dynamic Mechanisms with Martingale Utilities

Empirical Mechanism Design for Optimizing Clearing Interval in Frequent Call Markets

Computing Equilibrium in Matching Markets

Voting in the Limelight

Price Doubling and Item Halving: Robust Revenue Guarantees for Item Pricing

Information Sharing and Privacy in Networks

Truth and Regret in Online Scheduling

Controlled Dynamic Fair Division

Joint Pricing and Inventory Management with Strategic Customers

Interacting User Generated Content Technologies: How Q&As Affect Ratings & Reviews

From Monetary to Non-Monetary Mechanism Design via Artificial Currencies

Multidimensional Binary Search for Contextual Decision-Making

Approximately Efficient Two-Sided Combinatorial Auctions

Fair Public Decision Making

Stable Matching with Proportionality Constraints

Theoretical and Practical Advances on Smoothing for Extensive-Form Games

The Optimal Mechanism for Selling to a Budget Constrained Buyer: The General Case

Machine-Learning Aided Peer Prediction

Matching while Learning

Comparison-based Choices

Repeated Sales with Multiple Strategic Buyers

Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation

Communication Requirements and Informative Signaling in Matching Markets

Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties

The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders

Algorithmic Persuasion with No Externalities

Cost-Sharing Methods for Scheduling Games under Uncertainty

A Lower Bound for Equitable Cake Cutting

Pricing and Optimization in Shared Vehicle Systems: An Approximation Framework

Learning in the Repeated Secretary Problem

Gibbard-Satterthwaite Success Stories and Obvious Strategyproofness

Bifurcation Mechanism Design - from Optimal Flat Taxes to Improved Cancer Treatments

Learning in Repeated Auctions with Budgets: Regret Minimization and Equilibrium

Approximation Algorithms for Maximin Fair Division

Making it Safe to Use Centralized Markets: Epsilon - Dominant Individual Rationality and Applications to Market Design

A Network Game of Dynamic Traffic

Optimal Multi-Unit Mechanisms with Private Demands

Peer Prediction with Heterogeneous Users

Redesigning the Israeli Psychology Master's Match

Combinatorial Auctions Do Need Modest Interaction

Posted Price Mechanisms for a Random Stream of Customers

Surge Pricing Solves the Wild Goose Chase

Complementary Inputs and the Existence of Stable Outcomes in Large Trading Networks

Of the People: Voting Is More Effective with Representative Candidates

Assortment Optimisation under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments

Fairness Incentives for Myopic Agents

Multidimensional Dynamic Pricing for Welfare Maximization

Diffusion in Networks and the Unexpected Virtue of Burstiness

How (Not) to Allocate Affordable Housing

A Polynomial Time Algorithm for Spatio-Temporal Security Games

Of the People: Voting Is More Effective with Representative Candidates

Content Provider	ACM Digital Library
Author	Cheng, Yu Kempe, David Dughmi, Shaddin
Abstract	In light of the classic impossibility results of Arrow and Gibbard and Satterthwaite regarding voting with ordinal rules, there has been recent interest in characterizing how well common voting rules approximate the social optimum. In order to quantify the quality of approximation, it is natural to consider the candidates and voters as embedded within a common metric space, and to ask how much further the chosen candidate is from the population as compared to the socially optimal one. We use this metric preference model to explore a fundamental and timely question: does the social welfare of a population improve when candidates are representative of the population? If so, then by how much, and how does the answer depend on the complexity of the metric space? We restrict attention to the most fundamental and common social choice setting: a population of voters, two independently drawn candidates, and a majority rule election. When candidates are not representative of the population, it is known that the candidate selected by the majority rule can be thrice as far from the population as the socially optimal one; this holds even when the underlying metric is a line. We examine how this ratio improves when candidates are drawn independently from the population of voters. Our results are two-fold: When the metric is a line, the ratio improves from 3 to 4-2 √2}, roughly 1.1716; this bound is tight. When the metric is arbitrary, we show a lower bound of 1.5 and a constant upper bound strictly better than 2 on the approximation ratio of the majority rule. The positive result depends in part on the assumption that candidates are independent and identically distributed. However, we show that independence alone is not enough to achieve the upper bound: even when candidates are drawn independently, if the population of candidates can be different from the voters, then an upper bound of 2 on the approximation is tight. Thus, we show a constant gap between representative and non-representative candidates.
Starting Page	305
Ending Page	322
Page Count	18
File Format	PDF
ISBN	9781450345279
DOI	10.1145/3033274.3085155
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-06-20
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Social choice Distortion Metric preferences Majority voting
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in