Finding Preference Profiles of Condorcet Dimension $k$ via SAT
Condorcet winning sets are a set-valued generalization of the well-known concept of a Condorcet winner. As supersets of Condorcet winning sets are always Condorcet winning sets themselves, an interesting property of preference profiles is the size of the smallest Condorcet winning set they admit. This smallest size is called the Condorcet dimension of a preference profile. Since little is known about profiles that have a certain Condorcet dimension, we show in this paper how the problem of finding a preference profile that has a given Condorcet dimension can be encoded as a satisfiability problem and solved by a SAT solver. Initial results include a minimal example of a preference profile of Condorcet dimension 3, improving previously known examples both in terms of the number of agents as well as alternatives. Due to the high complexity of such problems it remains open whether a preference profile of Condorcet dimension 4 exists.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Soft Condorcet Optimization for Ranking of General Agents
Driving progress of AI models and agents requires comparing their performance on standardized benchmarks; for general agents, individual performances must be aggregated across a potentially wide variety of different task…
Statistical Impossibility and Possibility of Aligning LLMs with Human Preferences: From Condorcet Paradox to Nash Equilibrium
Aligning large language models (LLMs) with diverse human preferences is critical for ensuring fairness and informed outcomes when deploying these models for decision-making. In this paper, we seek to uncover fundamental …
FairnessPreference fusion and Condorcet's Paradox under uncertainty
Facing an unknown situation, a person may not be able to firmly elicit his/her preferences over different alternatives, so he/she tends to express uncertain preferences. Given a community of different persons expressing …
Local Diversity of Condorcet Domains
Several of the classical results in social choice theory demonstrate that in order for many voting systems to be well-behaved the set domain of individual preferences must satisfy some kind of restriction, such as being …
DiversityStrategy-proof aggregation rules in median semilattices with applications to preference aggregation
Two characterizations of the whole class of strategy-proof aggregation rules on rich domains of locally unimodal preorders in finite median join-semilattices are provided. In particular, it is shown that such a class con…