Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Truthfulness and stochastic dominance with monetary transfers
Hoefer M., Kesselheim T., Vöcking B. ACM Transactions on Economics and Computation4 (2):1-18,2016.Type:Article
Date Reviewed: Apr 29 2016

It is desirable to design auctions in such a way that participants have a financial incentive to provide true information about their interests. At first glance, an ideal description of this truthfulness requirement is that, in all possible situations, a person reporting the true valuation benefits gets the largest possible value of the difference vp between the value v of the objects gained in the auction minus the corresponding payment p. However, such a universal truthfulness requirement is too strong: such auction schemes exist, but the resulting solutions are often of low quality.

A much better quality is attained by truthful-in-expectation solutions, in which reporting the true valuation maximizes the expected monetary gain m = v p. However, this does not necessarily mean that in the real-life implementations of the corresponding auction designs, participants will report their true valuations. The reason is that while it may sound reasonable to maximize the expected value of monetary gain, this is not, in general, how people make decisions. The decisions of a rational person correspond to maximizing the expected utility, where utility u(m) is an increasing (and usually nonlinear) function of the monetary gain.

Different participants may make decisions based on different utility functions. From this viewpoint, it is desirable to look for auction schemes in which the truthful valuation is beneficial for all possible utility functions. This condition is difficult to check directly, since it requires considering all possible monotonic functions; however, it is known that such a condition can be equivalently reformulated as the requirement that F(a) is smaller than or equal to G(a) for all a, where F(a) is the truthful-valuation-case probability that the monetary m does not exceed a and G(a) is the similar probability for the case of a false valuation. This property is known as first-order stochastic dominance.

The authors describe all social-choice functions that are truthful in first-order stochastic dominance. Interestingly, it turns out that these are the same functions that allow truthful-in-expectation solutions--but to gain first-order stochastic dominance, one needs to somewhat change the payment rules. Another interesting result is that the situation does not improve if we only consider, for example, risk-averse participants: if we can guarantee truthfulness for them, then we can also guarantee truthfulness for all participants.

These interesting new results ensure that the corresponding auction designs encourage truthfulness and are, thus, ready for practical implementation.

Reviewer:  V. Kreinovich Review #: CR144367 (1607-0521)
Bookmark and Share
  Featured Reviewer  
 
Numerical Algorithms And Problems (F.2.1 )
 
 
Economics (J.4 ... )
 
 
Applications (G.1.10 )
 
 
Applications (G.2.3 )
 
 
Problem Solving, Control Methods, And Search (I.2.8 )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Algorithms And Problems": Date
On the computational complexity of ordinary differential equations
Ko K. (ed) Information and Control 58(1-3): 157-194, 1984. Type: Article
Jun 1 1985
The computational complexity of simultaneous diophantine approximation problems
Lagarias J. SIAM Journal on Computing 14(1): 196-209, 1985. Type: Article
Jan 1 1986
Parallel and distributed computation: numerical methods
Bertsekas D., Tsitsiklis J., Prentice-Hall, Inc., Upper Saddle River, NJ, 1989. Type: Book (9789780136487005)
Apr 1 1990
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy