Items from a database are often ranked based on a combination
of criteria. The weight given to each criterion in the
combination can greatly affect the fairness of the produced
ranking, for example, preferring men over women. A user
may have the flexibility to choose combinations that weigh
these criteria differently, within limits. In this paper, we develop
a system that helps users choose criterion weights
that lead to greater fairness. We consider ranking functions
that compute the score of each item as a weighted sum of
(numeric) attribute values, and then sort items on their score.
Each ranking function can be expressed as a point in a multidimensional
space. For a broad range of fairness criteria,
including proportionality, we show how to efficiently identify
regions in this space that satisfy these criteria. Using this
identification method, our system is able to tell users whether
their proposed ranking function satisfies the desired fairness
criteria and, if it does not, to suggest the smallest modification
that does. Our extensive experiments on real datasets
demonstrate that our methods are able to find solutions that
satisfy fairness criteria effectively (usually with only small
changes to proposed weight vectors) and efficiently (in interactive
time, after some initial pre-processing).
more »
« less
MithraRanking: A System for Responsible Ranking Design
Items from a database are often ranked based on a combination
of criteria. The weight given to each criterion in the
combination can greatly affect the ranking produced. Often,
a user may have a general sense of the relative importance of
the different criteria, but beyond this may have the flexibility,
within limits, to choose combinations that weigh these criteria
differently with an acceptable region. We demonstrate
MithraRanking, a system that helps users choose criterion
weights that lead to “better” rankings in terms of having
desirable properties while remaining within the acceptable
region. The goodness properties we focus on are stability
and fairness.
more »
« less
- PAR ID:
- 10108007
- Date Published:
- Journal Name:
- Proc. ACM SIGMOD Intl Conf on Management of Data
- Page Range / eLocation ID:
- 1913 to 1916
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A number of criteria have been proposed to judge test suite adequacy. While search-based test generation has improved greatly at criteria coverage, the produced suites are still often ineffective at detecting faults. Efficacy may be limited by the single-minded application of one criterion at a time when generating suites - a sharp contrast to human testers, who simultaneously explore multiple testing strategies. We hypothesize that automated generation can be improved by selecting and simultaneously exploring multiple criteria. To address this hypothesis, we have generated multi-criteria test suites, measuring efficacy against the Defects4J fault database. We have found that multi-criteria suites can be up to 31.15% more effective at detecting complex, real-world faults than suites generated to satisfy a single criterion and 70.17% more effective than the default combination of all eight criteria. Given a fixed search budget, we recommend pairing a criterion focused on structural exploration - such as Branch Coverage - with targeted supplemental strategies aimed at the type of faults expected from the system under test. Our findings offer lessons to consider when selecting such combinations.more » « less
-
Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Graph Drawing via Gradient Descent, (GD)^2, that can handle multiple readability criteria. (GD)^2 can optimize any criterion that can be described by a smooth function. If the criterion cannot be captured by a smooth function, a non-smooth function for the criterion is combined with another smooth function, or auto-differentiation tools are used for the optimization. Our approach is flexible and can be used to optimize several criteria that have already been considered earlier (e.g., obtaining ideal edge lengths, stress, neighborhood preservation) as well as other criteria which have not yet been explicitly optimized in such fashion (e.g., vertex resolution, angular resolution, aspect ratio). We provide quantitative and qualitative evidence of the effectiveness of (GD)^2 with experimental data and a functional prototype: http://hdc.cs.arizona.edu/~mwli/graph-drawing/more » « less
-
more » « less
Abstract The QZ algorithm computes the generalized Schur form of a matrix pencil. It is an iterative algorithm and, at some point, it must decide when to deflate, that is when a generalized eigenvalue has converged and to move on to another one. Choosing a deflation criterion that makes this decision is nontrivial. If it is too strict, the algorithm might waste iterations on already converged eigenvalues. If it is not strict enough, the computed eigenvalues might not have full accuracy. Additionally, the criterion should not be computationally expensive to evaluate. There are two commonly used criteria: the
elementwise criterion and thenormwise criterion. This paper introduces a new deflation criterion based on the size of and the gap between the eigenvalues. We call this new deflation criterion thestrict criterion. This new criterion for QZ is analogous to the criterion derived by Ahues and Tisseur for the QR algorithm. Theoretical arguments and numerical experiments suggest that the strict criterion outperforms the normwise and elementwise criteria in terms of accuracy. We also provide an example where the accuracy of the generalized eigenvalues using the elementwise or the normwise criteria is less than two digits whereas the strict criterion leads to generalized eigenvalues which are almost accurate to the working precision. Additionally, this paper evaluates some commonly used criteria for infinite eigenvalues. -
more » « less
The United Nations Sustainable Development Goals provide a road map for countries to achieve peace and prosperity. In this study, we address two of these sustainable development goals: achieving food security and reducing inequalities. Food banks are nonprofit organizations that collect and distribute food donations to food‐insecure populations in their service regions. Food banks consider three criteria while distributing the donated food: equity, effectiveness, and efficiency. The equity criterion aims to distribute food in proportion to the food‐insecure households in a food bank's service area. The effectiveness criterion aims to minimize undistributed food, whereas the efficiency criterion minimizes the total cost of transportation. Models that assume predetermined weights on these criteria may produce inaccurate results as the preference of food banks over these criteria may vary over time, and as a function of supply and demand. In collaboration with our food bank partner in North Carolina, we develop a single‐period, weighted multi‐criteria optimization model that provides the decision‐maker the flexibility to capture their preferences over the three criteria of equity, effectiveness, and efficiency, and explore the resulting trade‐offs. We then introduce a novel algorithm that elicits the inherent preference of a food bank by analyzing its actions within a single‐period. The algorithm does not require direct interaction with the decision‐maker. The non‐interactive nature of this algorithm is especially significant for humanitarian organizations such as food banks which lack the resources to interact with modelers on a regular basis. We perform extensive numerical experiments to validate the efficiency of our algorithm. We illustrate results using historical data from our food bank partner and discuss managerial insights. We explore the implications of different decision‐maker preferences for the criteria on distribution policies.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3299869.3320244
