1,721,212 research outputs found
Online mechanism design for vehicle-to-grid car parks
Full text linkVehicle-to-grid (V2G) is a promising approach whereby electric vehicles (EVs) are used to store excess electricity supply (e.g., from renewable sources), which is sold back to the grid in times of scarcity. In this paper we consider the setting of a smart car park, where EVs come and go, and can be used for V2G while parked. We develop novel allocation and payment mechanisms which truthfully elicit the EV owners' preferences and constraints, including arrival, departure, required charge, as well as the costs of discharging due to loss of efficiency of the battery. The car park will schedule the charging and discharging of each EV, ensuring the constraints of the EVs are met, and taking into consideration predictions about future electricity prices. Optimally solving the global problem is intractable, and we present three novel heuristic online scheduling algorithms. We show that, under certain conditions, two of these satisfy monotonicity and are therefore truthful. We furthermore evaluate the algorithms using simulations, and we show that some of our algorithms benefit significantly from V2G, achieving positive benefit for the car park even when agents do not pay for using it
Optimal incremental preference elicitation during negotiation
No full textThe last two decades have seen a growing interest in the development of automated agents that are able to negotiate on the user's behalf. When representing a user in a negotiation, it is essential for the agent to understand the user's preferences, without exposing them to elicitation fatigue. To this end, we propose a new model in which a negotiating agent may incrementally elicit the user's preference during the negotiation. We introduce an optimal elicitation strategy that decides, at every stage of the negotiation, how much additional user information to extract at a certain cost. Finally, we demonstrate the effectiveness of our approach by combining our policy with well-known negotiation strategies and show that it significantly outperforms other elicitation strategies
Fair allocation of resources with uncertain availability
No full textMulti-agent resource allocation is an important and well-studied problem within AI and economics. It is generally assumed that the quantity of each resource is known a priori. However, in many real-world problems, such as the production of renewable energy which is typically weather dependent, the exact amount of each resource may not be known at the time of decision making. In this paper we investigate fair division of a homogeneous divisible resource where the available amount is given by a probability distribution. Specifically, we study the notion of ex-ante envy-freeness, where, in expectation, agents weakly prefer their allocation over every other agent's allocation. We analyse the trade-off between fairness and social welfare. We show that allocations satisfying ex-ante envy-freeness can result in higher social welfare compared to those satisfying ex-post envy-freeness. Nevertheless, the price of envy-freeness is at least , where is the number of agents, and this is tight under concave valuation functions. Principally, we show that the problem of optimising ex-ante social welfare subject to ex-ante envy-freeness is NP-hard in the strong sense. Finally, we devise an integer program to calculate the optimal ex-ante envy-free allocation for linear satiable valuation functions
A Polynomial-time, truthful, individually rational and budget balanced ridesharing mechanism
Full text linkRidesharing has great potential to improve transportation efficiency while reducing congestion and pollution. To realize this potential, mechanisms are needed that allocate vehicles optimally and provide the right incentives to riders. However, many existing approaches consider restricted settings (e.g., only one rider per vehicle or a common origin for all riders). Moreover, naive applications of standard approaches, such as the Vickrey-Clarke-Groves or greedy mechanisms, cannot achieve a polynomial-time, truthful, individually rational and budget balanced mechanism. To address this, we formulate a general ridesharing problem and apply mechanism design to develop a novel mechanism which satisfies all four properties and whose social cost is within 8.6% of the optimal on average
A Scoring Rule-Based Mechanism for Aggregate Demand Prediction in the Smart Grid
No full textThis paper presents a novel scoring rule-based strictly dominant incentive compatible mechanism that encourages agents to produce costly estimates of future events and report them truthfully to a centre. Whereas prior work has assumed a fixed budget for payment towards agents, this work makes use of prior information held by the centre and assumes a budget that is determined by the savings made through the use of the agents' information over the centre's own prior information. This mechanism is compared to a simple benchmark mechanism wherein the savings are divided equally among all home agents, and a cooperative solution wherein agents act to maximise social welfare. Empirical analysis is performed in which the mechanism is applied to a simulation of the smart grid whereby an aggregator agent must use home agents' information to optimally purchase electricity. It is shown that this mechanism achieves up to 77% of the social welfare achieved by the cooperative solution
A principled information valuation for communications during multi-agent coordination
No full textDecentralised coordination in multi-agent systems is typically achieved using communication. However, in many cases, communication is expensive to utilise because there is limited bandwidth, it may be dangerous to communicate, or communication may simply be unavailable at times. In this context, we argue for a rational approach to communication --- if it has a cost, the agents should be able to calculate a value of communicating. By doing this, the agents can balance the need to communicate with the cost of doing so. In this research, we present a novel model of rational communication that uses information theory to value communications, and employ this valuation in a decision theoretic coordination mechanism. A preliminary empirical evaluation of the benefits of this approach is presented in the context of the RoboCupRescue simulator
Dataset for "Coordination of Electric Vehicle Aggregators: A Coalitional Approach"
No full textA. Perez-Diaz, E. Gerding, F. McGroarty
"Coordination of Electric Vehicle Aggregators: A Coalitional Approach"
In 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018). ACM. (In Press).
The historical OMIE market data present in the dataset can be obtained from http://www.omie.es/en/inicio</span
Adaptive microtolling in competitive online congestion games via multiagent reinforcement learning
No full textEfficient urban traffic management remains a critical challenge, yet traditional congestion games fail to capture the dynamic and competitive nature of real-world transportation systems. We introduce the Multi-Market Routing Problem (MMRP), an online and oligopolistic extension that models competition amongst route providers utilising adaptive microtolling strategies to influence driver behaviour and mitigate congestion. We formally define the MMRP, highlighting the computational complexity of solving the MMRP, and use an adapted version of Proximal Policy Optimisation (PPO) to improve update stability in multiagent environments to address this problem in online settings. Our empirical analysis demonstrates that our PPO-based approach not only matches the performance of existing benchmarks but also significantly enhances equity, reduces travel times for users, and increases profitability for providers
Enhanced network inference from sparse incomplete time series through automatically adapted L<sub>1</sub> regularization
No full textReconstructing dynamics of complex systems from sparse, incomplete time series data is a challenging problem with applications in various domains. Here, we develop an iterative heuristic method to infer the underlying network structure and parameters governed by Ising dynamics from incomplete spin configurations based on sparse and small-sized samples. Our method iterates between imputing missing spin states given current coupling strengths and re-estimating couplings from completed spin state data. Central to our approach is the novel application of adaptive l
1 regularization on updating coupling strengths, which features an automatic adjustment of the regularization strength throughout the iterative inference process. By doing so, we aim at preventing over-fitting and enforcing the sparsity of couplings without access to ground truth parameters. We demonstrate that this approach accurately recovers parameters and imputes missing spins even with substantial missing data and short time series, providing improvements in the inference of Ising model parameters even for relatively small sample sizes.</p
Graph theory for consent management: a new approach for complex data flows
No full textThrough legislation and technical advances users gain more control over how their data is processed, and they expect online services to respect their privacy choices and preferences. However, data may be processed for many different purposes by several layers of algorithms that create complex data workflows. To date, there is no existing approach to automatically satisfy fine-grained privacy constraints of a user in a way which optimises the service provider's gains from processing. In this article, we propose a solution to this problem by modelling a data flow as a graph. User constraints and processing purposes are pairs of vertices which need to be disconnected in this graph. We show that, in general, this problem is NP-hard and we propose several heuristics and algorithms. We discuss the optimality versus efficiency of our algorithms and evaluate them using synthetically generated data. On the practical side, our algorithms can provide nearly optimal solutions for tens of constraints and graphs of thousands of nodes, in a few seconds
- …
