Facility Reallocation on the Line
- URL: http://arxiv.org/abs/2103.12894v1
- Date: Tue, 23 Mar 2021 23:48:45 GMT
- Title: Facility Reallocation on the Line
- Authors: Bart de Keijzer and Dominik Wojtczak
- Abstract summary: We consider a multi-stage facility reallocation problem on the real line, where a facility is being moved between time stages based on the locations reported by $n$ agents.
The aim of the reallocation algorithm is to minimise the social cost, i.e., the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility.
- Score: 9.40406631624105
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a multi-stage facility reallocation problems on the real line,
where a facility is being moved between time stages based on the locations
reported by $n$ agents. The aim of the reallocation algorithm is to minimise
the social cost, i.e., the sum over the total distance between the facility and
all agents at all stages, plus the cost incurred for moving the facility. We
study this problem both in the offline setting and online setting. In the
offline case the algorithm has full knowledge of the agent locations in all
future stages, and in the online setting the algorithm does not know these
future locations and must decide the location of the facility on a
stage-per-stage basis. We derive the optimal algorithm in both cases. For the
online setting we show that its competitive ratio is $(n+2)/(n+1)$. As neither
of these algorithms turns out to yield a strategy-proof mechanism, we propose
another strategy-proof mechanism which has a competitive ratio of $(n+3)/(n+1)$
for odd $n$ and $(n+4)/n$ for even $n$, which we conjecture to be the best
possible. We also consider a generalisation with multiple facilities and
weighted agents, for which we show that the optimum can be computed in
polynomial time for a fixed number of facilities.
Related papers
- Communication Efficient Decentralization for Smoothed Online Convex Optimization [9.449153668916098]
We study the multi-agent Smoothed Online Convex Optimization (SOCO) problem, where $N$ agents interact through a communication graph.
In each round, each agent $i$ receives a strongly convex hitting cost function $fi_t$ in an online fashion.
Our results hold even when the communication graph changes arbitrarily and adaptively over time.
arXiv Detail & Related papers (2024-11-13T05:59:04Z) - Online Fair Allocation of Perishable Resources [1.4952056744888913]
We consider a practically motivated variant of the canonical online fair allocation problem.
A decision-maker has a budget of perishable resources to allocate over a fixed number of rounds.
The goal is to construct a sequence of allocations that is envy-free and efficient.
arXiv Detail & Related papers (2024-06-04T15:14:10Z) - Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
We develop a robust decentralized saddle-point algorithm against random link failures with heterogeneous probabilities.
We extend our algorithm and analysis to the two-point bandit feedback scenario.
arXiv Detail & Related papers (2024-01-04T00:57:33Z) - Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
We study decentralized learning in two-player zero-sum discounted Markov games.
The goal is to design a policy optimization algorithm for either agent satisfying two properties.
arXiv Detail & Related papers (2023-03-03T02:40:26Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions.
We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario.
Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
arXiv Detail & Related papers (2022-07-25T18:29:16Z) - Policy Optimization for Markov Games: Unified Framework and Faster
Convergence [81.3266426402464]
We show that the state-wise average policy of this algorithm converges to an approximate Nash equilibrium (NE) of the game.
We extend this algorithm to multi-player general Markov Games and show a $mathcalwidetildeO(T-1/2)$ convergence rate to Correlated Equilibria (CCE)
arXiv Detail & Related papers (2022-06-06T14:23:13Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
We study Federated Bilevel Optimization problems. Specifically, we first propose the FedBiO, a deterministic gradient-based algorithm.
We show FedBiO has complexity of $O(epsilon-1.5)$.
Our algorithms show superior performances compared to other baselines in numerical experiments.
arXiv Detail & Related papers (2022-05-03T16:40:22Z) - Improved Bounds for Online Facility Location with Predictions [14.973636284231047]
We consider Online Facility Location in the framework of learning-augmented online algorithms.
In OFL, demands arrive one-by-one in a metric space and must be assigned to an open facility upon arrival.
We present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities.
arXiv Detail & Related papers (2021-07-17T16:44:27Z) - Online Apprenticeship Learning [58.45089581278177]
In Apprenticeship Learning (AL), we are given a Markov Decision Process (MDP) without access to the cost function.
The goal is to find a policy that matches the expert's performance on some predefined set of cost functions.
We show that the OAL problem can be effectively solved by combining two mirror descent based no-regret algorithms.
arXiv Detail & Related papers (2021-02-13T12:57:51Z) - A Provably Efficient Algorithm for Linear Markov Decision Process with
Low Switching Cost [53.968049198926444]
We present the first algorithm for linear MDP with a low switching cost.
Our algorithm achieves an $widetildeOleft(sqrtd3H4Kright)$ regret bound with a near-optimal $Oleft(d Hlog Kright)$ global switching cost.
arXiv Detail & Related papers (2021-01-02T18:41:27Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
We consider a general online optimization problem with multiple budget constraints over a horizon of finite time periods.
The objective of the decision maker is to maximize the cumulative reward subject to the budget constraints.
This formulation captures a wide range of applications including online linear programming and network revenue management.
arXiv Detail & Related papers (2020-12-13T04:47:37Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.