Neural Information Processing Systems http://nips.cc/

We study how linear orders can be employed to realise choice functions for which the set of potential choices is restricted, i.e., the possible choice is not possible among the full powerset of all alternatives. In such restricted settings, constructing a choice function via a relation on the alternatives is not always possible. However, we show that one can always construct a choice function via a linear order on sets of alternatives, even when a fallback value is encoded as the minimal element in the linear order. The axiomatics of such choice functions are presented for the general case and the case of union-closed input restrictions. Restricted choice structures have applications in knowledge representation and reasoning, and here we discuss their applications for theory change and abstract argumentation.

Neural Information Processing Systems http://nips.cc/

Let m 2 and a,b A such that a is ordered before b in tie-breaking. Suppose PW (P) = { a,b } for some truthful profile P . Suppose PW (P) = { a,b } for some truthful profile P . Agents from the former set will best-respond to rankings whose top preference is a, changing the winner to a, whereas agents from the latter set will best-respond to rankings whose top preference is b, changing the winner back to b. If not, the unique equilibrium winner will be b .

Generating rational and generally accurate responses to tasks, often accompanied by example demonstrations, highlights Large Language Model's (LLM's) remarkable In-Context Learning (ICL) capabilities without requiring updates to the model's parameter space. Despite having an ongoing exploration focused on the inference from a document-level concept, its behavior in learning well-defined functions or relations in context needs a careful investigation. In this article, we present the performance of ICL on partially ordered relation by introducing the notion of inductively increasing complexity in prompts. In most cases, the saturated performance of the chosen metric indicates that while ICL offers some benefits, its effectiveness remains constrained as we increase the complexity in the prompts even in presence of sufficient demonstrative examples. The behavior is evident from our empirical findings and has further been theoretically justified in term of its implicit optimization process. The code is available here.

In this paper, we take a statistical decision-theoretic viewpoint on social choice, putting a focus on the decision to be made on behalf of a system of agents. In our framework, we are given a statistical ranking model, a decision space, and a loss function defined on (parameter, decision) pairs, and formulate social choice mechanisms as decision rules that minimize expected loss. This suggests a general framework for the design and analysis of new social choice mechanisms. We compare Bayesian estimators, which minimize Bayesian expected loss, for the Mallows model and the Condorcet model respectively, and the Kemeny rule. We consider various normative properties, in addition to computational complexity and asymptotic behavior. In particular, we show that the Bayesian estimator for the Condorcet model satisfies some desired properties such as anonymity, neutrality, and monotonicity, can be computed in polynomial time, and is asymptotically different from the other two rules when the data are generated from the Condorcet model for some ground truth parameter.

In the context of voting with ranked ballots, an important class of voting rules is the class of margin-based rules (also called pairwise rules). A voting rule is margin-based if whenever two elections generate the same head-to-head margins of victory or loss between candidates, then the voting rule yields the same outcome in both elections. Although this is a mathematically natural invariance property to consider, whether it should be regarded as a normative axiom on voting rules is less clear. In this paper, we address this question for voting rules with any kind of output, whether a set of candidates, a ranking, a probability distribution, etc. We prove that a voting rule is margin-based if and only if it satisfies some axioms with clearer normative content. A key axiom is what we call Preferential Equality, stating that if two voters both rank a candidate $x$ immediately above a candidate $y$, then either voter switching to rank $y$ immediately above $x$ will have the same effect on the election outcome as if the other voter made the switch, so each voter's preference for $y$ over $x$ is treated equally.

This paper studies the realizability of belief revision and belief contraction operators in epistemic spaces. We observe that AGM revision and AGM contraction operators for epistemic spaces are only realizable in precisely determined epistemic spaces. We define the class of linear change operators, a special kind of maxichoice operator. When AGM revision, respectively, AGM contraction, is realizable, linear change operators are a canonical realization.

In this paper, we take a statistical decision-theoretic viewpoint on social choice, putting a focus on the decision to be made on behalf of a system of agents. In our framework, we are given a statistical ranking model, a decision space, and a loss function defined on (parameter, decision) pairs, and formulate social choice mechanisms as decision rules that minimize expected loss. This suggests a general framework for the design and analysis of new social choice mechanisms. We compare Bayesian estimators, which minimize Bayesian expected loss, for the Mallows model and the Condorcet model respectively, and the Kemeny rule. We consider various normative properties, in addition to computational complexity and asymptotic behavior. In particular, we show that the Bayesian estimator for the Condorcet model satisfies some desired properties such as anonymity, neutrality, and monotonicity, can be computed in polynomial time, and is asymptotically different from the other two rules when the data are generated from the Condorcet model for some ground truth parameter.

Hallucination has been widely recognized to be a significant drawback for large language models (LLMs). There have been many works that attempt to reduce the extent of hallucination. These efforts have mostly been empirical so far, which cannot answer the fundamental question whether it can be completely eliminated. In this paper, we formalize the problem and show that it is impossible to eliminate hallucination in LLMs. Specifically, we define a formal world where hallucination is defined as inconsistencies between a computable LLM and a computable ground truth function. By employing results from learning theory, we show that LLMs cannot learn all of the computable functions and will therefore always hallucinate. Since the formal world is a part of the real world which is much more complicated, hallucinations are also inevitable for real world LLMs. Furthermore, for real world LLMs constrained by provable time complexity, we describe the hallucination-prone tasks and empirically validate our claims. Finally, using the formal world framework, we discuss the possible mechanisms and efficacies of existing hallucination mitigators as well as the practical implications on the safe deployment of LLMs.