Internet and Network Economics: 4th International Workshop, Wine 2008, Shanghai, China, December 17-20, 2008. Proceedings

ISBN-13: 9783540921844 / Angielski / Miękka / 2008 / 734 str.

Christos Papadimitriou

Opis

This volume contains the papers presented at the International Workshop on Internet and Network Economics held during December 17-20, 2008, in Sha- hai, China, for its fourth edition. WINE 2008 provided a forum for researchers from di?erent disciplines to communicate with each other and exchange their researching ?ndings in this emerging ?eld. WINE 2008hadteninvitedspeakers: FanChungGraham, MatthewJackson, Lawrence Lau, Tom Luo, Eric Maskin, Paul Milgrom, Christos Papadimitriou, Herbert Scarf, Hal Varian and Yinyu Ye. There were 126 submissions. Each submission was reviewed on average by 2. 5 Programme Committee members. The Committee decided to accept 68 papers. The programme also included 10 invited talks. This ?nal program contained papers covering topics including equilibrium, information markets, sponsored auction, network economics, mechanism - sign, socialnetworks, advertisementpricing, computationalequilibrium, network games, algorithms and complexity for games. December 2008 Christos Papadimitriou Shuzhong Zhang Organization Programme Chairs Conference Chair Herbert E. Scarf (Yale University) Program Co-chair Christos Papadimitriou (UC Berkeley) Program Co-chair Shuzhong Zhang (Chinese University of Hong Kong) Local Organizing Committee Chairs Committee Chair Yifan Xu (Fudan University) Committee Co-chair Duan Li (Chinese University of Hong Kong) Committee Co-chair ShouyangWang(ChineseAcademyofSciences) Committee Co-chair Xiaoping Zhao (SSE INFONET Ltd.

Spis treści

Invited Talks 1: Special Session.- Mechanism Design Theory: How to Implement Social Goals.- Thirty Years of Chinese Economic Reform: Reasons for Its Success and Future Directions.- Invited Talks 2: Plenary Session.- Average Distance, Diameter, and Clustering in Social Networks with Homophily.- Assignment Exchanges.- Search Engine Ad Auctions.- Computational Economy Equilibrium and Application.- Invited Talks 3: Tutorial Session.- Four Graph Partitioning Algorithms.- Dynamic Spectrum Management: Optimization and Game Theoretic Formulations.- Some Recent Results in Algorithmic Game Theory.- The Elements of General Equilibrium Theory.- Session A.1: Market Equilibrium.- A Fast and Simple Algorithm for Computing Market Equilibria.- A FPTAS for Computing a Symmetric Leontief Competitive Economy Equilibrium.- Online and Offline Selling in Limit Order Markets.- Predictive Pricing and Revenue Sharing.- Dual Payoffs, Core and a Collaboration Mechanism Based on Capacity Exchange Prices in Multicommodity Flow Games.- Session B.1: Congestion Games.- Graphical Congestion Games.- How Hard Is It to Find Extreme Nash Equilibria in Network Congestion Games?.- On the Road to -Completeness: 8 Agents in a Singleton Congestion Game.- Conflicting Congestion Effects in Resource Allocation Games.- The Price of Malice in Linear Congestion Games.- Session C.1: Information Markets.- Parimutuel Betting on Permutations.- Strategies in Dynamic Pari-Mutual Markets.- Truthful Surveys.- Correlated Equilibrium of Bertrand Competition.- Diffusion of Innovations on Random Networks: Understanding the Chasm.- Session A.2: Nash Equilibrium I.- An Efficient PTAS for Two-Strategy Anonymous Games.- Equilibria of Graphical Games with Symmetries.- Equilibrium Points in Fear of Correlated Threats.- Performance Evaluation of a Descent Algorithm for Bi-matrix Games.- Worst-Case Nash Equilibria in Restricted Routing.- Session B.2: Network Games I.- Stackelberg Routing in Arbitrary Networks.- Computational Aspects of a 2-Player Stackelberg Shortest Paths Tree Game.- Local Two-Stage Myopic Dynamics for Network Formation Games.- Interference Games in Wireless Networks.- Taxing Subnetworks.- Session C.2: Solution Concepts.- Anonymity-Proof Voting Rules.- Overlapping Coalition Formation.- A Network-Based Asymmetric Nash Bargaining Solution.- How Public Opinion Forms.- A Game-Theoretic Analysis of Games with a Purpose.- Session A.3: Algorithms and Optimization I.- Inapproximability of Combinatorial Public Projects.- Algorithms for Optimal Price Regulations.- Improving the Efficiency of Load Balancing Games through Taxes.- Network Formation and Routing by Strategic Agents Using Local Contracts.- Network Creation Games with Disconnected Equilibria.- Session B.3: Mechanism Design I.- Randomized Truthful Mechanisms for Scheduling Unrelated Machines.- Optimal Mechanisms for Single Machine Scheduling.- Welfare Undominated Groves Mechanisms.- Redistribution of VCG Payments in Assignment of Heterogeneous Objects.- Bin Packing of Selfish Items.- Session C.3: Network Games II.- Restricted Core Stability of Flow Games.- Three Selfish Spanning Tree Games.- Stochastic Submodular Maximization.- On Pure and (Approximate) Strong Equilibria of Facility Location Games.- Efficiency, Fairness and Competitiveness in Nash Bargaining Games.- Session A.4: Equilibrium.- Computing an Extensive-Form Correlated Equilibrium in Polynomial Time.- Homogeneous Interference Game in Wireless Networks.- A Network Coloring Game.- Session B.4: Mechanism Design II.- Asynchronous Best-Reply Dynamics.- Fault Tolerance in Distributed Mechanism Design.- Bargaining Solutions in a Social Network.- Session C.4: Online Advertisement.- Sharing Online Advertising Revenue with Consumers.- Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems.- Position Auctions with Bidder-Specific Minimum Prices.- Session A.5: Sponsored Search Auctions.- A Cascade Model for Externalities in Sponsored Search.- Sponsored Search Auctions with Reserve Prices: Going Beyond Separability.- Auctions for Share-Averse Bidders.- Sponsored Search Auctions with Markovian Users.- On the Equilibria and Efficiency of the GSP Mechanism in Keyword Auctions with Externalities.- Session B.5: Voting Problem.- Biased Voting and the Democratic Primary Problem.- Frequent Manipulability of Elections: The Case of Two Voters.- The Power of Small Coalitions in Cost Sharing.- Social Context Games.- Session C.5: Algorithms and Optimization II.- Approximability and Parameterized Complexity of Minmax Values.- An “Ethical” Game-Theoretic Solution Concept for Two-Player Perfect-Information Games.- The Secretary Problem with a Hazard Rate Condition.- Impact of QoS on Internet User Welfare.- Nonlinear Pricing with Network Externalities.

Blurb

This book constitutes the refereed proceedings of the 4th International Workshop on Internet and Network Economics, WINE 2008, held in Shanghai, China, in December 2008.

The 68 revised full papers presented together with 10 invited talks were carefully reviewed and selected from 126 submissions. The papers are organized in topical sections on market equilibrium, congestion games, information markets, nash equilibrium, network games, solution concepts, algorithms and optimization, mechanism design, equilibrium, online advertisement, sponsored search auctions, and voting problems.