Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Bidder optimal assignments for general utilities
 
research article

Bidder optimal assignments for general utilities

Duetting, Paul
•
Henzinger, Monika  
•
Weber, Ingmar
2013
Theoretical Computer Science

We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions u(i,j)(p(j)) expressing his utility of being matched to item j at price p(j). For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. We give sufficient conditions under which every mechanism that finds a bidder optimal outcome is incentive compatible. We also give a mechanism that finds a bidder optimal outcome if the conditions for incentive compatibility are satisfied. The running time of this mechanism is exponential in the number of items, but polynomial in the number of bidders. (C) 2013 Elsevier B.V. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.tcs.2013.01.030
Web of Science ID

WOS:000316924300002

Author(s)
Duetting, Paul
Henzinger, Monika  
Weber, Ingmar
Date Issued

2013

Publisher

Elsevier Science Bv

Published in
Theoretical Computer Science
Volume

478

Start page

22

End page

32

Subjects

Mechanism design

•

Matching markets

•

Discontinuous utilities

•

Envy freeness

•

Lattice

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LTAA  
Available on Infoscience
May 13, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/92167
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés