A distributed social choice protocol for combinatorial domains

Minyi Li, Quoc Bao Vo, Ryszard Kowalczyk

Research output: Contribution to journalArticleResearchpeer-review

Abstract

In this paper, we study the problem of collective decision-making over combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are not preferentially independent. Due to the large alternative space, most common rules for social choice cannot be directly applied to compute a winner. In this paper, we introduce a distributed protocol for collective decision-making in combinatorial domains, which enjoys the following desirable properties: (i) the final decision chosen is guaranteed to be a Smith member; (ii) it enables distributed decision-making and works under incomplete information settings, i.e., the agents are not required to reveal their preferences explicitly; (iii) it significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons; (iv) it is sufficiently general and does not restrict the choice of preference representation languages.
Original languageEnglish
Pages (from-to)453-481
Number of pages29
JournalJournal of Heuristics
Volume20
Issue number4
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Negotiation
  • Combinatorial domains
  • Structural preferences
  • CP-nets
  • Best possible agreement

Cite this

Li, Minyi ; Vo, Quoc Bao ; Kowalczyk, Ryszard. / A distributed social choice protocol for combinatorial domains. In: Journal of Heuristics. 2014 ; Vol. 20, No. 4. pp. 453-481.
@article{015c0e9ebda9474da7b1bf507be380cd,
title = "A distributed social choice protocol for combinatorial domains",
abstract = "In this paper, we study the problem of collective decision-making over combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are not preferentially independent. Due to the large alternative space, most common rules for social choice cannot be directly applied to compute a winner. In this paper, we introduce a distributed protocol for collective decision-making in combinatorial domains, which enjoys the following desirable properties: (i) the final decision chosen is guaranteed to be a Smith member; (ii) it enables distributed decision-making and works under incomplete information settings, i.e., the agents are not required to reveal their preferences explicitly; (iii) it significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons; (iv) it is sufficiently general and does not restrict the choice of preference representation languages.",
keywords = "Negotiation, Combinatorial domains, Structural preferences, CP-nets, Best possible agreement",
author = "Minyi Li and Vo, {Quoc Bao} and Ryszard Kowalczyk",
year = "2014",
doi = "10.1007/s10732-014-9246-1",
language = "English",
volume = "20",
pages = "453--481",
journal = "Journal of Heuristics",
issn = "1381-1231",
publisher = "Springer-Verlag London Ltd.",
number = "4",

}

A distributed social choice protocol for combinatorial domains. / Li, Minyi; Vo, Quoc Bao; Kowalczyk, Ryszard.

In: Journal of Heuristics, Vol. 20, No. 4, 2014, p. 453-481.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A distributed social choice protocol for combinatorial domains

AU - Li, Minyi

AU - Vo, Quoc Bao

AU - Kowalczyk, Ryszard

PY - 2014

Y1 - 2014

N2 - In this paper, we study the problem of collective decision-making over combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are not preferentially independent. Due to the large alternative space, most common rules for social choice cannot be directly applied to compute a winner. In this paper, we introduce a distributed protocol for collective decision-making in combinatorial domains, which enjoys the following desirable properties: (i) the final decision chosen is guaranteed to be a Smith member; (ii) it enables distributed decision-making and works under incomplete information settings, i.e., the agents are not required to reveal their preferences explicitly; (iii) it significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons; (iv) it is sufficiently general and does not restrict the choice of preference representation languages.

AB - In this paper, we study the problem of collective decision-making over combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are not preferentially independent. Due to the large alternative space, most common rules for social choice cannot be directly applied to compute a winner. In this paper, we introduce a distributed protocol for collective decision-making in combinatorial domains, which enjoys the following desirable properties: (i) the final decision chosen is guaranteed to be a Smith member; (ii) it enables distributed decision-making and works under incomplete information settings, i.e., the agents are not required to reveal their preferences explicitly; (iii) it significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons; (iv) it is sufficiently general and does not restrict the choice of preference representation languages.

KW - Negotiation

KW - Combinatorial domains

KW - Structural preferences

KW - CP-nets

KW - Best possible agreement

U2 - 10.1007/s10732-014-9246-1

DO - 10.1007/s10732-014-9246-1

M3 - Article

VL - 20

SP - 453

EP - 481

JO - Journal of Heuristics

JF - Journal of Heuristics

SN - 1381-1231

IS - 4

ER -