We define a subgradient algorithm to compute the maxmin value of a completely divisible good in both competitive and cooperative strategic contexts. The algorithm relies on the construction of upper and lower bounds for the optimal value which are based on the convexity properties of the range of utility vectors associated to all possible divisions of the good. The upper bound always converges to the optimal value. Moreover, if two additional hypotheses hold: that the preferences of the players are mutually absolutely continuous, and that there always exists relative disagreement among the players, then also the lower bound converges, and the algorithm finds an approximately optimal allocation.

Finding maxmin allocations in cooperative and competitive fair division / Dall'Aglio, Marco; DI LUCA, Camilla. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 1572-9338. - 223:1(2014), pp. 121-136. [10.1007/s10479-014-1611-9]

Finding maxmin allocations in cooperative and competitive fair division

DALL'AGLIO, MARCO;DI LUCA, CAMILLA
2014

Abstract

We define a subgradient algorithm to compute the maxmin value of a completely divisible good in both competitive and cooperative strategic contexts. The algorithm relies on the construction of upper and lower bounds for the optimal value which are based on the convexity properties of the range of utility vectors associated to all possible divisions of the good. The upper bound always converges to the optimal value. Moreover, if two additional hypotheses hold: that the preferences of the players are mutually absolutely continuous, and that there always exists relative disagreement among the players, then also the lower bound converges, and the algorithm finds an approximately optimal allocation.
Fair division theory; Cooperative game theory; Convex optimization; Subgradient algorithms
Finding maxmin allocations in cooperative and competitive fair division / Dall'Aglio, Marco; DI LUCA, Camilla. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 1572-9338. - 223:1(2014), pp. 121-136. [10.1007/s10479-014-1611-9]
File in questo prodotto:
File Dimensione Formato  
FindingMaxminANOR.pdf

Solo gestori archivio

Descrizione: Copia personale dell'articolo pubblicato
Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 345.81 kB
Formato Adobe PDF
345.81 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/136393
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact