Abstract In auctions and related allocation problems, the designer does not know the values of the bidders for the object to be allocated. Each bidder privately knows her own value for the object but does not know the values of others. An allocation rule specifies for every profile of values the probability with which each bidder gets the object. Suppose each bidder draws its value independently and identically, and this is common knowledge. Given such an allocation rule, a bidder with a value can compute the "interim" probability of getting the object (by taking expectation over others values). Matthews (1984) asks the following: suppose we are given the interim probabilities, when is it that there exists an allocation rule that can generate these interim probabilities. Border (1991) gives a full characterization of these interim probabilities. In the talk, I will give the statement and a sketch of a graph theoretic proof of Border's theorem. I will connect Border's result to polymatroid constraints in combinatorial optimization. The extreme points of these constraints help us in solving various allocation problems in economic theory. |
Pstujeme web | visit: Skluzavky