Dynamic Social Choice for Anaphora Resolution Sumiyo Nishiguchi Department of Liberal Arts, Faculty of Science Division I, Tokyo University of Science 1-3 Kagurazaka, Shinjuku, Tokyo 162-8601 Japan Email: nishiguchi@rs.tus.ac.jp Abstract In linguistic binding theory (Chomsky 1981, Reinhart 1983), antecedents are called binders, Disambiguation of pronoun reference has which bind bindees that are anaphoric pronouns, been an important issue for both theoret- e.g., him or himself. Condition B is that pro- ical and computational linguists. While nouns must be free in their local domain, mean- linguistic theories on binding conditions ing that they are not bound by the antecedent by eliminate impossible readings to a cer- means of coindexing and c-commanding relation. tain extent, many inter-sentential anaphora C-command is roughly equivalent to precedence, remain ambiguous. Nishiguchi (2011, with some restrictions. 2012a,b, 2014, 2016a,b) consider pronoun However, (3) is ambiguous in four ways and can resolution as a social choice among dis- have either one of the following interpretations: i) course participants which obeys Arrow’s John broke John’s leg, ii) John broke Bill’s leg, iii) Impossibility Theorem (Arrow 1963). Bill broke Bill’s leg, or iv) Bill broke John’s leg. This paper further discusses discourse up- He and his can be bound by either John or Bill. date of Social Welfare Function which The binding theories have no way of disambiguat- provides updated variable assignment. ing these pronouns since there is no way of know- In (1), she has multiple candidates for its ing speaker intention. Proximity does not predict antecedent— Emma, Lisa and Lisa’s mom. Prox- the different readings in (3) either. imity and saliency of antecedents have been con- (3) Anna: Billj is a good goalkeeper. sidered to be key factors to decide (Leass 1991). Kim: Johni said hei/j broke hisi/j leg re- In (1), the most proximate antecedent her (Lisa)’s cently. mom is identified to be the antecedent for she. (1) Frances: ...Not while Emma’s not here. You 1 Social Choice Theory know Emma Although Social Choice Theory (Arrow 1963, Billy: Mm. Moulin 1988, Taylor 2005, Gaertner 2009) has Frances: she’s, she was walking with Lisa only been briefly mentioned in van Rooij (2011) in and I weren’t there and her Mum sh– jus– , relation with interadjective comparison, Arrow’s like she muc– , she mucks about a lot and Impossibility Theorem is obeyed in a social choice she told Leigh that if he don’t serve her he’s of pronominal reference. Typically, social choice gonna die, she’s gonna punch him right! theory explains collective decision making in case However, proximity does not always resolve of voting and has solved the problems with ma- referential ambiguity of pronouns. Him in (2a) un- jority decision. Preferences are ordering between ambiguously means someone other than the clos- alternatives and should satisfy the following ax- est John—some discourse-salient entity. In (2b), ioms. When R stands for a knowledge of all pairs the pronoun is ambiguous. and x, y and z for alternatives, Axiom 1. For all x and y, either xRy or yRx. (2) a. Johni likes him{∗i/j6=i} . Axiom 2. For all x, y, and z, xRy and yRz imply b. Johni said he{i/j} likes himself{i/j} . xRz. Axiom 1 states that the relation R is 2 Application to Pronoun Resolution connected—every candidate is related to each other. Relations that satisfy Axiom 2 are transi- SWF for pronoun resolution satisfies Arrow’s Im- tive. In (4), N, a finite set of individuals or voters, possibility Theorem, or General Possibility The- consists of five individuals and χ, a nonempty set orem, by satisfying Axioms 1, 2, Pareto Condi- of alternatives or candidates, has three members. tion and IIA but demonstrating dictatorship. Pro- Let L(χ) denote the set of all linear orders on noun resolution is compared with voting by multi- χ. A profile R is a vector of linear orders, or ple voters, discourse participants. The candidates preferences. Ri is a vector of preferences of an or choices would be different interpretation of the individual i. NR sentence. In (5), the referent of he is ambigu- x>y denotes the set of individuals that prefer the candidate x to y. Supposing R the ous. Chris meant he to be Bob, while Naomi in- profile given in this model, NR terpreted him to be John. As the disagreement on o>c is a set of people who prefers Obama to Clinton, that are, Anna, pronominal reference is consolidated in the dis- Heather and George (cf. Endriss 2016). course, pronoun resolution is certainly a social choice and Social Choice Function (SCF) decides (4) a. N = {a, k, h, g, n} the antecedent. b. χ = {o, c, m} (5) Chris: John said he broke his leg. Naomi: Did he? John looked fine when I saw c. R ∈ L(χ)N him this morning. Chris: It is Bob who broke his leg. d. NR o>c = {a, h, g} Naomi: I thought you were talking about John. e. SWF F: L(χ)N → L(χ) When individuals I = {c, n}, candidates χ = {j, A social welfare function (SWF) F is a function b}, Chris and Naomi’s ordering is jRc b ∧ bRn j, which takes individual’s preferences and returns denote the set of linear orders on χ by L(χ). Pref- collective preference. Arrow demonstrated that erences (or ballots) are taken to be elements of any SWF for three or more alternatives the follow- L(χ). A profile R ∈ L(χ)I is a vector of prefer- ing conditions must be a dictatorship. Condition 2 ences. SCF or voting rule is a function F : L(χ)I states that the relative ranking of two candidates → 2χ \∅ mapping a given profile to a nonempty remains unchanged regardless of other candidates. set of winners; e.g., a singleton set {b} for (5). Theorem 1 (General Possibility Theorem (Impos- SWF is a function F : L(χ)I → L(χ) mapping any sibility Theorem)). If there are at least three alter- given profile to a (single) collective preference or- natives which the members of the society are free der. Although the preferences between the candi- to order in any way, then every social welfare func- dates vary between the individuals, SWF returns tion satisfying Conditions 1 and 2 and yielding a a single preference order and ambiguities are re- social ordering satisfying Axioms 1 and 2 must be solved during the conversation. either imposed or dictatorial. There are three possible antecedents for she in Condition 1 (Pareto condition). A SWF F satisfies (1)—Emma (e), Lisa (l) and Lisa’s mother (m). the Pareto condition if, whenever all individuals Let us say that Billy (b) prefers e to l, and also l rank x above y, then so does society: NR to m to be the antecedent. On the other hand, the x>y = N implies xF(R)y speaker Francis (f) prefers m to l, and l to e ac- cording to the proximity. All three candidates are Condition 2 (Independence of irrelevant alterna- ordered in accordance with Axiom 1, i.e., eRb l ∧ tives (IIA)). A SWF F satisfies IIA if the relative lRb m and mRf l ∧ lRf e. Transitivity also holds social ranking of two alternatives only depends on for pronoun antecedent preferences. Each of them their relative individual rankings: NR R0 x>y = Nx>y implies eRb lRb m and mRf lRf e. SWF for pronoun implies xF(R)y ⇔ xF(R’)y resolution also meets Pareto condition. When the Condition 3 (Nondictatorship). There is no indi- interpretation of the addressees agrees with the vidual i such that for every element in the domain one of the speaker, the decision of the society fol- of rule f, ∀x, y ∈ X: xPi y → xPy (Sen 1979) lows. It is unlikely that pronouns refer to someone else other than speaker’s intention and hearer’s in- (11) a. g = {: x refers to i} terpretation. A SWF F satisfies IIA if the relative social ranking of two alternatives only depends b. Information state σ consists of Social on their relative individual rankings. Let us say Welfare Function F, Social Choice Func- that the preference relations are denoted by R and tion g for variable assignment, individ- R’. Assume that IIA does not hold and consider ual’s preferences R, individuals in the dis- a dialogue in (7) where the relative rankings be- course X, a set of indices such as i, a set of tween Bob and John is affected by irrelevant can- discourse participants V, and relation be- didate Victor’s ranking. The social decision differs tween decisions B. from the relative ranking between John and Bob of Σ = < F, G, R, X, I, V, B> speaker and hearer, which does not happen, in (8). (6) Chris: Bob is a good skier. But John said he (12) σ1 There were ooh’s and aah’s when broke his leg. hex1 finished, and some unbridled laugh- Naomi: Did he? Poor Bob! ter. Aileena was looking dubiously at hery1 husbandh but hex2 was in no mood to disap- (7) Chris: Victor is a good skier and so is Bob. prove. But John said he broke his leg. σ2 Hex3 winked at the Duked and called Naomi: Did he? Poor Bob! across to himx4 , ‘What a grand thing, your (8) bR’c vR’c j ∧ bR’n jR’n v 6→ jF(R)b Honour, to have a wedding without a min- 0 Then, N R R b>j = N b>j implies bF(R)j ⇔ bF(R’)j ister!’ The Duked did hisx5 stately bow at that and then Donaldm was calling for an- The speaker’s decision on pronominal reference other song. dictates the social preference. Even when there is disagreement or misunderstanding, the speaker σ3 Some of the veteransv were on the corrects unifies interpretation in general, as in (9). point of giving tongue but young Donald Pronoun resolution is dominated, or dictated, by McCullochm was on hisx6 feet and moving the speaker’s meaning. into the middle of the ring, hex7 was full of himselfx8 , sparkling with mischief but with (9) Chris: Bob is a good skier. But John said he an undertow of ardour. broke his leg. Naomi: Did he? Poor Bob! σ4 ‘Duncan Ban MacIntyreb wrote a song for Chris: No. I mean John broke his leg. hisx9 wife Maryr . (10) xPc y → xPy σ5 I do not know if Alexl used it to court his10 M aryr – hex11 must have used some- Proof. Suppose: xPc y → ∼xPy, that is, xPc y → thing —‘The joke was unconscious but crow- yRx, where R is weak preference. However, the ing laughter came from the young menn be- dialogue normally proceeds jPc b → jPb as in (10). side the whisky jar. (BNC A0N1311-1315, Contradiction. King Cameron) Lemma 1. The social welfare function for pro- (13) a. g1= {, } noun resolution is IIA and Pareto but is dictato- I = {a, r} (a: author, r: reader) rial. S = {a, h} 3 Dynamic Update of SCF b. g2 = {, } In linguistic literature, a variable assignment func- tion g has been assumed to assign the referent to S = {a, h, d, m} indices indexed to pronouns. For example, g may c. g3 = { , , } assign John to the variable x: g(x) = John. Now, g can be considered to be SCF which selects a ref- S = {a, h, d, v, m} erent for a pronoun socially. Let us define g and the space as in (11). The assignment function g is d. g4 = {} updated throughout the discourse as in (12). S = {a, h, d, v, m, b, r} e. g5 = {, } (17) ‘...And Sarah Morgan likes the idea of An- S ={a, h, d, v, m, b, r, l, n} gela marrying someone in the government.’ McLeish considered this cold and rational as- f. [[hery ]]g1 = a sessment. ‘When did you last see her? Miss Angela Morgan, I mean.’ (BNC AB9) G is regarded as SCF. Also, the set of best ele- ments S’ can be called its choice set of the whole Out of 18 instances of “I mean PNP” (PNP set of alternaties, and is denoted g(S’, R) (cf. Sen stands for proper name” ) found with the query 1979) R is a sequence of individual’s preferences “I mean N” in BNC, 7 instances had a preceding where Rx is a preference ordering of x. pronoun, the caraphor. (14) g1(S, R) = {a, h} References g2(S, R) = {h, d} Arrow, K. J.: 1963, Social Choice and Individ- g3(S, R) = {m} ual Values, 2 edn, Yale University Press, New g4(S, R) = {b} Haven. g5(S, R) = {l} Chomsky, N.: 1981, Lectures on Government and As the author’s dynamic preferences change in Binding, Foris Publications, Dordrecht. the discourse as in (15a), g is updated throughout Endriss, U.: 2016, Judgment aggregation, in the discourse by means of a relation B. H. Moulin, F. Brandt, V. Conitzer, U. Endriss, J. Lang and A. D. Procaccia (eds), Handbook of (15) a. σ2: hRa d for hex3 ∧ dRa h for hex4 ∧ Computational Social Choice, Cambridge Uni- dRa hIa m for hex5 (aIx b: x is indifferent versity Press, pp. 399–426. between a and b, ∧: dynamic conjunc- tion) Gaertner, W.: 2009, A Primer in Social Choice Theory. Revised edition, LSE Perspectives in b. Social Decision: hRd ∧ dRh ∧ dRhIm Economic Analysis, Oxford University Press. c. B(gn ,gn+1 ) Groenendijk, J. and Stokhof, M.: 1991, Dy- namic predicate logic, Linguistics and Philos- (16) Dynamic Social Welfare Function: ophy 14, 39–100. Fn BFn+1 BFn+2 ,... Leass, H. J.: 1991, Anaphora resolution for ma- 4 Comparison with Other Studies chine translation: A study, IWBS Report 187. Moulin, H.: 1988, Axioms of Cooperative De- Dynamic Predicate Logic (Groenendijk and cision Making, Econometric Society Mono- Stokhof 1991) consider update semantics where graphs, Cambridge University Press, Cam- two states differ with respect to variable assign- bridge. ment. When h[x]g, the state g is updated with respect to the assignment to x. The current pa- Nishiguchi, S.: 2011, Computational social choice per consider an abstract function B between two for pronoun resolution, Ipsj sig-nl. SCFs. Parkes and Procaccia (2013) model dy- Nishiguchi, S.: 2012a, Social choice for anaphora namic decision making under constantly changing resolution, NLP2012 Proceedings, pp. 97–100. preferences using Markov decision processes, in Nishiguchi, S.: 2012b, Social choice for anaphora which the states coincide with preference profiles resolution, Society for Social Choice, New and a policy corresponds to a social choice func- Delhi. tion. Nishiguchi, S.: 2014, Application of social choice 5 Detection of Speaker Intention theory in pronoun resolution, Society for Social In order to implement Dynamic Social Choice Choice, Boston College. for pronoun disambiguation, speaker’s intention Nishiguchi, S.: 2016a, Social choice for anaphora needs to be detected from the text. The phrases resolution, Studies in Liberal Arts and Sciences, such as “I mean” are used to resolve ambiguity of Vol. 48, Tokyo University of Science, pp. 147– pronominal reference in the discourse. as in (17). 156. Nishiguchi, S.: 2016b, Social choice for disam- biguation of pronominal reference, Society for Social Choice, Lund University. Parkes, D. C. and Procaccia, A. D.: 2013, Dy- namic social choice with evolving preferences, Proceedings of the 27th AAAI Conference on Artificial Intelligence, Palo Alto, CA, pp. 767– 773. Reinhart, T.: 1983, Anaphora and Semantic In- terpretation, The University of Chicago Press, Chicago. Sen, A. K.: 1979, Collective Choice and Social Welfare, North-Holland, Amsterdam. Taylor, A.: 2005, Social Choice and the Mathe- matics of Manipulation, Cambridge University Press, Cambridge. van Rooij, R.: 2011, Measurement and inter- adjective comparisons, Journal of Semantics 28, 335–358.