Metric Distortion under Group-Fair Objectives
arxiv(2024)
摘要
We consider a voting problem in which a set of agents have metric preferences
over a set of alternatives, and are also partitioned into disjoint groups.
Given information about the preferences of the agents and their groups, our
goal is to decide an alternative to approximately minimize an objective
function that takes the groups of agents into account. We consider two natural
group-fair objectives known as Max-of-Avg and Avg-of-Max which are different
combinations of the max and the average cost in and out of the groups. We show
tight bounds on the best possible distortion that can be achieved by various
classes of mechanisms depending on the amount of information they have access
to. In particular, we consider group-oblivious full-information mechanisms that
do not know the groups but have access to the exact distances between agents
and alternatives in the metric space, group-oblivious ordinal-information
mechanisms that again do not know the groups but are given the ordinal
preferences of the agents, and group-aware mechanisms that have full knowledge
of the structure of the agent groups and also ordinal information about the
metric space.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要