Search

In evolutionary game theory, the effect of public goods like diffusible molecules has been modelled using linear, concave, sigmoid and step functions. The observation that biological systems are often sigmoid input-output functions, as described by the Hill equation, suggests that a sigmoid function is more realistic. The Michaelis-Menten model of enzyme kinetics, however, predicts a concave function, and while mechanistic explanations of sigmoid kinetics exist, we lack an adaptive explanation: what is the evolutionary advantage of a sigmoid benefit function? We analyse public goods games in which the shape of the benefit function can evolve, in order to determine the optimal and evolutionarily stable Hill coefficients. We find that, while the dynamics depends on whether output is controlled at the level of the individual or the population, intermediate or high Hill coefficients often evolve, leading to sigmoid input-output functions that for some parameters are so steep to resemble a step function (an on-off switch). Our results suggest that, even when the shape of the benefit function is unknown, biological public goods should be modelled using a sigmoid or step function rather than a linear or concave function., (Copyright © 2016 Elsevier Ltd. All rights reserved.)

Designing an incentive compatible auction that maximizes expected revenue is an intricate task. The single-item case was resolved in a seminal piece of work by Myerson in 1981, but more than 40 years later, a full analytical understanding of the optimal design still remains elusive for settings with two or more items. In this work, we initiate the exploration of the use of tools from deep learning for the automated design of optimal auctions. We model an auction as a multi-layer neural network, frame optimal auction design as a constrained learning problem, and show how it can be solved using standard machine learning pipelines. In addition to providing generalization bounds, we present extensive experimental results, recovering essentially all known solutions that come from the theoretical analysis of optimal auction design problems and obtaining novel mechanisms for settings in which the optimal mechanism is unknown. [ABSTRACT FROM AUTHOR]

We study a setting where a receiver must design a questionnaire to recover a sequence of symbols known to a strategic sender, whose utility may not be incentive compatible. We allow the receiver the possibility of selecting the alternatives presented in the questionnaire, and thereby linking decisions across the components of the sequence. We show that, despite the strategic sender and the noise in the channel, the receiver can recover exponentially many sequences, but also that exponentially many sequences are unrecoverable even by the best strategy. We define the growth rate of the number of recovered sequences as the information extraction capacity. A generalization of the Shannon capacity, it characterizes the optimal amount of communication resources required while communicating with a strategic sender. We derive bounds leading to an exact evaluation of the information extraction capacity in many cases. Our results form the building blocks of a novel, non-cooperative regime of communication involving a strategic sender. • An uninformed receiver aims to recover information from an informed strategic sender • No assumption of incentive compatibility or external incentives • Information-theoretic analysis shows a fundamental limit on recovered information • Real-world setting of screening of travellers using questionnaires can be studied • Novel theory combining Shannon's information theory and Myerson's mechanism design [ABSTRACT FROM AUTHOR]

Receiving uninterrupted videos from a scene with multiple cameras is a challenging task. One of the issues that significantly affects this task is called occlusion. In this paper, we propose an algorithm for occlusion handling in multi-camera systems. The proposed algorithm, which is called Real-time leader finder (Releaf), leverages mechanism design to assign leader and follower roles to each of the cameras in a multi-camera setup. We assign leader and follower roles to the cameras and lead the motion by the camera with the least occluded view using the Stackelberg equilibrium. The proposed approach is evaluated on our previously open-sourced tendon-driven 3D-printed robotic eye that tracks the face of a human subject. Experimental results demonstrate the superiority of the proposed algorithm over the Q-leaning and Deep Q Networks (DQN) baselines, achieving an improvement of 20 % and 18 % for horizontal errors and an enhancement of 81 % for vertical errors, as measured by the root mean squared error metric. Furthermore, Releaf has the superiority of real-time performance, which removes the need for training and makes it a promising approach for occlusion handling in multi-camera systems. [ABSTRACT FROM AUTHOR]

Receiving uninterrupted videos from a scene with multiple cameras is a challenging task. One of the issues that significantly affects this task is called occlusion. In this paper, we propose an algorithm for occlusion handling in multi-camera systems. The proposed algorithm, which is called Real-time leader finder (Releaf), leverages mechanism design to assign leader and follower roles to each of the cameras in a multi-camera setup. We assign leader and follower roles to the cameras and lead the motion by the camera with the least occluded view using the Stackelberg equilibrium. The proposed approach is evaluated on our previously open-sourced tendon-driven 3D-printed robotic eye that tracks the face of a human subject. Experimental results demonstrate the superiority of the proposed algorithm over the Q-leaning and Deep Q Networks (DQN) baselines, achieving an improvement of 20% and 18% for horizontal errors and an enhancement of 81% for vertical errors, as measured by the root mean squared error metric. Furthermore, Releaf has the superiority of real-time performance, which removes the need for training and makes it a promising approach for occlusion handling in multi-camera systems.

A common problem in many mature markets is how to deal with congestion-a situation in which transaction requests from market participants cannot be accommodated in an expedited manner. This paper examines the congestion problem in sequential Dutch auction markets. Transactions in these markets typically involve perishable goods, making market clearing speed crucial. Traditionally, sequential Dutch auctions have been implemented with fast-paced auction clocks that process equally attractive bids in the order they arrive and only award the first bidder as the winner of each round, which can lead to serious congestion in case of a demand surge. We propose a hybrid mechanism that capitalizes on the discrete nature of the auction clock and batches together the highest bids, allowing multiple transactions at the same price in each round. To evaluate the performance of the hybrid mechanism, we first develop a game-theoretic model comparing the hybrid mechanism to the traditional sequential Dutch auction mechanism. Our model predicts that the hybrid mechanism will achieve higher operational efficiency without compromising allocative efficiency. We then complement the theoretical analysis by evaluating the hybrid mechanism through a quasi-natural field experiment. The empirical analysis of the field data shows that the hybrid mechanism can significantly speed up the market clearing process and increase price stability without affecting the expected revenue. Our findings shed new light on the design and operation of multi-unit auctions. [ABSTRACT FROM AUTHOR]

An assumption that is pervasive in revenue management and economics is that buyers are perfect optimizers. However, in practice, buyers may be limited by their computational capabilities or lack of information and may not be able to perfectly optimize their response to a selling mechanism. This has motivated the introduction of approximate incentive compatibility as a solution concept for practical mechanisms. In "Mechanism Design under Approximate Incentive Compatibility," Balseiro, Besbes, and Castro study, for the first time, the problem of designing optimal selling mechanisms when buyers are imperfect optimizers. Their work characterizes structural properties of approximate incentive compatible mechanisms and establishes fundamental bounds on how much revenue can be garnered by moving from exact to approximate incentive constraints. Their work brings a new perspective to the theory of mechanism design by shedding light on a novel class of optimization problems, techniques, and challenges that emerge when relaxing incentive constraints. A fundamental assumption in classical mechanism design is that buyers are perfect optimizers. However, in practice, buyers may be limited by their computational capabilities or a lack of information and may not be able to perfectly optimize their response to a mechanism. This has motivated the introduction of approximate incentive compatibility (IC) as an appealing solution concept for practical mechanism design. Although most of the literature has focused on the analysis of particular approximate IC mechanisms, this paper is the first to study the design of optimal mechanisms in the space of approximate IC mechanisms and to explore how much revenue can be garnered by moving from exact to approximate incentive constraints. In particular, we study the problem of a seller facing one buyer with private values and analyze optimal selling mechanisms under ε-incentive compatibility. We establish that the gains that can be garnered depend on the local curvature of the seller's revenue function around the optimal posted price when the buyer is a perfect optimizer. If the revenue function behaves locally like an α-power for α ∈ (1 , ∞) , then no mechanism can garner gains higher than order ε α / (2 α − 1) . This improves on state-of-the-art results that imply maximum gains of ε 1 / 2 by providing the first parametric bounds that capture the impact of revenue function's curvature on revenue gains. Furthermore, we establish that an optimal mechanism needs to randomize as soon as ε > 0 and construct a randomized mechanism that is guaranteed to achieve order ε α / (2 α − 1) additional revenues, leading to a tight characterization of the revenue implications of approximate IC constraints. Our study sheds light on a novel class of optimization problems and the challenges that emerge when relaxing IC constraints. In particular, it brings forward the need to optimize not only over allocations and payments but also over best responses, and we develop a new framework to address this challenge. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2359. [ABSTRACT FROM AUTHOR]

We study the design of crowdsourcing contests in settings where the outputs of the contestants are quantifiable, for example, a data science challenge. This setting is in contrast to those where the output is only qualitative and cannot be objectively quantified, for example, when the goal of the contest is to design a logo. The literature on crowdsourcing contests focuses largely on ordinal contests, where contestants' outputs are ranked by the designer and awards are based on relative ranks. Such contests are ideally suited for the latter setting, where output is qualitative. For our setting (quantitative output), it is possible to design cardinal contests, where awards could be based on the actual outputs and not on their ranking alone—thus, the family of cardinal contests includes the family of ordinal contests. We study the problem of designing an optimal cardinal contest. We use mechanism design theory to derive an optimal cardinal mechanism and provide a convenient implementation—a decreasing reward‐meter mechanism—of the optimal contest. We establish the practicality of our mechanism by showing that it is "Obviously Strategy‐Proof," a recently introduced formal notion of simplicity in the literature. We also compare the optimal cardinal contest with the most popular ordinal contest—namely, the Winner‐Takes‐All (WTA) contest, along several metrics. In particular, the optimal cardinal mechanism delivers a superior expected best output, whereas the WTA contest yields a greater expected contestant welfare. Furthermore, under a sufficiently large budget, the contest designer's expected net‐benefit is higher under the optimal cardinal mechanism than that under the WTA contest, regardless of the number of contestants in the two mechanisms. Our numerical analysis suggests that, for the contest designer, the average improvement provided by the optimal cardinal mechanism over the WTA contest is about 23%. For a given number of contestants, the benefit of the optimal cardinal mechanism is especially appreciable for projects where the ratio of the designer's utility to agents' cost‐of‐effort falls within a wide practical range. For projects where this ratio is very high, the expected profit of the best WTA contest is reasonably close to that of the optimal cardinal mechanism. [ABSTRACT FROM AUTHOR]

US law continues its historical trend of growing more permissive towards actors who engage in violent action in purported self-defense. We draw on some informal game theory to show why this is strategically irrational and suggest rolling back self-defense doctrines like stand your ground to earlier historical precedents like duty to retreat. [ABSTRACT FROM AUTHOR]

Problem definition: We study an optimal contract design problem for a national brand (NB) manufacturer, which sells her product via a retailer. The retailer may introduce his store brand (SB) with private cost information. The manufacturer estimates that the retailer's SB cost may be high or low with certain probabilities and offers a menu of two-part tariff contracts to screen the retailer's cost information. Methodology/results: Following the mechanism design theory, we formulate the problem as a two-stage screening game to analyze the strategic interaction between the two players under asymmetric information. Despite the complexity resulting from type-dependent reservation profit of the retailer, we derive the NB manufacturer's optimal contracts analytically. We prove that there exists a unique threshold such that when the NB cost is below the threshold, the manufacturer offers both types of retailers incentive-compatible contracts; when the NB cost is above the threshold, the manufacturer offers a menu of contracts to shut down the low-type retailer and engage the high-type retailer only. Managerial implications: We find that when the NB product becomes more competitive (i.e., a higher quality or a lower cost), both the NB manufacturer and the retailer are better off. This result implies that under asymmetric information, the retailer has incentive to enhance the NB product quality or reduce its cost. Additionally, the private information is valuable to both members only when a contract without shutdown is offered. Moreover, such information is more valuable to both players when the NB product becomes more competitive. However, when SB quality improves or when SB cost decreases, the value of information may increase or decrease to both supply chain members. Finally, we derive a surprising result that under asymmetric information, the expected consumer surplus may increase because of a lower SB quality or a higher low-type SB cost. Funding: G. Xiao acknowledges financial support from the Research Grants Council of Hong Kong [General Research Fund Grant PolyU 15505621]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2021.0187. [ABSTRACT FROM AUTHOR]

This article connects recent work in formal epistemology to work in economics and computer science. Analysing the Dutch Book Arguments, Epistemic Utility Theory and Objective Bayesian Epistemology we discover that formal epistemologists employ the same argument structure as economists and computer scientists. Since similar approaches often have similar problems and have shared solutions, opportunities for cross-fertilisation abound. [ABSTRACT FROM AUTHOR]

Auction is a form of organization of competition that leads to the assignment and valuation of resources based on the information obtained from the competing agents. From the perspective of systems science it is a distributed resource allocation algorithm applied in the environment with information asymmetry, i.e., where the interconnected and interacting subsystems have different information about the system as a whole. This paper presents an overview of the historical development of mathematical theory underlying modern approach to auction design. Selected practical applications of the theory are also discussed.

In 2005 a company in charge of repairing electric transmission towers made a deal with guerrilla militants to demolish the towers. This company thrived, because the attacks were attributed to guerrilla groups, who commit these attacks often. However, the number of attacks increased significantly, raising alarms and leading to the discovery of the plot. We model this situation as a game between contractors and the power transmission company, and show how misaligned incentives enabled contractors to profit by colluding with guerrilla groups. We also analyze how to modify the contractual policies reducing the incentives to collude with guerrillas. In particular, the transmission company can prevent attacks by creating competition and exploiting market inefficiencies.

In 2005 a company in charge of repairing electric transmission towers made a deal with guerrilla militants to demolish the towers. This company thrived, because the attacks were attributed to guerrilla groups, who commit these attacks often. However, the number of attacks increased significantly, raising alarms and leading to the discovery of the plot. We model this situation as a game between contractors and the power transmission company, and show how misaligned incentives enabled contractors to profit by colluding with guerrilla groups. We also analyze how to modify the contractual policies reducing the incentives to collude with guerrillas. In particular, the transmission company can prevent attacks by creating competition and exploiting market inefficiencies.

We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. On each round, a mechanism first assigns an allocation to a set of agents and charges them a price; at the end of the round, the agents provide (stochastic) feedback to the mechanism for the allocation they received. This setting is motivated by applications in cloud markets and online advertising where an agent may know her value for an allocation only after experiencing it. Therefore, the mechanism needs to explore different allocations for each agent so that it can learn their values, while simultaneously attempting to find the socially optimal set of allocations. Our focus is on truthful and individually rational mechanisms which imitate the classical VCG mechanism in the long run. To that end, we first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. We show that these three terms are interdependent via an Ω(T2/3) lower bound for the maximum of these three terms after T rounds of allocations, and describe an algorithm which essentially achieves this rate. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets. Next, we define asymptotic variants for the truthfulness and individual rationality requirements and provide asymptotic rates to quantify the degree to which both properties are satisfied by the proposed algorithm. [ABSTRACT FROM AUTHOR]

As a newly emerging distributed machine learning technology, federated learning has unique advantages in the era of big data. We explore how to motivate participants to experience auctions more actively and safely. It is also essential to ensure that the final participant who wins the right to participate can guarantee relatively high−quality data or computational performance. Therefore, a secure, necessary and effective mechanism is needed through strict theoretical proof and experimental verification. The traditional auction theory is mainly oriented to price, not giving quality issues as much consideration. Hence, it is challenging to discover the optimal mechanism and solve the privacy problem when considering multi−dimensional auctions. Therefore, we (1) propose a multi−dimensional information security mechanism, (2) propose an optimal mechanism that satisfies the Pareto optimality and incentive compatibility named the SecMDGM and (3) verify that for the aggregation model based on vertical data, this mechanism can improve the performance by 2.73 times compared to that of random selection. These are all important, and they complement each other instead of being independent or in tandem. Due to security issues, it can be ensured that the optimal multi−dimensional auction has practical significance and can be used in verification experiments. [ABSTRACT FROM AUTHOR]

Many developed countries rely, to varying degrees, on competition among private health plans to obtain affordable and high-quality health insurance for their residents. Incorporating beneficiary-level competitive bidding into these healthcare systems can better align the incentives of these health plans, increase their willingness to enroll, and serve the sickest and most vulnerable patients while keeping costs manageable. We identify two digitally enabled program designs that allow private insurance plans to competitively bid to enroll individual beneficiaries. Compared with those used in existing entitlement programs, these designs always make a larger share of the beneficiary population profitable to enroll, thereby increasing willingness of the plans to enroll the most costly beneficiaries and improving access to care. On simulating the conditions of existing real-word healthcare entitlement programs, we found that these new designs actually tend to lower the tax burden in up to 83% of simulations. The research findings suggest that these new designs hold great promise in achieving the dual aim of improved access and lower costs. We believe that findings from this research can guide policymakers implement policies that will enroll more beneficiaries and cost the taxpayers less. Healthcare entitlement programs in the United States represent a large and growing financial outlay for taxpayers. In the pursuit of operational efficiencies, program administrators often contract with private managed care organizations (MCOs) to procure insurance for beneficiaries. This, however, encourages MCOs to attract the healthiest beneficiaries and avoid the sickest, a phenomenon known as risk selection. This paper investigates whether risk selection can be mitigated with a mechanism where MCOs bid to enroll each individual beneficiary. Although procurement auctions have been studied extensively in the literature, extant research has rarely discussed individual-level bidding. Digitization can contribute to the development and introduction of efficient market structures and mechanisms for matching beneficiaries with appropriate MCOs. We model demand- and supply-side aspects in a two-sided insurance marketplace to examine three mechanisms, risk adjustment, bidding, and a mix of prospective payment and bidding, with and without reserve prices. Analytical results show that traditional risk adjustment cannot optimally be used to eliminate risk selection, whereas the bidding mechanisms eliminate it entirely. Mixed bidding eliminates risk selection at a strictly lower cost than pure bidding. The proposed mixed bidding approach is a new type of mechanism with preauction offers that strictly dominates the second-price auction without requiring additional assumptions. Numerical analysis shows bidding dominates risk adjustment in 75.1% of simulated parameter sets. Compared with risk adjustment, bidding secures coordinated care for 12.1% more allocated beneficiaries while lowering program costs by 9.2% and largely preserving MCO profits. This would amount to approximately $27.2 billion in Medicaid program savings. Sensitivity analysis reveals that the proposed bidding mechanism dominates in scenarios that closely resemble real-world healthcare entitlement environments. These results show that digital markets that enable individual-level auctions are a promising approach for achieving the dual aim of financial sustainability and expanded access to care for the most vulnerable. History: This paper has been accepted by Ravi Bapna, Martin Bichler, Bob Day, and Wolfgang Ketter, Senior Editors; and Liangfei Qiu, Associate Editor, for the Information Systems Research Special Section on Market Design and Analytics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/isre.2021.1062. [ABSTRACT FROM AUTHOR]

Liberalization of the energy system sets the way towards market-based solutions for ancillary service provision. Local reactive power markets are envisioned to achieve more economically and technically efficient reactive power provision to solve voltage control problems in future distribution and transmission grids. However, market-based reactive power procurement is a difficult and yet unsolved problem. This survey provides a comprehensive overview of the characteristics and hardships of reactive power markets. That is followed by a literature overview of reactive power market design, including local markets and markets on system operator level. Further, methods how to analyse reactive power markets are discussed, focusing on market power, game theoretical approaches, Reinforcement Learning, and manipulation of reactive power markets. From this overview, trends and current research gaps are derived and some general research recommendations are given to serve as a guideline for future research in the field of reactive power markets.

The vast majority of artificial intelligence solutions are founded on game theory, and differential privacy is emerging as perhaps the most rigorous and widely adopted privacy paradigm in the field. However, alongside all the advancements made in both these fields, there is not a single application that is not still vulnerable to privacy violations, security breaches, or manipulation by adversaries. Our understanding of the interactions between differential privacy and game theoretic solutions is limited. Hence, we undertook a comprehensive review of literature in the field, finding that differential privacy has several advantageous properties that can make more of a contribution to game theory than just privacy protection. It can also be used to build heuristic models for game-theoretic solutions, to avert strategic manipulations, and to quantify the cost of privacy protection. With a focus on mechanism design, the aim of this article is to provide a new perspective on the currently held impossibilities in game theory, potential avenues to circumvent those impossibilities, and opportunities to improve the performance of game-theoretic solutions with differentially private techniques. [ABSTRACT FROM AUTHOR]

The Game Theory & Multi-Agent team at DeepMind studies several aspects of multi-agent learning ranging from computing approximations to fundamental concepts in game theory to simulating social dilemmas in rich spatial environments and training 3-d humanoids in difficult team coordination tasks. A signature aim of our group is to use the resources and expertise made available to us at DeepMind in deep reinforcement learning to explore multi-agent systems in complex environments and use these benchmarks to advance our understanding. Here, we summarise the recent work of our team and present a taxonomy that we feel highlights many important open challenges in multi-agent research. [ABSTRACT FROM AUTHOR]

An emerging computational paradigm, named federated edge learning (FEL), enables intelligent computing at the network edge with the feature of preserving data privacy for edge devices. Given their constrained resources, it becomes a great challenge to achieve high execution performance for FEL. Most of the state-of-the-arts concentrate on enhancing FEL from the perspective of system operation procedures, taking few precautions during the composition step of the FEL system. Though a few recent studies recognize the importance of FEL formation and propose server-centric device selection schemes, the impact of data sizes is largely overlooked. In this paper, we take advantage of game theory to depict the decision dilemma among edge devices regarding whether to participate in FEL or not given their heterogeneous sizes of local datasets. For realizing both the individual and global optimization, the server is employed to solve the participation dilemma, which requires accurate information collection for devices’ local datasets. Hence, we utilize mechanism design to enable truthful information solicitation. With the help of correlated equilibrium, we derive a decision making strategy for devices from the global perspective, which can achieve the long-term stability and efficacy of FEL. For scalability consideration, we optimize the computational complexity of the basic solution to the polynomial level. Lastly, extensive experiments based on both real and synthetic data are conducted to evaluate our proposed mechanisms, with experimental results demonstrating the performance advantages. [ABSTRACT FROM AUTHOR]

This paper considers the river sharing problem with incomplete information. We ask whether the efficient allocation of water in a river network is possible when agents have private information on their satiation levels. First, we introduce a trading model on a tree network with incomplete information. Then, we focus on the river sharing problem for a three-agent river network in which water flows from two upstream agents to one downstream agent. We assume that each agent has a satiation point and this satiation point is his private information. We are interested in allocation mechanisms that map each profile of the satiation points to an allocation of water and a list of monetary transfers between the agents. We show that, if each upstream agent's endowment of water is sufficiently larger than the downstream agent's endowment, then there exists an incentive compatible, individually rational, and budget balanced mechanism that allocates the water efficiently. • We consider the river sharing problem in which agents' satiation levels are private information. • We focus on a nonlinear river network with two upstream agents and one downstream agent. • We employ the theory of mechanism design to investigate the existence of efficient trading mechanisms for sharing water. • We find a sufficient condition based on water endowments for efficient trading mechanisms. [ABSTRACT FROM AUTHOR]

Illegal poaching poses threat to the natural ecosystem, hastens the extinction of animal species, and disrupts forestry and other natural resources. Countries usually deploy security personnel to protect these resources from poachers. However, preservation of such resources is oftentimes hindered by the lack of manpower of concerned agencies. Green security, a discipline that leverages the game theoretic concepts to assist human patrols has recently emerged to mitigate this problem. Over the past few years, a good number of studies have been conducted on various aspects of such security systems including poachers’ behavior modeling, optimal patrolling route generation, and signalling mechanisms to assist guards. In this paper, we contribute to the literature in the following three ways. First, we offer a radio signalling scheme to assist human guards. Second, we introduce two concepts regarding the guarding patterns: (a) the concept of “boundedness” is coined which limits the patrolling area of human guards and (b) the concept of “move skipping” is put forth which is to compulsorily abstain from moving at some timesteps while patrolling. Third, we investigate the required number of deployed drones to achieve an effective monitoring. Our simulation results show that the proposed schemes have the capability to reduce poaching occurrences, while, at the same time, decrease over-patrolling and fuel usage. Our research focuses on analyzing and comparing different variations of a green security game setup. In our research, we analyze and compare these different aspects of various patrolling patterns and based on our findings, we provide useful insights that contribute to the development of the research field of green security and security schemes in general, including both human patrols and drones, which are deployed to prevent poachers or adversaries from poaching resources.

Future cities promise to be more autonomous than ever, largely owing to our ability of coordinating complex systems in real time: fleets of self-driving cars will offer on-demand transportation services, delivery drones will fly parcels in our skies, power plants will provide renewable energy reliably. In many of these systems, there is no single decision-maker with full information and authority. Instead, the system performance greatly depends on the decisions made by interacting entities with local information and limited communication capabilities. Game theory, intended as the study of multi-agent decision-making, is a fitting paradigm to tackle many of the associated challenges. Moving from this observation, in this paper we review how tools and ideas from game theory can be brought to bear on the coordination of multi-agent systems. At the heart of the proposed approach is the design and influence of agents' preferences so that their local optimization induces a desirable system behavior. Its applicability spans a variety of settings irrespective of whether the decision makers are strategic (e.g., drivers in a road network), or not (e.g., delivery drones). Along the way, we also discuss future research directions and connections with related research areas including algorithmic game theory, incentive and mechanism design, economics, computational complexity, and approximation algorithms. [ABSTRACT FROM AUTHOR]

Federated learning enables machine learning algorithms to be trained over decentralized edge devices without requiring the exchange of local datasets. Successfully deploying federated learning requires ensuring that agents (e.g., mobile devices) faithfully execute the intended algorithm, which has been largely overlooked in the literature. In this study, we first use risk bounds to analyze how the key feature of federated learning, unbalanced and non-i.i.d. data, affects agents’ incentives to voluntarily participate and obediently follow traditional federated learning algorithms. To be more specific, our analysis reveals that agents with less typical data distributions and relatively more samples are more likely to opt out of or tamper with federated learning algorithms. To this end, we formulate the first faithful implementation problem of federated learning and design two faithful federated learning mechanisms which satisfy economic properties, scalability, and privacy. First, we design a Faithful Federated Learning (FFL) mechanism which approximates the Vickrey–Clarke–Groves (VCG) payments via an incremental computation. We show that it achieves (probably approximate) optimality, faithful implementation, voluntary participation, and some other economic properties (such as budget balance). Further, the time complexity in the number of agents $K$ is $\mathcal {O}(\log (K))$. Second, by partitioning agents into several clusters, we present a scalable VCG mechanism approximation. We further design a scalable and Differentially Private FFL (DP-FFL) mechanism, the first differentially private faithful mechanism, that maintains the economic properties. Our DP-FFL mechanism enables one to make three-way performance tradeoffs among privacy, the iterations needed, and payment accuracy loss. [ABSTRACT FROM AUTHOR]

Delay Tolerant Networks are a type of challenging, uninterrupted network in which there is not an end-to-end path between the source and the destination. These networks play a key role in managing crises in natural disasters such as earthquakes, fires, floods, and more. Due to limited resources, nodes may be reluctant to cooperate in the message relaying and may behave selfishly. Eventually, this lack of cooperation can result in performance degradation. Game theory is one of the mathematical tools to motivate the intermediate nodes to forward messages. In this paper, we use the theory of auction between relay nodes to motivate them to collaborate in forwarding messages. Based on the second-price sealed-bid auction mechanism, the node that does not cooperate in forwarding messages fails to acquire utility. In this way, if the node itself intends to send a message to another node, it will not be able to do so due to a lack of budget. Thus, the selfish behavior of the node causes it to be harmed. Our simulations using the ONE simulator shows that the performance of the proposed method in moderate traffic is improved in terms of significant criteria such as delivery ratio, average buffer usage, hop count, overhead, and so on. The results also show that under intense traffic conditions, the performance of the proposed method is far better than that of moderate traffic. [ABSTRACT FROM AUTHOR]

As a newly emerging distributed machine learning technology, federated learning has unique advantages in the era of big data. We explore how to motivate participants to experience auctions more actively and safely. It is also essential to ensure that the final participant who wins the right to participate can guarantee relatively high−quality data or computational performance. Therefore, a secure, necessary and effective mechanism is needed through strict theoretical proof and experimental verification. The traditional auction theory is mainly oriented to price, not giving quality issues as much consideration. Hence, it is challenging to discover the optimal mechanism and solve the privacy problem when considering multi−dimensional auctions. Therefore, we (1) propose a multi−dimensional information security mechanism, (2) propose an optimal mechanism that satisfies the Pareto optimality and incentive compatibility named the SecMDGM and (3) verify that for the aggregation model based on vertical data, this mechanism can improve the performance by 2.73 times compared to that of random selection. These are all important, and they complement each other instead of being independent or in tandem. Due to security issues, it can be ensured that the optimal multi−dimensional auction has practical significance and can be used in verification experiments.

In our multi-agent model, agents generate wealth from repeated interactions for which a prisoner's dilemma payoff matrix is assumed. Their gains are taxed by a government at a rate α. The resulting budget is spent to cover administrative costs and to pay a bonus to cooperative agents, which can be identified correctly only with a probability p. Agents decide at each time step to choose either cooperation or defection based on different information. In the local scenario, they compare their potential gains from both strategies. In the global scenario, they compare the gains of the cooperative and defective subpopulations. We derive analytical expressions for the critical bonus needed to make cooperation as attractive as defection. We show that for the local scenario the government can establish only a medium level of cooperation because the critical bonus increases with the level of cooperation. In the global scenario, instead full cooperation can be achieved once the cold-start problem is solved because the critical bonus decreases with the level of cooperation. This allows to lower the tax rate, while maintaining high cooperation. [ABSTRACT FROM AUTHOR]

Problem definition: This paper studies the optimal design of referral priority programs, in which customers on a waiting list can jump the line by inviting their friends to also join the waiting list. Academic/practical relevance: Recent years have witnessed a growing presence of referral priority programs as a novel customer-acquisition strategy for firms that maintain a waiting list. Different variations of this scheme are seen in practice, raising the question of what should be the optimal referral priority mechanism. Methodology: I build an analytical model that integrates queuing theory into a mechanism design framework in which the objective of the firm is to maximize the system throughput, that is, accelerate customer acquisition as much as possible. Results: My analysis shows that the optimal mechanism has one of the following structures: full priority; partial priority; first in, first out (FIFO); and strategic delay. A full-priority (partial-priority) scheme enables referring customers to get ahead of all (only some) nonreferring ones. A FIFO scheme does not provide any priority-based referral incentive. A strategic-delay scheme grants full priority to referring customers but artificially inflates the delay of nonreferring ones. I show that FIFO is optimal if either the base-market size or the referral cost is large. Otherwise, partial priority is optimal if the base-market size is above a certain threshold; full priority is optimal at the threshold base-market size; strategic delay is optimal if the base-market size is below the threshold. I also find that referrals motivate the firm to maintain a larger capacity and therefore can surprisingly shorten the average delay, even though more customers sign up and strategic delay is sometimes inserted. Managerial implications: My paper provides prescriptive guidance for launching an optimal referral priority program and rationalizes common referral schemes seen in practice. [ABSTRACT FROM AUTHOR]