检索结果-内蒙古大学图书馆

Designing Fast Converging Cost Sharing Methods for Multicast Transmissions

theory OF COMPUTING SYSTEMS 2010年第2期47卷 507-530页

作者： Bilo, Vittorio Fanelli, Angelo Flammini, Michele Melideo, Giovanna Moscardelli, Luca Univ Aquila Dipartimento Informat I-67100 Laquila Italy Univ Salento Prov Lecce Arnesano Dipartimento Matemat Ennio De Giorgi I-73100 Lecce Italy

We study a multicast game in non-cooperative directed networks in which a source sends the same message or service to a set of r receiving users and the cost of the used links is divided among the receivers according to a given cost sharing method. By following the approach recently proposed by Chen et al. (Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 854-863, 2008), we analyze the performances of a family of methods satisfying certain desiderata, namely, weak and strong budget-balance, fairness and separability. We show that any fair method may require an arbitrary number of selfish moves in order to converge to a pure Nash equilibrium, hence we focus on the solutions obtained after one round of selfish moves. We evaluate their quality according to two global social functions: the overall cost of the solution and the maximum shared cost of users. The only method satisfying all the properties is the well-known Shapley value for which we show an approximation ratio of the solutions reached after a one round walk equal to I similar to(r (2)). We then prove that relaxing the strong budget balance and separability properties (we call feasible any method satisfying weak budget balance and fairness) leads to improved performances since we determine a feasible method achieving an approximation ratio of the solutions reached after a one round walk equal to O(r). This bound is asymptotically optimal since we also show that any method satisfying weak budget balance cannot achieve an approximation ratio of the solutions reached after a one round walk smaller than r. Finally, we prove the NP-hardness of computing the sequence of moves leading to the best possible global performance and extend most of the results to undirected networks.

关键词： algorithmic game theory Nash equilibrium Cost sharing games Multicast in communication networks

来源：评论

学校读者我要写书评

暂无评论

Value of Information in Incentive Design: A Case Study in Simple Congestion Networks

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2023年第6期10卷 3077-3088页

作者： Ferguson, Bryce L. Brown, Philip N. Marden, Jason R. Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA Univ Colorado Dept Comp Sci Colorado Springs CO 80918 USA

It is well-known that system performance can experience significant degradation from the self-interested choices of human users. Accordingly, in this article, we study the question of how a system operator can exploit system-level knowledge to derive incentives to influence societal behavior and improve system performance. Throughout, we focus on a simple class of routing games where the system operator has uncertainty regarding the network characteristics (i.e., latency functions) and population characteristics (i.e., sensitivity to monetary taxes). Specifically, we address the question of what information can be most effectively exploited in the design of taxation mechanisms to improve system performance. Our main results characterize an optimal marginal-cost taxation mechanism and associated performance guarantee for varying levels of network and population information. The value of a piece of information cannot be known a priori, so we adopt a worst-case interpretation of the value a piece of information is guaranteed to provide. Several interesting observations emerge about the relative value of information, including the fact that the value of population information saturates unless we also acquire more network knowledge.

关键词： algorithmic game theory congestion games incentives value of information

来源：评论

学校读者我要写书评

暂无评论

The isolation game: A game of distances

引用

THEORETICAL COMPUTER SCIENCE 2009年第47-49期410卷 4905-4919页

作者： Zhao, Yingchao Chen, Wei Teng, Shang-hua Tsinghua Univ Dept Comp Sci Beijing Peoples R China Boston Univ Dept Comp Sci Boston MA 02215 USA

We introduce a new multi-player geometric game, which we will refer to as the isolation game, and study its Nash equilibria and best or better response dynamics. The isolation game is inspired by the Voronoi game, competitive facility location, and geometric sampling. In the Voronoi game studied by Durr and Thang, each player's objective is to maximize the area of tier Voronoi region. In contrast, in the isolation game, each player's objective is to position herself as far away from other players as possible ill a bounded Space. Even though this game has a simple definition. we show that its game-theoretic behaviors are quite rich and complex. We consider various measures of farness from one player to a group of players and analyze their impacts to the existence of Nash equilibria and to the convergence of the best or better response dynamics: We prove that it is NP-hard to decide whether a Nash equilibrium exists, using either a very simple fatness measure in an asymmetric space or a slightly more sophisticated fatness measure in a symmetric space. Complementing these hardness results, we establish existence theorems for several special families of fatness measures in symmetric spaces: We prove that, for isolation games where each player wants to maximize her distance to her mth nearest neighbor, for any in, equilibria always exist. Moreover, there is always a better response sequence starting from any configuration that leads to a Nash equilibrium. We show that when m = 1 the game is a potential game. no better response sequence has a cycle. but when m > 1 the games are not potential. More generally, we study farness functions that give different weights to a player's distances to others based oil the distance rankings, and obtain both existence and hardness results when the weights are monotonically increasing or decreasing. Finally, we present results on the hardness of computing best responses when the space has a compact representation as a hypercube. (C) 2009

关键词： algorithmic game theory Nash equilibrium Computational complexity

来源：评论

学校读者我要写书评

暂无评论

SUBMODULAR FUNCTIONS: LEARNABILITY, STRUCTURE, AND OPTIMIZATION

引用

SIAM JOURNAL ON COMPUTING 2018年第3期47卷 703-754页

作者： Balcan, Maria-Florina Harvey, Nicholas J. A. Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Univ British Columbia Dept Comp Sci Vancouver BC V6T 1Z1 Canada

Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications. They have been used in many areas, including combinatorial optimization, machine learning, and economics. In this work we study submodular functions from a learning theoretic angle. We provide algorithms for learning submodular functions, as well as lower bounds on their learnability. In doing so, we uncover several novel structural results revealing ways in which submodular functions can be both surprisingly structured and surprisingly unstructured. We provide several concrete implications of our work in other domains including algorithmic game theory and combinatorial optimization. At a technical level, this research combines ideas from many areas, including learning theory (distributional learning and PAC-style analyses), combinatorics and optimization (matroids and submodular functions), and pseudorandomness (lossless expander graphs).

关键词： submodular functions distributional learning matroids algorithmic game theory optimization PAC model gross substitutes

来源：评论

学校读者我要写书评

暂无评论

Convergence and approximation in potential games

引用

THEORETICAL COMPUTER SCIENCE 2012年 438卷 13-27页

作者： Christodoulou, George Mirrokni, Vahab S. Sidiropoulos, Anastasios Univ Liverpool Liverpool L69 3BX Merseyside England Google Res Grp New York NY USA Toyota Technol Inst Chicago Chicago IL 60637 USA

We study the speed of convergence to approximately optimal states in two classes of potential games. We provide bounds in terms of the number of rounds, where a round consists of a sequence of movements, with each player appearing at least once in each round. We model the sequential interaction between players by a best-response walk in the state graph, where every transition in the walk corresponds to a best response of a player. Our goal is to bound the social value of the states at the end of such walks. In this paper, we focus on two classes of potential games: selfish routing games, and cut games (or party affiliation games (Fabrikant et al. 2004[12])). Other than bounding the price of anarchy of selfish routing games (Roughgarden and Tardos, 2002 [25], Awerbuch et al. 2005 [2], Christodoulou and Koutsoupias, 2005 [9]), there are many interesting problems about game dynamics in these games. It is known that exponentially long best-response walks may exist to pure Nash equilibria (Fabrikant et al. 2004 [12]), and random best-response walks converge to solutions with good approximation guarantees after polynomially many best responses (Goemans et al. 2005[17]). In this paper, we study the speed of convergence on deterministic best-response walks in these games and prove that starting from an arbitrary configuration, after one round of best responses of players, the resulting configuration is a Theta(n)-approximate solution. Furthermore, we show that starting from an empty configuration, the solution after any round of best responses is a constant-factor approximation. We also provide a lower bound for the multi-round case, where we show that for any constant number of rounds t, the approximation guarantee cannot be better than n(epsilon(t)), for some epsilon(t) > 0. We also study cut games, that provide an illustrative example of potential games. The convergence of potential games to locally optimum solutions has been studied in the context of local search algori

关键词： algorithmic game theory Convergence time Potential games Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Decentralized dynamics for finite opinion games

引用

THEORETICAL COMPUTER SCIENCE 2016年第0期648卷 96-115页

作者： Ferraioli, Diodato Goldberg, Paul W. Ventre, Carmine Univ Salerno DIEM Fisciano SA Italy Univ Oxford Dept Comp Sci Oxford OX1 2JD England Univ Teesside Middlesbrough Cleveland England

game theory studies situations in which strategic players can modify the state of a given system, in the absence of a central authority. Solution concepts, such as Nash equilibrium, have been defined in order to predict the outcome of such situations. In multi player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to decrease their own cost and the hope is that the system reaches an "equilibrium" quickly. We study these dynamics for the class of opinion games, recently introduced by Bindel et al. [10]. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio. (C) 2016 Elsevier B.V. All rights reserved.

关键词： algorithmic game theory Convergence rate to equilibria Logit dynamics

来源：评论

学校读者我要写书评

暂无评论

Strategic Learning Approach for Deploying UAV-Provided Wireless Services

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2021年第3期20卷 1230-1241页

作者： Xu, Xinping Duan, Lingjie Li, Minming Singapore Univ Technol & Design Engn Syst & Design Pillar Singapore 487372 Singapore City Univ Hong Kong Dept Comp Sci Kowloon Tong Hong Kong Peoples R China

Unmanned Aerial Vehicle (UAV) have emerged as a promising technique to rapidly provide wireless services to a group of mobile users simultaneously. The article aims to address a challenging issue that each user is selfish and may misreport his location or preference for changing the optimal UAV location to be close to himself. Using algorithmic game theory, we study how to determine the final location of a UAV in the 3D space, by ensuring all selfish users' truthfulness in reporting their locations for learning purpose. To minimize the social service cost in this UAV placement game, we design strategyproof mechanisms with the approximation ratios, when comparing to the social optimum. We also study the obnoxious UAV placement game to maximally keep their social utility, where each incumbent user may misreport his location to keep the UAV away from him. Moreover, we present the dual-preference UAV placement game by considering the coexistence of the two groups of users above, where users can misreport both their locations and preference types (favorable or obnoxious) towards the UAV. Finally, we extend the three games above to include multiple UAVs and design strategyproof mechanisms with provable approximation ratios.

关键词： games Wireless communication Unmanned aerial vehicles game theory Ad hoc networks Mobile computing Three-dimensional displays algorithmic game theory approximation ratio strategyproof mechanism unmanned aerial vehicle

来源：评论

学校读者我要写书评

暂无评论

Towards More Practical Linear Programming-based Techniques for algorithmic Mechanism Design

引用

theory OF COMPUTING SYSTEMS 2016年第4期59卷 641-663页

作者： Elbassioni, Khaled Mehlhorn, Kurt Ramezani, Fahimeh Masdar Inst Sci & Technol Abu Dhabi U Arab Emirates Max Planck Inst Informat Campus E1 4 D-66123 Saarbrucken Germany Univ Isfahan Dept Math Esfahan *** Iran

R. Lavi and C. Swamy (FOCS 2005, J. ACM 58(6), 25, 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.

关键词： algorithmic game theory Mechanism design Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Strongly polynomial-time truthful mechanisms in one shot

引用

THEORETICAL COMPUTER SCIENCE 2009年第17期410卷 1607-1615页

作者： Penna, Paolo Proietti, Guido Widmayer, Peter Univ Salerno Dipartimento Informat & Applicaz Renato M Capocel Salerno Italy ETH Inst Theoret Informat Zurich Switzerland Univ Aquila Dipartimento Informat I-67100 Laquila Italy CNR Ist Anal Sistemi & Informat A Ruberti Rome Italy

One of the main challenges in algorithmic mechanism design is to turn (existing) efficient algorithmic Solutions into efficient truthful mechanisms. Building a truthful mechanism is indeed a difficult process since the underlying algorithm must obey certain "monotonicity" properties and suitable payment functions need to be computed (this task usually represents the bottleneck in the overall time complexity). We provide a general technique for building truthful mechanisms that provide optimal solutions in strongly polynomial time. We show that the entire mechanism can be obtained if one is able to express/write a strongly polynomial-time algorithm (for the corresponding optimization problem) as a "suitable combination" of simpler algorithms. This approach applies to a wide class of mechanism design graph problems, where each selfish agent corresponds to a weighted edge in a graph (the weight of the edge is the cost of using that edge). Our technique can be applied to several optimization problems which prior results cannot handle (e.g., MIN-MAX optimization problems). As an application, we design the first (strongly polynomial-time) truthful mechanism for the minimum diameter spanning tree problem, by obtaining it directly from an existing algorithm for solving this problem. For this non-utilitarian MIN-MAX problem, no truthful mechanism was known, even considering those running in exponential time (indeed, exact algorithms do not necessarily yield truthful mechanisms). Also, standard techniques for payment computations may result in a running time which is not polynomial in the size of the input graph. The overall running time of our mechanism, instead, is polynomial in the number n of nodes and in of edges, and it is only a factor O(n alpha(n, n)) away from the best known canonical centralized algorithm. (C) 2009 Elsevier B.V. All rights reserved.

关键词： algorithmic game theory Mechanism design Design and analysis of algorithms Minimum diameter spanning tree

来源：评论

学校读者我要写书评

暂无评论

Bounded Budget Connection (BBC) games or how to make friends and influence people, on a budget

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2014年第7期80卷 1266-1284页

作者： Laoutaris, Nikolaos Poplawski, Laura Rajaraman, Rajmohan Sundaram, Ravi Teng, Shang-Hua Telefon Res Toledo Spain Raytheon BBN Technol Cambridge MA 02138 USA Northeastern Univ Boston MA 02115 USA Univ So Calif Los Angeles CA 90089 USA

Motivated by applications in social and peer-to-peer networks, we introduce the Bounded Budget Connection (BBC) game and study its pure Nash equilibria. We have a collection of n players, each with a budget for purchasing links. Each link has a cost and a length. Each node has a preference weight for each node, and its objective is to purchase outgoing links within its budget to minimize its sum of preference-weighted distances to the nodes. We show that determining if a BBC game has pure Nash equilibria is NP-hard. We study (n, k)-uniform BBC games, where all link costs, lengths, and preferences are equal and every budget equals k. We show that pure Nash equilibria exist for all (n, k)-uniform BBC games and all equilibria are essentially fair. We construct a family of equilibria spanning the spectrum from minimum to maximum social cost. We also analyze best-response walks and alternative node objectives. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Network formation algorithmic game theory Nash equilibrium Network creation games Social networks Price of anarchy

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：