Algorithmic Mechanism Design Hong Zhu Fudan University, Shanghai, China

Input of Algorithms 1。 Traditional 传统的算法 Input ---> Output 2。 Internet 的兴起 Global computing -- 大数分解，网络上数千台计算机同时计算：given large integer N with 500 bits, 每台计算机猜一个素数p，各自判断p|N or not. 所以即使量子计算机没有，RSA 加密体制也是不安全的。 算法的设计者要把协议的参加者的反映reactions ，行为behaviour考虑进去。

My Research a 5 6 X 13 Y 7 5 b

Mechanism Design Concept 经济学的概念，将人的因素考虑进去，例:任务分配；组合拍卖。 机制设计是一种协议的设计，它将实现某种给定目标建立在假定协议的参加者agents都是自私的self-interested 和理性的rational，它们都尽力使自己的利益最大化。如同世贸总协定参加国之间的关系。

Mechanism Design 的重要特征 Truthfulness---Incentive Compatibility 鼓励讲真话 That is , a protocol motivates agents to tell their private preferences (valuations) truthfully

优化机制的设计问题一 Internet 管理者效益revenue最大化. 当agents的valuations是独立的和概率分布服从某些条件时，该问题获得部分解决，不幸的是，大多数结果是不理想的。

优化机制的设计问题二 其目标是agents的total valuations最大化，例如VCG体制，被广泛地讨论。 Utilitarian mechanism design 其目标是agents的total valuations最大化，例如VCG体制，被广泛地讨论。

Nash 平衡 n Players 每个player i, i=1,…,n.有一个策略集合S_i, 而且有一个收益函数u_i: S_1× S_2×…× S_n ├ R 理性的players是选择策略x_1  S_1, x_2  S_2,…, x_n  S_n,达到Nash equlibrium: for all I u_i(x_1, x_2,…,x_i,…, x_n ) u_i(x_1, x_2,…,y_i,…, x_n ) if y_ix_i

Single-Minded Auction An auctioneer sells m heterogeneous commodities Ω = {w1,…,wm} There are n buyers O1,…,On .For each buyer Oi, there is a unique Ωi ⊆ Ω, such that, for any bundle B ⊆ Ω, vi : the true valuation of each buyer, and vi(B) = vi(Ωi), if Ωi ⊆ B. vi(B) = 0, otherwise. bi : the actual submitted bid of each buyer. Pi : the payment of each buyer. Note that if a buyer does not win the item, Pi = 0.

Single-Minded Auction The auctioneer determines X = (X1,…,Xn), the allocation vector of buyers Px = (Pi,…,Pn), the payment vector Each buyer aims to maximize the utility value: ui = vi(Xi)-Pi

Special Case - English auction The auctioneer increases the price of the item in a continuous manner (or with an increment that is insignificantly small) until only one buyer stays in. If you are a buyer, will you bid your valuation truthfully?

Special Case - Dutch auction The auctioneer starts at a high price and reduces it continuously. The auction ends when some buyer shouts “Mine!” to claim the item at the current price. This time, will a buyer bid the truth?

Incentive compatibility We say an auction is incentive compatible (or truthful) if the utility of each buyer is maximized by bidding his true valuation, i.e., bi = vi , regardless the bids of other buyers. For example, English auction is incentive compatible. Dutch auction is not incentive compatible.

Previous Results Definition. An allocation algorithm X is monotone if for any given bids b-i and a winning declaration bi , any higher declaration b’i > bi still wins, where b-i is the bids vector of all buyers except i. Lemma. Let X be a monotone allocation algorithm. Then for any b-i, there exists a unique critical value ci(X; b-i) such that for any bi > ci(X; b-i), bi is a winning declaration, and for any bi < ci(X; b-i), bi is a losing declaration.

Previous Results Definition. The critical payment PX(b) associated with the monotone allocation algorithm X is defined by Pi = ci(X; b-i) if Xi = Ωi; and Pi = 0 otherwise. Theorem. [Mu’alem & Nisan, AAAI’02] A mechanism is incentive compatible if and only if its allocation algorithm is monotone and its payment is critical payment.

Conclusion Theorem. The Greedy Allocation Algorithm based on cost ranking associated with the critical payment is incentive compatible mechanism, and the payment can be interpreted as the price.

Revenue Consideration Definition. (Maximal Revenue Problem) Given constant k > 0 and single-minded auction, does there exist regular price vector and trading buyers such that the revenue of the auctioneer is at least k. Theorem. Maximal Revenue Problem is NP-hard.

Future Breakthrough New Tools Computational Model Game theory Mathematical Economics － Ecoinformatic Computational Model

STOC’01 and ICALP’01 by Papadimitriou of UC Berkeley 前五十年 computer – logic and combinatorics 新五十年 internet has aguable serpassed the von Neumann computer as the most complex computational artifact – Game theory, mathematical economics and （我本人的意见） finite model theory， 进程代数

题外话－－当前发展中国计算机科学和技术的障碍不能不提到教育和学术团体 改造计算机学会，国内外学者尤其国外的华裔学者都可以参加，以引入新鲜血液。 （印度）,也可以不分国籍。 学术浮夸－ 61年高教60条：找研究生宁缺毋烂 商人和学者不可兼 中国的计算机教育业必须靠在国外的计算机工作过一段时间的博士来根本改变现状。 世界第一流大学的教授不限国籍。基金申请

Thank you !