Internet and Network Economics

Name: Internet and Network Economics | 6th International Workshop, WINE 2010, Stanford, CA, USA, December 13-17, 2010, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

6th International Workshop, WINE 2010, Stanford, CA, USA, December 13-17, 2010, Proceedings

Amin Saberi(Herausgeber*in)

Springer (Verlag)

Erschienen am 6. Dezember 2010

X, 580 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-17572-5 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title Page
Preface
Organization
Table of Contents
Regular Papers
Efficient Computation of the Shapley Value for Centrality in Networks
Introduction
SV as a Centrality Measure
Algorithms for SV-Based Network Centrality
Game 1: 1(C) = #Agents At-Most 1 Degree Away
Game 2: 2(C) = #Agents with At-Least k Neighbors in C
Game 3: 3(C) = #Agents At-Most dCutoff Away
Game 4: 4(C) = viV(G) f(Distance(vi,C))
Summary and Conclusions
On Approximate Nash Equilibria in Network Design
Introduction
Unweighted Games
Non-cooperative Games
Cooperative Games
Source-Sink Games and Directed Graphs
Weighted Games
The Efficiency of Fair Division with Connected Pieces
Introduction
Definitions and Notations
Results
Related Work
The Price of Envy-Freeness and Proportionality
Utilitarian Welfare
Egalitarian Welfare
The Price of Equitability
Trading Fairness for Efficiency
Conclusions and Open Problems
Collusion in VCG Path Procurement Auctions
Introduction
Preliminaries
Collusion in VCG Path Procurement Auctions
Colluding in VCG Path Procurement Auctions
Collusion Schemes
The Collusion Game
Related Work
Conclusion
Sequential Item Pricing for Unlimited Supply
Introduction
Preliminaries
Sequential Pricing
Existing Bounds for Cm,n,k and a New Lower Bound
Hereditary Maximizers
Revenue Approximation for Independent HM Valuations
Positive Allocative Externalities
Conclusions and Future Directions
The Cost of Moral Hazard and Limited Liability in the Principal-Agent Problem
Introduction
The Principal-Agent Model
The Monotone Likelihood-Ratio Property
Worst-Case Welfare Loss
Preliminaries
Bounding the Welfare Loss
The Case of Two Efforts and Two Outcomes
The General Case
A Tight Instance
Generalizations of the Basic Model
Specializations and Generalizations of the Stackelberg Minimum Spanning Tree Game
Introduction
Exact Algorithm for StackMST(0,0) with Costs in {a,b}
StackMST(0,0) Can Be Approximated within 7/4 +
StackMST(,) on Trees of Bounded Radius
A Novel Approach to Propagating Distrust
Introduction
The Propagation of Trust and Distrust
Prior Work on Distrust Propagation
Our System
Notation and Definitions
The System
Axioms
Analysis
Conclusion
Incentives in Online Auctions via Linear Programming
Introduction
Auction Model
Results
Previous Results
Secretary Problem and Linear Programming
The Online Auction Mechanism
Optimal Pricing in the Presence of Local Network Effects
Introduction
Model
Consumption Equilibria
Optimal Pricing
Perfect Price Discrimination
Choosing a Single Uniform Price
The Case of Two Prices: Full and Discounted
Conclusions
Local Dynamics in Bargaining Networks via Random-Turn Games
Introduction
From a Bargaining Game to a Random-Turn Game
Rate of Convergence
Conclusion and Future Work
Selective Call Out and Real Time Bidding
Introduction
Selective Call Out: The Model
Our Results, Roadmap and Related Work
Preliminaries
The Total Value Problem
Generalized Second Price with Reserve (GSP-Reserve)
Approximation Schemes for Sequential Posted Pricing in Multi-unit Auctions
Introduction
Preliminaries
Basic Results
LP-Based Algorithm for Large K
Approximation Factor
PTAS for Constant K
PTAS for Computing SPM
PTAS for Computing ASPM
Truthful Mechanisms for Exhibitions
Introduction
Related Work
Results and Techniques
Problem Definition and Preliminaries
The Single-Minded Case
A General Framework for Monotone Mechanisms
The Fat Ranges Case
The Rectangles Case
The Non-Single-Minded Case
A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines
Introduction
Preliminaries
Segmented Partitions
Graph Construction
Monotone Algorithm for Covering
Conclusions
Braess's Paradox in Large Sparse Graphs
Introduction
Previous Work
Our Contribution
Sketch of Ideas via a Motivating Example
Small Latency Separates Interior Vertices
Equal Distance Separates the Interior from s and t
Braess's Paradox Occurs in Erdos-Rényi Graphs
False-Name-Proofness in Social Networks
Introduction
Setting
False-Name-Proofness
Exogenously Given Trusted Nodes
Choosing Nodes to Verify (Endogenous Trust)
Conclusions and Future Research
Stackelberg Strategies for Network Design Games
Introduction
Model and Definitions
Existence of ``Good" Strategies
Efficient Strategies
Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games
Introduction
Model, Definitions, and Notation
The Winner-Imposing Proportional Mechanism
A Randomized Mechanism for Facility Location
Oblivious Winner-Imposing Mechanisms
A Deterministic Mechanism for Facility Location on the Line
Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms
Introduction
Submodular Maximization and Secretary Problems in an Economic Context
Our Main Ideas
Related Work
Independent Work on Submodular Secretaries.
Preliminaries
Submodular Maximization Subject to a Cardinality Constraint
Fast Algorithms for p-Systems and Knapsacks
Submodular Maximization for Independence Systems
The Algorithm for p-Independence Systems.
Submodular Maximization Over Knapsacks
Constrained Submodular Maximization in the Secretary Setting
Subject to a Cardinality Constraint
Subject to a Partition Matroid Constraint
Subject to a General Matroid Constraint
Strategic Cooperation in Cost Sharing Games
Introduction
Strong Equilibria Using Linear Programming
Strong Equilibria beyond Linear Programming
Fractional and Non-binary Resources
Approximate Equilibria
Open Problems
References
Coalition Formation and Price of Anarchy in Cournot Oligopolies
Introduction
Related Work
The Model
Cournot Games with a Fixed Partitioning of the Players
Cournot Coalition Formation Games
The Main Result
The Proof of the Upper Bound
The Construction of the Lower Bound
Coalition Formation under No-Regret
Discussion and Future Work
An FPTAS for Bargaining Networks with Unequal Bargaining Powers
Introduction
Model
Related Work
Outline of the Paper
MainResults
A Fast Local Algorithm
Proofs of Lemmas 9 and 10
Stability Is Critical
Further Directions
References
Value of Learning in Sponsored Search Auctions
Introduction
Model and Notations
Incentives in Auctions without Exploration
Value of Learning
Revenue of Auctions with Value of Learning
Simulation Results
Exploiting Myopic Learning
Introduction and Related Work
Cheat-Audit Games
The Game
Learning Dynamics
Objective
Optimal Policy
Single Round
General Policy
Discussion
Comparison with Nash Equilibrium
An Empirical Example
Conclusion
Proof of Lemma 2
The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds
Introduction
The Primal-Dual Framework
Preliminaries
A Primal-Dual Framework for POA Bounds
The Limits of (,)-Smoothness
Better Dual Certificates Give Better POA Upper Bounds
On the Competitive Ratio of Online Sampling Auctions
Introduction
Our Model
Online Sampling Auctions
Randomized Competitive Online Sampling Auctions
A Deterministic Online Sampling Auction: BPSFr
On the Competitive Ratio of BPSF and RSOP
Conclusion
Relation of z and y Values
Near-Strong Equilibria in Network Creation Games
Introduction
Model and Preliminaries
Pure Strategies
Correlated Mixed Strategies
You Share, I Share: Network Effects and Economic Incentives in P2P File-Sharing Systems
Introduction
Related Work
Models and Preliminaries
The Demand Model
Payment Schemes, Sharing Process, and Administrator's Objective
Theoretical Analysis of the Model
Characterization of Coverage Processes
Coverage Property of the Seed Set Process
Concavity of Expected Social Welfare
Experimental Evaluation
Conclusions
The Complexity of Equilibria in Cost Sharing Games
Introduction
Definitions and Notation
Computing a Good Pure Nash Equilibrium
Singleton Cost Sharing Games
Matroid Cost Sharing Games
Intractability of Cost Sharing Games
General Cost Sharing Games
Extending to Network Games
Tightness of PLS-Reductions
Discussion and Further Results
Practical and Efficient Approximations of Nash Equilibria for Win-Lose Games Based on Graph Spectra
Introduction
Graph Representation
Stationary Points of Descent Algorithms
Spectral Representation
Approximating an Equilibrium
Special Cases
Comparison with an Existing Approximation Result
Discussion and Future Work
Market Communication in Production Economies
Introduction
Markets and Market Communication
Arrow-Debreu Markets
Market Communication
A Lower Bound for the Arrow-Debreu Model
Conclusion
Strategy-Proof Voting Rules over Multi-issue Domains with Restricted Preferences
Introduction
Preliminaries
Conditional Rule Nets (CR-Nets)
Restricting Voters' Preferences
Strategy-Proof Voting Rules in Lexicographic Preference Domains
An Impossibility Theorem
Conclusion
References
Short Papers
Optimal Iterative Pricing over Social Networks (Extended Abstract)
Introduction
The Basic(k) Problem
The Rapid(k) Problem
Concluding Remarks
Equilibrium Pricing with Positive Externalities (Extended Abstract)
Introduction
Related Work
Model
Uniqueness of Equilibria
Revenue Maximization
Symmetric Setting
Linear Version
The Good, The Bad and The Cautious: Safety Level Cooperative Games
Introduction
Preliminaries
Safety Level Cooperative Games
Safety Level Coalitions in Congestion Games
Anonymous Cooperative Games
Non-anonymous Settings
Conclusions
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing
Introduction
Preliminaries
Contributions
Hardness of Approximation
Proof of Theorem 1
Shortcut Instances
Conclusions
The Complexity of Determining the Uniqueness of Tarski's Fixed Point under the Lexicographic Ordering
Introduction
Polynomial-Time Reduction and Main Results
Approximation Algorithms for Non-single-minded Profit-Maximization Problems with Limited Supply
Introduction
Problem Definition and Preliminaries
The Main Algorithm and Its Applications
Applications
Refinement for the Non-single-Minded Highway Problem
Approximation Algorithms for Campaign Management
Introduction
Preliminaries
Scoring Rules
Copeland and Maximin
Conclusions
Envy-Free Pricing with General Supply Constraints
Introduction
Preliminaries
Envy-Free Pricing
Supply Constraints
Envy-Free Pricing and Supply Constraints
Walrasian Equilibria
General Unit Demand Case
Bounded Set Size (UD-BSS)
Bounded Frequency (UD-BF)
Impersonation Strategies in Auctions
Introduction
Model
Example: The Kelly Mechanism
Impersonation-Proofness
Market Equilibrium with Transaction Costs
Introduction
Algorithm
Analysis
An Axiomatic Characterization of Continuous-Outcome Market Makers
Introduction
Background
An Axiomatic Framework
Cost Functional Based Market Makers for Continuous-Outcome Events
Desirable Properties
Impossibility Result
Discussion and Conclusion
Online Labor Markets
Introduction
Overview
Definition
Nature of Labor Markets and Role for Intermediation
What the Market Creators Provide
Price and Price Structure
Setting the Optimal ad Valorem Price Level
Competition and Specialization
Market Creator Strategy
Recruitment that Affects Supply and Demand
Productivity and Welfare Implications
Discrete Strategies in Keyword Auctions and Their Inefficiency for Locally Aware Bidders
Introduction
Definitions and Preliminaries
Discrete Bidding Strategies
Locally Aware Bidders and Local Stability
On (Group) Strategy-Proof Mechanisms without Payment for Facility Location Games
Introduction
Preliminaries
Strategy-Proof Mechanisms
Group Strategy-Proof Mechanisms
Threshold Models for Competitive Influence in Social Networks
Introduction
The Weight-Proportional Competitive Linear Threshold Model
The Separated-Threshold Model for Competing Technologies
Competitive Threshold Model with Forcing
Hardness of Approximation
The OR Model
Repeating OR Processes
Conclusions
Counter Examples for the Weight-Proportional Competitive Linear Threshold Model
Proof of Monotonicity of Separated Threshold Model
Counter-Examples for the Competitive Threshold Model with Forcing
Proof of the Hardness of Approximation Result
Course Allocation by Proxy Auction
Introduction
The Proxy Bidding Mechanism
Welfare Properties
Comparison with the HBS Draft
Strategic Play in the Proxy Bidding Mechanism
Extended Preference Support
Conclusion and Future Work
False-Name-Proofness in Facility Location Problem on the Real Line
Introduction
False-Name-Proofness
Future Works
Non-separable, Quasiconcave Utilities are Easy - in a Perfect Price Discrimination Market Model (Extended Abstract)
Introduction
Price Discrimination and Our Results
The Market Model
Determining Buyers' Rates
The Convex/Nonlinear Program
The Welfare Theorems
Average-Case Analysis of Mechanism Design with Approximate Resource Allocation Algorithms
Introduction
Preliminaries
Connecting Approximation and Incentives
Applying the Non-uniform Incentive Bound
Example: Combinatorial Auctions
Conclusion
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken