| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142655 | Operations Research Letters | 2013 | 4 Pages |
Abstract
Bankruptcy problems are a fundamental class of fair division problems in microeconomics. Among the various solution concepts proposed for the problem, the random arrival rule is one of the most prominent. In this paper, we conduct a computational analysis of the rule. It is shown that the allocation returned by the rule is #P-complete to compute. The general complexity result is complemented by a pseudo-polynomial-time dynamic programming algorithm for the random arrival rule.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Haris Aziz,