## Internet and Network Economics: Third International Workshop,WINE 2007, San Diego, CA, USA, December 12-14, 2007, ProceedingsThe Workshop on Internet and Network Economics (WINE 2007), held Dec- ber 12 14, 2007 at San Diego for its third edition, provided a forum for - searchers from di?erent disciplines to communicate their research works in this emerging ?eld. Wehadfourplenaryspeakers: KennethArrow, HerbertScarf, VijayVazirani, and Christos Papadimitriou, speaking on economic equilibrium and its history, its solution methodologies (the simplicial structure method and the primal dual method), as well as the computation of Nash equilibrium. This?nalprogramincluded61peer-reviewedpaperscoveringtopicsincluding equilibrium, informationmarket, sponsoredauction, network economics, mec- nism design, socialnetworks, advertisementpricing, computationalgeneraleq- librium, network games, algorithms and complexity for games. December 2007 Xiaotie Deng Fan Chung Graham Please purchase PDF Split-Merge on www. verypdf. com to remove this watermark. Organization WINE 2007 was organized by the Department of Computer Science, Univeristy of California at San Diego. Program Committee Conference Chair Ronald Graham (University of California, San Diego) Local Arrangement Chair Tara Javidi (University of California, San Diego) Program Committee Co-chair Xiaotie Deng (City University of Hong Kong) Program Committee Co-chair Fan Chung Graham (University of California, San Diego) Plenary Speakers Kenneth J. Arrow (Stanford University) Christos H. Papadimitriou (University of California, Berkeley) Herbert E. Scarf (Yale University) Vijay V. Vazirani (Georgia Institute of Technology) Committee Members Sushil Bikhchandani (University of California, Los Angeles) Samuel R |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

A Problem and Its History | 1 |

My Favorite Simplicial Complex and Some of Its Applications | 3 |

Markets and the PrimalDual Paradigm | 4 |

The Computation of Equilibria | 5 |

A Note on Equilibrium Pricing as Convex Optimization | 7 |

New Algorithms for Approximate Nash Equilibria in Bimatrix Games | 17 |

A Unified Approach to Congestion Games and TwoSided Markets | 30 |

An Optimization Approach for Approximate Nash Equilibria | 42 |

Adwords Auctions with Decreasing Valuation Bids | 335 |

An Adaptive Sponsored Search Mechanism δGain Truthful in Valuation Time and Budget | 341 |

Extending Polynomial Time Computability to Markets with Demand Correspondences | 347 |

Market Equilibrium Using Auctions for a Class of GrossSubstitute Utilities | 356 |

Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets | 362 |

Beyond Weak Gross Substitutes | 368 |

On Competitiveness in Uniform Utility Allocation Markets | 374 |

Total Latency in Singleton Congestion Games | 381 |

GradientBased Algorithms for Finding Nash Equilibria in Extensive Form Games | 57 |

Bluffing and Strategic Reticence in Prediction Markets | 70 |

Mechanisms and Performance | 82 |

Information Sharing Communities | 96 |

Competitive Safety Strategies in Position Auctions | 108 |

Maintaining Equilibria During Exploration in Sponsored Search Auctions | 119 |

Stochastic Models for Budget Optimization in SearchBased Advertising | 131 |

Auctions with Revenue Guarantees for Sponsored Search | 143 |

Equilibrium Analysis of Dynamic Bidding in Sponsored Search Auctions | 155 |

Bidding Strategies in Sponsored Search Auction | 167 |

CostBalancing Tolls for Atomic Network Congestion Games | 179 |

Bilateral Contracting and Myopic Dynamics | 191 |

Who Should Pay for Forwarding Packets? | 208 |

On the Performance of Congestion Games for Optimum Satisfiability Problems | 220 |

IncentiveCompatible Interdomain Routing with Linear Utilities | 232 |

FalseNameProof Mechanisms for Hiring a Team | 245 |

Mechanism Design on Trust Networks | 257 |

Stochastic Mechanism Design | 269 |

A Note on Maximizing the Spread of Influence in Social Networks | 281 |

A Network Creation Game with Nonuniform Interests | 287 |

Making Money by Pricing Below Cost | 293 |

PageRank as a Weak Tournament Solution | 300 |

Competitive Influence Maximization in Social Networks | 306 |

Sponsored Search with Contexts | 312 |

Capacity Constraints and the Inevitability of Mediators in Adword Auctions | 318 |

Cost of Conciseness in Sponsored Search Auctions | 326 |

The Importance of Network Topology in Local Contribution Games | 388 |

Secure Relative Performance Scheme | 396 |

Selfishness Collusion and Power of Local Search for the ADMs Minimization Problem | 404 |

The WiFi Roaming Game | 412 |

On the Complexity of Pure Nash Equilibria in PlayerSpecific Network Congestion Games | 419 |

The Stable Roommates Problem with GloballyRanked Pairs | 431 |

A PSPACEcomplete Sperner Triangle Game | 445 |

Group Dominant Strategies | 457 |

Weighted Boolean Formula Games | 469 |

Core Stability of Vertex Cover Games | 482 |

Maximizing Revenue in Sequential Auctions | 491 |

Approximate Mechanisms for the Graphical TSP and Other Graph Traversal Problems | 503 |

To Be or Not to Be Served | 515 |

Ad Auction Design and User Experience | 529 |

An Approximation Algorithm | 535 |

Empirical Price Modeling for Sponsored Search | 541 |

Payperaction Model for Online Advertising | 549 |

Public Advertisement Broker Markets | 558 |

Stability Against Group Deviations in Noncooperative Computation | 564 |

Monotone Properties of Randomized Symmetric Incentive Compatible Auctions | 570 |

Computing Optimal Bundles for Sponsored Search | 576 |

On the Price of Truthfulness in Path Auctions | 584 |

Characterizing Truthful Market Design | 590 |

596 | |

### Common terms and phrases

advertiser agent algorithm allocation approximation assume beneﬁt Berlin Heidelberg 2007 bidder boolean bound budget bundle buyer clause competitive Computer Science consider constraint converges corresponding cost decreasing deﬁned Deﬁnition Deng and F.C. denote deviate diﬀerent distribution dynamic edge eﬀect eﬃcient Electronic Commerce envy-free exists F.C. Graham Eds feasible ﬁnd ﬁnding ﬁrst ﬁxed ﬂow Game Theory given graph Heidelberg incentive keyword Lemma linear LMSR LNCS matroid maximize maximum maximum matching mediator monotone Nash equilibrium node NP-hard number of players optimal solution outcome paper path payment payoﬀ player-speciﬁc polynomial prediction markets Price of Anarchy problem Proc proﬁle proﬁt proof resource revenue satisﬁes search engine selﬁsh slot social speciﬁc sponsored search sponsored search auctions Springer-Verlag Berlin Heidelberg stochastic subset Theorem tolls traders valuations variables vector vertex vertex cover vindictive WBFG xxxxx xxxxx xxxxx xxxxxx xxxxxx xxxxxx