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

Subgame perfect equilibria under the deferred acceptance algorithm

INTERNATIONAL JOURNAL OF GAME THEORY 2021年第2期50卷 503-546页

作者： Kawase, Yasushi Bando, Keisuke Univ Tokyo Tokyo Japan Shinshu Univ Nagano Japan

We analyze a subgame perfect equilibrium (SPE) of an extensive game with perfect information induced by the firm-oriented deferred acceptance (DA) algorithm in a one-to-one matching market between firms and workers. Our game repeats the following procedure until every firm in the market has a partner: (i) an unmatched firm strategically decides to which worker to make an offer or to exit the market, and (ii) the worker receiving the offer strategically decides whether to tentatively accept or reject it. When no agents are strategic, the resulting outcome is the firm-optimal stable matching. We show that the worker-optimal stable matching is the unique SPE outcome when only workers are strategic. By contrast, multiple SPE outcomes may exist, possibly including unstable matchings when only firms are strategic. We show that every firm weakly prefers any SPE outcome to the worker-optimal stable matching and that the matching induced by Kesten's efficiency-adjusted DA algorithm can be achieved as an SPE. When both workers and firms are strategic, we also show that the worker-optimal stable matching is still the unique SPE outcome.

关键词： Two-sided matching deferred acceptance algorithm Subgame perfect equilibrium

来源：评论

学校读者我要写书评

暂无评论

A Heuristic for Rebalancing Bike Sharing Systems Based on a deferred acceptance algorithm 5

A Heuristic for Rebalancing Bike Sharing Systems Based on a ...

引用

5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS)

作者： Elhenawy, Mohammed Rakha, Hesham Virginia Tech Transportat Inst 3500 Transportat Res Plaza Blacksburg VA 24061 USA

ISBN: (纸本)9781509064847

Many cities around the world are making investments in innovative public transportation infrastructure. Bike-sharing systems (BSS) are one example of this. One key recurring BSS operation problem is the rebalancing of bikes at regular intervals. This redistribution of bikes from full stations to empty stations is required to meet expected demand patterns. Rebalancing entails finding the shortest Hamiltonian cycle in a graph that has the minimal residual. This is an NP-hard problem, and there are a number of algorithms that can be used to find optimal tours, but none are feasible for large instances, since they all grow exponentially. In this paper, we propose a new rebalancing algorithm based on the deferred acceptance algorithm, a well-known game theory algorithm consisting of two phases: tour construction and tour improvement. The proposed algorithm models the rebalancing problem as two disjoint sets of players. Each player in these sets has their own objective function, which is used to build the preference list for players on the other side. Experimental results for the proposed algorithm are promising.

关键词： bike-sharing system rebalancing game theory deferred acceptance algorithm

来源：评论

学校读者我要写书评

暂无评论

M-DAFTO: Multi-Stage deferred acceptance Based Fair Task Offloading in IoT-Fog Systems

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2024年第6期17卷 3928-3941页

作者： Swain, Chittaranjan Sahoo, Manmath Narayan Satpathy, Anurag Bakshi, Sambit Ghosh, Soumya K. Natl Inst Technol Dept Comp Sci & Engn Rourkela 769008 Odisha India Missouri Univ Sci & Technol Dept Comp Sci Rolla MO 65409 USA Indian Inst Technol Dept Comp Sci & Engn Kharagpur 721302 W Bengal India

Resource-constrained Internet of Things (IoT) devices depend on remote Cloud/Fog Nodes (FNs) to execute deadline-sensitive services. Offloading computations of real-time services to a remote cloud server results in intolerable latency due to intermittent channels, higher transmission delays, and scarce spectrum resources. Therefore, offloading to nearby FNs is preferable;however, it introduces several significant issues: (i) allocation of limited FN resources, (ii) deadline constraint of heterogeneous services, and (iii) requirement of computationally inexpensive and scalable strategies. This article proposes a M-DAFTO model to tackle the abovementioned issues and generate a fair offloading plan in polynomial time. The offloading problem is modeled as a many-to-one matching game with maximum and minimum quotas at each FN. Because the deferred acceptance (DA) algorithm fails to operate with minimum quotas, we adopt a variant of the DA algorithm, a multistage deferred acceptance (MSDA) algorithm, to solve the offloading problem. The overall goal of M-DAFTO is to reduce the aggregate offloading delay with increased assignment of tasks to FNs. Extensive simulation and analysis confirm a 30.26% and a 93.53% reduction in offloading delay and outages (unassigned tasks) compared to the baselines.

关键词： Task offloading IoT fog systems matching theory deferred acceptance algorithm analytic hierarchy process technique for order performance by similarity to ideal solution Task offloading IoT fog systems matching theory deferred acceptance algorithm analytic hierarchy process technique for order performance by similarity to ideal solution

来源：评论

学校读者我要写书评

暂无评论

Characterizing priorities for deferred acceptance with or without outside options

引用

ECONOMIC THEORY 2025年第2期79卷 497-517页

作者： Han, Xiang Zhang, Junxiao Shanghai Univ Finance & Econ Sch Econ Shanghai Peoples R China

In a model of priority-based allocation of indivisible objects where there may not be outside options, we characterize the priority structures under which the deferred acceptance algorithm (DA) satisfies various desiderata. We first identify an acyclicity condition that is necessary and sufficient for DA to be group strategy-proof, robustly stable, weakly group robustly stable, or to implement the stable allocation correspondence in Nash equilibria. When there is no outside option and there are more agents than total resources, the condition becomes considerably weaker, and no longer requires the priorities between any pair of objects to be similar. We further find a condition on priorities that is necessary and sufficient for the efficiency or consistency of DA, which is in general stronger than the above incentive properties for this mechanism.

关键词： Priority-based allocation Outside option deferred acceptance algorithm Group strategy-proofness Efficiency Acyclicity C78 D47 D78 D82

来源：评论

学校读者我要写书评

暂无评论

Joint Task Offloading, Resource Allocation and Model Placement for AI as a Service in 6G Network

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2024年第6期17卷 3830-3843页

作者： Chai, Yuhao Gao, Kaice Zhang, Guohan Lu, Lu Li, Qin Zhang, Yong Beijing Univ Posts & Telecommun Sch Elect Engn Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Key Lab Math & Informat Networks Beijing 100876 Peoples R China China Mobile Res Inst Dept Basic Network Technol Res Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Sch Elect Engn Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Beijing Key Lab Work Safety Intelligent Monitoring Beijing 100876 Peoples R China

In the future, 6G network is expected to achieve deep integration of communication and computation, where computation-centric services will be ubiquitous in the network. There are differences in data size, computing power types (CPU/GPU), model complexity, and Quality of Service (QoS) requirements among various CPU computing services and artificial intelligence (AI) services. By providing AI as a Service (AIaaS) in 6G network, the deployment of AI models and the scheduling of task and computing resources can be accelerated. The fundamental challenge lies in the effective amalgamation of the long-term strategy of the model placement problem and the short-term strategy of the task scheduling problem to attain dynamic scheduling and management of tasks and heterogeneous computing resources. A two-timescale optimization method for joint task offloading, computing resource allocation and model placement is proposed in this article. We present an edge-network-cloud framework that configures AIaaS functional units, taking into account the heterogeneous computing requirements and QoS demands of different services. A long-term problem to minimize latency and energy consumption is formulated. To work out the coupled optimization parameters, the problem is decomposed into short-term deterministic sub-problems using Lyapunov optimization. We propose low-complexity algorithms for joint task offloading strategy based on deferred acceptance algorithm, computing resource allocation strategy based on convex optimization, and model placement strategy based on multi-armed bandits. Experimental results demonstrate that our approach outperforms reinforcement learning and other popular optimization algorithms in terms of complexity and effectiveness.

关键词： 6G network resource allocation AI as a service (AIaaS) Lyapunov optimization deferred acceptance algorithm multi-armed bandit 6G network resource allocation AI as a service (AIaaS) Lyapunov optimization deferred acceptance algorithm multi-armed bandit

来源：评论

学校读者我要写书评

暂无评论

ReMatch: An Efficient Virtual Data Center Re-Matching Strategy Based on Matching Theory

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2023年第2期16卷 1373-1386页

作者： Satpathy, Anurag Sahoo, Manmath Narayan Behera, Lucky Swain, Chittaranjan Natl Inst Technol Dept Comp Sci & Engn Rourkela 769008 Odisha India

A virtual data center (VDC) comprises multiple virtual machines (VMs) with communication dependencies represented as virtual links (VLs). These virtual components, i.e., VMs and VLs, often experience fluctuating demands across different resource types. In this article, we focus on addressing the issue of dynamic resource expansion that leads to the relocation of solution components (SCs), where a SC comprises a VM and its attached VLs, with either the VM and/or at least one of the VLs facing resource expansion. This is challenging because of the complexity involved in frequently relocating multiple dependent virtual components across the substrate network. This article presents a model called ReMatch that aims at building an efficient remapping plan with reduced remapping cost and improved resource utilization for service providers (SPs) in polynomial time. The overall relocation problem is formulated as a one-to-many matching game with heterogeneous VM demands. Owing to the inapplicability of the classical deferred acceptance algorithm (DAA) and revised DA (RDA), we propose a modified version of the RDA (MRDA) to obtain a weakly stable assignment. Thorough simulation and analysis show that ReMatch outperforms the baseline algorithms considering multiple evaluation metrics.

关键词： Cloud computing virtual data center matching theory solution component deferred acceptance algorithm analytical hierarchy process

来源：评论

学校读者我要写书评

暂无评论

The core of school choice problems

引用

ECONOMIC THEORY 2024年第3期77卷 783-800页

作者： Rong, Kang Tang, Qianfeng Zhang, Yongchao Shanghai Univ Finance & Econ Sch Econ Shanghai Peoples R China

We propose a notion of core for school choice (i.e., priority-based allocation) problems. We say that a coalition of students is able to enforce a subassignment among them if, given their priorities at schools, other students together cannot exclude any student in the coalition from her assigned school. An assignment is in the core if no coalition of students can enforce any subassignment among them that Pareto improves their assignments. We show that all assignments in the core are Pareto efficient, and the assignment produced by Kesten's efficiency-adjusted deferred acceptance algorithm is always in the core. We also propose a natural refinement of the core and show that it is equivalent to the concept of priority-efficiency proposed by Reny (Am Econ Rev 112:2025-2043, 2022).

关键词： Core deferred acceptance algorithm Pareto efficiency School choice Stability Top trading cycles

来源：评论

学校读者我要写书评

暂无评论

A theory of fair random allocation under priorities

引用

THEORETICAL ECONOMICS 2024年第3期19卷 1185-1221页

作者： Han, Xiang Shanghai Univ Finance & Econ Sch Econ Shanghai Peoples R China

In the allocation of indivisible objects under weak priorities, a common practice is to break the ties using a lottery and to randomize over deterministic mechanisms. Such randomizations usually lead to unfairness and inefficiency ex ante. We propose and study the concept of ex ante fairness for random allocations, extending some key results in the one-sided and two-sided matching markets. It is shown that the set of ex ante fair random allocations forms a complete and distributive lattice under first-order stochastic-dominance relations, and the agent-optimal ex ante fair mechanism includes both the deferred acceptance algorithm and the probabilistic serial mechanism as special cases. Instead of randomizing over deterministic mechanisms, our mechanism is constructed using the division method, a new general way to construct random mechanisms from deterministic mechanisms. As additional applications, we demonstrate that several previous extensions of the probabilistic serial mechanism have their foundations in existing deterministic mechanisms.

关键词： Indivisible object weak priority random allocation fairness deferred acceptance algorithm probabilistic serial mechanism C78 D47 D71 D78

来源：评论

学校读者我要写书评

暂无评论

A fair procedure in a marriage market

引用

REVIEW OF ECONOMIC DESIGN 2024年第3期28卷 533-550页

作者： Kuvalekar, Aditya Romero-Medina, Antonio Univ Essex Colchester England Univ Carlos III Madrid Getafe Spain

We propose a new algorithm in the two-sided marriage market wherein both sides of the market propose in each round. The algorithm always yields a stable matching. Moreover, the outcome is a Rawlsian stable matching if the number of men and women is equal. Lastly, the algorithm can be computed in polynomial time and, from a practical standpoint, can be used in markets where fairness considerations are important.

关键词： Two-sided matching Fair procedure deferred acceptance algorithm C72 C78 D41

来源：评论

学校读者我要写书评

暂无评论

An alternative characterization of the deferred acceptance algorithm

引用

INTERNATIONAL JOURNAL OF GAME THEORY 2013年第1期42卷 19-28页

作者： Morrill, Thayer N Carolina State Univ Raleigh NC 27607 USA

Kojima and Manea (Econometrica 78(2):633-653, 2010) present two characterizations of when an allocation rule corresponds to the agent-proposing deferred acceptance (DA) algorithm for some substitutable priority rule of the objects being assigned. Building on their results we characterize when an allocation rule is outcome equivalent to the DA algorithm for every substitutable priority rule. In particular, an assignment rule satisfies mutual best (MB) if an agent is always assigned her most preferred object whenever she has the highest priority for it. This mild requirement is a necessary but far from sufficient condition for an assignment rule to be stable. We demonstrate that any allocation mechanism that satisfies MB along with non-wastefulness, population monotonicity and either individually rational monotonicity or weak Maskin monotonicity not only is a stable assignment mechanism but is equivalent to the agent proposing DA algorithm.

关键词： deferred acceptance algorithm Stable allocations Axioms Mutual best

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：