An official website of the United States government
Experience management (EM) agents in multiplayer serious games face unique challenges and responsibilities regarding the fair treatment of players. One such challenge is the Greedy Bandit Problem that arises when using traditional Multi-Armed Bandits (MABs) as EM agents, which results in some players routinely prioritized while others may be ignored. We will show that this problem can be a cause of player non-adherence in a multiplayer serious game played by human users. To mitigate this effect, we propose a new bandit strategy, the Shapley Bandit, which enforces fairness constraints in its treatment of players based on the Shapley Value. We evaluate our approach via simulation with virtual players, finding that the Shapley Bandit can be effective in providing more uniform treatment of players while incurring only a slight cost in overall performance to a typical greedy approach. Our findings highlight the importance of fair treatment among players as a goal of multiplayer EM agents and discuss how addressing this issue may lead to more effective agent operation overall. The study contributes to the understanding of player modeling and EM in serious games and provides a promising approach for balancing fairness and engagement in multiplayer environments.
more »
« less
This content will become publicly available on November 4, 2025
Cost-sharing in Parking Games
In this paper, we study the total displacement statistic of parking functionsfrom the perspective of cooperative game theory. We introduce parking games,which are coalitional cost-sharing games in characteristic function formderived from the total displacement statistic. We show that parking games aresupermodular cost-sharing games, indicating that cooperation is difficult(i.e., their core is empty). Next, we study their Shapley value, whichformalizes a notion of fair cost-sharing and amounts to charging each car forits expected marginal displacement under a random arrival order. Our maincontribution is a polynomial-time algorithm to compute the Shapley value ofparking games, in contrast with known hardness results on computing the Shapleyvalue of arbitrary games. The algorithm leverages the permutation-invariance oftotal displacement, combinatorial enumeration, and dynamic programming. Weconclude with open questions around an alternative solution concept forsupermodular cost-sharing games and connections to other areas incombinatorics.
more »
« less
- Award ID(s):
- 1928930
- PAR ID:
- 10599993
- Publisher / Repository:
- EPISciences
- Date Published:
- Journal Name:
- Discrete Mathematics & Theoretical Computer Science
- Volume:
- vol. 26:3
- Issue:
- Combinatorics
- ISSN:
- 1365-8050
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
As solar electricity has become cheaper than the retail electricity price, residential consumers are trying to reduce costs by meeting more demand using solar energy. One way to achieve this is to invest in the solar infrastructure collaboratively. When houses form a coalition, houses with high solar potential or surplus roof capacity can install more panels and share the generated solar energy with others, lowering the total cost. Fair sharing of the resulting cost savings across the houses is crucial to prevent the coalition from breaking. However, estimating the fair share of each house is complex as houses contribute different amounts of generation and demand in the coalition, and rooftop solar generation across houses with similar roof capacities can vary widely. In this paper, we present HeliosFair, a system that minimizes the total electricity costs of a community that shares solar energy and then uses Shapley values to fairly distribute the cost savings thus obtained. Using real-world data, we show that the joint CapEx and OpEx electricity costs of a community sharing solar can be reduced by 12.7% on average (11.3% on average with roof capacity constraints) over houses installing solar energy individually. Our Shapley-value-based approach can fairly distribute these savings across houses based on their contributions towards cost reduction, while commonly used ad hoc approaches are unfair under many scenarios. HeliosFair is also the first work to consider practical constraints such as the difference in solar potential across houses, rooftop capacity and weight of solar panels, making it deployable in practice.more » « less
-
Competitive Spatial Pricing for Urban Parking Systems: Network Structures and Asymmetric Informationnull (Ed.)Inspired by new technologies to monitor parking occupancy and process market signals, we aim to expand the application of demand-responsive pricing in the parking industry. Based on a graphical Hotelling model wherein each garage has information for its incoming parking demand, we consider a general competitive spatial pricing in parking systems under an asymmetric information structure. We focus on the impact of urban network structure on the incentive of information sharing. Our analyses suggest that the garages are always better off in a circular-networked city, while they could be worse off in the suburbs of a star-networked city. Nevertheless, the overall revenue for garages is improved and the aggregate congestion is reduced under information sharing. Our results also suggest that information sharing helps garages further exploit the customers who in turn become worse-off. Therefore, policy-makers should carefully evaluate their transportation data policy since impacts on the service-providers and the customers are typically conflicting. Using the SFpark data, we empirically confirmed the value of information sharing. In particular, garages with higher price-demand elasticity and lower demand variance tend to enjoy larger benefits via information sharing. These insights support the joint design of parking rates structure and information systems.more » « less
-
Organizations that would mutually benefit from pooling their data are otherwise wary of sharing. This is because sharing data is costly—in time and effort—and, at the same time, the benefits of sharing are not clear. Without a clear cost-benefit analysis, participants default in not sharing. As a consequence, many opportunities to create valuable data-sharing consortia never materialize and the value of data remains locked. We introduce a new sharing model, market protocol, and algorithms to incentivize the creation of data-sharing markets. The combined contributions of this paper, which we call DSC, incentivize the creation of data-sharing markets that unleash the value of data for its participants. The sharing model introduces two incentives; one that guarantees that participating is better than not doing so, and another that compensates participants according to how valuable is their data. Because operating the consortia is costly, we are also concerned with ensuring its operation is sustainable: we design a protocol that ensures that valuable data-sharing consortia form when it is sustainable. We introduce algorithms to elicit the value of data from the participants, which is used to: first, cover the costs of operating the consortia, and second compensate data contributions. For the latter, we challenge the use of the Shapley value to allocate revenue. We offer analytical and empirical evidence for this and introduce an alternative method that compensates participants better and leads to the formation of more data-sharing consortia.more » « less
-
The increasing demand for data-driven machine learning (ML) models has led to the emergence of model markets, where a broker collects personal data from data owners to produce high-usability ML models. To incentivize data owners to share their data, the broker needs to price data appropriately while protecting their privacy. For equitable data valuation , which is crucial in data pricing, Shapley value has become the most prevalent technique because it satisfies all four desirable properties in fairness: balance, symmetry, zero element, and additivity. For the right to be forgotten , which is stipulated by many data privacy protection laws to allow data owners to unlearn their data from trained models, the sharded structure in ML model training has become a de facto standard to reduce the cost of future unlearning by avoiding retraining the entire model from scratch. In this paper, we explore how the sharded structure for the right to be forgotten affects Shapley value for equitable data valuation in model markets. To adapt Shapley value for the sharded structure, we propose S-Shapley value, a sharded structure-based Shapley value, which satisfies four desirable properties for data valuation. Since we prove that computing S-Shapley value is #P-complete, two sampling-based methods are developed to approximate S-Shapley value. Furthermore, to efficiently update valuation results after data owners unlearn their data, we present two delta-based algorithms that estimate the change of data value instead of the data value itself. Experimental results demonstrate the efficiency and effectiveness of the proposed algorithms.more » « less
