NDLI: Proportional response dynamics leads to market equilibrium

Please wait, while we are loading the content...

Statistically-hiding commitment from any one-way function

Voronoi diagrams in n · 2o(√lg lg n) time

Faster integer multiplication

Smooth sensitivity and sampling in private data analysis

How to rank with few errors

On the submodularity of influence in social networks

Hardness of routing with congestion in directed graphs

Iteratively constructing preconditioners via the conjugate gradient method

Distributed computing theory: algorithms, impossibility results, models, and proofs

The condition number of a randomly perturbed matrix

Circuit lower bounds for Merlin-Arthur classes

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

Linear probing with constant independence

Limitations of VCG-based mechanisms

Interval completion with few edges

Parallel repetition: simplifications and the no-signaling case

Randomly coloring planar graphs with fewer colors than the maximum degree

Property testing in hypergraphs and the removal lemma

Exponential separations for one-way quantum communication complexity, with applications to cryptography

Playing games with approximation algorithms

Toward a general theory of quantum games

All-pairs bottleneck paths for general graphs in truly sub-cubic time

Uncertainty principles, extractors, and explicit embeddings of l2 into l1

Survivable network design with degree or order constraints

Lower bounds for randomized read/write stream algorithms

On achieving the "best of both worlds" in secure multiparty computation

Lower bounds for 2-dimensional range counting

Fourier meets möbius: fast subset convolution

The price of privacy and the limits of LP decoding

Approximation algorithms for budgeted learning problems

First to market is not everything: an analysis of preferential attachment with fitness

Polynomial flow-cut gaps and hardness of directed cut problems

On the convergence of Newton's method for monotone systems of polynomial equations

Balanced allocations: the weighted case

Interpolation of depth-3 arithmetic circuits with two multiplication gates

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

Optimal suffix selection

The communication complexity of uncoupled nash equilibrium procedures

Computing crossing number in linear time

An efficient parallel repetition theorem for Arthur-Merlin games

Inapproximability of the Tutte polynomial

Testing k-wise and almost k-wise independence

Negative weights make adversaries stronger

Reordering buffers for general metric spaces

Search via quantum walk

More algorithms for all-pairs shortest paths in weighted graphs

Vertex cuts, random walks, and dimension reduction in series-parallel graphs

Approximating minimum bounded degree spanning trees to within one of optimal

Lower bounds in communication complexity based on factorization norms

Zero-knowledge from secure multiparty computation

Combinatorial complexity in O-minimal geometry

An approximation algorithm for max-min fair allocation of indivisible goods

Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads

Balanced max 2-sat might not be the hardest

A combinatorial, primal-dual approach to semidefinite programs

Towards 3-query locally decodable codes of subexponential length

Separating $AC^{0}$ from depth-2 majority circuits

Proportional response dynamics leads to market equilibrium

Terminal backup, 3D matching, and covering cubic graphs

Low-end uniform hardness vs. randomness tradeoffs for AM

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

Low-degree tests at large distances

On the impossibility of a quantum sieve algorithm for graph isomorphism

Some new results on node-capacitated packing of A-paths

Local embeddings of metric spaces

Improved approximation for directed cut problems

Constructing non-computable Julia sets

Simple deterministic approximation algorithms for counting matchings

Tight bounds for asynchronous randomized consensus

A 3-query PCP over integers

One sketch for all: fast algorithms for compressed sensing

Eisenberg-Gale markets: algorithms and structural properties

Holographic algorithms: from art to science

Verifying and decoding in constant depth

Lattices that admit logarithmic worst-case to average-case connection factors

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs

Sampling-based dimension reduction for subspace approximation

Degree-constrained network flows

Proportional response dynamics leads to market equilibrium

Content Provider	ACM Digital Library
Author	Zhang, Li Wu, Fang
Abstract	One of the main reasons of the recent success of peer to peer (P2P)file sharing systems such as BitTorrent is their built-in tit-for-tat mechanism. In this paper, we model the bandwidth allocation in a P2P system as an exchange economy and study a tit-for-tat dynamics, namely the proportional response dynamics, in this economy. In aproportional response dynamics each player distributes its good to its neighbors proportional to the utility it received from them in thelast period. We show that this dynamics not only converges but converges to a market equilibrium, a standard economic characterization of efficient exchanges in a competitive market. In addition, for some classes of utility functions we consider, it converges much faster than the classical tat process and any existingalgorithms for computing market equilibria. As a part of our proof we study the double normalization of a matrix, an operation that linearly scales the rows of a matrix sothat each row sums to a prescribed positive number, followed by a similar scaling of the columns. We show that the iterative double normalization process of any non-negative matrix always converges. This complements the previous studies in matrix scaling that has focused on the convergence condition of the process when the row and column normalizations are considered as separate steps.
Starting Page	354
Ending Page	363
Page Count	10
File Format	PDF
ISBN	9781595936318
DOI	10.1145/1250790.1250844
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-06-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Proportional response dyanmics Matrix equilibrium Matrix scaling Peer to peer sharing
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in