Submodular optimization views on the random assignment problem

DOI10.1007/S10107-018-1310-4MaRDI QIDQ2330658zbMATH OpenOpenAlexFDO

Authors Satoru Fujishige, Yoshio Sano, Ping Zhan

Publication date 22 October 2019

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2433/232502

zbMATH Keywords

probabilistic serial mechanismrandom assignment problemsubmodular optimizationsubmodular flowsindependent flowsnon-pricing allocation

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Matching models (91B68)

Recommendations

• A simple characterization of assignment mechanisms on set constraints
• A solution to the random assignment problem on the full preference domain
• Optimal approximation for the submodular welfare problem in the value oracle model
• Extended random assignment mechanisms on a family of good sets
• The Fair Resource Allocation Problem with Submodular Constraints

Cites work

• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Concept of Egalitarianism Under Participation Constraints
• A Fast Parametric Maximum Flow Algorithm and Applications
• A new solution to the random assignment problem.
• A note on object allocation under lexicographic preferences
• A solution to the random assignment problem on the full preference domain
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• Allocation of divisible goods under lexicographic preferences
• An equilibrium analysis of the probabilistic serial mechanism
• Balancing supply and demand under bilateral constraints
• Consistent bilateral assignment
• Discrete Convex Analysis
• Efficient, fair, and strategy-proof (re)allocation under network constraints
• Egalitarianism under earmark constraints
• Entropy, desegregation, and proportional rationing
• GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY
• Generalized reduced-form auctions: a network-flow approach
• Groupstrategyproofness of the egalitarian mechanism for constrained rationing problems
• Incentives in the probabilistic serial mechanism
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Monotone-path Dutta-Ray solutions on convex games
• One-dimensional mechanism design
• Optimal flows in networks with multiple sources and sinks
• Population monotonicity and consistency in convex games: Some logical relations
• Probabilistic assignment of objects: characterizing the serial rule
• Probabilistic assignment problem with multi-unit demands: a generalization of the serial rule and its characterization
• Random Matching Under Dichotomous Preferences
• Random assignment of multiple indivisible objects
• Random assignment: redefining the serial rule
• Submodular functions and optimization.
• The Bipartite Rationing Problem
• The replacement principle in networked economies with single-peaked preferences
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Two axiomatic approaches to the probabilistic serial mechanism
• \(M\)-convex function on generalized polymatroid

Cited in

(6)

• A simple characterization of assignment mechanisms on set constraints
• Extended random assignment mechanisms on a family of good sets
• Simultaneous eating algorithm and greedy algorithm in assignment problems
• Submodular reassignment problem for reallocating agents to tasks with synergy effects
• Submodular Cost Allocation Problem and Applications
• Ex ante and ex post envy-freeness on polytope resources

This page was built for publication: Submodular optimization views on the random assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330658)