We study the rational preferences of an agent participating to a mechanism whose outcome is a weak order among participants. We propose a set of self-interest axioms and characterize the resulting preference theories.
In many applications, a series of measurements are designed in order to obtain a ranking among a set of
agents. Tournaments [
In this paper, we assume that an arbitrary mechanism produces a weak order among a set of agents, and we study the preferences that those agents may exhibit over the outcomes of that mechanism. More specifically, we introduce six basic conditions reflecting different aspects of the rational behaviour of an agent and study the theories deriving from choosing a generic subset of those conditions. We show that only a relatively small number of theories are distinct and we provide a hierarchical characterization thereof. Understanding the types of preferences that a rational agent can hold is necessary to study the strategic reasoning that they apply to the mechanism, and ultimately predict or control their behaviour. This provides the theoretical underpinnings for avoiding the often arbitrary tie-breaking phase or for minimizing in sporting tournaments the occurrence of matches that are competitively irrelevant for one or both of the involved players.
This preliminary study paves to way to many further directions. For example, we aim at investigating the connection between this preference theory and mechanisms producing a numerical ranking or distributing monetary rewards.
Recall the following definitions: a pre-order is a reflexive and transitive binary relation, a weak order is a total pre-order, and a linear order is an antisymmetric weak order. Given a pre-order v, we denote its asymmetric part by @ (that is, a @ b iff a v b and b 6v a), and its symmetric complement by 7 (that is, a 7 b iff a 6v b and b 6v a).
We assume that an undescribed process, such as a competition or a vote, produces a weak order on a set of agents A. We want to study the ways in which the agents compare different outcomes.
Given a finite set of agents A, let W(A) denote the set of all weak orders on A. For an agent a ∈ A, a preference relation for a (in short, an a-preference) is a weak order P on W(A). In Section 2.2 we will qualify which preference relations are rational for an agent by introducing suitable self-interest axioms.
We say that a pre-order v2 perfects another pre-order v1 if a @1 b implies a @2 b, and a 72 b implies a 71 b, for all agents a and b. Intuitively, v2 exhibits at least the same strong preferences of v1, but it may distinguish agents that are equivalent for v1, as well as distinguishing or equating agents that are incomparable for v1. This notion is incomparable to the classical notion of refinement (that is, inclusion) between relations. Perfectioning is itself a pre-order, whose bottom element is the identity relation and whose top elements are the linear orders. 2.1
This section presents a selection of preferences, showing that there is a wide variety of reasonable ways to compare two weak rankings from the point of view of one of the participants.
For a weak order v∈ W(A) and an agent a, let belowa(v), samea(v), abovea(v) be the partition of A into the agents that are strictly below, equivalent, and strictly above a, respectively. Moreover, let levela>(v) be the length of the longest @-chain starting from a, which can be recursively defined as follows: levela>(v) = (1 maxb∈abovea(v) levelb>(v) + 1 if abovea(v) = ∅ otherwise.
One can dually define levela⊥(v) as the length of the longest @-chain ending in a. Informally, this measures the level of a, starting from the bottom.
Next, we are going to present a list of interesting preference relations for a, using a uniform naming system, based on the following abbreviations:
> ⊥ a s b
levela>(v) −levela⊥(v) |abovea(v)| |samea(v)| |belowa(v)| We use the above abbreviations as a superscript to indicate that a preference tries to minimise the corresponding quantity. For example, P a is the preference that minimises |abovea(v)|, i.e., P a(v1, v2) holds iff |abovea(v1)| ≥ |abovea(v2)|. We also write P x,y for the preference that tries to minimise first quantity x and then quantity y, lexicographically. Finally, we allow simple arithmetic expressions, like P a+s for the preference that minimises the sum of |abovea(v)| and |samea(v)|.
• Level-based. P > prefers to minimise the level of a in the weak order, i.e., levela>(v). In particular, it is insensitive to ties. • Level-based top-k. For a positive integer k, Pk> prefers a to be within the first k levels in the weak order. This preference only distinguishes two classes of weak orders: those where a sits in one of the top k levels, and all the others. Any element of the first class is (strongly) preferred to any element of the second class. • Lexicographic. P a,s prefers having fewer agents above a; equal that, it prefers to have fewer agents tied with a. It is equivalent to minimising the vector |abovea(v)|, |samea(v)| , lexicographically. • Best linearization. P bst judges a weak order the same as its linear extension where a has the best position. The canonical name for this preference is P a, because it is equivalent to minimising |abovea(v)|. • Worst linearization. P wst is the dual of P bst. The canonical name for this preference is P a+s, because it is equivalent to minimising |abovea(v) ∪ samea(v)|.
The preference P > may reflect a conscientious participant when a group of students is being partitioned into
different levels of ability. Similarly, the preference Pk> can be adopted by the candidate of a competition
based on a public threshold k such that all candidates with the k highest marks are recruited. In [
Given two weak orders v1, v2∈ W(A) and an agent a ∈ A, define the following properties: a )2 coincide. If we need to emphasize the Same-context. The restrictions of v1 and v2 to (A \ { }
arguments, this property can also be denoted by the extended notation Same-context(a, v1, v2). Dominance. For all b ∈ A, if b @1 a then b @2 a, and if b ≡1 a then b v2 a. Extended notation:
Dominance(a, v1, v2).
Improvement. There exists b ∈ A such that either a ≡1 b and b @2 a, or a @1 b and b v2 a. Extended notation: Improvement(a, v1, v2).
Swap. There exists b ∈ A such that a @1 b and v2 is obtained from v1 by switching a and b. The properties above allow us to describe three notions of a basic improvement for agent a: • a trades place with an agent that is higher up in the order (Swap); • a moves up in the order, and all other agents stay put (Same-context and Improvement); • a moves up in the order, and all other agents do not cross the position of a (Dominance and
Improvement).
In any of these three cases, one may think that a rational agent should prefer the new situation to the old one, at least weakly. In fact, in the following we show that there are reasonable scenarios where some of the above are undesired.
First, we observe that the Dominance property has a close relationship with the idea of splitting the agents into three tiers (below, same, and above), relative to a specified agent a. Say that two weak orders v1, v2 are 3-tier equivalent for a if belowa(v1) = belowa(v2), samea(v1) = samea(v2), and abovea(v1) = abovea(v2). The following equivalence states that two weak orders are equivalent according to Dominance iff they are 3-tier equivalent. The proofs of this result and of all subsequent ones are omitted due to space limitations.
Lemma 1. For all agents a and weak orders v1, v2∈ W(A), the following two properties are equivalent: 1. Dominance(a, v1, v2) and Dominance(a, v2, v1); 2. v1 and v2 are 3-tier equivalent for a.
We now introduce six self-interest axioms on a given preference relation P , based on the above three notions of basic improvement. For each notion, we propose a weak and a strong axiom, depending on whether they prescribe weak or strong preference. We break the symmetry only for Dominance ∧ Improvement. Specifically, we follow classical game theory where the notion of dominance alone implies weak preference and we reserve strong preference to the tighter condition Dominance ∧ Improvement. Same-context ∧ Improvement =⇒ P (v1, v2) Same-context ∧ Improvement =⇒ P (v1, v2) ∧ ¬P (v2, v1)
Dominance =⇒ P (v1, v2) Dominance ∧ Improvement =⇒ P (v1, v2) ∧ ¬P (v2, v1)
Swap =⇒ P (v1, v2)
Swap =⇒ P (v1, v2) ∧ ¬P (v2, v1)
Let T denote the set of the above six axioms, the following result characterizes the implications holding between the self-interest axioms in T .
Theorem 1. The only implications holding among the self-interest axioms in T are displayed in the Hasse diagram in Figure 1.
For a set of axioms T ⊆ T , we denote by Pref (T ) the set of preferences satisfying those axioms (a.k.a. the preference theory of T ). In the next section we investigate the relationships between the preference theories induced by different subsets of axioms. 3
SC SSC
Dom SDom
(SC) (SSC) (Dom) (SDom)
(Sw) (SSw) Sw SSw We claim that axioms SC and Sw are primitive and should Figure 1: Hasse diagram for implibe satisfied by any a-preference. This claim is supported by cation order between self-interest axthe observation that all “plausible” preferences that we have ioms. Lower axioms imply higher ones. been able to define satisfy those two axioms, starting with the Thick boxes denote axioms that prepreferences listed in Section 2.1. Therefore, in this section we scribe strong preference. study the set of all preference theories that refine Pref (SC, Sw).
Syntactically, there are 32 subsets of T that contain both SC and Sw. Those theories obviously refine Pref (SC, Sw). Figure 1 implies that all theories containing either Dom or SDom also refine Pref (SC, Sw). This adds 27 more sets to the count. As a matter of fact, it is easier to list the only five subsets of T that do not refine Pref (SC, Sw): they are ∅, {SC}, {Sw}, {SSC}, and {SSw}. Of the remaining 59 theories, we find that only nine of them are actually distinct, as stated by the following result and depicted in Figure 2.
Theorem 2. For all T ⊆ T , if Pref (T ) ⊆ Pref (SC, Sw) then Pref (T ) is equal to one of the nine canonical theories in Figure 2. Moreover, all of those theories are distinct and non-empty. Theorem 3. Let T1, T2 be two of the nine theories in Figure 2. It holds Pref (T1) ⊂ Pref (T2) if and only if there is a sequence of arrows going from T1 to T2 in Figure 2.
Define P dom as the pre-order on W(A) such that P dom(v1, v2) iff Dominance holds. The following theorem characterizes the preferences in the strongest theory in terms of P dom.
Theorem 4. A preference belongs to Pref (Dom, SDom) iff it refines and perfects P dom.
To appreciate the relevance of the previous theorem, notice that Lemma 1 tells us that all preferences satisfying the axiom Dom are 3-tier (that is, they do not distinguish between 3-tier equivalent weak orders). However, if Dominance establishes a strong preference between two weak orders, a preference satisfying Dom may instead equate those orders. For an extreme example, the degenerate preference P ≡ equates all weak orders, but it still satisfies Dom. Theorem 4 states that adding SDom to the picture forces preferences to uphold those strong preferences as well. Indeed, since preferences are total orders, a preference refining and perfecting P dom can only (and must) establish a preference among weak orders that are incomparable for P dom. P ≡, Pka {Dom} {SC, SSw} P >, P ⊥
{SSC, Sw} {Dom, SSw} P a, P a+s
{SSC, SSw} P >,⊥, P ⊥,>, P >,s {Dom, SSC}
{SDom} P a,s,> a
P a−b, P a,s, P a+s,a, P b+1 {Dom, SDom} This paper initiates an investigation about the rational behavior of self-interested agents participating in a competition whose outcome is a weak order among participants. Our preliminary results show an intriguing landscape of self-interest theories, most of which include simple preferences that are easily motivated by practical scenarios.
From the point of view of the competition designer, being able to pinpoint the likely preference theory adopted by the participants is valuable information because it allows the designer to predict the participants’ behavior during the competition. Generally speaking, the designer will want participants to act competitively, rather than indifferently or even cooperatively.
How to direct participants toward a specific theory or set of theories is a matter of future investigation, but some simple observations are already apparent. For example, the designer may announce that ties in the weak order will be resolved by a random linearization. In that case, cautious (that is, pessimistic) participants are likely to adopt preference P wst = P a, whereas optimistic ones may adopt P bst = P a+s. Both preferences lie in the theory {Dom, SSw}, and the presence of the axiom SSw ensures that an agent will act competitively whenever its actions may result in swapping its position with another agent that would otherwise finish higher up in the final ranking.
We also plan to investigate the case when the competition designer is able to assign monetary rewards to the participants, based on the weak order. Even if the assigned rewards do not break the ties in the order, they may still be able to influence the agents’ preferences simply by tuning the distance between different levels in the weak order.