Files and links (1)
SubmittedOpen Access (License Unspecified), Open
Conference proceeding
Mechanisms for Hiring a Matroid Base without Money
ALGORITHMIC GAME THEORY, SAGT 2014, v 8768, pp 255-266
01 Jan 2014
Abstract
We consider the problem of designing mechanisms for hiring a matroid base without money. In our model, the elements of a given matroid correspond to agents who might misreport their actual costs that are incurred if they are hired. The goal is to hire a matroid base of minimum total cost. There are no monetary transfers involved. We assume that the reports are binding in the sense that an agent's cost is equal to the maximum of his declared and actual costs. Our model encompasses a variety of problems as special cases, such as computing a minimum cost spanning tree or finding minimum cost allocation of jobs to machines.
We derive a polynomial-time randomized mechanism that is truthful in expectation and achieves an approximation ratio of (m - r)/2 + 1, where m and r refer to the number of elements and the rank of the matroid, respectively. We also prove that this is best possible by showing that no mechanism that is truthful in expectation can achieve a better approximation ratio in general. If the declared costs of the agents are bounded by the cost of a socially optimal solution, we are able derive an improved approximation ratio of 3 root m. For example, this condition is satisfied if the costs constitute a metric in the graphical matroid.
Our mechanism iteratively extends a partial solution by adding feasible elements at random. As it turns out, this algorithm achieves the best possible approximation ratio if it is equipped with a distribution that is optimal for the allocation of a single task to multiple machines. This seems surprising given that matroids allow for much richer combinatorial structures than the assignment of a single job.
Metrics
Details
- Title
- Mechanisms for Hiring a Matroid Base without Money
- Creators
- Emmanouil Pountourakis - Northwestern UniversityGuido Schafer - Centrum Wiskunde & Informatica
- Contributors
- R Lavi (Editor)
- Publication Details
- ALGORITHMIC GAME THEORY, SAGT 2014, v 8768, pp 255-266
- Series
- Lecture Notes in Computer Science
- Publisher
- Springer Nature
- Number of pages
- 12
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000347388000022
- Scopus ID
- 2-s2.0-84921378091
- Other Identifier
- 991021869008104721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Information Systems
- Computer Science, Theory & Methods