JP7754592B2 - Systems and methods for ranking objects - Google Patents

Description

CROSS-REFERENCE TO RELATED APPLICATIONS
This application (corresponding U.S. application) claims priority under 35 U.S.C. 119 to French Patent Application No. FR2104801, filed May 6, 2021, the contents of which are incorporated herein by reference.

This application (corresponding U.S. application) further claims priority under 35 U.S.C. 119 to European Patent Application No. EP 21306565, filed November 8, 2021, the contents of which are incorporated herein by reference.

The field of the present invention is information retrieval and recommendation. More specifically, embodiments of the present invention relate to computer-implemented methods and systems for unbiased ranking of retrieved objects.

Information retrieval and recommendation generally consists of two steps: the first step focuses on searching a candidate set of multiple results, and the second step focuses on ranking the candidate set of multiple results.

The candidate set of results may include search results (e.g., a list of links to documents from search results in response to a query) and recommendations (e.g., a list of recommended points of interest in response to an identified location, or a list of recommended songs in response to a genre selection, etc.).

For example, for information retrieval, a query can be input to a first-step searcher, which processes the query (e.g., based on relevance) to retrieve a set of documents. A second-step or ranker (or reranker) then ranks the retrieved set of documents and outputs a ranked set of documents, which may be the same or smaller in number than the first set.

While users (e.g., content consumers) expect the most relevant results to be exposed, providers (e.g., content producers) seek fair (or impartial) exposure to their content. Therefore, in the second step, when ranking the candidate sets of results, it is desirable for the ranking method to maintain a balance between utility (representing users accessing the set of results) and fairness (representing providers composing the set of results).

While some ranking methods exist that maintain a balance between utility and fairness, the complexity of the methods generally prohibits their use in realistic scenarios. Thus, there is a continuing need for optimal methods with reduced complexity relative to existing methods (e.g., capable of computing an exact optimal solution), e.g., to enable web-scale fairness-utility ranking.

Korean Patent Registration No. 10-1710465

An exemplary method of the present invention provides a computer-implemented method for ranking a set of objects according to a first aspect, the method including the steps of receiving a set of objects and a set of objective functions; defining a decision space having n decision variables using a permutohedron, where n is the number of objects to be ranked and the vertices of the permutohedron represent permutations of exposure provided to objects in the set with corresponding ranks; determining a Pareto set for the set of objective functions; determining a Pareto optimal point within the Pareto set and using the decision space to determine a distribution over ranks for the objects in the set, where each rank and a ratio within the distribution are associated; selecting a sequence of ranks for the objects in the set from the distribution over ranks by ratio; and outputting the selected sequence of ranks.

A preferred, but non-limiting, embodiment of the method according to the first embodiment is as follows:

The set of multiple objective functions may include quadratic and linear functions;
The quadratic function may be a fairness function, and the linear function may be a utility function;
The fairness function may be a normalized difference, such as the L2-norm squared difference, between a vector composed of decision variables and a target vector,
The method may further include receiving a list of exposures to be provided to the objects in the set, each associated with a relevance score and a rank for each object in the set, a ranking fairness objective function, and a ranking utility objective function;
Determining a Pareto set for a set of multiple objective functions may include calculating a Pareto set in a decision space given a ranking fairness objective function and a ranking utility objective function; and using the decision space to determine a distribution over ranks for the objects in the set may include receiving specific points in the Pareto set that are translated into target exposures across the objects in the set in the decision space; and using the target exposures to determine a distribution over ranks that on average achieves the target exposures for the objects in the set, wherein each rank in the distribution over ranks corresponds to a vertex in the decision space;
The step of using the decision space to determine a distribution for ranks for the objects in the set includes determining a distribution for the number of objects in the set by:
(i) determining an arbitrary vertex of the decision space;
(ii) drawing a line starting from any vertex with the target exposure until the line intersects with a face of the decision space; and
(iii) repeating (i) and (ii) on the intersected face of the decision space using the new intersection point instead of the target exposure until the new intersected face becomes a vertex;
The fairness function can be based on meritocratic fairness or demographic fairness;
The step of determining a distribution for ranks of objects in the set using the decision space can use a GLS (Grotschel, Lovasz and Schrijver) procedure;
selecting a sequence of rankings for the objects in the set may include one or more of stochastic sampling, low-discrepancy sequences, additive-recurrence sequences, stride scheduling, or m-balancing;
An object in a set can contain multiple queries,
The objects in the set can be identified in response to a query;
An object in the set can contain multiple recommendations,
The objects in the set can be identified according to map location;
The outputting step may include providing at least a subset of the set of objects ranked according to the selected ranking sequence for display on a display of the device;
At least a subset of the set of objects may be provided on a search engine results page.

According to each of the second, third, fourth and fifth aspects, the present invention may provide a computer program product including code instructions that, when executed on a computer, cause the computer to perform a method according to the first aspect of the present invention; a computer-readable medium having the computer program product stored thereon; a data processing device including a processor configured to perform a method according to the first aspect of the present invention; and/or a system for information retrieval including a computer-implemented first step searcher configured to receive a query and generate a set of objects, and a computer-implemented second step ranker configured to rank the set of objects according to the first aspect of the present invention.

The accompanying drawings are incorporated herein to explain the principles of the embodiments. The drawings should not be construed as limiting the invention to the illustrated and described embodiments or to the manner in which they may be made and used. Additional features and advantages will become apparent in the following description and more particular section of the embodiments, as illustrated in the accompanying drawings.
FIG. 1 illustrates an example architecture capable of performing the disclosed methods. 1 is a flowchart illustrating one embodiment of the disclosed method. FIG. 10 shows an example of an exemplary permutohedron for n=4. FIG. 10 is a diagram showing an example of a procedure for decomposing a point in a permutohedron into a combination of up to n vertices of the permutohedron. FIG. 1 shows an example of an exemplary generalized permutohedron (referred to as an expohedron in the exemplary method) for n=3. FIG. 10 illustrates an example decomposition method intent code that can be used in some methods. FIG. 1 shows examples of equi-utility curves and max-utility solutions in expohedron (n=3). FIG. 1 shows an example of a maximum utility solution for an expohedron with relational ties (n=3). Figure 1 shows examples of optimal demographic and meritocratic fairness solutions and equivalent fairness curves in expohedron (n=3). Figure 1 shows examples of optimal demographic and meritocratic fairness solutions and equivalent fairness curves in expohedron (n=3). FIG. 10 shows an example of a Pareto set for expohedron (n=3). FIG. 10 illustrates intent codes for an exemplary Pareto set identification method.

1. Architecture The disclosed computer-implemented methods and embodiments for ranking objects can be implemented within an architecture (e.g., network or system architecture) such as that shown in FIG. 1 , which includes a server 100 and one or more client devices 102 communicating over a network 104 (wireless and/or wired), such as the Internet, for exchanging data. The server 100 and the client devices 102 include a data processor 112 and memory 113, such as, but not limited to, random access memory (RAM), read-only memory (ROM), a hard disk, a solid-state disk, or other non-volatile storage medium. Additionally, the memory 113 can be provided in whole or in part by external memory or storage in communication with the data processor 112. The client devices 102 can be any device in communication with the server 100.

The exemplary methods provided herein may be implemented by a processor, such as data processor 112 or other processors in server 100 and/or client device 102. Data processor 112 may include a single processor or multiple processors operating in serial or parallel. Memory used in the exemplary methods may be implemented, for example, by memory 113 and/or suitable storage within server 100, client devices 102b-102e, connected remote storage, or any combination. Memory may include one or more memories or memory elements or structures, including a combination of memory types and/or locations. Data in memory may be stored in any suitable format for data retrieval and processing.

Server 100 may include, but is not limited to, a dedicated server, a cloud-based server, or a combination thereof (e.g., shared). Data streams may be communicated/communicated to, received/received by, or generated by server 100 and/or client devices 102b-102e.

Client devices 102b-102e may be any processor-based device, terminal, or the like, or may be embodied as a client application executable by a processor-based device, etc. The client devices may be located within server 100 (locally, remotely, or any combination), or may be located outside the server and communicate with the server. Exemplary client devices 102b-102e include, but are not limited to, various processor-based devices not shown in FIG. 1, such as autonomous vehicle 102b, robot 102c, computer 102d, and mobile communication devices (e.g., smartphones, tablet PCs, etc.) such as smartphone 102e, as well as virtual reality (VR), augmented reality (AR) or mixed reality (MR) devices, wearable computers, etc. Client devices 102b-102e may, but are not necessarily, configured to transmit/receive data to/from server 100 and may include one or more output devices such as, but not limited to, a display, speaker, printer, etc. for displaying, presenting, or printing the results of a particular method provided for display by the server. A client device may include a combination of client devices.

2. Method for Ranking a Set of Multiple Objects The exemplary method provided herein solves the problem of efficiently designing an optimal fairness-utility ranking policy using a set of optimization/decision variables. A first feature of the exemplary method is to select as an optimization/decision variable the key objectives that constitute the ideal ranking, in particular the "listing exposure" variable, which serves as the core link between the utility objective, which typically represents the user or consumer's perspective, and the fairness objective, which typically represents the provider or supplier's perspective.

Advantageously, a second feature of the exemplary method is a generalized permutohedron, which allows optimization problems to be expressed in a decision space with only n decision variables (where n is the number of objects to be ranked), while maintaining policy expressibility for precise and complete control of utility and fairness objectives. The vertices of the disclosed exemplary permutohedron can indicate exposures associated with corresponding rankings; such permutohedrons are referred to herein as "expohedrons." Any distribution (or convex combination) of rankings (or, synonymously, permutations) through the decision space provided by the permutohedron (e.g., expohedron) can be represented, and geometric reasoning can be used to resolve utility-fairness tradeoffs in this space. In particular, the entire Pareto set of a multi-objective optimization (MOO) problem can be easily obtained without explicit scalarization techniques, thereby reducing required processing time and resources.

The exemplary method can determine optimal policies using unbiased estimates of relevance scores with uniform estimation quality for objects and exposure models with known structure and parameters.

Exemplary methods operate with O(n ² log n) complexity. Such methods are amenable to geometric reasoning. Most steps of the methods can be expressed by closed-form equations. Other steps of the methods can be provided by ordering operations. Also, the global Pareto set can be generated analytically and geometrically, without relying on scalarization techniques that scan the global boundary, for example.

FIG. 2 is a flowchart illustrating one embodiment of the disclosed method for ranking a set of objects. The method according to the embodiment of FIG. 2 is performed by a server 100, and the exemplary method is described in connection with the server 100. However, it should be understood that the method may equally be performed by a client device 102, or by a combination of the server 100 and the client device 102.

In step 202, server 100 receives, from any suitable source(s), including external and/or internal sources, a set of objects, a (e.g., unbiased) relevance score for each object in the set of objects, a list of exposures, each associated with a rank, and objective functions, including a ranking fairness objective function and a ranking utility objective function. In step 204, server 100 defines a decision space using a permutohedron with n decision variables, where n is the number of objects to rank, and the vertices of the permutohedron indicate permutations of exposures to be provided to the objects in the set with corresponding ranks.

In step 206, using the ranked fairness objective function and the ranked utility objective function, server 100 calculates a Pareto set (i.e., a set of non-dominated solutions for which there are no better solutions for all objective functions, e.g., no exposures that simultaneously provide greater utility and greater fairness) within the decision space defined by the list of exposures between the first point exhibiting optimal fairness and the second point exhibiting optimal utility. From an exemplary method, optimal fairness types can include, for example, demographic fairness and meritocratic fairness. As described below, ideal exposures for demographic fairness allow for equal exposures, whereas for meritocratic fairness, exposures can be defined based on relevance (e.g., using a relevance vector). In other embodiments, the optimal fairness type can additionally or alternatively be customized based on a predetermined ratio different from fairness (e.g., to allocate prize money).

An exemplary fairness typology considers individual fairness as opposed to group fairness. While individual fairness seeks to ensure fairness from the level of individual objects, group fairness assumes that objects are associated with groups and fairness is ensured from the group level, typically preventing some groups from being disadvantaged.

In step 207, server 100 outputs the Pareto set to a decision maker (internally or externally). In step 208, server 100 receives (internally or externally) the points of the Pareto set, which are converted to target exposures in the decision space. This target exposure corresponds to the exposure across the objects in the set. In one embodiment, the target exposure is defined by a decision maker, internal or external to server 100, who sets a defined utility/fairness trade-off, which is set with case-by-case or general fixed constraints (e.g., setting a constraint that fairness does not fall below a predefined threshold). In some embodiments, the decision maker can be a human administrator. In other embodiments, the decision maker can be an automated system. A combination of a human administrator and an automated system can also be used.

In step 210, using the target exposure received by the decision maker as the optimal tradeoff from the Pareto set, the server 100 determines a distribution for ranks (e.g., a set of weighted ranks) that will, on average, achieve the target exposure for the objects in the set, where each rank in the distribution for ranks corresponds to a vertex in the decision space. In one embodiment, determining the distribution for ranks can be performed as follows: (i) an arbitrary vertex of the decision space is determined; (ii) a line is drawn (e.g., calculated) starting from the arbitrary vertex with the target exposure received from the decision maker until the line intersects with a face of the decision space; (iii) steps (i) and (ii) are repeated on the intersected face of the decision space, substituting the decision maker's target exposure for the intersection point, until the newly intersected face becomes a vertex. Steps (i) through (iii) can be performed for as many objects in the set, with the intersection point in step (iii) being a vertex. Each vertex of the decision space has an associated ratio.

In step 212, the server 100 distributes the distribution of ranks by selecting a sequence of ranks for the set of objects from the distribution of ranks according to their ratios.

In other embodiments, as previously described, the method according to the embodiment of FIG. 2 may be performed partially or completely from the client device 102. In still other embodiments, the method may be performed on different servers or client devices or multiple servers in a distributed manner.

In one exemplary embodiment, a non-personalized query (e.g., a query generated by an anonymous user) is repeatedly received for general points of interest from a predefined map location. In this exemplary embodiment, the set of objects may be a list of general points of interest, such as restaurants, museums, stores, and gas stations. In another exemplary embodiment, a non-personalized keyword query is repeatedly received by a search engine. In this exemplary embodiment, the set of objects may be a list of links to documents, such as web pages. Repeated such queries over time result in a varying order of the set of objects, with each ranking sequence achieving target exposure.

In step 212, based on the selected ranking sequence, one, all, or a subset of the set of objects may be presented in a search engine results page (SERP), e.g., forwarded to an external or internal device for presentation (e.g., display, publication, printing, importing, exporting, saving, etc.). For example, a SERP including one, a subset, or all of the objects (each positioned based on the determined ranking within the selected sequence) may be generated and forwarded to the server 100 or the client device 102 for display on a display. If one or a subset of the objects is presented in the SERP instead of all objects, such presented objects may be, for example, objects that each have a higher ranking in the selected sequence than other objects in the set of objects.

3. Exposure (display)
In the field of information retrieval (IR), exposure, also known as "attention" or "examination," can be defined as the probability that a user examines an object (such as, but not limited to, a document) at a particular location on a search engine results page (SERP). Exposure values (e.g., forming part of the list of exposures received in step 202(iii) of FIG. 2) can be captured by methods such as, but not limited to, eye-tracking studies or arbitration collection (e.g., placing the same document in two different rankings for the same query). Exposure values can also be determined by methods using "click models" (i.e., user browsing models) known in the field of information retrieval (e.g., as disclosed by Chuklin et al. in "Click models for web search" (Synthesis Lectures on Information Concepts, Retrieval, and Services, 7(3):1-115, July 2015). For the most part, such models attempt to explain clicking behavior through a natural sequence of two steps: first, inspect (or pay your attention to) a list or its representative snippets, and then click on it if it is interesting.

From the consumer's (i.e., user's) perspective, the consumer desires that more relevant objects receive higher exposure in order to avoid wasting time searching for relevant objects in obscure locations in the SERP. This consumer desire can be expressed in an exemplary manner by defining the ranking utility as the dot product between an exposure vector (i.e., a vector composed of the exposure values provided by the ranking for each object) and a gain vector (i.e., a vector composed of the gain of each object, where the gain of an object is defined by an arbitrary monotonically increasing function of the object's relevance score). Known information retrieval utility measures, such as, but not limited to, Discounted Cumulative Gain (DCG) and Expected Reciprocal Rank (ERR), reflect this formula along with a specific selection of exposure model parameters. For example, DCG assumes that the exposure of an object from rank (k) is given by 1/ _log2 (1+k), and the gain function g(d) is given by g(d) = ^2rel(d) , where rel(d) is the relevance score of d. ERR measurement is based on a cascade model, assuming that exposure varies depending on the relevance of the previous object in the list; in particular, if a user is satisfied with an object, the exposure of the next object in the list will be 0.

From a provider's perspective, they would like their objects to have higher exposure in the SERP. However, because there are so many providers, non-disparate treatment of the objects offered to users is desirable.

The consumer and provider perspectives, corresponding to the "utility" goal and "fairness" criterion, respectively, can both be expressed in terms of "exposure" in the exemplary methods disclosed herein. Exposure serves as a link between the ideal ranking goal, i.e., the utility goal (e.g., representing the user or consumer's perspective) and the fairness criterion (e.g., representing the object provider or supplier's perspective).

4. Permutohedron
An exemplary permutohedron is a polytope, where each vertex corresponds to a particular ranking or permutation of n objects (e.g., documents), and the polytope is a convex hull of such vertices. This polytope is contained in n-dimensional space, but is actually (n-1)-dimensional. For example, FIG. 3 shows a three-dimensional object 300 for n=4 objects, which appears like a sphere with a mixture of hexagonal and square facets. Consider vertex 4312 in 302. This indicates a ranking that places _d1 at rank 4, _d2 at rank ₃ , d3 at rank 1, and _d4 at rank 2. Further consider edge 306 connecting vertex 4312 in 302 with vertex 3412 in 304. This indicates an arbitrary distribution (or convex combination) of the two rankings.

Also, all facets of the three-dimensional object 300 represent a partial ordering of the n objects into two groups. For example, facet 308 containing vertices (4312), (3412), (2413), (2314), (3214), and (4213) indicates a partial order in which _d3 is always first (i.e., _d3 @ order 1) and can be followed by three other documents in any order; facet 310 containing vertices (3214), (2314), (1324), (1234), (2134), and (3124) indicates a partial order in which _d4 is always last (i.e., _d4 @ order 4) and can be preceded by three other documents in any order; square facet 312 containing vertices (2413), (1423), (1324), and (2314) indicates a partial order in which _d1 and _d3 can be in any order for the first two positions and _d2 and _d4 can be followed in any order for the last two positions (i.e., (d2 and _{d4 )} ) before (d ₁ and d ₃ ).

In general, each facet of dimension (n−k), which generalizes the concept of facets along a hierarchy of decreasing dimensionality (e.g., facet → edge → vertex for n=4), represents all possible distributions (or convex combinations) associated with a given partial ordering of n objects into k groups. Also, as shown in FIG. 3, the edge 306 connecting the vertex (4312) in 302 with the vertex (3412) in 304 corresponds to the following partial ordering: d ₃ first, d ₄ second, d ₁ and d ₂ follow in any order.

5. Decomposition According to Caratheodory's theorem, a set consisting of m points (v _i ) contained in d-dimensional space

Any point in the convex hull of can be decomposed into a convex combination of at most (d+1) of these points.

Considering the permutohedron as a special case, any point on the permutohedron (which is a d-dimensional object with d = (n-1), where n is the number of objects) can be decomposed into distributions for up to n ranks. In one embodiment, a procedure known as the GLS procedure (Grotschel, Lovasz, and Schrijver) can be used to determine one such decomposition (although generally, more than one decomposition is possible). An example of the GLS procedure (see Grotschel et al., "Geometric Algorithms and Combinatorial Optimization," Springer Science & Business Media, published December 2012) is illustrated in Figure 4, which shows an n = 3 polytope applied to the method disclosed herein.

Figure 4(a) shows a point (x) to be decomposed at 402. As shown in Figure 4(b), the procedure begins by selecting an arbitrary vertex (v ₁ ) at 404 of polytope 400 (n=3) and extending a line segment from v ₁ towards x (the point to be decomposed 402) until it intersects with a face of dimension (n-2). This provides a new point (x'), where x is expressed as a convex combination of v ₁ and x' (i.e., x = λ ₁ v ₁ + (1-λ ₁ ) x').

As shown in Figure 4(c), a point (x') on an (n-2)-dimensional surface can be decomposed using the same procedure by selecting an arbitrary vertex (called _v2 ) belonging to the x' surface and extending the line segment ( _v2 -x') until it intersects with a surface of dimension (n-3). In the example shown in Figure 4(c), since n=3, this surface is vertex ( _v3 ), and the procedure stops at this point, with the initial point (x) being represented as a convex combination of three vertices (i.e., x= _λ1v1 +( ₁ - _λ1 ) _λ2v2 +(1- _λ1 )(1- _λ2 ) _v3 ). In general, the higher _the value of n, the more times this recursive step is repeated, each time considering surfaces of decreasing dimension until a surface (i.e., a vertex) of dimension (0) is reached.

6. Notation Describing the exemplary ranking method described herein in more detail, the following notation is used to formally describe features of the exemplary method:
a) q is a query repeated infinitely by a single (e.g., anonymous) user (e.g., consumer); the query need not be a text query in the general "information retrieval" sense, but should be understood in a broad sense; for example, the query can also include any trigger context in a "recommendation" setting.

b) For a query (q), there is a fixed candidate set of n objects (e.g., documents, points of interest (POIs), recommendations, etc.), D = (d ₁ ,...,d _n ), where the relevance score for query (q) is denoted by ρ = (ρ ₁ ,...,ρ _n );
c) A ranking policy (π(q)) is a distribution (e.g., a convex combination) over m ranks, m<=n σ _i (i = 1,...,m):

where each rank (σ _i ) maps each object (d _j ) to a rank (σ _i (d _j )). The use of a distribution for up to n ranks (m<=n) is a consequence of Carathéodory's theorem in the permutohedron as used in the exemplary method. As will be explained below, a ranking policy (π(q)) can be distributed to a sequence of ranks as close as possible to the ratios provided by the α _i coefficients. The goal is to find an optimal set of policies (π(q)) in conjunction with a multi-objective optimization problem that includes utility and fairness criteria.

7. Optimizing Ranking Policies An exemplary method can use a ranking policy, denoted herein as π(q), that is useful and fair by expressing everything (e.g., utility for consumers and fairness for providers) in terms of a single set of decision/optimization variables, referred to herein as "control levers." The control levers are:

We define an exposure vector, denoted as: where is the number of objects in the image. This vector is indexed by object (the first component corresponds to document (d ₁ ), etc.). This means that instead of working directly in a decision space defined using a permutohedron, where vertex coordinates indicate rank, the disclosed method can use a modified polytope, referred to herein as an expohedron, where vertex coordinates indicate the exposure associated with the corresponding rank. In other words, the vertices of the expohedron indicate the permutation of exposure provided to objects with the corresponding rank. While there may be a one-to-one correspondence between permutohedrons and expohedrons, the expohedron directly points to the control lever space (i.e., the decision space).

Further referring to the exposure vector denoted by: the ranking policy is a distribution over up to m rankings (m<=n),

where:

is the vector of exposure that rank (σ _i ) provides to the object.

Such optimization problems can be expressed as multi-objective optimization problems. A Pareto set (i.e., the set of feasible non-dominated solutions) can be determined by geometric reasoning. A particular tradeoff in this determined Pareto set can then be selected or determined, for example, by a decision maker, where the tradeoff is a single target point (i.e., target exposure) in the decision space. This point can be decomposed as a convex combination of up to n ranks, as known from Carathéodory's theorem mentioned above.

Once such combinations are determined, they (i.e., the ordering of the set of objects from the distribution relative to the rank) can be distributed using a fair scheduling strategy, which in one embodiment uses a low-discrepancy sequence such as a golden ratio low-discrepancy sequence (see "Weighted Round Robin (Weighted Random Integers) Using the Golden Ratio Low Discrepancy Sequence," published on the Internet at demofox.org in June 2020). Those skilled in the art should understand that other scheduling strategies can be used in alternative embodiments, such as, but not limited to, m-balanced word or similar algorithms similar to stride scheduling.

An advantage of the exemplary methods is that they can perform various steps, or most of the steps, using geometric reasoning, which in practice leads to simple algebraically closed-form solutions. An additional advantage of the exemplary methods is that they offer a time complexity of O(n ² log(n)). Another advantage of the exemplary methods is that they operate in n-dimensional space instead of, for example, n _! -dimensional space or n2 ^- dimensional space. As a result, the number of decision/optimization variables used by the exemplary methods is no greater than n, which allows any optimal solution to be realized as a distribution over up to n ranks.

An exemplary method can be provided for a general type of exposure model referred to as a "Position-Based Model" (PBM). This type of model assumes that an object's exposure depends only on its rank. Each rank (k) is then associated with a parameter (γk), which indicates the probability that this rank will be inspected by a user. Other types of models can be processed using the exemplary method.

8. Expohedrons Associated with PBM Models In an embodiment, the exemplary method uses a fixed set of n parameters.

We use a PBM typological exposure model characterized by: Without loss of generality, we assume that γ _k are sorted in descending order. This does not necessarily mean that the inspection probability decreases with rank, although this often occurs in practice. In this model, the sum of the exposures of objects (e.g., documents) in the ranked list is always the same,

A specific example of an expohedron for n=3 is shown in Figure 5. Since the sum of the exposures is constant in the exemplary method, the exemplary expohedron lies in a plane contained in 3D space. Figure 5 shows the projection onto that plane.

Any point within the expohedron shown in Figure 5 represents a specific exposure vector, which can be realized with up to three different permutation or rank distributions. The centroid 502 of the hexagon 500 corresponds to the same exposure (i.e., demographic fairness) to each object (e.g., document), but can be realized as a uniform distribution across the three different ranks.

There is a simple mathematical method to determine whether a point belongs to an expohedron, and this method will be utilized as an exemplary method described herein. In mathematics, this is known as the majorization condition, and when ∈ is majored by γ (which means that

), and only if the point

This defines that belongs to the expohedron.

The mathematical definition of primalization is as follows:

and

and x↓ is a vector with the same components as x, but sorted in descending order.

As used herein, a "region" is defined as a set of points with coordinates (i.e., exposures) in the same order. More specifically, such points can correspond to vectors such that the indices of their components, sorted in ascending order, are identical. For example, in Python, this corresponds to arrays in which the output of the argsort function is the same. An expohedron has as many regions as vertices, with each region containing only one vertex. An exemplary region can be viewed as an unbounded pyramid, with its vertices being its centroid and its semi-axes corresponding to the lines connecting the expohedron's centroid to the centroids of each facet adjacent to a unique vertex that the region contains.

Given a point in the expohedron's decision space with coordinates provided by
Define the utility of a ranking policy (π(q)) in this decision space;
Define different fairness measures for ranking policies in this decision space;
Determine the Pareto set (a set of non-dominated policies) for multi-objective optimization (MOO) problems to maintain a balance between utility and fairness;
decomposing the decision maker's specific choice of target exposure for this Pareto set as a distribution over up to n ranks;
An efficient and effective scheduling strategy distributes distributions for up to n ranks.

9. Utility in PBM-Expohedron An exemplary utility criterion specifies that objects with high relevance scores, or more generally high gain, should have higher exposure. Without loss of generality, ρ is

is defined as the vector of gains (or relevance scores, if the gain function is chosen as identity) normalized in the same units as the constant exposure vector for a given PBM, in the sense that ρ lies on the same hyperplane as the exposure vectors, and they can be directly compared, constructed, or visualized jointly on a projected expohedron.

Utility can be expressed, for example, as the dot product between the relevance vector and the exposure vector:

As a result, in expohedron, the equivalent utility surface is the hyperplane with the same normal as ρ for hyperplanes 702, 704, and 706, as illustrated in Figure 7. The definition of utility corresponds to the payoff function as 2 ^relevance and the ^standard Discounted Cumulative Gain (DCG) definition for the utility of information retrieval for a particular choice of exposure parameters, i.e.:

is.

Given this mathematical expression of utility, the expohedron's maximum utility ranking policy is its projection onto ρ, i.e.,

The search can be performed using the point (∈) (or in some example methods, a set of points) located on the face of the expohedron where ρ is largest (see, for example, point 708 on face 710 in FIG. 7). To find this maximum utility ranking, one need not project all points of the expohedron, but only those vertices in the same domain as ρ, which requires a single alignment. This is the same formulation as the probability ranking principle for information retrieval (see Stephen Robertson, "The Probability Ranking Principle in IR," Journal of Documentation, 33:294-304, December 1977).

When the relevance vectors have ties (i.e., when at least two elements of the relevance vectors are the same), the overall surface 802 constitutes the set of maximum utility solutions, as shown in Figure 8 with ties (as shown by the relevance vector [0.7, 0.7, 0.4]).

10. Fairness in PBM-Expohedron An exemplary fairness criterion is expressed in the expohedron framework. The individual demographic fairness criterion specifies that ideally, all objects (e.g., documents) should have the same exposure. Since the sum of exposures is a constant, this means that the target exposure of the demographic fairness policy is the centroid of the expohedron:

Therefore, the fairness criterion can be defined as a quadratic function, e.g., proximity (or distance reduction) to the center of gravity:

Considering meritocratic fairness, the ideal exposure vector should be proportional to the relevance vector or merit vector, commonly denoted ρ', where the merit of an object is defined as a monotonically increasing function of this object's relevance score or, equivalently, its gain (

(In the sense that when working with merit vectors normalized to the same units as the exposure vectors, the proportionality constant is now the same as 1.) ρ and ρ' lie in the same domain due to the monotonically increasing relationship connecting them. ρ and ρ' can be chosen to be identical and be the same as the relevance score vector (i.e., the payoff and merit functions are chosen as identity functions), although this need not be the case. Formally, the meritocratic fairness of a policy with exposure (∈) can be defined as a quadratic function, e.g., its proximity (or distance reduction) to the normalized relevance vector:

In an expohedron (n=3) 900 as shown in Figure 9, where ρ and ρ' are chosen to be equal, for demographic fairness 902 and meritocratic fairness 904, the equivalent fairness surface is a hypersphere centered at β or ρ, and the equivalent fairness curves for optimal demographic and meritocratic fairness are circles surrounding the optimal fairness points 902, 904, respectively, where vector 906 is the relevance vector.

If the merit vector is outside the expohedron, i.e.,

(i.e., the main condition is not satisfied). In this case, we can relax the pure proportional relationship to an affine relationship, with the offset being as small as possible while still remaining in the expohedron (e.g., the fairness definition expressed in [Biega et al., "Overview of the TREC 2019 Fair Ranking Track", arXiv:2003.11650, March 2020] and [Diaz et al., "Evaluating Stochastic Rankings with Expected Exposure", Proceedings of the ^29th ACM International Conference on Information & Knowledge Management, pages 275-284, October 2020]). This is similar to selecting a target vector that lies at the intersection of the merit vector axis and the expohedron boundary.

Figure 10 shows an example where the optimal point 1004 identified by the merit vector 1002 is outside the expohedron 1000 and is therefore infeasible. This new feasible target vector is displayed at point 1006. This can be calculated as follows:

It is expressed as:

The intersection of the relevance vector axis and the expohedron boundary is the normalized advantage.

(referred to as "Affine Transformation" in FIG. 10):

and this is

and expresses that b is the smallest value that guarantees the condition ∀k <n;

and this is

This expresses that...

An alternative solution to the affine transformation for selecting a viable meritocratic fairness point is to compute an orthogonal projection, the results of which for the example shown in Figure 10 are displayed at point 1008.

11. Pareto Sets in PBM-Expohedron Once we determine how to compute and optimize utility and fairness separately, we can compute the complete Pareto set of a multi-objective utility-fairness problem.

To explain the method intuitively and geometrically, an exemplary computational method starts from one extreme of the Pareto set, i.e., the "totally fair" solution. Then, to draw (e.g., compute) the entire Pareto set, we (computationally) follow the payoff vector direction. It turns out that all these points are not dominated by other points in the expohedron and correspond to the optimal tradeoff between fairness and utility. If we always follow the payoff vector direction, the boundary of the expohedron will necessarily intersect at a certain point, meaning the solution is no longer feasible. Next, we (computationally) follow the payoff vector direction projected onto the directly intersected (n-2)-dimensional facet. Following this new direction results in a new facet, now (n-3) dimensional, being intersected, and we once again follow the payoff vector direction projected onto the new facet. Finding the projection of the payoff vector on any facet corresponds to a closed-form expression. This path-tracing procedure is computationally repeated again until we finally arrive at a non-dominated maximum-utility solution. Every point along the path corresponds to a strongly non-dominated solution of the utility-fairness trade-off; in other words, the path is a Pareto set.

The path-tracing procedure described above is illustrated in FIG. 11 for n=3 and the gain and merit functions chosen as identity functions (i.e., a document's merit and gain are the same as its relevance score). Pareto sets are defined from 1102 to 1110 when the demographic fairness criterion is used, and from 1106 to 1110 when the meritocratic fairness criterion is used. When the demographic fairness criterion is used, the Pareto set starts from the graph's centroid 1102, follows the direction of line segment 1104 (which is the gain vector axis), passes through meritocratic fairness point 1106 on the graph, intersects with edge 1108, or facet, corresponding to the mixed ranking where objects (e.g., documents) _d1 and _d2 are initially permuted in two ranks, and then follows this facet until it reaches the maximum utility solution, represented on the graph by star 1110. When the meritocratic fairness criterion is used, the Pareto set should start from point 1106.

More formally, the Pareto optimal set is i = 1,...,(n-1),

of

Next, without loss of generality and for notational simplicity, let us assume that the objects (e.g., documents) are ordered by decreasing payoff, i.e., ρ ₁ >= ρ ₂ >=...>= ρ _n.

Assume that the initial position is aligned to

is either β or ρ' depending on whether demographic or meritocratic fairness is considered (

(It is not possible to substitute for .) In constructing the Pareto set, the points are always located in the same region (i.e., the region of the maximum utility or PRP vertex; note that since every region has a centroid at the vertex, the centroid belongs to every region). The reason is that the order of the components of the corresponding exposure vector does not change when projected onto the surface if a vector in the direction of the payoff vector is incrementally added to such exposure vector.

One example of a Pareto set construction method is illustrated in Figure 12 as an intention code. More specifically, Figure 12 illustrates an intention code for Pareto set identification, which (without loss of generality) is a payoff vector.

A vector of PBM parameters (γ) associated with each rank and the initial point

Suppose that the are in an ordered storage region, sorted from highest to lowest value.

12. GLS Decomposition in PBM-Expohedrons As described herein, for example, a point in the Pareto set that can be selected by a decision maker can be transformed into a target exposure in the decision space. This point in the Pareto set can be decomposed into a convex combination of up to n ranks. To address this decomposition problem, an exemplary method specializes the general GLS procedure described above and applies it to the construction of the expohedron polytope.

One example of how to achieve decomposition is illustrated as the code in Figure 6. The decomposition method in Figure 6 takes advantage of the fact that if a point is on a facet (or a plane of lower dimensionality), then vertices on this facet (or plane) can be found by selecting the vertices of the region in which the point is located (this can be done by sorting the components of the point) (see line 5 in Figure 6). Note that this step has a complexity of O(n log n).

The exemplary method in line 9 of FIG. 6 searches for a point by extending the v ⁽ⁱ⁾ → x ⁽ⁱ⁾ line segment until a facet (i.e., a surface) is reached, and this intersection point (x ⁽ⁱ⁺¹⁾ ) defines a new point for recursive decomposition. In each iteration of the loop, the new point (x ⁽ⁱ⁺¹⁾ ) is on a surface of dimension (n-i), meaning that the final point is always a vertex (dimension = 0). Since searching for an intersection point is the same as searching for the root of a "majorization" condition (i.e., the point where the condition value goes from true to false), line 9 of FIG. 6 uses the majorization criterion to apply a bisection method (i.e., a numerical method for searching for the root of a provided function) to determine when to stop the method. The majorization criterion can also be used to search for an efficient upper endpoint at the intersection with the surface (λ) (here, efficient upper endpoint is used herein to mean "not too far from the true intersection point"). This endpoint calculation is performed in lines 6 through 8 of FIG. 6.

The bisection itself has a number of iterations (e.g., 5-10 iterations) that is independent of n. Checking the majorization condition within the bisection requires O(n log n) complexity, so the overall complexity of the method is O(n ² log n).

13. Policy Distribution with Low Discrepancy Sequences When target exposures are decomposed into rank-order distributions, any of a variety of methods can be used, alone or in combination, to distribute the distributions in the form of rank sequences.

For example, stochastic sampling (i.e., a random number generator) can be used to distribute the distribution for the ranks. In other embodiments, low-discrepancy sequences can be used (see, e.g., Martin Roberts, "The unreasonable effectiveness of quasirandom sequences," Apr 2018).

A low discrepancy sequence (LDS) is provided such that the subsequences of ranks _R1 , _R2 , ..., _Rt for all t have low discrepancy (i.e., the ratio of ranks is close to the desired ratio, i.e., the ratio of infinite sequences). A low discrepancy sequence is typically a quasi-random sequence in the interval [0, 1] that is as close as possible to a uniform distribution, and such a floating-point sequence in [0, 1] can be converted into a ranked sequence with the desired ratio by comparing the generated floating-point with the cumulative value of the ratio.

The use of additive-recursive sequences based on irrational numbers (referred to as Kronecker, Weyl, or Richtmyer sequences) can be used in embodiments, particularly for the golden number, which is in some sense the most irrational number. The general recursive form of the sequence is as follows:

, which is the value that achieves the best discrepancy for the additive-recursive sequence class of LDS.

A range of efficient sampling strategies other than low-discrepancy sequences can alternatively or additionally be used. For example, stride scheduling or equivalently m-balanced word-based strategies can also be used, providing very similar performance.

Expressed in terms of an example problem, the m-balanced word generator generates a sequence of ranks from any pair of subsequences of the same length, where the frequency of any rank varies by at most m. In other words, the generator ensures that the generated sequence produces ranks with a ratio as close as possible to the target ratio. While not wishing to be bound by theory, the theoretically best achievable m is at most n-1 in the example case. An example algorithm that can efficiently generate an m-balanced sequence of ranks, given a specific distribution of ranks, is provided in Algorithm (1) of the reference [Shinya Sano, Naoto Miyoshi, and Ryohei Kataoka. 2004. m-Balanced words: A generalization of balanced words. Theoretical Computer Science 314, 1-2 (Feb. 2004), 97-120. https://doi.org/10.1016/j.tcs.2003.11.021]. This generator is similar to known stride scheduling algorithms used to generate fair sequences in resource (CPU) management for concurrent processes, for example as described in the literature [C.A. Waldspurger and E. Weihl. W. 1995. Stride Scheduling: Deterministic Proportional-Share Resource Management. Technical Report. Massachusetts Institute of Technology, USA].

14. Computer Program Product The exemplary method described for ranking objects may be provided as a computer program product, which may include code instructions for executing the method (e.g., using the data processor 112 of the server 100 and the client device 102), and storage means readable by computer equipment provided with the computer program product (e.g., using the memory 113 of the server 100 and the client device 102) for storing such code instructions.

15. General The foregoing description is merely exemplary in nature and is not intended to limit the present disclosure, its application, or uses. The broad teachings of the present disclosure can be embodied in a variety of forms. Accordingly, while the present disclosure includes specific examples, the true scope of the present disclosure should not be limited thereto. This is because other variations will become apparent upon study of the drawings, the specification, and the claims. It should be understood that one or more steps within a method may be performed in a different order (or simultaneously) without altering the principles of the present disclosure. Also, although each embodiment is described above as having certain features, any one or more of these features described in connection with any embodiment of the present disclosure may be embodied/embodied with or combined with features of any other embodiment, although such combinations are not expressly stated. In other words, the described embodiments are not mutually exclusive, and permutations of one or more embodiments with each other are within the scope of the present disclosure. Any references cited herein are incorporated herein by reference in their entirety without any admission that such references constitute prior art.

Each module may include one or more interface circuits. In some examples, the interface circuits may include wired or wireless interfaces connected via a local area network (LAN), the Internet, a wide area network (WAN), or a combination thereof. The functionality of any provided module in this disclosure may be distributed across multiple modules connected by interface circuits. For example, multiple modules may allow for load balancing. In other examples, a server (remote or cloud) module may perform some functionality on behalf of a client module. Each module may be embodied using code. The term code, as used herein, may include software, firmware, and/or microcode and may refer to programs, routines, functions, classes, data structures, and/or objects.

Memory circuits herein are a subset of computer-readable media. Computer-readable media herein do not include transient electrical or electromagnetic signals propagated through a medium (e.g., on a carrier wave); therefore, computer-readable media can be considered both a type and a non-transitory type. Non-limiting examples of non-transitory and types of computer-readable media include non-volatile memory circuits (e.g., flash memory circuits, erasable programmable read-only memory circuits, or masked read-only memory circuits), volatile memory circuits (e.g., static random access memory circuits, dynamic random access memory circuits), magnetic storage media (e.g., analog or digital magnetic tape or hard disk drives), and optical storage media (e.g., CDs, DVDs, or Blu-ray discs).

The systems and methods described in this application may be implemented, in part or in whole, by a special-purpose computer created by configuring a general-purpose computer to perform one or more specific functions embodied in a computer program. The functional blocks, flowchart components, and other elements described above serve as software specifications that can be converted into a computer program by the routine work of a skilled engineer or programmer.

A computer program includes at least one processor-executable instruction. A computer program may also include or rely on stored data. A computer program may include a basic input/output system (BIOS) that interacts with hardware in a special-purpose computer, device drivers that interact with specific devices in a special-purpose computer, one or more operating systems, user applications, background services, background applications, etc.

Variations of the above-described embodiments and other features and functions, or alternatives thereof, can be preferably combined in many different systems or applications. It should be understood that various presently unforeseeable alternatives, modifications, variations, or improvements may subsequently be made by those skilled in the art and are within the scope of the foregoing description and the following claims.

Claims (23)

1. A computer-implemented method for ranking a set of objects, comprising:
a processor of the computer receiving the set of objects and a set of objective functions;
the processor using a permutohedron associated with a position-based model (PBM) to define a decision space having n decision variables, the decision variables being variables to be optimized for ranking the exposure of objects corresponding to information search results, the decision space being a space defined by the decision variables, n being the number of objects to be ranked;
determining a Pareto set corresponding to a multi-objective optimization (MOO) problem for the set of multiple objective functions, the Pareto set being a path from a centroid of a facet determined based on a convex combination of associated exposure rankings from the decision space, intersecting edges and reaching a vertex of the facet, the determining step being determined using geometric reasoning;
the processor using the decision space to determine a distribution for ranks for the objects in the set using a GLS (Grotschel, Lovasz and Schrijver) procedure, with Pareto points in the Pareto set, wherein a coefficient is associated with each rank in the distribution;
the processor selecting a set of ranks for the objects in the set from a distribution for the ranks by a coefficient , wherein selecting a set of ranks for the objects in the set includes using one or more of stochastic sampling, low discrepancy sequences, additive repeat sequences, stride scheduling, or m-balance;
the processor outputting the selected set of rankings; and
the processor receiving a list of exposures to be provided to the objects in the set, each associated with a relevance score and a rank for each object in the set, a ranking fairness objective function, and a ranking utility objective function;
the set of objective functions includes a quadratic function and a linear function;
The computer-implemented method, wherein the quadratic function comprises a fairness function, the linear function comprises a utility function, the fairness function being a normalized function of the difference between a vector composed of the decision variables and a target vector, and the utility function being a linear function that indicates a high relevance score for a user accessing a set of results. The computer-implemented method of claim 1, wherein the set of multiple objective functions includes a fairness function and a utility function, the fairness function being a normalized function of the difference between a vector composed of the decision variables and a target vector, and the utility function being a linear function indicating that a user has access to a higher relevance score. The computer-implemented method of claim 1 or 2, wherein the fairness function is a normalized function. The computer-implemented method of claim 3, wherein the normalized function is a squared L2-norm function. The computer-implemented method of claim 1, wherein the step of the processor determining the Pareto set for the set of objective functions includes the step of the processor calculating the Pareto set using Carathéodory's theorem within the decision space using the ranking fairness objective function and the ranking utility objective function. The step of the processor determining a distribution for the ranks for the objects in the set using the decision space includes, with respect to the number of objects in the set:
(i) the processor determining an arbitrary vertex of the decision space;
(ii) the processor drawing the line starting from the arbitrary vertex with a target exposure until the line intersects a face of the decision space; and
(iii) the processor repeats (i) and (ii) on the intersected face of the decision space using the new intersection point in place of the target exposure until the newly intersected face becomes a vertex;
The computer-implemented method of claim 5 , wherein each vertex of the decision space has an associated coefficient in the distribution for the rank. the set of objective functions includes a fairness function and a utility function;
The computer-implemented method of claim 1 , wherein the fairness function is based on meritocratic fairness, which can be defined as proximity to a normalized relevance vector. the set of objective functions includes a fairness function and a utility function;
The computer-implemented method of claim 1 , wherein the fairness function is based on demographic fairness corresponding to equal exposure to each object. The computer-implemented method of claim 1, wherein the objects in the set include multiple queries. The computer-implemented method of claim 1, wherein the objects in the set include multiple documents. The computer-implemented method of claim 1, wherein the objects in the set are identified in response to a query. The computer-implemented method of claim 1, wherein the objects in the set include multiple recommendations. The computer-implemented method of claim 1, wherein the objects in the set are identified according to map location. The step of outputting by the processor includes:
2. The computer-implemented method of claim 1, further comprising the step of: the processor providing at least a subset of the set of objects ranked according to the selected ranking sequence for display on a display of a device. The computer-implemented method of claim 1, wherein at least a subset of the set of objects is provided on a search engine results page. A computer program comprising non-transitory machine-readable instructions,
The instructions, when executed on a computer, cause a processor of the computer to perform the following method, which method includes:
receiving a set of a plurality of objects and a set of a plurality of objective functions;
defining a decision space having n decision variables using a palmtohedron associated with a position-based model (PBM), the decision variables being variables to be optimized for ranking the exposure of objects, the decision space being a space defined by the decision variables corresponding to information search results, n being the number of objects to be ranked;
determining a Pareto set corresponding to a multi-objective optimization (MOO) problem for the set of multiple objective functions, the Pareto set being a path from a centroid of a facet determined based on a convex combination of associated exposure rankings from the decision space, intersecting edges to reach a vertex of the facet, the determining step being determined using geometric reasoning;
taking Pareto points within the Pareto set and using the decision space to determine a distribution for ranks for the objects in the set using a GLS (Grotschel, Lovasz and Schrijver) procedure , wherein a coefficient is associated with each rank in the distribution;
selecting a set of ranks for the objects in the set from a distribution for the ranks by a coefficient , wherein selecting a set of ranks for the objects in the set includes using one or more of stochastic sampling, low discrepancy sequences, additive repeat sequences, stride scheduling, or m-balance;
outputting the selected set of rankings; and
receiving a list of exposures to be provided to the objects in the set, each associated with a relevance score and a ranking for each object in the set, a ranking fairness objective function, and a ranking utility objective function. 1. A data processing device including a processor configured to perform a method, comprising:
The method comprises:
the processor receiving a set of a plurality of objects and a set of a plurality of goal functions;
the processor using a palmtohedron associated with a position-based model (PBM) to define a decision space having n decision variables, the decision variables being variables to be optimized for ranking the exposure of objects corresponding to information search results, the decision space being a space defined by the decision variables, n being the number of objects to be ranked;
determining a Pareto set corresponding to a multi-objective optimization (MOO) problem for the set of multiple objective functions, the Pareto set being a path from a centroid of a facet determined based on a convex combination of associated exposure rankings from the decision space, intersecting edges and reaching a vertex of the facet, the determining step being determined using geometric reasoning;
the processor taking Pareto points within the Pareto set and using the decision space to determine a distribution for ranks for the objects in the set using a GLS (Grotschel, Lovasz and Schrijver) procedure , wherein a coefficient is associated with each rank in the distribution;
the processor selecting a set of ranks for the objects in the set from a distribution for the ranks by a coefficient , wherein selecting a set of ranks for the objects in the set includes using one or more of stochastic sampling, low discrepancy sequences, additive repeat sequences, stride scheduling, or m-balance;
the processor outputting the selected set of rankings; and
A data processing device comprising: the processor receiving a list of exposures to be provided to the objects in the set, each associated with a relevance score and a ranking for each object in the set, a ranking fairness objective function, and a ranking utility objective function. The data processing device of claim 17, wherein the data processing device is integrated into a second-step ranker for a two-step information retrieval system. The data processing device of claim 17 or 18, wherein the data processing device includes a server. The data processing device of claim 17 or 18, wherein the data processing device includes a client device. An information retrieval system, comprising:
a first-step searcher implemented on a computer configured to receive a query and generate a set of a plurality of objects; and
a computer-implemented second step ranker; wherein the computer-implemented second step ranker comprises:
receiving the set of objects and the set of objective functions;
using a palmtohedron associated with a position-based model (PBM) to define a decision space having n decision variables, the decision variables being variables to be optimized for ranking the exposure of objects corresponding to information search results, the decision space being a space defined by the decision variables, n being the number of objects to be ranked;
determining a Pareto set corresponding to a multi-objective optimization (MOO) problem for the set of multiple objective functions, the Pareto set being a path from a centroid of a facet determined based on a convex combination of associated exposure rankings from the decision space, intersecting an edge, and reaching a vertex of the facet, the determining being determined using geometric reasoning;
determining a distribution for ranks for the objects in the set using a GLS (Grotschel, Lovasz and Schrijver) procedure, with Pareto points in the Pareto set and using the decision space , wherein a coefficient is associated with each rank in the distribution;
selecting a set of ranks for the objects in the set from a distribution for the ranks by a coefficient , wherein selecting a set of ranks for the objects in the set includes using one or more of stochastic sampling, low discrepancy sequences, additive repeat sequences, stride scheduling, or m-balance;
outputting the selected series of rankings;
An information retrieval system configured to receive a list of exposures to be provided to the objects in the set, each associated with a relevance score and a rank for each object in the set, a ranking fairness objective function, and a ranking utility objective function. The information retrieval system of claim 21, wherein the outputting includes the ranker providing at least a subset of the set of objects ranked by the selected ranking sequence for display on a display of a device. The information retrieval system of claim 22, wherein at least a subset of the set of objects is provided in a search engine results page for display on a server or client device display.