{"controller"=>"catalog", "action"=>"show", "id"=>"2150782656"}
  • EN
  • DA

Danish NationalResearch Database

  • Search Publications & Researchers
  • Open Access Indicator
  • Publications
  • Researchers
Example Finds records
water{} containing the word "water".
water supplies"{}" containing the phrase "water supplies".
author:"Doe, John"author:"{}" containing the prase "Doe, John" in the author field.
title:IEEEtitle:{} containing the word "IEEE" in the title field.
Need more help? Advanced search tutorial
  • Selected (0)
  • History

Social welfare in one-sided matchings: Random priority and beyond

    • Save to Mendeley
    • Export to BibTeX
    • Export to RIS
    • Email citation
Authors:
  • Filos-Ratsikas, Aris ;
    Close
    Department of Computer Science, Science and Technology, Aarhus University
  • Frederiksen, Søren Kristoffer Stiil ;
    Close
    Department of Computer Science, Science and Technology, Aarhus University
  • Zhang, Jie
    Close
    Department of Computer Science, University of Oxford
Editor:
Lavi, Ron
DOI:
10.1007/978-3-662-44803-8_1
Abstract:
We study the problem of approximate social welfare maximization (without money) in one-sided matching problems when agents have unrestricted cardinal preferences over a finite set of items. Random priority is a very well-known truthful-in-expectation mechanism for the problem. We prove that the approximation ratio of random priority is Theta(n^{-1/2}) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n^{-1/2}), where n is the number of agents and items. Furthermore, we prove that the approximation ratio of all ordinal (not necessarily truthful-in-expectation) mechanisms is upper bounded by O(n^{-1/2}), indicating that random priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem.
ISBN:
9783662448021, 9783662448038
Type:
Conference paper
Language:
English
Published in:
Lecture Notes in Computer Science: 7th International Symposium, Sagt 2014, Proceedings, 2014, p. 1-12
Main Research Area:
Science/technology
Series:
Lecture Notes in Computer Science
Conference:
Symposium on Algorithmic Game TheorySymposium on Algorithmic Game Theory, 2014
Publisher:
Springer-VS
Submission year:
2014
ID:
2150782656

Full text access

  • Openaccess Aarhus University
  • Doi Get publisher edition via DOI resolver
Checking for on-site access...

On-site access

At institution

  • Aarhus university.en

Metrics

Feedback

Sitemap

  • Search
    • Statistics
    • Tutorial
    • Data
    • FAQ
    • Contact
  • Open Access
    • Overview
    • Development
    • FAQ
    • Contact
  • About
    • Institutions
    • Release History
    • Cookies and privacy policy

Copyright © 1998–2018.

Fivu en