Name
Abstract | ||
|---|---|---|
We propose a parametric family of measures of fairness in allocations of TU-cooperative games. Their definition is based on generalized Renyi Entropy, is related to the Cowell-Kuga generalized entropy indices in welfare economics, and aims to parallel the spirit of the notion of price of anarchy in the case of convex TU-cooperative games. Since computing these indices is NP-complete in general, we first upper bound the performance of a "reverse greedy" algorithm for approximately computing worst-case fairness. The result provides a general additive error guarantee in terms of two (problem dependent) packing constants. We then particularize this result to the class of induced subset games. For such games computing worst-case fairness is NP-complete, and the additive guarantee constant can be explicitly computed. We compare this result to the performance of an alternate algorithm based on "biased orientations". |
Year | Venue | Field |
|---|---|---|
2012 | CoRR | Mathematical optimization,Mathematical economics,Parametric family,Upper and lower bounds,Rényi entropy,Regular polygon,Parametric statistics,Price of anarchy,Mathematics |
DocType | Volume | Citations |
Journal | abs/1208.0283 | 2 |
PageRank | References | Authors |
0.38 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cosmin Bonchiş | 1 | 13 | 7.75 |
| Gabriel Istrate | 2 | 99 | 24.96 |