Social choice - Revision history

Lê Nguyên Hoang: /* Harsanyi's Utilitarian Theorem */

2020-02-23T09:34:50Z

Harsanyi's Utilitarian Theorem

Lê Nguyên Hoang: /* Harsanyi's Utilitarian Theorem */

2020-02-23T09:34:03Z

Harsanyi's Utilitarian Theorem

Lê Nguyên Hoang: /* Harsanyi's Utilitarian Theorem */

2020-02-23T09:32:50Z

Harsanyi's Utilitarian Theorem

Lê Nguyên Hoang: /* Harsanyi's Utilitarian Theorem */

2020-02-22T22:49:05Z

Harsanyi's Utilitarian Theorem

Lê Nguyên Hoang at 22:48, 22 February 2020

2020-02-22T22:48:47Z

Lê Nguyên Hoang at 22:22, 22 February 2020

2020-02-22T22:22:14Z

Lê Nguyên Hoang: /* Applications to AI Ethics */

2020-02-11T16:55:36Z

Applications to AI Ethics

Lê Nguyên Hoang: /* Bounds for limited communication complexity */

2020-01-26T16:07:24Z

Bounds for limited communication complexity

Lê Nguyên Hoang: Created page with "Social choice is the study of how to elicit, aggregate and explain human preferences for collective decision-making. This is critical to AI ethics, as we will need to decide c..."

2020-01-20T21:32:58Z

Created page with "Social choice is the study of how to elicit, aggregate and explain human preferences for collective decision-making. This is critical to AI ethics, as we will need to decide c..."

New page

Social choice is the study of how to elicit, aggregate and explain human preferences for collective decision-making. This is critical to AI ethics, as we will need to decide collectively on which ethics an AI will follow. For instance, what video should be recommended by the YouTube algorithm when a user queries "Trump", "vaccine" or "social justice"?

== Background ==

Social choice theory arguably started with a remarkable memoire by Condorcet [http://classiques.uqac.ca/classiques/condorcet/Essai_application_discours_preliminaire/discours_preliminaire.pdf Condorcet][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=Essai+sur+l%27application+de+l%27analyse+%C3%A0+la+probabilit%C3%A9+des+d%C3%A9cisions+rendues+%C3%A0+la+pluralit%C3%A9+des+voix.+1785&btnG= 1785]. He argued that if one alternative is preferred to any other alternative by a majority then it should be selected. This is the [https://en.wikipedia.org/wiki/Condorcet_criterion Condorcet principle] (see [https://www.youtube.com/watch?v=hI89r4LqaCc MrPhi17aFR], [https://www.youtube.com/watch?v=ZZb4TjvupkI MrPhi17bFR]).

Unfortunately, social choice theory is plagued with impossibility results, like the Condorcet paradox ([https://www.youtube.com/watch?v=HoAnYQZrNrQ PBSInfinite17], [https://www.youtube.com/watch?v=v8-2YdUqQqM MicMaths15FR]), Arrow's impossibility theorem ([https://s3.amazonaws.com/academia.edu.documents/40888103/arrow.pdf?response-content-disposition=inline%3B%20filename%3DArrow.pdf&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Credential=AKIAIWOWYYGZ2Y53UL3A%2F20200118%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Date=20200118T214628Z&X-Amz-Expires=3600&X-Amz-SignedHeaders=host&X-Amz-Signature=283c657c6dc5c2c225f77e14996a77846974b6dd3a2008f4e299131c6255fd75 Arrow][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=A+Difficulty+in+the+Concept+of+Social+Welfare&btnG= 50], [https://www.youtube.com/watch?v=AhVR7gFMKNg PBSInfinite17], [https://www.youtube.com/watch?v=VNcj7-XUhoc S4A17bFR]) and the Gibbard-Satterthwaite theorem ([https://www.youtube.com/watch?v=m5crte26fiw Wandida17], [https://www.youtube.com/watch?v=VNcj7-XUhoc S4A17bFR]). Different voting systems yield different winners ([https://www.youtube.com/watch?v=vfTJ4vmIsO4 StatChat16FR], [https://www.youtube.com/watch?v=fBYCoPAmpr4&t=371s S4A17aFR]).

Today's most convincing social choice mechanisms are probably the [https://en.wikipedia.org/wiki/Approval_voting approval voting] ([https://dblp.org/rec/bibtex/books/daglib/0017739 BramsFishburnBook07], [https://www.youtube.com/watch?v=orybDrUj4vA CGPGrey]), [https://en.wikipedia.org/wiki/Majority_judgment majority judgment] ([https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=majority+judgment+laraki+balinski&btnG= BalinksiLarakiBook11], [https://www.youtube.com/watch?v=ZoGH7d51bvc ScienceÉtonnante16FR], [https://www.youtube.com/watch?v=_MAo8pUl0U4 S4A17cFR]) and the randomized Condorcet voting system ([https://dspace.mit.edu/bitstream/handle/1721.1/107673/355_2017_1031_ReferencePDF.pdf?sequence=1&isAllowed=y Hoang][https://dblp.org/rec/bibtex/journals/scw/Hoang17 17], [https://www.youtube.com/watch?v=wKimU8jy2a8 S4A17dFR], [https://www.youtube.com/watch?v=vAdGZkXhlNM S4A17eFR]).

== The (Huge) Flaw of Classical Social Choice ==

Unfortunately, such approaches are limited because they can only handle a reasonable amount of alternatives. If we are to design AI ethics collectively, we need to choose a code (or, say, guidelines or texts of laws). Yet there are combinatorially many such codes! If we consider 1,000-line codes, this would represent ~210,000 alternatives. Classical voting systems won't do the trick.

Now, there are already lots of results in social choice for structured combinatorial sets of alternatives, mostly derived from auction theory ([https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_mechanism VCG mechanism] [https://dblp.org/rec/bibtex/books/cu/NRTV2007 NRTV07] [https://www.youtube.com/watch?v=qruxfBdYTh8 S4A17fFR], Myerson's auction [https://dblp.org/rec/bibtex/journals/mor/Myerson81 Myerson81] [https://www.youtube.com/watch?v=FjP5JMUVXxw S4A17gFR], Gale-Shapley [https://dblp.org/rec/bibtex/journals/tamm/GaleS13 GaleShapley62] [https://www.youtube.com/watch?v=Qcv1IqHWAzg Numberphile14] [https://www.youtube.com/watch?v=oHYcOXi06uY S4A17hFR]...). Most impressively, in a series of papers [https://dblp.org/rec/bibtex/journals/sigecom/CaiDW11 CDW11], [https://dblp.org/rec/bibtex/conf/stoc/CaiDW12 CDW12a], [https://dblp.org/rec/bibtex/conf/focs/CaiDW12 CDW12b], [https://dblp.org/rec/bibtex/conf/soda/CaiDW13 CDW13a] and [https://dblp.org/rec/bibtex/conf/focs/CaiDW13 CDW13b], Cai, [https://en.wikipedia.org/wiki/Constantinos_Daskalakis Daskalakis] and Weinberg proved that the polynomial tractability of a Bayesian social choice approximation problem (i.e. with incentive-compatibility constraints) is equivalent to that of the full-information problem with an additional social welfare term to be optimized (see [https://www.youtube.com/watch?v=qruxfBdYTh8 S4A17fFR]).

However, we surely have to also tackle the case of unstructured combinatorial sets of alternatives (also, polytime may be too slow in practice).

== Bounds for limited communication complexity ==

A fascinating result by [http://papers.nips.cc/paper/8939-efficient-and-thrifty-voting-by-any-means-necessary MPSW19] shows that the worst-case lost of social welfare due to polynomial communication complexity (voters communicate at most log(#alternatives) bits) is unbounded (#alternatives2 for deterministic elicitation+voting, #alternatives for randomized).

There are caveats though. For one thing, this is a worst-case analysis. But human preferences may be more structured. Also, priors can be invoked. Plus, authors assumed that the same elicitation was applied to all voters, which is clearly suboptimal. A lot more research on the communication-complexity versus social-welfare tradeoff is definitely desired. This is exciting!

== Applications to AI Ethics ==

It has been argued to be critical to solve the problem of AI ethics ([https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12457/12204 GRTVW][https://dblp.org/rec/bibtex/conf/aaai/GreeneRTVW16 16],[http://isaim2018.cs.virginia.edu/papers/ISAIM2018_Ethics_Conitzer_etal.pdf CSBDK][https://dblp.org/rec/bibtex/conf/isaim/ConitzerSBD018 17]). In brief, we are unlikely to agree on what ethics to program. However, we might be able to agree on how to agree on some ethics to program even though we disagree. The trick to implement some (virtual) democratic voting on moral preferences.

Interestingly, ideas along these lines have already been developed for the cases of autonomous car dilemmas [https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17052/15857 NGAD+][https://dblp.org/rec/bibtex/conf/aaai/NoothigattuGADR18 18] [https://www.youtube.com/watch?v=Y6jfGZXubq0 UpAndAtom18], kidney transplant [https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17384/15863 FBSDC][https://dblp.org/rec/bibtex/conf/aaai/FreedmanBSDC18 18] and food donation (called WeBuildAI [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=2ahUKEwj4y5-ggu3mAhXB2qQKHT6GDZ4QFjACegQIARAC&url=https%3A%2F%2Fwww.cs.cmu.edu%2F~akahng%2Fpapers%2Fwebuildai.pdf&usg=AOvVaw2BknquyvgNufy-JlCoPj_G LKKK+][https://dblp.org/rec/bibtex/journals/pacmhci/LeeKKKYCSNLPP19 19]).

Note that in all such applications, the set of alternatives is combinatorially large. The trick to perform voting with limited elicitation from voters is to collect binary-choice-based preferences, and to then extrapolate preferences for other cases using machine learning (with some inductive bias). Another way to interpret this is to consider that voters get substituted by digital surrogates, whose task is to answer just as the voters would. This is kind of like representative democracy, where voters are replaced by their representatives. But machine learning can allow individual representatives through customized surrogates!

To build trust in the surrogate, WeBuildAI proposes to voters to test their surrogates, and to replace it, if needs be, by some computational model of their owns. They show that such interactions build trust from voters. They also propose some [[interpretability]] framework, where voters are given the implications of the vote of their surrogates.

Now what Lê can't wait for, is for all such frameworks to be applied to problems that really matter, because they influence billions of people. Yes, Lê is (again!) talking about recommender algorithms of social medias like YouTube. How should hate speech be moderated? What should be shown to someone who wants to learn about climate change? Should there be an additional tax on, say, car advertisements? Should angering videos be less viral?

Lê would be thrilled to see social choice theory applied to such critical moral questions.

== Scaled voting ==

One frequent remark that is being made is whether we really can (and should) agree on ethical issues. For instance, [https://www.nature.com/articles/s41586-018-0637-6 ADKSH+][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=The+Moral+Machine+experiment+nature+2018&btnG= 18] showed that Japanese prefer to save walkers, while Chinese prefer to save car passengers. Should we really enforce a common ethics worldwide?

Well, we probably don't need to. Cars could be programmed to save Japanese walkers and Chinese car passengers. They could be made to defend freedom in US and baguette in France. While humans usually have preferences for what happens elsewhere in the world, they usually have stronger preferences for what happens near their home. This probably is something that should be considered when designing voting-based ethics.

One proposal to reflect such nuances is [https://en.wikipedia.org/wiki/Quadratic_voting quadratic voting] [https://www.sss.ias.edu/files/pdfs/Rodrik/workshop%2014-15/Weyl-Quadratic_Voting.pdf LalleyWeyl][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=quadratic+voting+lalley+weyl&btnG=&oq=quadratic+voting 18], which can be made secure [https://link.springer.com/article/10.1007/s11127-017-0407-2 ParkRivest][https://dblp.org/rec/bibtex/journals/iacr/ParkR16 16]. In quadratic voting, a voter who wants its vote to weigh n times more must pay n2. This guarantees (asymptotic) efficiency (utilitarian outcome) and incentive-compatibility. But quadratic voting only applies to 2-alternative votes (typically statu quo vs new law) and is manipulable by collusion.

Another interesting point to be made about multidimensional voting is that the (geometric) median is strategy-proof for voters with a peaked preference, and a valuation that decreases with the distance to the peaked preference. The geometric median is particularly suited for, say, determining budget allocation through social choice. Weirdly, we don't know of a neat paper on this, though using sum of distance minimizer is well-known (need citation).

== Preferences versus volitions ==

It's been argued [https://intelligence.org/files/CEV.pdf Yudkowsky][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=coherent+extrapolated+volition+yudkowsky&btnG= 04], [https://www.izmemar.com/files/CEV-MachineEthics.pdf Tarleton][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=coherent+extrapolated+volition+tarleton&btnG= 10], [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.674.6424&rep=rep1&type=pdf Soares][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=the+value+learning+problem+soares&btnG= 15], [http://ceur-ws.org/Vol-2301/paper_1.pdf Hoang][https://dblp.org/rec/bibtex/conf/aaai/Hoang19 19] that we surely should not aggregate today's human moral preferences, because of [[cognitive biases]] [https://www.amazon.com/s?k=thinking+fast+and+slow&ref=nb_sb_noss KahnemanBook][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=thinking+fast+and+slow+kahneman+2011&btnG= 11]. Mostly, our preferences are inconsistent, manipulable via framing, time-dependent, subject to addictions, and so on. We are likely to regret today's claimed preferences in the future, or as soon as we better understand their consequences. Instead, it is argued, we should program human [[volition|volitions]], which corresponds to what we would prefer to prefer, instead of what we simply prefer.

Unfortunately, a lot more research is needed to better formalize and analyze the concept of volition, and how it diverges from preferences. One fruitful path may be to analyze the difference between what's learned through [[inverse reinforcement learning]], as opposed to through (well-framed) elicitation. See [[volition]] for a lot more discussion on this problem.

@@ Line 13: / Line 13: @@
 [http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf Harsanyi][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>p</math> and <math>q</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.
-To prove it, consider a finite set of alternatives. Denote <math>u_{ij}</math> is the utility of individual <math>i</math> for alternative <math>j</math>. Individual <math>i</math>'s utility for a probability <math>p</math> equals <math>(up)_i</math>. Denoting <math>v_j</math> the group's utility for alternative <math>j</math>, the indifference property says that <math>u (p-q) = 0</math> implies <math>v^T (p-q) = 0</math>. Using linear algebra and the fact that this holds for all <math>p, q</math> then implies that <math>v</math> belongs to the vector space spanned by the <math>u_i</math>'s. This results in saying that <math>w = a + \sum w_i u_i</math>, for nonnegative weights <math>w_i</math>'s (and arbitrary constant <math>a</math>).
+To prove it, consider a finite set of alternatives. Denote <math>u_{ij}</math> is the utility of individual <math>i</math> for alternative <math>j</math>. Individual <math>i</math>'s utility for a probability <math>p</math> equals <math>(up)_i</math>. Denoting <math>v_j</math> the group's utility for alternative <math>j</math>, the indifference property says that <math>up=uq</math> implies <math>v^Tp = v^Tq</math>. Using linear algebra and the fact that this holds for all <math>p, q</math> then implies that <math>v</math> belongs to the vector space spanned by the <math>u_i</math>'s. This results in saying that <math>w = a + \sum w_i u_i</math>, for nonnegative weights <math>w_i</math>'s (and arbitrary constant <math>a</math>).
 However, there are major caveats to applying this mechanism in practice. First note that the scaling of different individuals' utility functions (or equivalently of their weights) remains to be settled, which does not seem straightforward to be done. But most importantly, this social choice mechanism is not incentive-compatible. If implemented, individuals will have incentives to exaggerate their preferences (or to tell their representatives to do so). Finally, such expected utility maximization will surely turn into the maximization of some expected proxies, which would then be prone to [[Goodhart's law]].

@@ Line 13: / Line 13: @@
 [http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf Harsanyi][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>p</math> and <math>q</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.
-To prove it, consider a finite set of alternatives. Denote <math>u_{ij}</math> is the utility of individual <math>i</math> for alternative <math>j</math>. Individual <math>i</math>'s utility for a probability <math>p</math> equals <math>u_i^T p</math>. Denoting <math>v_j</math> the group's utility for alternative <math>j</math>, the indifference property says that <math>u (p-q) = 0</math> implies <math>v^T (p-q) = 0</math>. Using linear algebra and the fact that this holds for all <math>p, q</math> then implies that <math>v</math> belongs to the vector space spanned by the <math>u_i</math>'s. This results in saying that <math>w = a + \sum w_i u_i</math>, for nonnegative weights <math>w_i</math>'s (and arbitrary constant <math>a</math>).
+To prove it, consider a finite set of alternatives. Denote <math>u_{ij}</math> is the utility of individual <math>i</math> for alternative <math>j</math>. Individual <math>i</math>'s utility for a probability <math>p</math> equals <math>(up)_i</math>. Denoting <math>v_j</math> the group's utility for alternative <math>j</math>, the indifference property says that <math>u (p-q) = 0</math> implies <math>v^T (p-q) = 0</math>. Using linear algebra and the fact that this holds for all <math>p, q</math> then implies that <math>v</math> belongs to the vector space spanned by the <math>u_i</math>'s. This results in saying that <math>w = a + \sum w_i u_i</math>, for nonnegative weights <math>w_i</math>'s (and arbitrary constant <math>a</math>).
 However, there are major caveats to applying this mechanism in practice. First note that the scaling of different individuals' utility functions (or equivalently of their weights) remains to be settled, which does not seem straightforward to be done. But most importantly, this social choice mechanism is not incentive-compatible. If implemented, individuals will have incentives to exaggerate their preferences (or to tell their representatives to do so). Finally, such expected utility maximization will surely turn into the maximization of some expected proxies, which would then be prone to [[Goodhart's law]].

@@ Line 11: / Line 11: @@
 == Harsanyi's Utilitarian Theorem ==
-[http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf Harsanyi][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>\mu</math> and <math>\nu</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.
+[http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf Harsanyi][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>p</math> and <math>q</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.
-To prove it, consider a finite set of alternatives. Denote <math>u_{ij}</math> is the utility of individual <math>i</math> for alternative <math>j</math>. Individual <math>i</math>'s utility for a probability <math>\mu</math> equals <math>u_i^T \mu</math>. Denoting <math>v_j</math> the group's utility for alternative <math>j</math>, the indifference property says that <math>u (\mu-\nu) = 0</math> implies <math>v^T (\mu-\nu) = 0</math>. Using linear algebra and the fact that this holds for all <math>\mu, \nu</math> then implies that <math>v</math> belongs to the vector space spanned by the <math>u_i</math>'s. This results in saying that <math>w = a + \sum w_i u_i</math>, for nonnegative weights <math>w_i</math>'s (and arbitrary constant <math>a</math>).
+To prove it, consider a finite set of alternatives. Denote <math>u_{ij}</math> is the utility of individual <math>i</math> for alternative <math>j</math>. Individual <math>i</math>'s utility for a probability <math>p</math> equals <math>u_i^T p</math>. Denoting <math>v_j</math> the group's utility for alternative <math>j</math>, the indifference property says that <math>u (p-q) = 0</math> implies <math>v^T (p-q) = 0</math>. Using linear algebra and the fact that this holds for all <math>p, q</math> then implies that <math>v</math> belongs to the vector space spanned by the <math>u_i</math>'s. This results in saying that <math>w = a + \sum w_i u_i</math>, for nonnegative weights <math>w_i</math>'s (and arbitrary constant <math>a</math>).
 However, there are major caveats to applying this mechanism in practice. First note that the scaling of different individuals' utility functions (or equivalently of their weights) remains to be settled, which does not seem straightforward to be done. But most importantly, this social choice mechanism is not incentive-compatible. If implemented, individuals will have incentives to exaggerate their preferences (or to tell their representatives to do so). Finally, such expected utility maximization will surely turn into the maximization of some expected proxies, which would then be prone to [[Goodhart's law]].

@@ Line 11: / Line 11: @@
 == Harsanyi's Utilitarian Theorem ==
-[Harsanyi http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>\mu</math> and <math>\nu</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.
+[http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf Harsanyi][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>\mu</math> and <math>\nu</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.
 To prove it, consider a finite set of alternatives. Denote <math>u_{ij}</math> is the utility of individual <math>i</math> for alternative <math>j</math>. Individual <math>i</math>'s utility for a probability <math>\mu</math> equals <math>u_i^T \mu</math>. Denoting <math>v_j</math> the group's utility for alternative <math>j</math>, the indifference property says that <math>u (\mu-\nu) = 0</math> implies <math>v^T (\mu-\nu) = 0</math>. Using linear algebra and the fact that this holds for all <math>\mu, \nu</math> then implies that <math>v</math> belongs to the vector space spanned by the <math>u_i</math>'s. This results in saying that <math>w = a + \sum w_i u_i</math>, for nonnegative weights <math>w_i</math>'s (and arbitrary constant <math>a</math>).

← Older revision		Revision as of 22:48, 22 February 2020
Line 12:		Line 12:

	[Harsanyi http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>\mu</math> and <math>\nu</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.		[Harsanyi http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>\mu</math> and <math>\nu</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.
		+
		+	To prove it, consider a finite set of alternatives. Denote <math>u_{ij}</math> is the utility of individual <math>i</math> for alternative <math>j</math>. Individual <math>i</math>'s utility for a probability <math>\mu</math> equals <math>u_i^T \mu</math>. Denoting <math>v_j</math> the group's utility for alternative <math>j</math>, the indifference property says that <math>u (\mu-\nu) = 0</math> implies <math>v^T (\mu-\nu) = 0</math>. Using linear algebra and the fact that this holds for all <math>\mu, \nu</math> then implies that <math>v</math> belongs to the vector space spanned by the <math>u_i</math>'s. This results in saying that <math>w = a + \sum w_i u_i</math>, for nonnegative weights <math>w_i</math>'s (and arbitrary constant <math>a</math>).

	However, there are major caveats to applying this mechanism in practice. First note that the scaling of different individuals' utility functions (or equivalently of their weights) remains to be settled, which does not seem straightforward to be done. But most importantly, this social choice mechanism is not incentive-compatible. If implemented, individuals will have incentives to exaggerate their preferences (or to tell their representatives to do so). Finally, such expected utility maximization will surely turn into the maximization of some expected proxies, which would then be prone to [[Goodhart's law]].		However, there are major caveats to applying this mechanism in practice. First note that the scaling of different individuals' utility functions (or equivalently of their weights) remains to be settled, which does not seem straightforward to be done. But most importantly, this social choice mechanism is not incentive-compatible. If implemented, individuals will have incentives to exaggerate their preferences (or to tell their representatives to do so). Finally, such expected utility maximization will surely turn into the maximization of some expected proxies, which would then be prone to [[Goodhart's law]].

← Older revision		Revision as of 22:22, 22 February 2020
Line 8:		Line 8:

	Today's most convincing social choice mechanisms are probably the [https://en.wikipedia.org/wiki/Approval_voting approval voting] ([https://dblp.org/rec/bibtex/books/daglib/0017739 BramsFishburnBook07], [https://www.youtube.com/watch?v=orybDrUj4vA CGPGrey]), [https://en.wikipedia.org/wiki/Majority_judgment majority judgment] ([https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=majority+judgment+laraki+balinski&btnG= BalinksiLarakiBook11], [https://www.youtube.com/watch?v=ZoGH7d51bvc ScienceÉtonnante16<sup>FR</sup>], [https://www.youtube.com/watch?v=_MAo8pUl0U4 S4A17c<sup>FR</sup>]) and the randomized Condorcet voting system ([https://dspace.mit.edu/bitstream/handle/1721.1/107673/355_2017_1031_ReferencePDF.pdf?sequence=1&isAllowed=y Hoang][https://dblp.org/rec/bibtex/journals/scw/Hoang17 17], [https://www.youtube.com/watch?v=wKimU8jy2a8 S4A17d<sup>FR</sup>], [https://www.youtube.com/watch?v=vAdGZkXhlNM S4A17e<sup>FR</sup>]).		Today's most convincing social choice mechanisms are probably the [https://en.wikipedia.org/wiki/Approval_voting approval voting] ([https://dblp.org/rec/bibtex/books/daglib/0017739 BramsFishburnBook07], [https://www.youtube.com/watch?v=orybDrUj4vA CGPGrey]), [https://en.wikipedia.org/wiki/Majority_judgment majority judgment] ([https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=majority+judgment+laraki+balinski&btnG= BalinksiLarakiBook11], [https://www.youtube.com/watch?v=ZoGH7d51bvc ScienceÉtonnante16<sup>FR</sup>], [https://www.youtube.com/watch?v=_MAo8pUl0U4 S4A17c<sup>FR</sup>]) and the randomized Condorcet voting system ([https://dspace.mit.edu/bitstream/handle/1721.1/107673/355_2017_1031_ReferencePDF.pdf?sequence=1&isAllowed=y Hoang][https://dblp.org/rec/bibtex/journals/scw/Hoang17 17], [https://www.youtube.com/watch?v=wKimU8jy2a8 S4A17d<sup>FR</sup>], [https://www.youtube.com/watch?v=vAdGZkXhlNM S4A17e<sup>FR</sup>]).
		+
		+	== Harsanyi's Utilitarian Theorem ==
		+
		+	[Harsanyi http://darp.lse.ac.uk/papersDB/Harsanyi_(JPolE_55).pdf][https://scholar.google.ch/scholar?hl=en&as_sdt=0%2C5&q=cardinal+welfare%2C+individualistic+ethics%2C+harsanyi&btnG= 55] proved that weighted sums of individuals' utilities are the only social choice mechanisms that aggregate [[Von Neumann-Morgenstern preferences]] to yield Von Neumann-Morgenstern group preferences in such a way that, if every individual of the group is indifferent between probabilistic outcomes <math>\mu</math> and <math>\nu</math>, then so is the group. This is a compelling argument for a simple addition of individuals' preferences.
		+
		+	However, there are major caveats to applying this mechanism in practice. First note that the scaling of different individuals' utility functions (or equivalently of their weights) remains to be settled, which does not seem straightforward to be done. But most importantly, this social choice mechanism is not incentive-compatible. If implemented, individuals will have incentives to exaggerate their preferences (or to tell their representatives to do so). Finally, such expected utility maximization will surely turn into the maximization of some expected proxies, which would then be prone to [[Goodhart's law]].

	== The (Huge) Flaw of Classical Social Choice ==		== The (Huge) Flaw of Classical Social Choice ==

@@ Line 27: / Line 27: @@
 It has been argued to be critical to solve the problem of AI ethics ([https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12457/12204 GRTVW][https://dblp.org/rec/bibtex/conf/aaai/GreeneRTVW16 16],[http://isaim2018.cs.virginia.edu/papers/ISAIM2018_Ethics_Conitzer_etal.pdf CSBDK][https://dblp.org/rec/bibtex/conf/isaim/ConitzerSBD018 17]). In brief, we are unlikely to agree on what ethics to program. However, we might be able to agree on how to agree on some ethics to program even though we disagree. The trick to implement some (virtual) democratic voting on moral preferences.
-Interestingly, ideas along these lines have already been developed for the cases of autonomous car dilemmas [https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17052/15857 NGAD+][https://dblp.org/rec/bibtex/conf/aaai/NoothigattuGADR18 18] [https://www.youtube.com/watch?v=Y6jfGZXubq0 UpAndAtom18], kidney transplant [https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17384/15863 FBSDC][https://dblp.org/rec/bibtex/conf/aaai/FreedmanBSDC18 18] and food donation (called WeBuildAI [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=2ahUKEwj4y5-ggu3mAhXB2qQKHT6GDZ4QFjACegQIARAC&url=https%3A%2F%2Fwww.cs.cmu.edu%2F~akahng%2Fpapers%2Fwebuildai.pdf&usg=AOvVaw2BknquyvgNufy-JlCoPj_G LKKK+][https://dblp.org/rec/bibtex/journals/pacmhci/LeeKKKYCSNLPP19 19]).
+Interestingly, ideas along these lines have already been developed for the cases of autonomous car dilemmas [https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17052/15857 NGADR+][https://dblp.org/rec/bibtex/conf/aaai/NoothigattuGADR18 18] [https://www.youtube.com/watch?v=Y6jfGZXubq0 UpAndAtom18], kidney transplant [https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17384/15863 FBSDC][https://dblp.org/rec/bibtex/conf/aaai/FreedmanBSDC18 18] and food donation (called WeBuildAI [https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=2ahUKEwj4y5-ggu3mAhXB2qQKHT6GDZ4QFjACegQIARAC&url=https%3A%2F%2Fwww.cs.cmu.edu%2F~akahng%2Fpapers%2Fwebuildai.pdf&usg=AOvVaw2BknquyvgNufy-JlCoPj_G LKKKY+][https://dblp.org/rec/bibtex/journals/pacmhci/LeeKKKYCSNLPP19 19]).
 Note that in all such applications, the set of alternatives is combinatorially large. The trick to perform voting with limited elicitation from voters is to collect binary-choice-based preferences, and to then <em>extrapolate</em> preferences for other cases using machine learning (with some inductive bias). Another way to interpret this is to consider that voters get substituted by digital surrogates, whose task is to answer just as the voters would. This is kind of like representative democracy, where voters are replaced by their representatives. But machine learning can allow individual representatives through customized surrogates!

@@ Line 19: / Line 19: @@
 == Bounds for limited communication complexity ==
-A fascinating result by [http://papers.nips.cc/paper/8939-efficient-and-thrifty-voting-by-any-means-necessary MPSW19] shows that the worst-case lost of social welfare due to polynomial communication complexity (voters communicate at most log(#alternatives) bits) is unbounded (#alternatives<sup>2</sup> for deterministic elicitation+voting, #alternatives for randomized).
+A fascinating result by [http://papers.nips.cc/paper/8939-efficient-and-thrifty-voting-by-any-means-necessary MPSW][https://dblp.org/rec/bibtex/conf/nips/MandalP0W19 19] shows that the worst-case lost of social welfare due to polynomial communication complexity (voters communicate at most log(#alternatives) bits) is unbounded (#alternatives<sup>2</sup> for deterministic elicitation+voting, #alternatives for randomized).
 There are caveats though. For one thing, this is a worst-case analysis. But human preferences may be more structured. Also, priors can be invoked. Plus, authors assumed that the same elicitation was applied to all voters, which is clearly suboptimal. A lot more research on the communication-complexity versus social-welfare tradeoff is definitely desired. This is exciting!