1
日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

Auctions and Mechanism DesignTakayuki Ito

In this talk, I will present an introduction of Auction theory and Mechanism Design (MD) theory. Auction
theory is a kind of the central example of the MD theory, and the best introduction about MD theory.
Thus I will present mainly Auction theory in this talk. The most important concept of MD theory is”truthfulness” (that is called as also ”incentive compatible”). I will explain how truthfulness is defined andrealized in several auction settings. Also, it is important to consider the computational issues in mechanism
design. It is well-known that the winner determination in the combinatorial auction is an NP-complete
problem however it is possible to compute approximately the winner with preserving truthfulness. Suchcomputational consideration is required to realize the mechanism work in the real world, and we call it
Computational Mechanism Design (CDM) theory.

1 Introduction
Mechanism design (MD) is a field in microeconomics and game theory. It deals with problems
in which multiple selfish agents are to be organized
in a way that the global outcome meets sociallydesigned goals. Auction can be seen as one of
the mechanisms, where people buy and sell goods
or services by bidding, allocation (awarding), andpricing. Auction theory deals with how people act
in auction markets and investigates the propertiesof auction markets. Auction design can be seen asa subset of MD.
The following four auctions are thought as thebasic designs of auctions.
• First-price sealed-bid auctions,• Second-price sealed-bid auctions (Vickrey auctions),• Open Ascending-bid auctions (English auctions), and• Open Descending-bid auctions (Dutch auc-

オークションとメカニズムデザインTakayuki Ito, 名古屋工業大学産業戦略工学専攻／情報工学科, School of Techno-Business Administration/ Dept. of Computer Science, Nagoya Institute ofTechnology..

tions).
Vickrey Auction is the Second price auction
where the winner is the bidder who submitted thehighest bid and the price he pays is the second highest bid value. It is known that it gives bidders an
incentive to bid their true value. Namely, the dominant strategy in Vickrey auction with a single, indivisible item is for each bidder to bid their true
value of the item. This is because the winner cannot manipulate its payment price, since the payment price is not determined by the winner s bidprice.

2 Combinatorial Auctions and Vickrey
Clark Groves (VCG) Mechanism
The above basic auctions are basically handlinga single good. It has been widely studied combinatorial auctions (CA) where multiple distinguishedgoods are sold and bidders can submit bids to somecombinations of the goods. For example, there canbe three goods, A, B, and C. A bidder can submit
a bid like USD40 for {A,B} and USD30 for {A}.
The auctioneer awards to the combination of thesubmitted bids that maximizes the total revenue.
This process is called the winner determination andis known as an NP-hard problem. VCG mechanism is the mechanism that makes the combinato-rial auction truthful with a sophisticated payment
scheme. In VCG, the payment of the winner is determined as how much he reduces the social surplusof the other agents.

3 Generalized Second Price Auctions(GSP)
Internet advertisement business started fromwell-known banner-ads , which put advertisement
pictures on the web-pages based on, for example,
views/month. Overture, Inc., first developed thePay-Per-Click based Internet advertisement, whereadvertisers pay the cost based on the number ofclicks for its advertisement. This was a very innovative business model but it was not stable interms of prices because bidders have incentive tomaneuver their prices because the payment was determined by what their declarations. Google foundthat bidders do not want to pay more than the bidof the next position. Thus, in 2002, Google starts
the Google AdWords, where each bidder pays theprice of its next position. This is called generalized
second price auction (GSP)[1] and is based on avery similar idea of Vickrey auction in which bidder s payment cannot be determined by its own bid.
In this sense, GSP is the most widely used Vickrey(like) auction in the world because when someone
searches a word by Google, it run one GSP process.
(In theory, GSP does not satisfy dominant strategy
incentive compatible but it is known that bidders
are on locally-envy free equilibrium in the GSP.)

4 Computational Mechanism Design
Computational mechanism [2] design brings together the concern in microeconomics and gametheory with decision making under distributed private information, uncertainty, and self-interest, andthe concern in computer science with computational and communication complexity. The following are a couple of the recent research topics:
Truthful Greedy-allocation Combinatorial Auctions [3]:As we explained in section 3, CA is one of theNP-hard problems that means much computational power are required. The study tackles
this problem in which they build an greedy algorithm that find approximated optimal com-bination instead of finding the exact optimal
combination while keeping truthfulness. Tokeep truthfulness, a special notion of criticalvalue that means the minimum value that awinner can still win.
Interdependent Value Auctions [4] [5]:This work considers the problem of auction
design with agents that have interdependent
values, i.e. values that depend on each others
private values. The work adopt the contingent
bids model allow agents to submit bids of theform if player 1 bids xf orgoodthenIwillbidy.
This work identified a specific linear valuation
model for which there exists an eﬃcient auction
for a single item, and extend this to provide anapproximately eﬃcient CA.

5 Conclusion
We briefly explained auction theory and mechanism design. The work presented here has a significant impact because while some results, like theGSP, are theoretically developed well, it has been
actually developed and used in the real world.
Acknowledgement This work is partially supported by the Funding Program for Next Generation World-Leading Researchers (NEXT Program)of the Japan Cabinet Oﬃce.
References[ 1 ] B. Edelman, M. Ostrovsky and M. Schwarz,Internet Advertising and the Generalized Second
Price Auction: Selling Billions of Dollars Worthof Keywords, American Economic Review, vol.97,no.1, pp242-259, 2007.
[ 2 ] Takayuki Ito, ”Computational Mechanism Design”，Computer Software, Japan Society for Software Science and Technology, Vol. 25, No.4, pp.2032, 2008 (in Japanese).
[ 3 ] D. Lehmann, L.I.O Callaghan, and Y. Shoham,
Truth Revelation in Approximately Eﬃcient Combinatorial Auctions, Journal of the ACM, vol.49,no.5, pp.1-6, 2002.
[ 4 ] T. Ito and D. Parkes, ” Instantiating the Contingent Bids Model of Truthful Interdependent Value
Auctions”, Proc. of the Fifth International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS2006), pp.1151-1158, 2006.
[ 5 ] V. Robu, D. Parkes, T. Ito, N. Jennings, ”Eﬃcient Interdependent Value Combinatorial Auctions
with Single-Minded Bidders”, In the Proceedings ofIJCAI 2013, Beijing, China, on August 3-9, 2013.