Ιωάννης 的可爱🇬🇷口音

exponential 一克斯破烂秀

guarantee 尬兰提

Mechanism design for single-parameter environments

3 goals of mechanism designs:

DSIC
Social welfare maximization
simplicity

solution: Myerson’s lemma

possible obstacle: computational complexity of the social welfare maximization problem

hence, the second and the third goals may not be compatible

The Knapsack

The Knapsack problem

aka 背包问题

A burglar enters a house to steal, with a knapsack that can hold items of total weight $W$

the burglar sees $n$ items of value $v_1,v_2,\cdots,v_n$ , weight $w_1,w_2,\cdots,w_n$ .

the total weight of all items exceed the capacity of the knapsack

the optimization problem the burglar has to solve is to select items of total weight at most $W$ that have as high total value as possible.

可用动态规划解决，令 dp[i][j] 为将第 i 件物品装入限重为 j 的背包中，获得的最大的价值
状态转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) 时间复杂度 $\Theta(W\times N)$

The Knapsack auctions

every potential buyer i has a publicly known weight $w_i$ and a private valuation $v_i$

the seller has capacity $W$

the feasible set $X$ consists of the binary vector $(x_1,x_2,\cdots,x_n)$ that satisfy the inequality $\sum_{i=1}^nw_ix_i\le W$ .

a potential buyer wins if $x_i=1$ .

example: the k-unit auctions are knapsack auctions with $W=k$ and $w_i=1$ .

knapsack auction design

assuming that the participants will report their true preferences, maximize the social welfare selecting the allocation rule $x(\mathbf{b})=\arg\max_X\sum_{i=1}^nb_ix_i$ .
since the allocation rule is monotone, we compute payments that ensure DSIC using Myerson’s lemma.

Monotone allocation rule:

consider a participant i
if her reported preference $b_i$ is tiny, then $x_i=0$ . if huge, then $x_i=1$
keeping the remaining reported preference fixed, increasing the report $b_i$ of participant i will at some point result in changing $x_i$ von 0 bis 1. can be proofed by contradiction

Q: is the knapsack auction ideal?

DSIC? ✅
social welfare maximizing? ✅
simple? ❌

the knapsack problem is NP-hard😭

Approximately optimal knapsack auction

we want simplicity and relax the requirement of DSIC.

techniques from approximation algorithms

interested in approximation algorithms as allocations rules that are monotone.

ignore all participants with weight higher than $W$ , then re-index participants so that: $\frac{b_1}{w_1}\ge\frac{b_2}{w_2}\ge\cdots\ge\frac{b_n}{w_n}$ . （按投标效益 aka “性价比”排序 bid-effectiveness）

select winners with this order until some participants does not fit in the knapsack.

return either this allocation or the allocation with the participant that has the highest reported preference.

the approximation knapsack auction runs in polynomial time
it computes an allocation with `at least 50% of the maximum social welfare.
the approximate knapsack auction uses a monotone allocation rule.

critical bid aka 离散分配函数的“阶跃点”，只要超过这个就能中标。所以是分配函数是单调不降的

所有合理的分配规则都是单调的吗？

NO!!! some better algorithms for knapsack problem are not necessarily monotone.

Non-truthful mechanisms

with DSIC, the participants know exactly what to do

the designer can predict the outcome of the mechanism, assuming that the participants report their true valuations as preferences.

in spite of this, non-truthful mechanisms are used extensively in practice.

Definition of DSIC

for every preference profile

the mechanism has a dominant strategy equilibrium in which each participant follows a dominant strategy.
in the equilibrium, all participants report their true valuation as preference.

any mechanisms that are DSIC but not social welfare maximization?