Predecessor Search
- PDF / 221,021 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 1 Downloads / 214 Views
Definition 2 A symmetric Nash equilibrium set of prices (SNE) satisfies vs p s x s vs p t x t for all t and s: Equivalently, vs (x s x t ) p s x s p t x t for all t and s:
Key Results
P
Recommended Reading 1. Demange, G., Gale, D., Sotomayor, M.: Multi-item auctions. J. Polit. Econ. 94(4), 863–72 (1986) 2. Edelman, B., Ostrovsky, M., Schwartz, M.: Internet advertising and the generalized second price auction. NBER Working Paper, 11765, November 2005 3. Roth, A., Sotomayor, M.: Two-Sided Matching. Cambridge University Press, Cambridge (1990) 4. Shapely, L., Shubik, M.: The Assignment Game I: the core. Int. J. Game Theor. 1, 111–130 (1972) 5. Varian, H.R.: Position auctions. Int. J. Ind. Organ. 25(6), 1163– 1178 (2007)
Facts of NE and SNE Fact 1 (Non-negative surplus) In an SNE, vs p s . Fact 2 (Monotone values) In an SNE, vs1 vs , for all s. Fact 3 (Monotone prices) In an SNE, p s1 x s1 > p s x s and p s1 p s for all s. If vs > p s then p s1 > p s . Fact 4 (N E SN E) If a set of prices is an SNE then it is an NE. Fact 5 (One-step solution) If a set of bids satisfies the symmetric Nash equilibria inequalities for s + 1 and s 1, then it satisfies these inequalities for all s. Fact 6 The maximum revenue NE yields the same revenue as the upper recursive solution to the SNE. A Sufficient and Necessary Condition of the Existence of a Pure Strategy Nash Equilibrium in the Position Auction Game Theorem 1 In the position auction described before, a pure strategy Nash equilibrium exists if and only if all the intervals p s x s p s+1 x s+1 p s1 x s1 p s x s ; ; for s = 2; 3; : : : ; S x s x s+1 x s1 x s are non-empty. Applications The model studied in this paper is a simple and elegant abstraction of the real adword auctions used by search engines such as Google and Yahoo. Different search engines have slightly different rules. For example, Yahoo ranks the advertisers according to their bids, while Google ranks the advertisers not only according to their bids but also according to the likelihood of their links being clicked. However, similar analysis can be applied to real world situations, as the author has demonstrated above for the Google adword auction case. Cross References Adwords Pricing
Predecessor Search ˘ scu, Thorup 2006; Patra¸ ˘ MIHAI PATRA S¸ CU CSAIL, MIT, Cambridge, MA, USA
Keywords and Synonyms Predecessor problem Successor problem IP lookup Problem Definition Consider an ordered universe U, and a set T U with jTj = n. The goal is to preprocess T, such that the following query can be answered efficiently: given x 2 U, report the predecessor of x, i. e. maxfy 2 T j y < xg. One can also consider the dynamic problem, where elements are inserted and deleted into T. Let tq be the query time, and tu the update time. This is a fundamental search problem, with an impressive number of applications. Later, this entry discusses IP lookup (forwarding packets on the Internet), orthogonal range queries and persistent data structures as examples. The problem was considered in
Data Loading...
