IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Login to save this paper or follow this series

Approximate Judgement Aggregation

In this paper we analyze judgement aggregation problems in which a group of agents independently votes on a set of complex propositions that has some interdependency constraint between them (e.g., transitivity when describing preferences). We consider the issue of judgement aggregation from the perspective of approximation. That is, we generalize the previous results by studying approximate judgement aggregation. We relax the main two constraints assumed in the current literature, Consistency and Independence and consider mechanisms that only approximately satisfy these constraints, that is, satisfy them up to a small portion of the inputs. The main question we raise is whether the relaxation of these notions significantly alters the class of satisfying aggregation mechanisms. The recent works for preference aggregation of Kalai, Mossel, and Keller fit into this framework. The main result of this paper is that, as in the case of preference aggregation, in the case of a subclass of a natural class of aggregation problems termed `truth-functional agendas', the set of satisfying aggregation mechanisms does not extend non-trivially when relaxing the constraints. Our proof techniques involve Boolean Fourier transform and analysis of voter influences for voting protocols. The question we raise for Approximate Aggregation can be stated in terms of Property Testing. For instance, as a corollary from our result we get a generalization of the classic result for property testing of linearity of Boolean functions.

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

File URL: http://ratio.huji.ac.il/sites/default/files/publications/dp574R.pdf
File Function: Revised version
Download Restriction: no

File URL: http://link.springer.com/article/10.1007%2Fs10472-013-9358-6
File Function: Published version
Download Restriction: no

Paper provided by The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem in its series Discussion Paper Series with number dp574r.

as
in new window

Length: 27 pages
Date of creation: 05 Jun 2011
Date of revision: 11 2011
Publication status: Published in WINE 2011. Forthcoming in Annals of Mathematics & Artificial Intelligence - Special issue is on algorithms, approximation, and empirical studies in behavorial and computational social choice
Handle: RePEc:huj:dispap:dp574r
Contact details of provider: Postal: Feldman Building - Givat Ram - 91904 Jerusalem
Phone: +972-2-6584135
Fax: +972-2-6513681
Web page: http://www.ratio.huji.ac.il/
Email:


More information through EDIRC

No references listed on IDEAS
You can help add them by filling out this form.

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

When requesting a correction, please mention this item's handle: RePEc:huj:dispap:dp574r. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ilan Nehama)

If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

If references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.

This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.