We study the decision-making problems encountered by two agents in parallel allocation and introduce the concept of risk attitudes. Risk attitudes reflect the likelihood of success in a competitive parallel allocation scenario. The probability of success is zero for risk-averse individuals, whereas it is certain for risk-seeking individuals. Individuals with different risk attitudes can accordingly adjust their strategies. When both agents are risk-averse, we provide the strategic characteristics that satisfy the Subgame Perfect Nash Equilibrium (SPNE) and design an algorithm to find the SPNE strategies. We prove the algorithm's correctness and resolve the selection conflict issues caused by even and odd items. When both agents are risk-seeking, we similarly provide the strategic characteristics that satisfy the SPNE and design an algorithm to find the SPNE strategies. Finally, we present a strategic analysis demonstrating the non-existence of relevant SPNE when one agent is risk-seeking and the other is risk-averse.
We study the problem of fairly allocating a set of indivisible goods between two agents with additive valuations. Fair distribution has become an emerging research topic in computer science and artificial intelligence, and envy-free is the most widely studied concept of fairness. Envy-free allocation always exists when goods are divisible, but not always for indivisible goods, which motivates us to study envy-free relaxation. In this paper, we introduce a novel solution concept called EFS1, in which envy between two agents can be eliminated by swapping a good in the bundle of the two agents. Furthermore, we propose an efficient algorithm capable of finding such allocations in polynomial time, and we demonstrate the algorithm's execution through an example involving a dummy good. Our research offers promising solutions for addressing envy in allocation scenarios with the introduction of the EFS1 concept and an efficient algorithm.
Parallel allocation is a decentralized mechanism for allocating indivisible objects to agents, in which agents are allowed to report their favorite objects among the remaining goods parallelly. How to maximize the interests of self-interested agents while taking into account fairness has always been a hot research topic. In this paper, we study the loser-reporting policy which ensures that the difference between the number of items taken by the agents does not exceed one. In order to make the expected benefit obtained by the agent equal to the expected benefit obtained by the agent in the sub-game perfect Nash equilibrium (SPNE) in parallel allocation, we come up with a concept of shelving disputes, and the SPNE strategy can be computed in polynomial time with respect to the number of objects.
Parallel allocation is one of the most fundamental mechanisms for allocating indivisible objects to agents in a decentralized manner, in which agents are allowed to parallelly report their favorite objects among the remainder according to a policy that is insensitive to agent’s identities. In recent years, algorithmic issues about agent’s manipulations have been investigated, such as the computational complexity of verifying whether a manipulator can obtain a given bundle possibly, and maximizing her utility optimistically. In this paper, we consider the allocation policy of loser reporting, where the allocation process is divided into rounds, in each round, each agent that has obtained the smallest number of objects can report exactly one remaining object, and each reported object is allocated to one of the agents that report it at random. We show that for general additive utilities, under the optimistic assumption (i.e., the manipulator can obtain an object once she reports it), an optimal manipulation can be computed in polynomial time with respect to the number of objects.
Small scale damaged image inpainting is divided into iterative inpainting and interpolation-based image inpainting algorithms. In previous studies, it is found that there are some phenomena such as sawtooth effect, edge blur and so on. The sawtooth effect exists because the weight calculation of neighborhood pixels only considers the spatial information, ignores the image feature information. In addition, there are many factors leading to edge blur including the error accumulation of inpainted pixels, the low weight of gradient direction, and the inpainting priority of pixel. In this paper, we propose an image inpainting method based on Fast Marching Method (FMM). Firstly we use gradient direction and isophote direction to maintain the edge consistency, so as to improve the algorithm effect. Secondly we explore the confidence matrix to reduce the error accumulation. Finally we use the low rank of image to preprocess the image region to reduce the algorithm time complexity. The results of the experiment show that our improved method get well performance in inpainting procedure than the-state-of-the-art method.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.