Dynamic Combinatorial Assignment
We study a model of dynamic combinatorial assignment of indivisible objects without money. We introduce a new solution concept called `dynamic approximate competitive equilibrium from equal incomes'' (DACEEI), which stipulates that markets must approximately clear in almost all time periods. A naive repeated application of approximate competitive equilibrium from equal incomes (Budish, 2011) does not yield a desirable outcome because the approximation error in market-clearing compounds quickly over time. We therefore develop a new version of the static approximate competitive equilibrium from carefully constructed random budgets which ensures that, in expectation, markets clear exactly. We then use it to design the `online combinatorial assignment mechanism'' (OCAM) which implements a DACEEI with high probability. The OCAM is (i) group-strategyproof up to one object (ii) envy-free up to one object for almost all agents (iii) approximately market-clearing in almost all periods with high probability when the market is large and arrivals are random. Applications include refugee resettlement, daycare assignment, and airport slot allocation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Decentralizing Coordination in Open Vehicle Fleets for Scalable and Dynamic Task Allocation
One of the major challenges in the coordination of large, open, collaborative, and commercial vehicle fleets is dynamic task allocation. Self-concerned individually rational vehicle drivers have both local and global obj…
Combinatorial OptimizationFractals2019: Combinatorial Optimisation with Dynamic Constraint Annealing
Fractals2019 started as a new experimental entry in the RoboCup Soccer 2D Simulation League, based on Gliders2d code base, and advanced to become a RoboCup-2019 champion. We employ combinatorial optimisation methods, wit…
BlockingNeural Approximate Dynamic Programming for On-Demand Ride-Pooling
On-demand ride-pooling (e.g., UberPool) has recently become popular because of its ability to lower costs for passengers while simultaneously increasing revenue for drivers and aggregation companies. Unlike in Taxi on De…
Deep Reinforcement LearningReinforcement LearningBayesian Optimization-based Combinatorial Assignment
We study the combinatorial assignment domain, which includes combinatorial auctions and course allocation. The main challenge in this domain is that the bundle space grows exponentially in the number of items. To address…
Bayesian OptimizationAssignment-Space-Based Multi-Object Tracking and Segmentation
Multi-object tracking and segmentation (MOTS) is important for understanding dynamic scenes in video data. Existing methods perform well on multi-object detection and segmentation for independent video frames, but tr…
Multi-Object TrackingMulti-Object Tracking and SegmentationObjectobject-detection+3