Present-Biased Optimization
- URL: http://arxiv.org/abs/2012.14736v1
- Date: Tue, 29 Dec 2020 12:40:59 GMT
- Title: Present-Biased Optimization
- Authors: Fedor V. Fomin, Pierre Fraigniaud, and Petr A. Golovach
- Abstract summary: The paper extends the framework proposed by Akerlof (1991) for studying various aspects of human behavior related to time-inconsistent planning.
We show that the ratio between the cost of the solutions computed by present-biased agents and the cost of the optimal solutions may differ significantly depending on the problem constraints.
- Score: 8.775878711928591
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper explores the behavior of present-biased agents, that is, agents
who erroneously anticipate the costs of future actions compared to their real
costs. Specifically, the paper extends the original framework proposed by
Akerlof (1991) for studying various aspects of human behavior related to
time-inconsistent planning, including procrastination, and abandonment, as well
as the elegant graph-theoretic model encapsulating this framework recently
proposed by Kleinberg and Oren (2014). The benefit of this extension is
twofold. First, it enables to perform fine grained analysis of the behavior of
present-biased agents depending on the optimisation task they have to perform.
In particular, we study covering tasks vs. hitting tasks, and show that the
ratio between the cost of the solutions computed by present-biased agents and
the cost of the optimal solutions may differ significantly depending on the
problem constraints. Second, our extension enables to study not only
underestimation of future costs, coupled with minimization problems, but also
all combinations of minimization/maximization, and
underestimation/overestimation. We study the four scenarios, and we establish
upper bounds on the cost ratio for three of them (the cost ratio for the
original scenario was known to be unbounded), providing a complete global
picture of the behavior of present-biased agents, as far as optimisation tasks
are concerned.
Related papers
- Triple Simplex Matrix Completion for Expense Forecasting [11.52704888524571]
This paper proposes a constrained non-negative matrix completion model that predicts expenses by learning the likelihood of the project correlating with certain expense patterns in the latent space.
Results from two real datasets demonstrate the effectiveness of the proposed method in comparison to state-of-the-art algorithms.
arXiv Detail & Related papers (2023-10-23T18:25:33Z) - Leaving the Nest: Going Beyond Local Loss Functions for
Predict-Then-Optimize [57.22851616806617]
We show that our method achieves state-of-the-art results in four domains from the literature.
Our approach outperforms the best existing method by nearly 200% when the localness assumption is broken.
arXiv Detail & Related papers (2023-05-26T11:17:45Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions.
We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers.
We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
arXiv Detail & Related papers (2023-02-02T16:30:33Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints.
We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates.
The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
arXiv Detail & Related papers (2022-09-16T09:38:38Z) - Resource Allocation to Agents with Restrictions: Maximizing Likelihood
with Minimum Compromise [28.2469613376685]
We show that a Principle chooses a maximum matching randomly so that each agent is matched to a resource with some probability.
Agents would like to improve their chances of being matched by modifying their restrictions within certain limits.
We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets.
arXiv Detail & Related papers (2022-09-12T11:58:19Z) - Planning with Dynamically Estimated Action Costs [2.8326418377665346]
Information about action costs is critical for real-world AI planning applications.
Recent approaches use black-box external action cost estimators, often learned from data, that are applied during the planning phase.
We suggest a generalization of deterministic planning with action costs that allows selecting between multiple estimators for action cost.
arXiv Detail & Related papers (2022-06-08T21:10:37Z) - Probabilistically Robust Recourse: Navigating the Trade-offs between
Costs and Robustness in Algorithmic Recourse [34.39887495671287]
We propose an objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates.
We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance.
Experimental evaluation with multiple real world datasets demonstrates the efficacy of the proposed framework.
arXiv Detail & Related papers (2022-03-13T21:39:24Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
We casting online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of $m$m resource constraints.
Our framework allows the decision maker to handle its evidence flexibility and costoretic functions.
arXiv Detail & Related papers (2022-02-28T12:10:48Z) - Towards Robust and Reliable Algorithmic Recourse [11.887537452826624]
We propose a novel framework, RObust Algorithmic Recourse (ROAR), that leverages adversarial training for finding recourses that are robust to model shifts.
We also carry out detailed theoretical analysis which underscores the importance of constructing recourses that are robust to model shifts.
arXiv Detail & Related papers (2021-02-26T17:38:52Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values.
We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism.
Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
arXiv Detail & Related papers (2020-04-19T18:00:58Z) - Cost-Sensitive Portfolio Selection via Deep Reinforcement Learning [100.73223416589596]
We propose a cost-sensitive portfolio selection method with deep reinforcement learning.
Specifically, a novel two-stream portfolio policy network is devised to extract both price series patterns and asset correlations.
A new cost-sensitive reward function is developed to maximize the accumulated return and constrain both costs via reinforcement learning.
arXiv Detail & Related papers (2020-03-06T06:28:17Z)
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.