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

Breaking the traditional: a survey of algorithmic mechanism design applied to economic and complex environments

NEURAL COMPUTING & APPLICATIONS 2023年第22期35卷 16193-16222页

作者： Chen, Qian Wang, Xuan Jiang, Zoe Lin Wu, Yulin Li, Huale Cui, Lei Sun, Xiaozhen Harbin Inst Technol Shenzhen Comp Sci & Technol Shenzhen 518000 Guangdong Peoples R China Peng Cheng Lab Shenzhen 518000 Guangdong Peoples R China Guangdong Prov Key Lab Novel Secur Intelligence Te Shenzhen 518000 Guangdong Peoples R China

The mechanism design theory can be applied not only in the economy but also in many fields, such as politics and military affairs, which has important practical and strategic significance for countries in the period of system innovation and transformation. As Nobel Laureate Paul said, the complexity of the real economy makes it difficult for "Unorganized Markets" to ensure supply-demand balance and the efficient allocation of resources. When traditional economic theory cannot explain and calculate the complex scenes of reality, we require a high-performance computing solution based on traditional theory to evaluate the mechanisms, meanwhile, get better social welfare. The mechanism design theory is undoubtedly the best option. Different from other existing works, which are based on the theoretical exploration of optimal solutions or single perspective analysis of scenarios, this paper focuses on the more real and complex markets. It explores to discover the common difficulties and feasible solutions for the applications. Firstly, we review the history of traditional mechanism design and algorithm mechanism design. Subsequently, we present the main challenges in designing the actual data-driven market mechanisms, including the inherent challenges in the mechanism design theory, the challenges brought by new markets and the common challenges faced by both. In addition, we also comb and discuss theoretical support and computer-aided methods in detail. This paper guides cross-disciplinary researchers who wish to explore the resource allocation problem in real markets for the first time and offers a different perspective for researchers struggling to solve complex social problems. Finally, we discuss and propose new ideas and look to the future.

关键词： algorithmic mechanism design Incentive mechanism Online advertising Privacy preserving

来源：评论

学校读者我要写书评

暂无评论

Strategy Equilibrium of Evolutionary Computation: towards Its algorithmic mechanism design

Strategy Equilibrium of Evolutionary Computation: towards It...

引用

IEEE International Conference on Systems, Man, and Cybernetics (SMC)

作者： Pei, Yan Univ Aizu Div Comp Sci Ikki Machi Fukushima 9658580 Japan

ISBN: (纸本)9781479986965

We consider algorithmic design, enhancement, and improvement of evolutionary computation (EC) as a mechanism design problem. All individuals or several groups of individuals can be considered as self-interested agents. The individuals in EC can manipulate the parameter settings and operations of an EC algorithm by satisfying their own preferences rather than by following a fixed algorithm rule. EC algorithm designers or EC self-adaptive methods should construct appropriate rules and mechanisms for all agents (individuals) to conduct their evolution behavior correctly in order to definitely achieve the desired and pre-set objective(s) definitively. We propose a formal framework on parameter setting, strategy selection, and algorithmic design of EC by considering the strategy equilibrium implementation of a mechanism design problem in the search process. We attempt to use Nash strategy equilibrium (NE) concept in an implementation of an algorithmic mechanism design problem, but our proposed framework is not limited to Nash strategy equilibrium. The evaluation results present the efficiency of the framework. Its primary principle can be implemented in any EC algorithm that needs to consider the strategy selection issue in its optimization process. The final objective of our work is to implement EC design as an algorithmic mechanism design problem and establish EC fundamental aspects based on this perspective.

关键词： Game theory mechanism design algorithmic mechanism design Evolutionary computation Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

BLACK-BOX RANDOMIZED REDUCTIONS IN algorithmic mechanism design

引用

SIAM JOURNAL ON COMPUTING 2014年第1期43卷 312-336页

作者： Dughmi, Shaddin Roughgarden, Tim Univ So Calif Dept Comp Sci Los Angeles CA 90089 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA

We give the first black-box reduction from approximation algorithms to truthful approximation mechanisms for a non-trivial class of multi-parameter problems. Specifically, we prove that every welfare-maximization problem that admits a fully polynomial-time approximation scheme (FPTAS) and can be encoded as a packing problem also admits a truthful-in-expectation randomized mechanism that is an FPTAS. Our reduction makes novel use of smoothed analysis by employing small perturbations as a tool in algorithmic mechanism design. We develop a "duality" between linear perturbations of the objective function of an optimization problem and of its feasible set, and we use the "primal" and "dual" viewpoints to prove the running time bound and the truthfulness guarantee, respectively, for our mechanism.

关键词： algorithmic mechanism design smoothed analysis black-box reductions

来源：评论

学校读者我要写书评

暂无评论

Budget-Feasible mechanism design: Simpler, Better mechanisms and General Payment Constraints 15

Budget-Feasible Mechanism Design: Simpler, Better Mechanisms...

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Neogi, Rian Pashkovich, Kanstantsin Swamy, Chaitanya Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada

ISBN: (纸本)9783959773096

In budget-feasible mechanism design, a buyer wishes to procure a set of items of maximum value from self-interested rational players. We are given an item-set U and a nonnegative valuation function v : 2(U) (sic) R+. Each item e is held by a player who incurs a private cost c(e) for supplying item e. The goal is to devise a truthful mechanism such that the total payment made to the players is at most some given budget B, and the value of the set returned is a good approximation to OPT := max {v(S) : c(S) <= B, S subset of U}. We call such a mechanism a budget-feasible mechanism. More generally, there may be additional side constraints requiring that the set returned lies in some downwards-monotone family I subset of 2(U). Budget-feasible mechanisms have been widely studied, but there are still significant gaps in our understanding of these mechanisms, both in terms of what kind of oracle access to the valuation is required to obtain good approximation ratios, and the best approximation ratio that can be achieved. We substantially advance the state of the art of budget-feasible mechanisms by devising mechanisms that are simpler, and also better, both in terms of requiring weaker oracle access and the approximation factors they obtain. For XOS valuations, we devise the first polytime O(1)-approximation budget-feasible mechanism using only demand oracles, and also significantly improve the approximation factor. For subadditive valuations, we give the first explicit construction of an O(1)-approximation mechanism, where previously only an existential result was known. We also introduce a fairly rich class of mechanism-design problems that we dub using the umbrella term generalized budget-feasible mechanism design, which allow one to capture payment constraints that are much-more nuanced than a single constraint on the total payment doled out. We demonstrate the versatility of our ideas by showing that our constructions can be adapted to yield approximation guarantees in

关键词： algorithmic mechanism design Approximation algorithms Budget-feasible mechanisms

来源：评论

学校读者我要写书评

暂无评论

Edge Manipulations for the Maximum Vertex-Weighted Bipartite b-matching

引用

ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY 2025年第1期16卷 1-26页

作者： Auricchio, Gennaro Liu, Jun Ma, Qun Zhang, Jie Univ Bath Bath England Beijing Normal Univ Sch Math Sci Beijing Peoples R China Tianjin Univ Tianjin Peoples R China

In this article, we explore the mechanism design aspects of the Maximum Vertex-Weighted b-matching (MVbM) problem on bipartite graphs (A boolean OR T,E). The set A comprises agents, while T represents tasks. The set E, which connects A and T, is the private information of either agents or tasks. In this framework, we investigate three mechanisms-M-BFS, M-DFS, and M-G. We examine scenarios in which either agents or tasks are strategic and report their adjacent edges to one of the three mechanisms. In both cases, we assume that the strategic entities are bounded by their statements: They can hide edges, but they cannot report edges that do not exist. First, we consider the case in which agents can manipulate. In this framework, M-BFS and M-DFS are optimal but not truthful. By characterizing the Nash Equilibria induced by M-BFS and M-DFS, we reveal that both mechanisms have a Price of Anarchy (PoA) and Price of Stability (PoS) of 2. These efficiency guarantees are tight;no deterministic mechanism can achieve a lower PoA or PoS. In contrast, the third mechanism, M-G, is not optimal, but truthful and its approximation ratio is 2. We demonstrate that this ratio is optimal;no deterministic and truthful mechanism can outperform it. We then shift our focus to scenarios where tasks can exhibit strategic behavior. In this case, MBFS, M-DFS, and M-G all maintain truthfulness, making M-BFS and M-DFS truthful and optimal mechanisms. In conclusion, we investigate the manipulability of M-BFS and M-DFS through experiments on randomly generated graphs. We observe that (i) M-BFS is less prone to be manipulated by the first agent than M-DFS, and (ii) M-BFS is more manipulable on instances in which the total capacity of the agents is equal to the number of tasks.

关键词： algorithmic mechanism design Vertex Weighted Matching problems Edge Manipulations

来源：评论

学校读者我要写书评

暂无评论

An Incentive-Compatible and Computationally Efficient Fog Bargaining mechanism

引用

COMPUTATIONAL ECONOMICS 2023年第4期62卷 1883-1918页

作者： Sim, Kwang Mong Singapore Singapore

This work contributes an (approximately) incentive-compatible and computationally efficient bargaining mechanism for pricing fog computing resources. In network settings (e.g., fog computing), it is plausible to think that self-interested and incompletely informed players (represented by software agents) will attempt to maximize their own benefits at the expense of others. Hence, it is crucial that fog bargaining mechanisms give incentives to agents for behaving in a manner consistent with the desired outcome where every agent's benefit is maximized. Equilibrium analyses validate that the fog bargaining mechanism in this work is approximately Bayesian incentive compatible because every agent can approximately maximize its expected utility by adhering to the strategy recommended by the bargaining mechanism given that all other agents also adhere to their equilibrium strategies. That is, if every agent in the market adheres to the strategy recommended by the bargaining mechanism, then the strategy profile of the agents forms an approximate Bayesian Nash equilibrium. Given that a fog resource market has a large number of buyers and a large number of sellers, computational efficiency is also imperative since every agent needs to process a huge number of trading alternatives. Computational complexity analyses validate that 1) the procedure for carrying out the bargaining strategy has a linear time complexity, and with every passing round, the search space dwindles but the solutions become progressively better, 2) the number of rounds for each agent to complete bargaining is logarithmic in the number of its opponents, and 3) each agent has a linear message complexity.

关键词： algorithmic mechanism design Bargaining mechanism Bayesian incentive compatibility ?-Bayesian incentive compatibility Bayesian Nash equilibrium Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Restricted Existence and Approximation Algorithms for PMMS

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2023年第0期

作者： Guo, Xinru Dai, Sijia Gao, Guichen Ma, Ruikang Xu, Yicheng Ning, Li Fan, Jianping Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Guangdong Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Guangxi Key Lab Cryptog & Informat Secur Guilin 541004 Guangxi Peoples R China Peking Univ Beijing Peoples R China

This paper studies the problem of dividing m indivisible items among n agents fairly and efficiently. Specifically, this research concentrates on pairwise maximin share (PMMS), which is defined to be the maximum value that an agent can guarantee for herself if she were to repartition the items with another agent and receive the bundle with the minimum value. PMMS is an important concept in the fair division. However, whether PMMS for indivisible items exists is still open. This work concentrates on PMMS by proving the existence of PMMS on linear graphs with binary valuation functions. Besides, this paper designs an algorithm to approximate PMMS in the case where different agents have identical valuations among the same items, achieving a ratio strictly greater than 0.8, which outperforms the state-of-the-art ratio of 0.781 from Kurokawa [22]. The time complexity of our FFD-based algorithm is O(mn + m log m).

关键词： Fair division pairwise maximin share algorithmic mechanism design approximation

来源：评论

学校读者我要写书评

暂无评论

ON THE POWER OF RANDOMIZATION IN algorithmic mechanism design

引用

SIAM JOURNAL ON COMPUTING 2013年第6期42卷 2287-2304页

作者： Dobzinski, Shahar Dughmi, Shaddin Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA

In many settings the power of truthful mechanisms is severely bounded. In this paper we use randomization to overcome this problem in the multi-unit auction setting. In particular, we construct a fully polynomial-time approximation scheme (FPTAS) for multi-unit auctions that is truthful in expectation, whereas there is evidence that no polynomial-time truthful deterministic mechanism provides an approximation ratio better than 2. We leverage the FPTAS to show for the first time that truthful in expectation polynomial-time mechanisms are provably stronger than polynomial-time universally truthful mechanisms. Specifically, we show that there is a setting, related to multi-unit auctions, in which (1) there is a nonpolynomial time truthful mechanism that always outputs the optimal solution, and that (2) no universally truthful randomized mechanism can provide an approximation ratio better than 2 in polynomial time, but (3) an FPTAS that is truthful in expectation exists.

关键词： truthfulness multi-unit auctions algorithmic mechanism design

来源：评论

学校读者我要写书评

暂无评论

First Price Auction is 1-1/e² Efficient 63

First Price Auction is 1-1/e<SUP>2</SUP> Efficient

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Jin, Yaonan Lu, Pinyan Columbia Univ Dept Comp Sci New York NY 10027 USA Shanghai Univ Finance & Econ Inst Theoret Comp Sci Shanghai Peoples R China

We prove that the PoA of First Price Auctions is 1 - 1/e(2) approximate to 0.8647, closing the gap between the best known bounds [0.7430, 0.8689].

ISBN: (纸本)9781665455190

We prove that the PoA of First Price Auctions is 1 - 1/e(2) approximate to 0.8647, closing the gap between the best known bounds [0.7430, 0.8689].

关键词： algorithmic game theory algorithmic mechanism design Quality of equilibria Exact and approximate computation of equilibria Representations of games and their complexity Mathematical optimization

来源：评论

学校读者我要写书评

暂无评论

The Sample Complexity of Up-to-ε Multi-dimensional Revenue Maximization

引用

JOURNAL OF THE ACM 2021年第3期68卷 1–28页

作者： Gonczarowski, Yannai A. Weinberg, S. Matthew Microsoft Res One Mem Dr Cambridge MA 02139 USA Princeton Univ 35 Olden St Princeton NJ 08540 USA

We consider the sample complexity of revenue maximization for multiple bidders in unrestricted multi-dimensional settings. Specifically, we study the standard model of n additive bidders whose values for m heterogeneous items are drawn independently. For any such instance and any epsilon > 0, we show that it is possible to learn an e-Bayesian Incentive Compatible auction whose expected revenue is within epsilon of the optimal epsilon-BIC auction from only polynomially many samples. Our fully nonparametric approach is based on ideas that hold quite generally and completely sidestep the difficulty of characterizing optimal (or near-optimal) auctions for these settings. Therefore, our results easily extend to general multi-dimensional settings, including valuations that are not necessarily even subadditive, and arbitrary allocation constraints. For the cases of a single bidder and many goods, or a single parameter (good) and many bidders, our analysis yields exact incentive compatibility (and for the latter also computational efficiency). Although the single-parameter case is already well understood, our corollary for this case extends slightly the state of the art.

关键词： algorithmic game theory algorithmic mechanism design auctions sample complexity generalization bounds PAC learning approximate revenue maximization multi-dimensional auctions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：