E-resources
Peer reviewed
-
Aziz, Haris; Li, Bo; Moulin, Hervé; Wu, Xiaowei; Zhu, Xinran
Artificial intelligence, June 2024, 2024-06-00, Volume: 331Journal Article
Proportionality (PROP) is one of the simplest and most intuitive fairness criteria used for allocating items among agents with additive utilities. However, when the items are indivisible, ensuring PROP becomes unattainable, leading to increased focus on its relaxations. In this paper, we focus on the relaxation of proportionality up to any item (PROPX), where proportionality is satisfied if an arbitrary item is removed from every agent's allocation. We show that PROPX is an appealing fairness notion for the allocation of indivisible chores, which approximately implies some share-based notions, such as maximin share (MMS) and AnyPrice share (APS). We further provide a comprehensive understanding of PROPX allocations, regarding the computation, approximation, and compatibility with efficiency. On top of these, we extend the study to scenarios where agents do not share equal liability towards the chores, and approximate PROPX allocations using partial information about agents' utilities. •We design algorithms to compute PROPX allocations for indivisible chores when the agents have asymmetric weights.•We design algorithms, which only access the agents' ordinal preferences, to compute approximate PROPX allocations.•We investigate the compatibility of PROPX and Pareto optimality in the general and special cases.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.