Eisenberg-Gale markets: algorithms and game-theoretic properties

DOI10.1016/j.geb.2008.11.011zbMath1201.91110OpenAlexW1974874470MaRDI QIDQ993788

J. Martínez

Publication date: 20 September 2010

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.geb.2008.11.011

zbMATH Keywords

fairnessresource allocationconvex programprimal-dual algorithmcombinatorial algorithmgeneral equilibrium theoryascending price auctionscompetition monotonicityFisher market modelweak Gross substitutability

Mathematics Subject Classification ID

Convex programming (90C25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Deterministic network models in operations research (90B10) General equilibrium theory (91B50)

Related Items

2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties ⋮ Convergence of incentive-driven dynamics in Fisher markets ⋮ Multi-unit assignment under dichotomous preferences ⋮ On a Reduction for a Class of Resource Allocation Problems ⋮ Fair Division of Indivisible Goods for a Class of Concave Valuations ⋮ Dividing bads under additive utilities ⋮ Tatonnement beyond gross substitutes? Gradient descent to the rescue ⋮ Markets for public decision-making ⋮ Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets ⋮ A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives ⋮ Monotonicity and competitive equilibrium in cake-cutting ⋮ Bipartite choices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On total functions, existence theorems and computational complexity
• On competitiveness in uniform utility allocation markets
• A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Rationality and Strongly Polynomial Solvability of Eisenberg–Gale Markets with Two Agents
• Rate control for communication networks: shadow prices, proportional fairness and stability
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Understanding TCP Vegas
• Consensus of Subjective Probabilities: The Pari-Mutuel Method
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Market equilibrium via a primal--dual algorithm for a convex program
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Equitable cost allocations via primal-dual-type algorithms
• Minimum cuts, modular functions, and matroid polyhedra
• Optimal flows in networks with multiple sources and sinks
• The Complexity of Multiterminal Cuts
• Network information flow
• Multiway cuts in directed and node weighted graphs
• Packing Spanning Trees
• A primal-dual approximation algorithm for generalized Steiner network problems
• On Convex Minimization over Base Polytopes
• Automata, Languages and Programming
• Optimum branchings
• Multi-Commodity Network Flows