Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimizing Fund Allocation for Game-based Verifiable Computation Outsourcing
93
0
0.0
(
0
)
Added by
Pinglan Liu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper considers the setting where a cloud server services a static set or a dynamic sequence of tasks submitted by multiple clients. Every client wishes to assure honest execution of tasks by additionally employing a trusted third party (TTP) to re-compute the tasks with a certain probability. The cloud server makes a deposit for each task it takes, each client allocates a budget (including the wage for the server and the cost for possibly hiring TTP) for each task submitted, and every party has its limited fund for either deposits or task budgets. We study how to allocate the funds optimally to achieve the three-fold goals: a rational cloud server honestly computes each task; the servers wage is maximized; the overall delay for task verification is minimized. We apply game theory to formulate the optimization problems, and develop the optimal or heuristic solutions for three application scenarios. For each of the solutions, we analyze it through either rigorous proofs or extensive simulations. To the best of our knowledge, this is the first work on optimizing fund allocation for verifiable outsourcing of computation in the setting of one server and multiple clients, based on game theory.
rate research
Read More
In this paper, a multi-user cooperative computing framework is applied to enable mobile users to utilize available computing resources from other neighboring users via direct communication links. An incentive scheme based on Bertrand game is proposed for the user to determine textit{who} and textit{how} to cooperate. We model the resource demand users as textit{buyers} who aim to use minimal payments to maximize energy savings, whereas resource supply users as textit{sellers} who aim to earn payments for their computing resource provision. A Bertrand game against textit{buyers market} is formulated. When the users have textit{complete information} of their opponents, the Nash equilibrium (NE) of the game is obtained in closed form, while in the case of textit{incomplete information}, a distributed iterative algorithm is proposed to find the NE. The simulation results verify the effectiveness of the proposed scheme.
Mechanism design is addressed in the context of fair allocations of indivisible goods with monetary compensation. Motivated by a real-world social choice problem, mechanisms with verification are considered in a setting where (i) agents declarations on allocated goods can be fully verified before payments are performed, and where (ii) verification is not used to punish agents whose declarations resulted in incorrect ones. Within this setting, a mechanism is designed that is shown to be truthful, efficient, and budget-balanced, and where agents utilities are fairly determined by the Shapley value of suitable coalitional games. The proposed mechanism is however shown to be #P-complete. Thus, to deal with applications with many agents involved, two polynomial-time randomized variants are also proposed: one that is still truthful and efficient, and which is approximately budget-balanced with high probability, and another one that is truthful in expectation, while still budget-balanced and efficient.
Vehicular ad-hoc networks (VANETs) have recently attracted a lot of attention due to their immense potentials and applications. Wide range of coverage and accessibility to end users make VANETs a good target for commercial companies. In this paper, we consider a scenario in which advertising companies aim to disseminate their advertisements in different areas of a city by utilizing VANETs infrastructure. These companies compete for renting the VANETs infrastructure to spread their advertisements. We partition the city map into different blocks, and consider a manager for all the blocks who is in charge of splitting the time between interested advertising companies. Each advertising company (AdC) is charged proportional to the allocated time. In order to find the best time splitting between AdCs, we propose a Stackelberg game scheme in which the block manager assigns the companies to the blocks and imposes the renting prices to different companies in order to maximize its own profit. Based on this, AdCs request the amount of time they desire to rent the infrastructure in order to maximize their utilities. To obtain the Stackelberg equilibrium of the game, a mixed integer nonlinear optimization problem is solved using the proposed optimal and sub-optimal algorithms. The simulation results demonstrate that the sub-optimal algorithm approaches the optimal one in performance with lower complexity.
Computational advertising has been studied to design efficient marketing strategies that maximize the number of acquired customers. In an increased competitive market, however, a market leader (a leader) requires the acquisition of new customers as well as the retention of her loyal customers because there often exists a competitor (a follower) who tries to attract customers away from the market leader. In this paper, we formalize a new model called the Stackelberg budget allocation game with a bipartite influence model by extending a budget allocation problem over a bipartite graph to a Stackelberg game. To find a strong Stackelberg equilibrium, a standard solution concept of the Stackelberg game, we propose two algorithms: an approximation algorithm with provable guarantees and an efficient heuristic algorithm. In addition, for a special case where customers are disjoint, we propose an exact algorithm based on linear programming. Our experiments using real-world datasets demonstrate that our algorithms outperform a baseline algorithm even when the follower is a powerful competitor.
Coded distributed computing (CDC) has emerged as a promising approach because it enables computation tasks to be carried out in a distributed manner while mitigating straggler effects, which often account for the long overall completion times. Specifically, by using polynomial codes, computed results from only a subset of edge servers can be used to reconstruct the final result. However, incentive issues have not been studied systematically for the edge servers to complete the CDC tasks. In this paper, we propose a tractable two-level game-theoretic approach to incentivize the edge servers to complete the CDC tasks. Specifically, in the lower level, a hedonic coalition formation game is formulated where the edge servers share their resources within their coalitions. By forming coalitions, the edge servers have more Central Processing Unit (CPU) power to complete the computation tasks. In the upper level, given the CPU power of the coalitions of edge servers, an all-pay auction is designed to incentivize the edge servers to participate in the CDC tasks. In the all-pay auction, the bids of the edge servers are represented by the allocation of their CPU power to the CDC tasks. The all-pay auction is designed to maximize the utility of the cloud server by determining the allocation of rewards to the winners. Simulation results show that the edge servers are incentivized to allocate more CPU power when multiple rewards are offered, i.e., there are multiple winners, instead of rewarding only the edge server with the largest CPU power allocation. Besides, the utility of the cloud server is maximized when it offers multiple homogeneous rewards, instead of heterogeneous rewards.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
