A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation

E-resources

PDF

Full text

Peer reviewed Open access

A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation

Aziz, Haris; Moulin, Hervé; Sandomirskiy, Fedor

Operations research letters, 09/2020, Volume: 48, Issue: 5

Journal Article

We consider fair allocation of indivisible items under additive utilities. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. The result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.

Keep searching

Author

Aziz, Haris | Moulin, Hervé | Sandomirskiy, Fedor

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
Year	JCR	SNIP	JCR	SNIP	JCR	SNIP	JCR	SNIP

Links to authors' personal bibliographies	Links to information on researchers in the SICRIS system

Source: Personal bibliographies and: SICRIS

Upload image

Shelf entry

Adding material to shelf was successful.

Adding material to shelf failed.

It was not necessary to add the material to the shelf.

Permalink

E-mail

Impact factor

Select the library membership card:

DRS, in which the journal is indexed

Citations

Theme