Les matroïdes et leur implication dans l'allocation de ressources indivisibles: algorithmes d'approximation avec garantie de performance

Lydia Tlilane

in Economics Thesis from University Paris Dauphine from Paris Dauphine University

Abstract: In this thesis, we are interested in collective decision-making. The objective is to find a tradeoff solution for problems that are evaluated by multiple points of view. We consider problems having a matroid structure. Matroid theory is significant in combinatorial optimization, it helped to unify apparently separated structures like forests and matchings in graphs and it includes efficient algorithms for solving non-trivial optimization problems in polynomial time. We are interested to provide polynomial time centralized and decentralized approximation algorithms for finding a tradeoff solution which is a base of the matroid. The tradeoff solution must also be fair for all the members of the community. We are particularly interested in the issue of the fair division of indivisible goods which is central in computational social choice and that can be modeled by matroids.

Keywords: Optimisation combinatoire; Approximation polynomiale à garantie de performance; Matroïdes; Allocation de biens indivisibles; Notions d’équité; Combinatorial optimization; Polynomial time approximation with guaranteed performance; Matroids; Allocation of indivisible goods; Fairness notions (search for similar items in EconPapers)
JEL-codes: C44 (search for similar items in EconPapers)
Date: 2014 Written 2014
Note: dissertation
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://basepub.dauphine.fr/xmlui/bitstream/123456789/14807/2/2014PA090068.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to basepub.dauphine.psl.eu:443 (Bad file descriptor) (http://basepub.dauphine.fr/xmlui/bitstream/123456789/14807/2/2014PA090068.pdf [301 Moved Permanently]--> https://basepub.dauphine.psl.eu/xmlui/bitstream/123456789/14807/2/2014PA090068.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:dau:thesis:123456789/14807

Ordering information: This item can be ordered from
http://basepub.dauph ... ndle/123456789/14807

Access Statistics for this book

More books in Economics Thesis from University Paris Dauphine from Paris Dauphine University Contact information at EDIRC.
Bibliographic data for series maintained by Alexandre Faure ( this e-mail address is bad, please contact ).