Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Natural Dynamics for Bargaining on Exchange Networks
107
0
0.0
(
0
)
Added by
Yashodhan Kanoria
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Bargaining networks model the behavior of a set of players that need to reach pairwise agreements for making profits. Nash bargaining solutions are special outcomes of such games that are both stable and balanced. Kleinberg and Tardos proved a sharp algorithmic characterization of such outcomes, but left open the problem of how the actual bargaining process converges to them. A partial answer was provided by Azar et al. who proposed a distributed algorithm for constructing Nash bargaining solutions, but without polynomial bounds on its convergence rate. In this paper, we introduce a simple and natural model for this process, and study its convergence rate to Nash bargaining solutions. At each time step, each player proposes a deal to each of her neighbors. The proposal consists of a share of the potential profit in case of agreement. The share is chosen to be balanced in Nashs sense as far as this is feasible (with respect to the current best alternatives for both players). We prove that, whenever the Nash bargaining solution is unique (and satisfies a positive gap condition) this dynamics converges to it in polynomial time. Our analysis is based on an approximate decoupling phenomenon between the dynamics on different substructures of the network. This approach may be of general interest for the analysis of local algorithms on networks.
rate research
Read More
We consider a one-sided assignment market or exchange network with transferable utility and propose a model for the dynamics of bargaining in such a market. Our dynamical model is local, involving iterative updates of offers based on estimated best alternative matches, in the spirit of pairwise Nash bargaining. We establish that when a balanced outcome (a generalization of the pairwise Nash bargaining solution to networks) exists, our dynamics converges rapidly to such an outcome. We extend our results to the cases of (i) general agent capacity constraints, i.e., an agent may be allowed to participate in multiple matches, and (ii) unequal bargaining powers (where we also find a surprising change in rate of convergence).
We consider bargaining problems which involve two participants, with a nonempty closed, bounded convex bargaining set of points in the real plane representing all realizable bargains. We also assume that there is no definite threat or disagreement point which will provide the default bargain if the players cannot agree on some point in the bargaining set. However, there is a nondeterministic threat: if the players fail to agree on a bargain, one of them will be chosen at random with equal probability, and that chosen player will select any realizable bargain as the solution, subject to a reasonable restriction.
Coalitional games are mathematical models suited to analyze scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental problem for coalitional games is to single out the most desirable outcomes in terms of appropriate notions of worth distributions, which are usually called solution concepts. Motivated by the fact that decisions taken by realistic players cannot involve unbounded resources, recent computer science literature reconsidered the definition of such concepts by advocating the relevance of assessing the amount of resources needed for their computation in terms of their computational complexity. By following this avenue of research, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonable compact form (otherwise, if the worths of all coalitions are explicitly listed, the input sizes are so large that complexity problems are---artificially---trivial). The starting investigation point is the setting of graph games, about which various open questions were stated in the literature. The paper gives an answer to these questions, and in addition provides new insights on the setting, by characterizing the computational complexity of the three concepts in some relevant generalizations and specializations.
We study decentralized markets with the presence of middlemen, modeled by a non-cooperative bargaining game in trading networks. Our goal is to investigate how the network structure of the market and the role of middlemen influence the markets efficiency and fairness. We introduce the concept of limit stationary equilibrium in a general trading network and use it to analyze how competition among middlemen is influenced by the network structure, how endogenous delay emerges in trade and how surplus is shared between producers and consumers.
There has been much work on exhibiting mechanisms that implement various bargaining solutions, in particular, the Kalai-Smorodinsky solution cite{moulin1984implementing} and the Nash Bargaining solution. Another well-known and axiomatically well-studied solution is the lexicographic maxmin solution. However, there is no mechanism known for its implementation. To fill this gap, we construct a mechanism that implements the lexicographic maxmin solution as the unique subgame perfect equilibrium outcome in the n-player setting. As is standard in the literature on implementation of bargaining solutions, we use the assumption that any player can grab the entire surplus. Our mechanism consists of a binary game tree, with each node corresponding to a subgame where the players are allowed to choose between two outcomes. We characterize novel combinatorial properties of the lexicographic maxmin solution which are crucial to the design of our mechanism.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
