# US 12,216,667 B2 · Ranking systems and methods using a dynamic bayesian network exposure model > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,216,667 B2 - Document ID: US12216667B2 - Status: Granted - Kind: B2 - Application number: 18/084,239 - Filed: 2022-12-19 - Published: 2023-06-15 - Granted: 2025-02-04 - Earliest claimed: 2021-05-06 - Assignees: Naver Corporation - Applicants: Naver Corporation - Inventors: Till Kletti; Jean-Michel Renders - Web page: https://patentgrep.com/patent/US12216667B2 ## CPC - G06F 16/24578: {using ranking} - G06F 16/29: Geographical information databases - G06F 16/953: Querying, e.g. by the use of web search engines - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for ranking a set of objects includes: receiving the set of objects to rank, a relevance score for each object, and a set of objective functions; based on the relevance scores for the objects, defining a decision space having n decision variables using a polytope, where n is the number of objects to rank and where vertices of the polytope represent permutations of exposures provided to the objects in the set by corresponding rankings; determining a Pareto-set for the set of objective functions; based on a Pareto-optimal point in the Pareto-set, determining a distribution over rankings for the objects in the set using the decision space, where a proportion is associated with each ranking in the distribution; selecting a sequence of rankings for the objects in the set based on the distribution in accordance with their proportions; and outputting the selected sequence of rankings of the objects. ## Claims ### Claim 1 A computer-implemented method for ranking a set of objects, the method comprising: receiving a query from a computing device via a network; identifying the objects in the set based on the query; receiving the set of objects to rank, a relevance score for each object in the set, and a set of objective functions, the set of objective functions including a fairness function and a utility function; based on the relevance scores for the objects, defining a decision space having n decision variables using a polytope, where n is the number of objects to rank and where vertices of the polytope represent permutations of exposures provided to the objects in the set by corresponding rankings; determining a Pareto-set for the set of objective functions; based on a Pareto-optimal point in the Pareto-set, determining a distribution over rankings for the objects in the set using the decision space, where a proportion is associated with each ranking in the distribution; selecting a sequence of rankings for the objects in the set based on the distribution in accordance with their proportions; and transmitting, in response to the query, the selected sequence of rankings of the objects to the computing device via the network for display of at least a subset of the set of objects on a display according to the selected sequence of rankings. ### Claim 2 (depends on 1) The computer-implemented method according to claim 1, wherein the set of objective functions comprises a quadratic function and a linear function. ### Claim 3 (depends on 2) The computer-implemented method according to claim 2, wherein the quadratic function comprises the fairness function, and the linear function comprises the utility function. ### Claim 4 (depends on 3) The computer-implemented method according to claim 3, wherein the fairness function is a normalized function of the difference between a vector made up of decision variables and a target vector. ### Claim 5 (depends on 3) The computer-implemented method according to claim 3, wherein the fairness function is a normalized function. ### Claim 6 (depends on 5) The computer-implemented method according to claim 5, wherein the normalized function is a squared L2-norm function. ### Claim 7 (depends on 1) The computer-implemented method according to claim 1, wherein the method further comprises: receiving a list of exposures provided to the objects in the set, a ranking fairness objective function, and a ranking utility objective function, wherein defining the decision space includes determining the decision space based on the relevance scores and the list of exposures, and wherein determining the Pareto-set includes determining the Pareto-set within the decision space based on the ranking fairness objective function and the ranking utility objective function. ### Claim 8 (depends on 7) The computer-implemented method according to claim 7, wherein determining the distribution includes: receiving a point in the Pareto-set which translates to a target exposure across the objects in the set within the decision space; and using the target exposure, determining the distribution which achieve on average the target exposure for the objects in the set, each ranking corresponding to a vertex in the decision space. ### Claim 9 (depends on 8) The computer-implemented method according to claim 8, wherein the determining the distribution includes, for the number of objects in the set: (i) determining a vertex of the decision space; (ii) drawing a line starting at the vertex through the target exposure until the line intersects a face of the polytope; and (iii) repeating (i) and (ii) on the intersected face of the polytope using the new intersection point instead of the target exposure, until the newly intersected face is a second vertex, wherein each vertex of the decision space has an associated proportion in the distribution. ### Claim 10 (depends on 1) The computer-implemented method according to claim 1, wherein the fairness function comprises at least one of a meritocratic fairness function and a demographic fairness function. ### Claim 11 (depends on 1) The computer-implemented method according to claim 1, wherein the polytope is determined based on the relevance score using an exposure model with exposures that depend on a document's rank. ### Claim 12 (depends on 1) The computer-implemented method according to claim 1, wherein the polytope is determined based on the relevance score using an exposure model with exposures that depend on a document's rank and a document's relevance. ### Claim 13 (depends on 12) The computer-implemented method according to claim 12, wherein the polytope is determined based on the relevance score using an exposure model with exposures that depend on a document's rank and a document's relevance and ranks of other documents and relevances of the other documents. ### Claim 14 (depends on 1) The computer-implemented method according to claim 1, wherein said determining the distribution includes determining the distribution using a Grotschel, Lovasz and Schrijver (GLS) procedure. ### Claim 15 (depends on 1) The computer-implemented method according to claim 1, wherein the selecting a sequence of rankings includes selecting the sequence of rankings using one or more of stochastic sampling, Low-Discrepancy Sequences, additive-recurrence sequences, Stride Scheduling, or m-balancing. ### Claim 16 (depends on 1) The computer-implemented method according to claim 1, wherein the objects in the set include documents. ### Claim 17 (depends on 1) The computer-implemented method according to claim 1, wherein the objects in the set include recommendations. ### Claim 18 (depends on 17) The computer-implemented method according to claim 17 further comprising identifying the objects in the set in response to a location. ### Claim 19 A computer-implemented method, comprising: receiving a query from a computing device via a network; determining a set of items to be ranked based on the query; determining relevance scores for the items, respectively, using a fairness function and a utility function; determining a polytope using an exposure model based on the relevance scores; determining a point that lies within the polytope; performing a Carathéodory decomposition; generating a distribution for the items based on a result of the Carathéodory decomposition; sampling from the distribution; determining rankings for the items based on the sampling; and in response to the query, transmitting the rankings of the items to the computing device via the network for displaying at least a subset of the set of objects on a display according to the rankings. ### Claim 20 (depends on 19) The computer-implemented method of claim 19 wherein the exposure model is one of a Position-Based Model (PBM) and a Dynamic Bayesian Network (DBN) model. ### Claim 21 (depends on 19) The computer-implemented method of claim 19 wherein the Carathéodory decomposition includes selecting a vertex of the polytope, finding an intersection of a line with a border of the polytope using a bisection search. ### Claim 22 (depends on 21) The computer-implemented method of claim 21 wherein the result of the Carathéodory decomposition includes vertices of the polytope and coefficients for the vertices, respectively. ### Claim 23 (depends on 19) The computer-implemented method of claim 19 wherein the determining the point includes determining a smallest dimension face upon which the point lies. ### Claim 24 (depends on 23) The computer-implemented method of claim 23 wherein the face is one of a vertex, an edge, a face, and the polytope. ### Claim 25 (depends on 24) The computer-implemented method of claim 24 wherein the determining the smallest dimension face includes determining a number of adjacent faces upon which the point lies. ### Claim 26 (depends on 19) The computer-implemented method of claim 19 wherein the sampling includes one of sampling from the distribution using one of random sampling and m-balanced words sampling. ### Claim 27 (depends on 19) The computer-implemented method of claim 19 wherein the determining the rankings includes: determining a face of the polytope upon which the point lies; determining a projection on a plane of the face; projecting the projection on the plane; and finding the point on the projection where a utility of the rankings is a maximum utility. ### Claim 28 (depends on 27) The computer-implemented method of claim 27 wherein the determining the ranks further includes: determining a second face of the polytope upon which the point lies; determining a second projection on a second plane of the second face; projecting the second projection on the second plane; and finding the point on the second projection where the utility of the rankings is the maximum utility. ### Claim 29 (depends on 27) The computer-implemented method of claim 27 wherein the polytope is asymmetrical. ### Claim 30 (depends on 19) The computer-implemented method of claim 19 wherein the determining the polytope includes determining the polytope further based on a continuation probability value and a satisfaction probability value. ### Claim 31 (depends on 30) The computer-implemented method of claim 30 wherein the continuation probability value corresponds to a probability of a user stopping reviewing the items. ### Claim 32 (depends on 31) The computer-implemented method of claim 31 wherein the satisfaction probability value corresponds to a probability of a user being satisfied with one of the items. ### Claim 33 A system comprising: a computing device; one or more processors; and memory including code that, when executed by the one or more processors, perform to: receive a query from the computing device via a network; determine a set of items to be ranked based on the query; determine relevance scores for the items, respectively, using a fairness function and a utility function; determine a polytope using an exposure model based on the relevance scores; determine a point that lies within the polytope; perform a Carathéodory decomposition; generate a distribution for the items based on a result of the Carathéodory decomposition; sample from the distribution; determine rankings for the items based on the sampling; and transmit the rankings of the items to the computing device via the network, wherein the computing device is configured to display at least a subset of the set of objects on a display according to the rankings.