Algorithms for Pareto optimal exchange with bounded exchange cycles

被引：3

作者：

Aziz, Haris ^{[1
,2
]}

机构：

[1] UNSW Sydney, Sydney, NSW, Australia

[2] Data61 CSIRO, Sydney, NSW, Australia

来源：

OPERATIONS RESEARCH LETTERS | 2019年 / 47卷 / 05期

关键词：

Kidney exchange; Housing markets; Strategyproofness; Pareto optimality; Individual rationality; ALLOCATION;

D O I：

10.1016/j.orl.2019.06.002

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider exchange markets with single-unit endowments and demands where there is a bound on the size of the exchange cycles. The computational problem we study is that of computing a Pareto optimal and individually rational allocation. We present polynomial-time algorithms to compute a Pareto optimal and individually rational allocation when preferences are strict, the exchange bound is two, or when Pareto optimality is replaced with weak Pareto optimality. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：344 / 347

页数：4

共 15 条

[1]

Abraham DJ, 2007, EC'07: PROCEEDINGS OF THE EIGHTH ANNUAL CONFERENCE ON ELECTRONIC COMMERCE, P295

[2]

Abraham DJ, 2005, LECT NOTES COMPUT SC, V3827, P1163, DOI 10.1007/11602613_115

[3]

Aziz H, 2012, P 26 AAAI C ART INT, P1249

[4]

Aziz H, 2016, AAMAS'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, P402

[5]

Biro P., 2007, P 5 JAP HUNG S CIT, P97

[6]

Biro P., 2018, SERIAL DICTATORSHIPS

[7]

Costa V., 2018, NEW INTEGER PROGRAMM

[8] The difference indifference makes in strategy-proof allocation of objects [J].

Jaramillo, Paula ;

Manjunath, Vikram .

JOURNAL OF ECONOMIC THEORY, 2012, 147 (05) :1913-1946

[9] STRATEGY-PROOFNESS AND THE STRICT CORE IN A MARKET WITH INDIVISIBILITIES [J].

MA, JP .

INTERNATIONAL JOURNAL OF GAME THEORY, 1994, 23 (01) :75-83

[10] Transplant quality and patients' preferences in paired kidney exchange [J].

Nicolo, Antonio ;

Rodriguez-Alvarez, Carmelo .

GAMES AND ECONOMIC BEHAVIOR, 2012, 74 (01) :299-310

← 1 2 →